91using namespace PatternMatch;
93#define DEBUG_TYPE "simplifycfg"
96 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
98 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
99 "into preserving DomTree,"));
108 "Control the amount of phi node folding to perform (default = 2)"));
112 cl::desc(
"Control the maximal total instruction cost that we are willing "
113 "to speculatively execute to fold a 2-entry PHI node into a "
114 "select (default = 4)"));
118 cl::desc(
"Hoist common instructions up to the parent block"));
123 cl::desc(
"Allow reordering across at most this many "
124 "instructions when hoisting"));
128 cl::desc(
"Sink common instructions down to the end block"));
132 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
136 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
137 "precede - hoist multiple conditional stores into a single "
138 "predicated store"));
142 cl::desc(
"When merging conditional stores, do so even if the resultant "
143 "basic blocks are unlikely to be if-converted as a result"));
147 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
152 cl::desc(
"Limit maximum recursion depth when calculating costs of "
153 "speculatively executed instructions"));
158 cl::desc(
"Max size of a block which is still considered "
159 "small enough to thread through"));
165 cl::desc(
"Maximum cost of combining conditions when "
166 "folding branches"));
169 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
171 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
172 "to fold branch to common destination when vector operations are "
177 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
181 cl::desc(
"Limit cases to analyze when converting a switch to select"));
183STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
185 "Number of switch instructions turned into linear mapping");
187 "Number of switch instructions turned into lookup tables");
189 NumLookupTablesHoles,
190 "Number of switch instructions turned into lookup tables (holes checked)");
191STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
193 "Number of value comparisons folded into predecessor basic blocks");
195 "Number of branches folded into predecessor basic block");
198 "Number of common instruction 'blocks' hoisted up to the begin block");
200 "Number of common instructions hoisted up to the begin block");
202 "Number of common instruction 'blocks' sunk down to the end block");
204 "Number of common instructions sunk down to the end block");
205STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
207 "Number of invokes with empty resume blocks simplified into calls");
208STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
209STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
216using SwitchCaseResultVectorTy =
225struct ValueEqualityComparisonCase {
232 bool operator<(ValueEqualityComparisonCase RHS)
const {
240class SimplifyCFGOpt {
250 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
251 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
254 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
257 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
271 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
274 bool hoistCommonCodeFromSuccessors(
BasicBlock *BB,
bool EqTermsOnly);
275 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
294 "SimplifyCFG is not yet capable of maintaining validity of a "
295 "PostDomTree, so don't ask for it.");
302 bool requestResimplify() {
321 "Only for a pair of incoming blocks at the time!");
327 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
328 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
331 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
332 EquivalenceSet->contains(IV1))
355 if (!SI1Succs.
count(Succ))
361 FailBlocks->insert(Succ);
377 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
379 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
380 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
389 assert((!isa<Instruction>(
I) ||
391 "Instruction is not safe to speculatively execute!");
417 unsigned Depth = 0) {
446 if (AggressiveInsts.
count(
I))
470 for (
Use &
Op :
I->operands())
484 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
485 DL.isNonIntegralPointerType(V->getType()))
490 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
493 if (isa<ConstantPointerNull>(V))
494 return ConstantInt::get(PtrTy, 0);
498 if (CE->getOpcode() == Instruction::IntToPtr)
499 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
504 return cast<ConstantInt>(
522struct ConstantComparesGatherer {
526 Value *CompValue =
nullptr;
529 Value *Extra =
nullptr;
535 unsigned UsedICmps = 0;
542 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
543 ConstantComparesGatherer &
544 operator=(
const ConstantComparesGatherer &) =
delete;
549 bool setValueOnce(
Value *NewVal) {
550 if (CompValue && CompValue != NewVal)
553 return (CompValue !=
nullptr);
567 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
578 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
622 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
624 if (!setValueOnce(RHSVal))
629 ConstantInt::get(
C->getContext(),
630 C->getValue() | Mask));
645 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
647 if (!setValueOnce(RHSVal))
651 Vals.
push_back(ConstantInt::get(
C->getContext(),
652 C->getValue() & ~Mask));
673 Value *CandidateVal =
I->getOperand(0);
676 CandidateVal = RHSVal;
691 if (!setValueOnce(CandidateVal))
696 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
707 void gather(
Value *V) {
718 while (!DFT.
empty()) {
726 if (Visited.
insert(Op1).second)
728 if (Visited.
insert(Op0).second)
735 if (matchInstruction(
I, isEQ))
759 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
760 Cond = dyn_cast<Instruction>(SI->getCondition());
761 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
762 if (BI->isConditional())
763 Cond = dyn_cast<Instruction>(BI->getCondition());
765 Cond = dyn_cast<Instruction>(IBI->getAddress());
777 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
780 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
781 CV =
SI->getCondition();
782 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
783 if (BI->isConditional() && BI->getCondition()->hasOneUse())
784 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
792 Value *
Ptr = PTII->getPointerOperand();
793 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
802BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
803 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
804 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
805 Cases.reserve(
SI->getNumCases());
806 for (
auto Case :
SI->cases())
807 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
808 Case.getCaseSuccessor()));
809 return SI->getDefaultDest();
815 Cases.push_back(ValueEqualityComparisonCase(
824 std::vector<ValueEqualityComparisonCase> &Cases) {
830 std::vector<ValueEqualityComparisonCase> &C2) {
831 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
834 if (V1->size() > V2->size())
839 if (V1->size() == 1) {
842 for (
const ValueEqualityComparisonCase &VECC : *V2)
843 if (TheVal == VECC.
Value)
850 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
851 while (i1 != e1 && i2 != e2) {
872 SI->setMetadata(LLVMContext::MD_prof,
N);
878 uint32_t FalseWeight,
bool IsExpected) {
879 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
883 if (TrueWeight || FalseWeight)
886 I->setMetadata(LLVMContext::MD_prof,
N);
894bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
900 Value *ThisVal = isValueEqualityComparison(TI);
901 assert(ThisVal &&
"This isn't a value comparison!!");
902 if (ThisVal != PredVal)
909 std::vector<ValueEqualityComparisonCase> PredCases;
911 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
915 std::vector<ValueEqualityComparisonCase> ThisCases;
916 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
928 if (isa<BranchInst>(TI)) {
931 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
937 ThisCases[0].Dest->removePredecessor(PredDef);
940 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
947 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
955 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
959 <<
"Through successor TI: " << *TI);
967 if (DeadCases.
count(i->getCaseValue())) {
976 std::vector<DominatorTree::UpdateType> Updates;
977 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
979 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
980 DTU->applyUpdates(Updates);
991 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
992 if (PredCases[i].Dest == TIBB) {
995 TIV = PredCases[i].
Value;
997 assert(TIV &&
"No edge from pred to succ?");
1002 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1003 if (ThisCases[i].
Value == TIV) {
1004 TheRealDest = ThisCases[i].Dest;
1010 TheRealDest = ThisDef;
1017 if (Succ != CheckEdge) {
1018 if (Succ != TheRealDest)
1019 RemovedSuccs.
insert(Succ);
1022 CheckEdge =
nullptr;
1029 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1036 for (
auto *RemovedSucc : RemovedSuccs)
1037 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1038 DTU->applyUpdates(Updates);
1048struct ConstantIntOrdering {
1050 return LHS->getValue().ult(
RHS->getValue());
1062 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1071 assert(MD &&
"Invalid branch-weight metadata");
1077 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1088 if (Max > UINT_MAX) {
1103 if (BonusInst.isTerminator())
1108 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1132 if (isa<DbgInfoIntrinsic>(BonusInst))
1135 NewBonusInst->
takeName(&BonusInst);
1136 BonusInst.setName(NewBonusInst->
getName() +
".old");
1137 VMap[&BonusInst] = NewBonusInst;
1143 auto *UI = cast<Instruction>(U.getUser());
1144 auto *PN = dyn_cast<PHINode>(UI);
1146 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1147 "If the user is not a PHI node, then it should be in the same "
1148 "block as, and come after, the original bonus instruction.");
1152 if (PN->getIncomingBlock(U) == BB)
1156 assert(PN->getIncomingBlock(U) == PredBlock &&
1157 "Not in block-closed SSA form?");
1158 U.set(NewBonusInst);
1163bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1171 std::vector<ValueEqualityComparisonCase> BBCases;
1172 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1174 std::vector<ValueEqualityComparisonCase> PredCases;
1175 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1187 if (PredHasWeights) {
1190 if (Weights.
size() != 1 + PredCases.size())
1191 PredHasWeights = SuccHasWeights =
false;
1192 }
else if (SuccHasWeights)
1196 Weights.
assign(1 + PredCases.size(), 1);
1199 if (SuccHasWeights) {
1202 if (SuccWeights.
size() != 1 + BBCases.size())
1203 PredHasWeights = SuccHasWeights =
false;
1204 }
else if (PredHasWeights)
1205 SuccWeights.
assign(1 + BBCases.size(), 1);
1207 if (PredDefault == BB) {
1210 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1211 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1212 if (PredCases[i].Dest != BB)
1213 PTIHandled.insert(PredCases[i].
Value);
1216 std::swap(PredCases[i], PredCases.back());
1218 if (PredHasWeights || SuccHasWeights) {
1220 Weights[0] += Weights[i + 1];
1225 PredCases.pop_back();
1231 if (PredDefault != BBDefault) {
1233 if (DTU && PredDefault != BB)
1234 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1235 PredDefault = BBDefault;
1236 ++NewSuccessors[BBDefault];
1239 unsigned CasesFromPred = Weights.
size();
1241 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1242 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1243 PredCases.push_back(BBCases[i]);
1244 ++NewSuccessors[BBCases[i].Dest];
1245 if (SuccHasWeights || PredHasWeights) {
1249 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1250 ValidTotalSuccWeight += SuccWeights[i + 1];
1254 if (SuccHasWeights || PredHasWeights) {
1255 ValidTotalSuccWeight += SuccWeights[0];
1257 for (
unsigned i = 1; i < CasesFromPred; ++i)
1258 Weights[i] *= ValidTotalSuccWeight;
1260 Weights[0] *= SuccWeights[0];
1266 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1267 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1268 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1269 if (PredCases[i].Dest == BB) {
1272 if (PredHasWeights || SuccHasWeights) {
1273 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1278 std::swap(PredCases[i], PredCases.back());
1279 PredCases.pop_back();
1286 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1287 if (PTIHandled.count(BBCases[i].Value)) {
1289 if (PredHasWeights || SuccHasWeights)
1291 PredCases.push_back(BBCases[i]);
1292 ++NewSuccessors[BBCases[i].Dest];
1299 if (PredHasWeights || SuccHasWeights)
1301 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1302 ++NewSuccessors[BBDefault];
1314 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1316 for (
auto I :
seq(NewSuccessor.second)) {
1320 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1321 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1334 for (ValueEqualityComparisonCase &V : PredCases)
1337 if (PredHasWeights || SuccHasWeights) {
1354 if (!InfLoopBlock) {
1362 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1369 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1371 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1373 DTU->applyUpdates(Updates);
1376 ++NumFoldValueComparisonIntoPredecessors;
1384bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1387 Value *CV = isValueEqualityComparison(TI);
1388 assert(CV &&
"Not a comparison?");
1390 bool Changed =
false;
1393 while (!Preds.empty()) {
1402 Value *PCV = isValueEqualityComparison(PTI);
1408 for (
auto *Succ : FailBlocks) {
1414 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1428 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1429 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1430 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1449 if (
I->mayReadFromMemory())
1453 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1470 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1480 if (
auto *CB = dyn_cast<CallBase>(
I))
1481 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1488 if (
auto *J = dyn_cast<Instruction>(
Op))
1489 if (J->getParent() == BB)
1508 auto *C1 = dyn_cast<CallInst>(I1);
1509 auto *C2 = dyn_cast<CallInst>(I2);
1511 if (C1->isMustTailCall() != C2->isMustTailCall())
1519 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1520 if (CB1->cannotMerge() || CB1->isConvergent())
1522 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1523 if (CB2->cannotMerge() || CB2->isConvergent())
1538 if (!I1->hasDbgRecords())
1540 using CurrentAndEndIt =
1541 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1547 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1548 return Pair.first == Pair.second;
1554 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1560 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1562 if (!
Other->hasDbgRecords())
1565 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1572 while (
none_of(Itrs, atEnd)) {
1573 bool HoistDVRs = allIdentical(Itrs);
1574 for (CurrentAndEndIt &Pair : Itrs) {
1591bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1613 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1617 if (isa<PHINode>(*SuccItr))
1619 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1628 if (!INonDbg->isTerminator())
1638 unsigned NumSkipped = 0;
1641 if (SuccIterPairs.
size() > 2) {
1643 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1644 if (SuccIterPairs.
size() < 2)
1648 bool Changed =
false;
1651 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1652 auto &BB1ItrPair = *SuccIterPairBegin++;
1653 auto OtherSuccIterPairRange =
1660 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1662 return I1->isIdenticalToWhenDefined(I2);
1664 if (!AllDbgInstsAreIdentical) {
1665 while (isa<DbgInfoIntrinsic>(I1))
1666 I1 = &*++BB1ItrPair.first;
1667 for (
auto &SuccIter : OtherSuccIterRange) {
1669 while (isa<DbgInfoIntrinsic>(I2))
1674 bool AllInstsAreIdentical =
true;
1675 bool HasTerminator =
I1->isTerminator();
1676 for (
auto &SuccIter : OtherSuccIterRange) {
1679 if (AllInstsAreIdentical && (!
I1->isIdenticalToWhenDefined(I2) ||
1681 AllInstsAreIdentical =
false;
1685 for (
auto &SuccIter : OtherSuccIterRange)
1690 if (HasTerminator) {
1694 if (NumSkipped || !AllInstsAreIdentical) {
1699 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1703 if (AllInstsAreIdentical) {
1704 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1705 AllInstsAreIdentical =
1707 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1709 unsigned SkipFlagsBB2 = Pair.second;
1719 if (AllInstsAreIdentical) {
1721 if (isa<DbgInfoIntrinsic>(I1)) {
1730 for (
auto &SuccIter : OtherSuccIterRange) {
1731 auto *I2 = &*SuccIter++;
1732 assert(isa<DbgInfoIntrinsic>(I2));
1744 for (
auto &SuccIter : OtherSuccIterRange) {
1758 NumHoistCommonCode += SuccIterPairs.
size();
1760 NumHoistCommonInstrs += SuccIterPairs.
size();
1769 for (
auto &SuccIterPair : SuccIterPairs) {
1778bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1782 auto *BI = dyn_cast<BranchInst>(TI);
1784 bool Changed =
false;
1789 auto *I2 = *OtherSuccTIs.
begin();
1805 if (isa<CallBrInst>(I1))
1810 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1812 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1832 if (!
NT->getType()->isVoidTy()) {
1833 I1->replaceAllUsesWith(NT);
1835 OtherSuccTI->replaceAllUsesWith(NT);
1839 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1845 for (
auto *OtherSuccTI : OtherSuccTIs)
1846 Locs.
push_back(OtherSuccTI->getDebugLoc());
1858 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1861 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1862 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1868 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1872 if (isa<FPMathOperator>(PN))
1881 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1882 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1883 PN.setIncomingValue(i, SI);
1894 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1899 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1903 DTU->applyUpdates(Updates);
1909 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1910 switch (
II->getIntrinsicID()) {
1913 case Intrinsic::lifetime_start:
1914 case Intrinsic::lifetime_end:
1925 return !isa<IntrinsicInst>(
I);
1938 std::optional<unsigned> NumUses;
1939 for (
auto *
I : Insts) {
1941 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1942 I->getType()->isTokenTy())
1947 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1954 if (
const auto *
C = dyn_cast<CallBase>(
I))
1955 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1959 NumUses =
I->getNumUses();
1960 else if (NumUses !=
I->getNumUses())
1966 for (
auto *
I : Insts) {
1967 if (!
I->isSameOperationAs(I0))
1973 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1975 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1988 for (
const Use &U : I0->
uses()) {
1989 auto It = PHIOperands.find(&U);
1990 if (It == PHIOperands.end())
1993 if (!
equal(Insts, It->second))
2007 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2011 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2015 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2023 if (isa<CallBase>(I0)) {
2025 return cast<CallBase>(
I)->isIndirectCall();
2027 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2028 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2029 if (HaveIndirectCalls) {
2030 if (!AllCallsAreIndirect)
2034 Value *Callee =
nullptr;
2036 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2038 Callee = CurrCallee;
2039 else if (Callee != CurrCallee)
2045 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2047 if (
Op->getType()->isTokenTy())
2055 if (!
all_of(Insts, SameAsI0)) {
2061 for (
auto *
I : Insts)
2062 Ops.push_back(
I->getOperand(OI));
2072 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2077 for (
auto *BB :
Blocks) {
2080 I =
I->getPrevNode();
2081 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2082 if (!isa<DbgInfoIntrinsic>(
I))
2107 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2110 PN->insertBefore(BBEnd->begin());
2111 for (
auto *
I : Insts)
2112 PN->addIncoming(
I->getOperand(O),
I->getParent());
2121 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2124 for (
auto *
I : Insts)
2142 auto *PN = cast<PHINode>(U);
2143 PN->replaceAllUsesWith(I0);
2144 PN->eraseFromParent();
2148 for (
auto *
I : Insts) {
2153 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2154 I->replaceAllUsesWith(I0);
2155 I->eraseFromParent();
2169 class LockstepReverseIterator {
2182 for (
auto *BB : Blocks) {
2184 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2202 for (
auto *&Inst : Insts) {
2203 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2216 for (
auto *&Inst : Insts) {
2217 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2280 bool HaveNonUnconditionalPredecessors =
false;
2282 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2283 if (PredBr && PredBr->isUnconditional())
2286 HaveNonUnconditionalPredecessors =
true;
2288 if (UnconditionalPreds.
size() < 2)
2301 for (
const Use &U : PN.incoming_values())
2302 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2303 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2305 Ops.push_back(*IncomingVals[Pred]);
2310 LockstepReverseIterator LRI(UnconditionalPreds);
2311 while (LRI.isValid() &&
2313 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2315 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2326 if (!followedByDeoptOrUnreachable) {
2330 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2331 unsigned NumPHIInsts = 0;
2332 for (
Use &U : (*LRI)[0]->operands()) {
2333 auto It = PHIOperands.
find(&U);
2334 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2335 return InstructionsToSink.contains(V);
2343 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2344 return NumPHIInsts <= 1;
2361 while (
Idx < ScanIdx) {
2362 if (!ProfitableToSinkInstruction(LRI)) {
2365 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2368 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2378 if (
Idx < ScanIdx) {
2381 InstructionsToSink = InstructionsProfitableToSink;
2387 !ProfitableToSinkInstruction(LRI) &&
2388 "We already know that the last instruction is unprofitable to sink");
2396 for (
auto *
I : *LRI)
2397 InstructionsProfitableToSink.
erase(
I);
2398 if (!ProfitableToSinkInstruction(LRI)) {
2401 InstructionsToSink = InstructionsProfitableToSink;
2413 bool Changed =
false;
2415 if (HaveNonUnconditionalPredecessors) {
2416 if (!followedByDeoptOrUnreachable) {
2424 bool Profitable =
false;
2425 while (
Idx < ScanIdx) {
2459 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2461 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2469 NumSinkCommonInstrs++;
2473 ++NumSinkCommonCode;
2479struct CompatibleSets {
2497 if (CompatibleSets::shouldBelongToSameSet({Set.front(),
II}))
2506 getCompatibleSet(
II).emplace_back(
II);
2510 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2514 return II->cannotMerge() ||
II->isInlineAsm();
2516 if (
any_of(Invokes, IsIllegalToMerge))
2521 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2522 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2523 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2524 if (HaveIndirectCalls) {
2525 if (!AllCallsAreIndirect)
2531 Value *CurrCallee =
II->getCalledOperand();
2532 assert(CurrCallee &&
"There is always a called operand.");
2535 else if (Callee != CurrCallee)
2543 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2545 if (
any_of(Invokes, HasNormalDest)) {
2548 if (!
all_of(Invokes, HasNormalDest))
2555 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2557 NormalBB = CurrNormalBB;
2558 else if (NormalBB != CurrNormalBB)
2566 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2577 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2579 UnwindBB = CurrUnwindBB;
2581 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2588 Invokes.front()->getUnwindDest(),
2589 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2595 for (
auto *
II : Invokes.drop_front())
2596 if (!
II->isSameOperationAs(II0))
2600 auto IsIllegalToMergeArguments = [](
auto Ops) {
2601 Use &U0 = std::get<0>(Ops);
2602 Use &U1 = std::get<1>(Ops);
2609 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2610 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2611 IsIllegalToMergeArguments))
2623 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2629 bool HasNormalDest =
2630 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2634 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2638 II0->
getParent()->getIterator()->getNextNode();
2643 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2645 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2647 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2649 if (!HasNormalDest) {
2653 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2660 return MergedInvoke;
2668 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2674 SuccBBOfMergedInvoke});
2681 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2684 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2687 for (
Use &U : MergedInvoke->operands()) {
2689 if (MergedInvoke->isCallee(&U)) {
2690 if (!IsIndirectCall)
2692 }
else if (!MergedInvoke->isDataOperand(&U))
2697 return II->getOperand(
U.getOperandNo()) !=
U.get();
2704 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2716 Invokes.front()->getParent());
2724 if (!MergedDebugLoc)
2725 MergedDebugLoc =
II->getDebugLoc();
2733 OrigSuccBB->removePredecessor(
II->getParent());
2735 II->replaceAllUsesWith(MergedInvoke);
2736 II->eraseFromParent();
2739 MergedInvoke->setDebugLoc(MergedDebugLoc);
2740 ++NumInvokeSetsFormed;
2743 DTU->applyUpdates(Updates);
2770 bool Changed =
false;
2776 CompatibleSets Grouper;
2782 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2786 if (Invokes.
size() < 2)
2798class EphemeralValueTracker {
2802 if (isa<AssumeInst>(
I))
2804 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2806 return EphValues.count(cast<Instruction>(U));
2812 if (isEphemeral(
I)) {
2851 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2863 unsigned MaxNumInstToLookAt = 9;
2867 if (!MaxNumInstToLookAt)
2869 --MaxNumInstToLookAt;
2872 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2875 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2879 if (SI->getPointerOperand() == StorePtr &&
2880 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2881 SI->getAlign() >= StoreToHoist->
getAlign())
2883 return SI->getValueOperand();
2887 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2888 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2889 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2912 unsigned &SpeculatedInstructions,
2920 bool HaveRewritablePHIs =
false;
2938 HaveRewritablePHIs =
true;
2941 if (!OrigCE && !ThenCE)
2948 if (OrigCost + ThenCost > MaxCost)
2955 ++SpeculatedInstructions;
2956 if (SpeculatedInstructions > 1)
2960 return HaveRewritablePHIs;
3000bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3007 if (isa<FCmpInst>(BrCond))
3017 bool Invert =
false;
3026 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3029 (TWeight + FWeight) != 0) {
3030 uint64_t EndWeight = Invert ? TWeight : FWeight;
3034 if (BIEndProb >= Likely)
3048 unsigned SpeculatedInstructions = 0;
3049 Value *SpeculatedStoreValue =
nullptr;
3051 EphemeralValueTracker EphTracker;
3054 if (isa<DbgInfoIntrinsic>(
I)) {
3062 if (isa<PseudoProbeInst>(
I)) {
3072 if (EphTracker.track(&
I))
3077 ++SpeculatedInstructions;
3078 if (SpeculatedInstructions > 1)
3084 &
I, BB, ThenBB, EndBB))))
3086 if (!SpeculatedStoreValue &&
3092 if (SpeculatedStoreValue)
3093 SpeculatedStore = cast<StoreInst>(&
I);
3098 for (
Use &
Op :
I.operands()) {
3103 ++SinkCandidateUseCounts[OpI];
3110 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3112 ++SpeculatedInstructions;
3113 if (SpeculatedInstructions > 1)
3119 bool Convert = SpeculatedStore !=
nullptr;
3122 SpeculatedInstructions,
3124 if (!Convert ||
Cost > Budget)
3128 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3131 if (SpeculatedStoreValue) {
3135 Value *FalseV = SpeculatedStoreValue;
3139 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3168 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3170 DbgAssign->replaceVariableLocationOp(OrigV, S);
3183 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3185 if (!isa<DbgAssignIntrinsic>(&
I))
3188 I.dropUBImplyingAttrsAndMetadata();
3191 if (EphTracker.contains(&
I)) {
3193 I.eraseFromParent();
3207 It.dropOneDbgRecord(&DR);
3209 std::prev(ThenBB->
end()));
3226 Value *TrueV = ThenV, *FalseV = OrigV;
3240 if (!isa<DbgAssignIntrinsic>(
I))
3241 I->eraseFromParent();
3251 EphemeralValueTracker EphTracker;
3257 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3258 if (CI->cannotDuplicate() || CI->isConvergent())
3264 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3271 for (
User *U :
I.users()) {
3273 if (UI->
getParent() != BB || isa<PHINode>(UI))
3287 auto *
I = dyn_cast<Instruction>(V);
3288 if (
I &&
I->getParent() == To)
3292 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3304static std::optional<bool>
3320 if (
auto *CB = dyn_cast<ConstantInt>(U))
3325 KnownValues[CB].
insert(Pred);
3329 if (KnownValues.
empty())
3338 for (
const auto &Pair : KnownValues) {
3356 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3359 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3367 EdgeBB->setName(RealDest->
getName() +
".critedge");
3368 EdgeBB->moveBefore(RealDest);
3378 TranslateMap[
Cond] = CB;
3384 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3391 N->insertInto(EdgeBB, InsertPt);
3394 N->setName(BBI->getName() +
".c");
3397 for (
Use &
Op :
N->operands()) {
3399 if (PI != TranslateMap.
end())
3405 if (!BBI->use_empty())
3406 TranslateMap[&*BBI] = V;
3407 if (!
N->mayHaveSideEffects()) {
3408 N->eraseFromParent();
3413 if (!BBI->use_empty())
3414 TranslateMap[&*BBI] =
N;
3420 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3421 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3422 SrcDbgCursor = std::next(BBI);
3424 N->cloneDebugInfoFrom(&*BBI);
3427 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3433 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3434 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3435 InsertPt->cloneDebugInfoFrom(BI);
3438 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3444 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3445 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3456 return std::nullopt;
3466 std::optional<bool> Result;
3467 bool EverChanged =
false;
3471 EverChanged |= Result == std::nullopt || *Result;
3472 }
while (Result == std::nullopt);
3480 bool SpeculateUnpredictables) {
3495 if (isa<ConstantInt>(IfCond))
3502 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3505 "Will have either one or two blocks to speculate.");
3512 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3513 if (!IsUnpredictable) {
3516 (TWeight + FWeight) != 0) {
3521 if (IfBlocks.
size() == 1) {
3523 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3524 if (BIBBProb >= Likely)
3527 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3535 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3536 if (IfCondPhiInst->getParent() == BB)
3544 unsigned NumPhis = 0;
3556 if (SpeculateUnpredictables && IsUnpredictable)
3559 bool Changed =
false;
3578 PN = dyn_cast<PHINode>(BB->
begin());
3584 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3595 auto IsBinOpOrAnd = [](
Value *V) {
3615 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3628 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3630 <<
" F: " << IfFalse->
getName() <<
"\n");
3644 if (isa<FPMathOperator>(PN))
3664 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3682 if (Opc == Instruction::And)
3684 if (Opc == Instruction::Or)
3697 bool PredHasWeights =
3699 bool SuccHasWeights =
3701 if (PredHasWeights || SuccHasWeights) {
3702 if (!PredHasWeights)
3703 PredTrueWeight = PredFalseWeight = 1;
3704 if (!SuccHasWeights)
3705 SuccTrueWeight = SuccFalseWeight = 1;
3715static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3719 "Both blocks must end with a conditional branches.");
3721 "PredBB must be a predecessor of BB.");
3729 (PTWeight + PFWeight) != 0) {
3737 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3738 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3742 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3745 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3746 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3752 return std::nullopt;
3765 bool InvertPredCond;
3766 std::tie(CommonSucc, Opc, InvertPredCond) =
3769 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3776 {LLVMContext::MD_annotation});
3779 if (InvertPredCond) {
3792 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3794 SuccTrueWeight, SuccFalseWeight)) {
3801 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3807 (SuccFalseWeight + SuccTrueWeight) +
3808 PredTrueWeight * SuccFalseWeight);
3814 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3815 PredFalseWeight * SuccTrueWeight);
3817 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3835 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3836 {DominatorTree::Delete, PredBlock, BB}});
3863 ++NumFoldBranchToCommonDest;
3870 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3871 return U->getType()->isVectorTy();
3881 unsigned BonusInstThreshold) {
3895 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3896 !isa<SelectInst>(
Cond)) ||
3897 Cond->getParent() != BB || !
Cond->hasOneUse())
3907 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3918 bool InvertPredCond;
3920 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3952 unsigned NumBonusInsts = 0;
3953 bool SawVectorOp =
false;
3954 const unsigned PredCount = Preds.
size();
3960 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3971 NumBonusInsts += PredCount;
3979 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3980 auto *UI = cast<Instruction>(U.getUser());
3981 if (
auto *PN = dyn_cast<PHINode>(UI))
3983 return UI->
getParent() == BB &&
I.comesBefore(UI);
3987 if (!
all_of(
I.uses(), IsBCSSAUse))
3991 BonusInstThreshold *
3997 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4007 for (
auto *BB : {BB1, BB2}) {
4011 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4023 Value *AlternativeV =
nullptr) {
4041 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4042 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4043 PHI = cast<PHINode>(
I);
4049 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4050 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4058 if (!AlternativeV &&
4059 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4064 PHI->addIncoming(V, BB);
4074 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4083 if (!PStore || !QStore)
4104 if (
I.mayReadOrWriteMemory())
4106 for (
auto &
I : *QFB)
4107 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4110 for (
auto &
I : *QTB)
4111 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4115 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4131 if (
I.isTerminator())
4135 if (
auto *S = dyn_cast<StoreInst>(&
I))
4139 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4149 "When we run out of budget we will eagerly return from within the "
4150 "per-instruction loop.");
4154 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4156 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4157 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4265 bool InvertPCond =
false, InvertQCond =
false;
4271 if (QFB == PostBB) {
4290 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4293 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4301 for (
auto *BB : {PTB, PFB}) {
4306 PStoreAddresses.
insert(SI->getPointerOperand());
4308 for (
auto *BB : {QTB, QFB}) {
4313 QStoreAddresses.
insert(SI->getPointerOperand());
4319 auto &CommonAddresses = PStoreAddresses;
4321 bool Changed =
false;
4322 for (
auto *Address : CommonAddresses)
4325 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4343 !BI->
getParent()->getSinglePredecessor())
4345 if (!IfFalseBB->
phis().empty())
4355 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4366 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4367 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4378 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4379 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4458 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4460 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4464 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4467 if (CommonDestProb >= Likely)
4477 unsigned NumPhis = 0;
4499 if (OtherDest == BB) {
4506 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4507 OtherDest = InfLoopBlock;
4527 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4542 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4543 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4546 SuccTrueWeight, SuccFalseWeight);
4548 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4549 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4550 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4551 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4555 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4556 PredOther * SuccCommon,
4557 PredOther * SuccOther};
4586 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4587 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4588 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4589 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4592 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4593 PredOther * SuccCommon};
4616bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4627 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4634 if (Succ == KeepEdge1)
4635 KeepEdge1 =
nullptr;
4636 else if (Succ == KeepEdge2)
4637 KeepEdge2 =
nullptr;
4642 if (Succ != TrueBB && Succ != FalseBB)
4643 RemovedSuccessors.
insert(Succ);
4651 if (!KeepEdge1 && !KeepEdge2) {
4652 if (TrueBB == FalseBB) {
4660 if (TrueWeight != FalseWeight)
4663 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4685 for (
auto *RemovedSuccessor : RemovedSuccessors)
4686 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4687 DTU->applyUpdates(Updates);
4697bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4702 if (!TrueVal || !FalseVal)
4707 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4708 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4711 uint32_t TrueWeight = 0, FalseWeight = 0;
4716 if (Weights.
size() == 1 +
SI->getNumCases()) {
4718 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4720 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4725 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4734bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4747 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4768bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4788 if (
SI->getCondition() != V)
4794 if (
SI->getDefaultDest() != BB) {
4796 assert(VVal &&
"Should have a unique destination value");
4804 return requestResimplify();
4810 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4820 return requestResimplify();
4827 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4852 auto W0 = SIW.getSuccessorWeight(0);
4856 SIW.setSuccessorWeight(0, *NewW);
4858 SIW.addCase(Cst, NewBB, NewW);
4860 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4869 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4870 DTU->applyUpdates(Updates);
4878bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4890 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4893 Value *CompVal = ConstantCompare.CompValue;
4894 unsigned UsedICmps = ConstantCompare.UsedICmps;
4895 Value *ExtraCase = ConstantCompare.Extra;
4914 if (ExtraCase && Values.
size() < 2)
4929 <<
" cases into SWITCH. BB is:\n"
4939 nullptr,
"switch.early.test");
4963 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4969 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4970 <<
"\nEXTRABB = " << *BB);
4978 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4985 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4986 New->addCase(Values[i], EdgeBB);
4992 PHINode *PN = cast<PHINode>(BBI);
4994 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5001 DTU->applyUpdates(Updates);
5003 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5009 return simplifyCommonResume(RI);
5010 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHI()) &&
5013 return simplifySingleResume(RI);
5021 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5026 switch (IntrinsicID) {
5027 case Intrinsic::dbg_declare:
5028 case Intrinsic::dbg_value:
5029 case Intrinsic::dbg_label:
5030 case Intrinsic::lifetime_end:
5040bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5050 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5053 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5055 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5056 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5060 if (IncomingBB->getUniqueSuccessor() != BB)
5063 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5065 if (IncomingValue != LandingPad)
5069 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5070 TrivialUnwindBlocks.
insert(IncomingBB);
5074 if (TrivialUnwindBlocks.
empty())
5078 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5082 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5096 TrivialBB->getTerminator()->eraseFromParent();
5099 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5106 return !TrivialUnwindBlocks.empty();
5110bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5114 "Resume must unwind the exception that caused control to here");
5118 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5154 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5171 int Idx = DestPN.getBasicBlockIndex(BB);
5185 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5186 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5188 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5192 DestPN.addIncoming(
Incoming, Pred);
5219 std::vector<DominatorTree::UpdateType> Updates;
5223 if (UnwindDest ==
nullptr) {
5235 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5236 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5263 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5264 if (!SuccessorCleanupPad)
5273 SuccessorCleanupPad->eraseFromParent();
5302 bool Changed =
false;
5331 BBI->dropDbgRecords();
5335 BBI->eraseFromParent();
5341 if (&BB->
front() != UI)
5344 std::vector<DominatorTree::UpdateType> Updates;
5350 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5354 [BB](
auto *
Successor) { return Successor == BB; })) {
5362 "The destinations are guaranteed to be different here.");
5373 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5379 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5380 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5382 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5383 if (i->getCaseSuccessor() != BB) {
5388 i = SU.removeCase(i);
5393 if (DTU &&
SI->getDefaultDest() != BB)
5394 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5395 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5396 if (
II->getUnwindDest() == BB) {
5398 DTU->applyUpdates(Updates);
5402 if (!CI->doesNotThrow())
5403 CI->setDoesNotThrow();
5406 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5407 if (CSI->getUnwindDest() == BB) {
5409 DTU->applyUpdates(Updates);
5418 E = CSI->handler_end();
5421 CSI->removeHandler(
I);
5428 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5429 if (CSI->getNumHandlers() == 0) {
5430 if (CSI->hasUnwindDest()) {
5434 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5435 Updates.push_back({DominatorTree::Insert,
5436 PredecessorOfPredecessor,
5437 CSI->getUnwindDest()});
5438 Updates.push_back({DominatorTree::Delete,
5439 PredecessorOfPredecessor, Predecessor});
5442 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5446 DTU->applyUpdates(Updates);
5455 CSI->eraseFromParent();
5458 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5460 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5461 "Expected to always have an unwind to BB.");
5463 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5471 DTU->applyUpdates(Updates);
5486 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5487 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5495 bool RemoveOrigDefaultBlock =
true) {
5497 auto *BB = Switch->getParent();
5498 auto *OrigDefaultBlock = Switch->getDefaultDest();
5499 if (RemoveOrigDefaultBlock)
5500 OrigDefaultBlock->removePredecessor(BB);
5505 Switch->setDefaultDest(&*NewDefaultBlock);
5508 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5509 if (RemoveOrigDefaultBlock &&
5511 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5519bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5521 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5524 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5526 auto *BB =
SI->getParent();
5529 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5534 for (
auto Case :
SI->cases()) {
5538 if (Dest == DestA) {
5544 if (Dest == DestB) {
5554 "Single-destination switch should have been folded.");
5556 assert(DestB !=
SI->getDefaultDest());
5557 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5565 ContiguousCases = &CasesA;
5566 ContiguousDest = DestA;
5569 ContiguousCases = &CasesB;
5570 ContiguousDest = DestB;
5579 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5581 Value *Sub =
SI->getCondition();
5582 if (!
Offset->isNullValue())
5597 if (Weights.
size() == 1 +
SI->getNumCases()) {
5600 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5601 if (
SI->getSuccessor(
I) == ContiguousDest)
5602 TrueWeight += Weights[
I];
5604 FalseWeight += Weights[
I];
5606 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5615 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5616 unsigned PreviousEdges = ContiguousCases->
size();
5617 if (ContiguousDest ==
SI->getDefaultDest())
5619 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5620 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5622 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5623 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5624 if (OtherDest ==
SI->getDefaultDest())
5626 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5627 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5635 auto *UnreachableDefault =
SI->getDefaultDest();
5638 SI->eraseFromParent();
5640 if (!HasDefault && DTU)
5641 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5657 unsigned MaxSignificantBitsInCond =
5664 for (
const auto &Case : SI->cases()) {
5665 auto *
Successor = Case.getCaseSuccessor();
5671 const APInt &CaseVal = Case.getCaseValue()->getValue();
5674 DeadCases.
push_back(Case.getCaseValue());
5687 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5688 const unsigned NumUnknownBits =
5691 if (HasDefault && DeadCases.
empty() &&
5692 NumUnknownBits < 64 ) {
5693 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5694 if (SI->getNumCases() == AllNumCases) {
5701 if (SI->getNumCases() == AllNumCases - 1) {
5702 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5709 for (
const auto &Case : SI->cases())
5710 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5712 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5721 if (DeadCases.
empty())
5727 assert(CaseI != SI->case_default() &&
5728 "Case was not found. Probably mistake in DeadCases forming.");
5730 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5735 std::vector<DominatorTree::UpdateType> Updates;
5736 for (
auto *
Successor : UniqueSuccessors)
5737 if (NumPerSuccessorCases[
Successor] == 0)
5738 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5758 if (!Branch || !Branch->isUnconditional())
5764 int Idx =
PHI.getBasicBlockIndex(BB);
5765 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5768 if (InValue != CaseValue)
5784 ForwardingNodesMap ForwardingNodes;
5786 bool Changed =
false;
5787 for (
const auto &Case : SI->cases()) {
5789 BasicBlock *CaseDest = Case.getCaseSuccessor();
5808 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5809 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5810 count(Phi.blocks(), SwitchBlock) == 1) {
5811 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5819 ForwardingNodes[Phi].push_back(PhiIdx);
5822 for (
auto &ForwardingNode : ForwardingNodes) {
5823 PHINode *Phi = ForwardingNode.first;
5829 for (
int Index : Indexes)
5830 Phi->setIncomingValue(
Index, SI->getCondition());
5840 if (
C->isThreadDependent())
5842 if (
C->isDLLImportDependent())
5845 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5846 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5847 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5853 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5869 if (
Constant *
C = dyn_cast<Constant>(V))
5885 if (
A->isAllOnesValue())
5887 if (
A->isNullValue())
5893 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5918 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5920 if (
I.isTerminator()) {
5922 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5925 CaseDest =
I.getSuccessor(0);
5932 for (
auto &
Use :
I.uses()) {
5935 if (
I->getParent() == CaseDest)
5938 if (Phi->getIncomingBlock(
Use) == CaseDest)
5951 *CommonDest = CaseDest;
5953 if (CaseDest != *CommonDest)
5958 int Idx =
PHI.getBasicBlockIndex(Pred);
5971 Res.push_back(std::make_pair(&
PHI, ConstVal));
5974 return Res.size() > 0;
5980 SwitchCaseResultVectorTy &UniqueResults,
5982 for (
auto &
I : UniqueResults) {
5983 if (
I.first == Result) {
5984 I.second.push_back(CaseVal);
5985 return I.second.size();
5988 UniqueResults.push_back(
5999 SwitchCaseResultVectorTy &UniqueResults,
6003 uintptr_t MaxUniqueResults) {
6004 for (
const auto &
I : SI->cases()) {
6018 const size_t NumCasesForResult =
6026 if (UniqueResults.size() > MaxUniqueResults)
6037 BasicBlock *DefaultDest = SI->getDefaultDest();
6038 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6043 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6044 if ((!DefaultResult &&
6065 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6066 ResultVector[1].second.size() == 1) {
6067 ConstantInt *FirstCase = ResultVector[0].second[0];
6068 ConstantInt *SecondCase = ResultVector[1].second[0];
6069 Value *SelectValue = ResultVector[1].first;
6070 if (DefaultResult) {
6071 Value *ValueCompare =
6072 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6073 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6074 DefaultResult,
"switch.select");
6076 Value *ValueCompare =
6077 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6078 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6079 SelectValue,
"switch.select");
6083 if (ResultVector.size() == 1 && DefaultResult) {
6085 unsigned CaseCount = CaseValues.
size();
6093 for (
auto *Case : CaseValues)
6094 if (Case->getValue().slt(MinCaseVal->
getValue()))
6099 for (
auto *Case : CaseValues)
6100 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6106 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6110 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6115 if (CaseValues.
size() == 2) {
6117 "switch.selectcmp.case1");
6119 "switch.selectcmp.case2");
6120 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6121 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6134 std::vector<DominatorTree::UpdateType> Updates;
6140 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6145 PHI->removeIncomingValueIf(
6146 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6147 PHI->addIncoming(SelectValue, SelectBB);
6150 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6156 if (DTU && RemovedSuccessors.
insert(Succ).second)
6157 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6159 SI->eraseFromParent();
6174 SwitchCaseResultVectorTy UniqueResults;
6180 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6182 Value *SelectValue =
6194class SwitchLookupTable {
6245 bool LinearMapValWrapped =
false;
6253SwitchLookupTable::SwitchLookupTable(
6257 assert(Values.
size() &&
"Can't build lookup table without values!");
6258 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6261 SingleValue = Values.
begin()->second;
6267 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6273 TableContents[
Idx] = CaseRes;
6275 if (CaseRes != SingleValue)
6276 SingleValue =
nullptr;
6280 if (Values.
size() < TableSize) {
6282 "Need a default value to fill the lookup table holes.");
6285 if (!TableContents[
I])
6286 TableContents[
I] = DefaultValue;
6289 if (DefaultValue != SingleValue)
6290 SingleValue =
nullptr;
6296 Kind = SingleValueKind;
6303 bool LinearMappingPossible =
true;
6308 bool NonMonotonic =
false;
6309 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6312 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6316 LinearMappingPossible =
false;
6321 APInt Dist = Val - PrevVal;
6324 }
else if (Dist != DistToPrev) {
6325 LinearMappingPossible =
false;
6333 if (LinearMappingPossible) {
6334 LinearOffset = cast<ConstantInt>(TableContents[0]);
6335 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6336 bool MayWrap =
false;
6337 APInt M = LinearMultiplier->getValue();
6338 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6339 LinearMapValWrapped = NonMonotonic || MayWrap;
6340 Kind = LinearMapKind;
6347 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6349 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6351 TableInt <<=
IT->getBitWidth();
6353 if (!isa<UndefValue>(TableContents[
I - 1])) {
6354 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6355 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6358 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6359 BitMapElementTy =
IT;
6370 GlobalVariable::PrivateLinkage, Initializer,
6371 "switch.table." + FuncName);
6372 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6381 case SingleValueKind:
6383 case LinearMapKind: {
6386 false,
"switch.idx.cast");
6387 if (!LinearMultiplier->isOne())
6388 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6390 !LinearMapValWrapped);
6392 if (!LinearOffset->isZero())
6395 !LinearMapValWrapped);
6411 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6412 "switch.shiftamt",
true,
true);
6415 Value *DownShifted =
6416 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6418 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6424 Array->getInitializer()->getType()->getArrayNumElements();
6425 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6428 "switch.tableidx.zext");
6432 GEPIndices,
"switch.gep");
6434 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6441bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6443 Type *ElementType) {
6444 auto *
IT = dyn_cast<IntegerType>(ElementType);
6451 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6453 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6462 auto *
IT = dyn_cast<IntegerType>(Ty);
6474 DL.fitsInLegalInteger(
IT->getBitWidth());
6486 return NumCases * 100 >= CaseRange * MinDensity;
6507 if (SI->getNumCases() > TableSize)
6510 bool AllTablesFitInRegister =
true;
6511 bool HasIllegalType =
false;
6512 for (
const auto &
I : ResultTypes) {
6513 Type *Ty =
I.second;
6519 AllTablesFitInRegister =
6520 AllTablesFitInRegister &&
6521 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6526 if (HasIllegalType && !AllTablesFitInRegister)
6531 if (AllTablesFitInRegister)
6548 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6551 return all_of(ResultTypes, [&](
const auto &KV) {
6552 return SwitchLookupTable::WouldFitInRegister(
6581 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6603 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6608 for (
auto ValuePair : Values) {
6611 if (!CaseConst || CaseConst == DefaultConst ||
6612 (CaseConst != TrueConst && CaseConst != FalseConst))
6626 if (DefaultConst == FalseConst) {
6629 ++NumTableCmpReuses;
6632 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6633 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6636 ++NumTableCmpReuses;
6646 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6665 if (SI->getNumCases() < 3)
6670 assert(!SI->cases().empty());
6687 MinCaseVal = CaseVal;
6689 MaxCaseVal = CaseVal;
6694 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6704 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6710 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6718 bool HasDefaultResults =
6720 DefaultResultsList,
DL,
TTI);
6722 for (
const auto &
I : DefaultResultsList) {
6725 DefaultResults[
PHI] = Result;
6729 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6731 if (UseSwitchConditionAsTableIndex)
6740 bool DefaultIsReachable = !SI->defaultDestUndefined();
6742 bool TableHasHoles = (NumResults < TableSize);
6747 bool AllHolesAreUndefined = TableHasHoles && !HasDefaultResults;
6755 bool NeedMask = AllHolesAreUndefined && DefaultIsReachable;
6758 if (SI->getNumCases() < 4)
6760 if (!
DL.fitsInLegalInteger(TableSize))
6767 std::vector<DominatorTree::UpdateType> Updates;
6773 assert(MaxTableSize >= TableSize &&
6774 "It is impossible for a switch to have more entries than the max "
6775 "representable value of its input integer type's size.");
6786 if (UseSwitchConditionAsTableIndex) {
6787 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6788 TableIndex = SI->getCondition();
6790 TableIndexOffset = MinCaseVal;
6793 bool MayWrap =
true;
6794 if (!DefaultIsReachable) {
6799 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6800 "switch.tableidx",
false,
6809 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6817 return SwitchLookupTable::WouldFitInRegister(
6818 DL, UpperBound, KV.second );
6822 TableSize = std::max(UpperBound, TableSize);
6825 DefaultIsReachable =
false;
6829 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6830 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6833 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6838 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6840 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6842 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6852 MaskBB->
setName(
"switch.hole_check");
6859 APInt MaskInt(TableSizePowOf2, 0);
6860 APInt One(TableSizePowOf2, 1);
6862 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6863 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6866 MaskInt |= One <<
Idx;
6876 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6879 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6881 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6882 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6888 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6891 SI->getDefaultDest()->removePredecessor(BB,
6894 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6898 const ResultListTy &ResultList = ResultLists[
PHI];
6902 AllHolesAreUndefined ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6904 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6907 Value *Result = Table.BuildLookup(TableIndex, Builder);
6911 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6914 for (
auto *
User :
PHI->users()) {
6919 PHI->addIncoming(Result, LookupBB);
6924 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6928 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6931 if (Succ == SI->getDefaultDest())
6934 if (DTU && RemovedSuccessors.
insert(Succ).second)
6935 Updates.push_back({DominatorTree::Delete, BB, Succ});
6937 SI->eraseFromParent();
6944 ++NumLookupTablesHoles;
6959 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6960 if (CondTy->getIntegerBitWidth() > 64 ||
6961 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6965 if (SI->getNumCases() < 4)
6973 for (
const auto &
C : SI->cases())
6974 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6982 int64_t
Base = Values[0];
6983 for (
auto &V : Values)
6996 unsigned Shift = 64;
6997 for (
auto &V : Values)
7001 for (
auto &V : Values)
7002 V = (int64_t)((
uint64_t)V >> Shift);
7018 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7021 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7023 Ty, Intrinsic::fshl,
7024 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7025 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7027 for (
auto Case : SI->cases()) {
7028 auto *Orig = Case.getCaseValue();
7029 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
7030 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7046 Value *Condition = SI->getCondition();
7048 auto *CondTy = cast<IntegerType>(Condition->
getType());
7050 if (CondTy->getIntegerBitWidth() > 64 ||
7051 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7065 if (SI->getNumCases() < 4)
7071 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7076 for (
const auto &Case : SI->cases()) {
7077 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7094 for (
auto &Case : SI->cases()) {
7095 auto *OrigValue = Case.getCaseValue();
7096 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7097 OrigValue->getValue().countr_zero()));
7104 SI->setCondition(ConditionTrailingZeros);
7112 if (isValueEqualityComparison(SI)) {
7116 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7117 return requestResimplify();
7121 if (SimplifySwitchOnSelect(SI,
Select))
7122 return requestResimplify();
7127 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7128 return requestResimplify();
7134 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7135 return requestResimplify();
7139 return requestResimplify();
7142 return requestResimplify();
7145 return requestResimplify();
7152 if (
Options.ConvertSwitchToLookupTable &&
7154 return requestResimplify();
7157 return requestResimplify();
7160 return requestResimplify();
7163 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7164 return requestResimplify();
7171 bool Changed =
false;
7180 RemovedSuccs.
insert(Dest);
7190 std::vector<DominatorTree::UpdateType> Updates;
7191 Updates.reserve(RemovedSuccs.
size());
7192 for (
auto *RemovedSucc : RemovedSuccs)
7193 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7194 DTU->applyUpdates(Updates);
7212 if (SimplifyIndirectBrOnSelect(IBI, SI))
7213 return requestResimplify();
7245 if (isa<PHINode>(*Succ->
begin()))
7249 if (BB == OtherPred)
7255 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7261 std::vector<DominatorTree::UpdateType> Updates;
7268 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7269 "unexpected successor");
7270 II->setUnwindDest(OtherPred);
7272 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7273 Updates.push_back({DominatorTree::Delete, Pred, BB});
7280 if (isa<DbgInfoIntrinsic>(Inst))
7287 Updates.push_back({DominatorTree::Delete, BB, Succ});
7301 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7302 : simplifyCondBranch(
Branch, Builder);
7305bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7317 bool NeedCanonicalLoop =
7328 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7330 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7332 if (
I->isTerminator() &&
7333 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7340 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7350 if (
Options.SpeculateBlocks &&
7353 return requestResimplify();
7361 if (!PPred || (PredPred && PredPred != PPred))
7398 if (!SuccBI || !SuccBI->isConditional())
7402 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7403 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7406 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7425 Updates.
push_back({DominatorTree::Delete, BB, BB1});
7426 Updates.
push_back({DominatorTree::Insert, BB, BB4});
7427 Updates.
push_back({DominatorTree::Delete, BB, BB2});
7428 Updates.
push_back({DominatorTree::Insert, BB, BB3});
7432 bool HasWeight =
false;
7437 BBTWeight = BBFWeight = 1;
7442 BB1TWeight = BB1FWeight = 1;
7447 BB2TWeight = BB2FWeight = 1;
7449 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
7450 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
7461 "Tautological conditional branch should have been eliminated already.");
7464 if (!
Options.SimplifyCondBranch ||
7469 if (isValueEqualityComparison(BI)) {
7474 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7475 return requestResimplify();
7481 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7482 return requestResimplify();
7485 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7486 return requestResimplify();
7491 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7504 return requestResimplify();
7510 if (
Options.SpeculateBlocks &&
7513 return requestResimplify();
7523 return requestResimplify();
7531 return requestResimplify();
7540 return requestResimplify();
7547 return requestResimplify();
7552 if (PBI != BI && PBI->isConditional())
7554 return requestResimplify();
7559 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7560 if (PBI != BI && PBI->isConditional())
7562 return requestResimplify();
7566 return requestResimplify();
7580 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7584 auto *Use = cast<Instruction>(U);
7586 switch (Use->getOpcode()) {
7589 case Instruction::GetElementPtr:
7590 case Instruction::Ret:
7591 case Instruction::BitCast:
7592 case Instruction::Load:
7593 case Instruction::Store:
7594 case Instruction::Call:
7595 case Instruction::CallBr:
7596 case Instruction::Invoke:
7600 if (FindUse ==
I->user_end())
7602 auto *
Use = cast<Instruction>(*FindUse);
7606 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7620 if (
GEP->getPointerOperand() ==
I) {
7627 if (!
GEP->hasAllZeroIndices() &&
7628 (!
GEP->isInBounds() ||
7630 GEP->getPointerAddressSpace())))
7631 PtrValueMayBeModified =
true;
7637 bool HasNoUndefAttr =
7638 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7640 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7643 if (
C->isNullValue() && HasNoUndefAttr &&
7644 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7645 return !PtrValueMayBeModified;
7655 if (!LI->isVolatile())
7657 LI->getPointerAddressSpace());
7661 if (!SI->isVolatile())
7663 SI->getPointerAddressSpace())) &&
7664 SI->getPointerOperand() ==
I;
7667 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
7669 if (
I == Assume->getArgOperand(0))
7673 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7677 if (CB->getCalledOperand() ==
I)
7680 if (
C->isNullValue()) {
7683 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7684 if (CB->isPassingUndefUB(ArgIdx) &&
7685 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7687 return !PtrValueMayBeModified;
7690 }
else if (isa<UndefValue>(
C)) {
7694 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7695 if (CB->isPassingUndefUB(ArgIdx)) {
7712 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7739 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7741 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7749 for (
const auto &Case : SI->cases())
7750 if (Case.getCaseSuccessor() == BB) {
7752 Case.setSuccessor(Unreachable);
7754 if (SI->getDefaultDest() == BB) {
7756 SI->setDefaultDest(Unreachable);
7761 { { DominatorTree::Insert, Predecessor, Unreachable },
7762 { DominatorTree::Delete, Predecessor, BB } });
7770bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7771 bool Changed =
false;
7795 return requestResimplify();
7816 if (
Options.SpeculateBlocks &&
7820 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7823 Options.SpeculateUnpredictables))
7830 case Instruction::Br:
7831 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7833 case Instruction::Resume:
7834 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7836 case Instruction::CleanupRet:
7837 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7839 case Instruction::Switch:
7840 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7842 case Instruction::Unreachable:
7843 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7845 case Instruction::IndirectBr:
7846 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7854 bool Changed =
false;
7862 Changed |= simplifyOnce(BB);
7863 }
while (Resimplify);
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< 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...
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static bool ValidLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static Constant * ConstantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static Constant * LookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool SafeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static void GetBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static ConstantInt * GetConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static void EliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static std::optional< bool > FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
static PHINode * FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{Tru...
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
static bool SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights, bool IsExpected)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool IncomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool FoldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool ForwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static int ConstantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static void FitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static void EraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static unsigned skippedInstrFlags(Instruction *I)
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static bool ValuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void MergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool ShouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool CasesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool isLifeTimeMarker(const Instruction *I)
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static bool MergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class represents a no-op cast from one type to another.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
bool hasPostDomTree() const
Returns true if it holds a PostDomTreeT.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
LLVMContext & getContext() const
Get the global data context.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
pred_iterator pred_end(BasicBlock *BB)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
auto unique(Range &&R, Predicate P)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
pred_iterator pred_begin(BasicBlock *BB)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It)
Advance It while it points to a debug instruction and return the result.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
bool FoldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
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.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
unsigned succ_size(const MachineBasicBlock *BB)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
A MapVector that performs no allocations if smaller than a certain size.