91using namespace PatternMatch;
93#define DEBUG_TYPE "simplifycfg"
96 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
98 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
99 "into preserving DomTree,"));
108 "Control the amount of phi node folding to perform (default = 2)"));
112 cl::desc(
"Control the maximal total instruction cost that we are willing "
113 "to speculatively execute to fold a 2-entry PHI node into a "
114 "select (default = 4)"));
118 cl::desc(
"Hoist common instructions up to the parent block"));
123 cl::desc(
"Allow reordering across at most this many "
124 "instructions when hoisting"));
128 cl::desc(
"Sink common instructions down to the end block"));
132 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
136 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
137 "precede - hoist multiple conditional stores into a single "
138 "predicated store"));
142 cl::desc(
"When merging conditional stores, do so even if the resultant "
143 "basic blocks are unlikely to be if-converted as a result"));
147 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
152 cl::desc(
"Limit maximum recursion depth when calculating costs of "
153 "speculatively executed instructions"));
158 cl::desc(
"Max size of a block which is still considered "
159 "small enough to thread through"));
165 cl::desc(
"Maximum cost of combining conditions when "
166 "folding branches"));
169 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
171 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
172 "to fold branch to common destination when vector operations are "
177 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
181 cl::desc(
"Limit cases to analyze when converting a switch to select"));
183STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
185 "Number of switch instructions turned into linear mapping");
187 "Number of switch instructions turned into lookup tables");
189 NumLookupTablesHoles,
190 "Number of switch instructions turned into lookup tables (holes checked)");
191STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
193 "Number of value comparisons folded into predecessor basic blocks");
195 "Number of branches folded into predecessor basic block");
198 "Number of common instruction 'blocks' hoisted up to the begin block");
200 "Number of common instructions hoisted up to the begin block");
202 "Number of common instruction 'blocks' sunk down to the end block");
204 "Number of common instructions sunk down to the end block");
205STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
207 "Number of invokes with empty resume blocks simplified into calls");
208STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
209STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
216using SwitchCaseResultVectorTy =
225struct ValueEqualityComparisonCase {
232 bool operator<(ValueEqualityComparisonCase RHS)
const {
240class SimplifyCFGOpt {
250 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
251 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
254 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
257 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
271 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
274 bool hoistCommonCodeFromSuccessors(
BasicBlock *BB,
bool EqTermsOnly);
275 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
294 "SimplifyCFG is not yet capable of maintaining validity of a "
295 "PostDomTree, so don't ask for it.");
302 bool requestResimplify() {
321 "Only for a pair of incoming blocks at the time!");
327 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
328 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
331 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
332 EquivalenceSet->contains(IV1))
355 if (!SI1Succs.
count(Succ))
361 FailBlocks->insert(Succ);
377 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
379 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
380 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
389 assert((!isa<Instruction>(
I) ||
391 "Instruction is not safe to speculatively execute!");
417 unsigned Depth = 0) {
446 if (AggressiveInsts.
count(
I))
470 for (
Use &
Op :
I->operands())
484 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
485 DL.isNonIntegralPointerType(V->getType()))
490 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
493 if (isa<ConstantPointerNull>(V))
494 return ConstantInt::get(PtrTy, 0);
498 if (CE->getOpcode() == Instruction::IntToPtr)
499 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
504 return cast<ConstantInt>(
522struct ConstantComparesGatherer {
526 Value *CompValue =
nullptr;
529 Value *Extra =
nullptr;
535 unsigned UsedICmps = 0;
542 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
543 ConstantComparesGatherer &
544 operator=(
const ConstantComparesGatherer &) =
delete;
549 bool setValueOnce(
Value *NewVal) {
550 if (CompValue && CompValue != NewVal)
553 return (CompValue !=
nullptr);
567 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
578 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
622 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
624 if (!setValueOnce(RHSVal))
629 ConstantInt::get(
C->getContext(),
630 C->getValue() | Mask));
645 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
647 if (!setValueOnce(RHSVal))
651 Vals.
push_back(ConstantInt::get(
C->getContext(),
652 C->getValue() & ~Mask));
673 Value *CandidateVal =
I->getOperand(0);
676 CandidateVal = RHSVal;
691 if (!setValueOnce(CandidateVal))
696 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
707 void gather(
Value *V) {
718 while (!DFT.
empty()) {
726 if (Visited.
insert(Op1).second)
728 if (Visited.
insert(Op0).second)
735 if (matchInstruction(
I, isEQ))
759 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
760 Cond = dyn_cast<Instruction>(SI->getCondition());
761 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
762 if (BI->isConditional())
763 Cond = dyn_cast<Instruction>(BI->getCondition());
765 Cond = dyn_cast<Instruction>(IBI->getAddress());
777 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
780 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
781 CV =
SI->getCondition();
782 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
783 if (BI->isConditional() && BI->getCondition()->hasOneUse())
784 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
792 Value *
Ptr = PTII->getPointerOperand();
793 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
802BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
803 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
804 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
805 Cases.reserve(
SI->getNumCases());
806 for (
auto Case :
SI->cases())
807 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
808 Case.getCaseSuccessor()));
809 return SI->getDefaultDest();
815 Cases.push_back(ValueEqualityComparisonCase(
824 std::vector<ValueEqualityComparisonCase> &Cases) {
830 std::vector<ValueEqualityComparisonCase> &C2) {
831 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
834 if (V1->size() > V2->size())
839 if (V1->size() == 1) {
842 for (
const ValueEqualityComparisonCase &VECC : *V2)
843 if (TheVal == VECC.
Value)
850 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
851 while (i1 != e1 && i2 != e2) {
870 SI->setMetadata(LLVMContext::MD_prof,
N);
877 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
881 if (TrueWeight || FalseWeight)
884 I->setMetadata(LLVMContext::MD_prof,
N);
892bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
898 Value *ThisVal = isValueEqualityComparison(TI);
899 assert(ThisVal &&
"This isn't a value comparison!!");
900 if (ThisVal != PredVal)
907 std::vector<ValueEqualityComparisonCase> PredCases;
909 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
913 std::vector<ValueEqualityComparisonCase> ThisCases;
914 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
926 if (isa<BranchInst>(TI)) {
929 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
935 ThisCases[0].Dest->removePredecessor(PredDef);
938 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
945 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
953 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
957 <<
"Through successor TI: " << *TI);
965 if (DeadCases.
count(i->getCaseValue())) {
974 std::vector<DominatorTree::UpdateType> Updates;
975 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
977 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
978 DTU->applyUpdates(Updates);
989 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
990 if (PredCases[i].Dest == TIBB) {
993 TIV = PredCases[i].
Value;
995 assert(TIV &&
"No edge from pred to succ?");
1000 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1001 if (ThisCases[i].
Value == TIV) {
1002 TheRealDest = ThisCases[i].Dest;
1008 TheRealDest = ThisDef;
1015 if (Succ != CheckEdge) {
1016 if (Succ != TheRealDest)
1017 RemovedSuccs.
insert(Succ);
1020 CheckEdge =
nullptr;
1027 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1034 for (
auto *RemovedSucc : RemovedSuccs)
1035 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1036 DTU->applyUpdates(Updates);
1046struct ConstantIntOrdering {
1048 return LHS->getValue().ult(
RHS->getValue());
1060 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1069 assert(MD &&
"Invalid branch-weight metadata");
1075 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1086 if (Max > UINT_MAX) {
1101 if (BonusInst.isTerminator())
1106 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1130 if (isa<DbgInfoIntrinsic>(BonusInst))
1133 NewBonusInst->
takeName(&BonusInst);
1134 BonusInst.setName(NewBonusInst->
getName() +
".old");
1135 VMap[&BonusInst] = NewBonusInst;
1141 auto *UI = cast<Instruction>(U.getUser());
1142 auto *PN = dyn_cast<PHINode>(UI);
1144 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1145 "If the user is not a PHI node, then it should be in the same "
1146 "block as, and come after, the original bonus instruction.");
1150 if (PN->getIncomingBlock(U) == BB)
1154 assert(PN->getIncomingBlock(U) == PredBlock &&
1155 "Not in block-closed SSA form?");
1156 U.set(NewBonusInst);
1161bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1169 std::vector<ValueEqualityComparisonCase> BBCases;
1170 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1172 std::vector<ValueEqualityComparisonCase> PredCases;
1173 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1185 if (PredHasWeights) {
1188 if (Weights.
size() != 1 + PredCases.size())
1189 PredHasWeights = SuccHasWeights =
false;
1190 }
else if (SuccHasWeights)
1194 Weights.
assign(1 + PredCases.size(), 1);
1197 if (SuccHasWeights) {
1200 if (SuccWeights.
size() != 1 + BBCases.size())
1201 PredHasWeights = SuccHasWeights =
false;
1202 }
else if (PredHasWeights)
1203 SuccWeights.
assign(1 + BBCases.size(), 1);
1205 if (PredDefault == BB) {
1208 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1209 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1210 if (PredCases[i].Dest != BB)
1211 PTIHandled.insert(PredCases[i].
Value);
1214 std::swap(PredCases[i], PredCases.back());
1216 if (PredHasWeights || SuccHasWeights) {
1218 Weights[0] += Weights[i + 1];
1223 PredCases.pop_back();
1229 if (PredDefault != BBDefault) {
1231 if (DTU && PredDefault != BB)
1232 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1233 PredDefault = BBDefault;
1234 ++NewSuccessors[BBDefault];
1237 unsigned CasesFromPred = Weights.
size();
1239 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1240 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1241 PredCases.push_back(BBCases[i]);
1242 ++NewSuccessors[BBCases[i].Dest];
1243 if (SuccHasWeights || PredHasWeights) {
1247 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1248 ValidTotalSuccWeight += SuccWeights[i + 1];
1252 if (SuccHasWeights || PredHasWeights) {
1253 ValidTotalSuccWeight += SuccWeights[0];
1255 for (
unsigned i = 1; i < CasesFromPred; ++i)
1256 Weights[i] *= ValidTotalSuccWeight;
1258 Weights[0] *= SuccWeights[0];
1264 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1265 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1266 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1267 if (PredCases[i].Dest == BB) {
1270 if (PredHasWeights || SuccHasWeights) {
1271 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1276 std::swap(PredCases[i], PredCases.back());
1277 PredCases.pop_back();
1284 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1285 if (PTIHandled.count(BBCases[i].Value)) {
1287 if (PredHasWeights || SuccHasWeights)
1289 PredCases.push_back(BBCases[i]);
1290 ++NewSuccessors[BBCases[i].Dest];
1297 if (PredHasWeights || SuccHasWeights)
1299 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1300 ++NewSuccessors[BBDefault];
1312 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1314 for (
auto I :
seq(NewSuccessor.second)) {
1318 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1319 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1332 for (ValueEqualityComparisonCase &V : PredCases)
1335 if (PredHasWeights || SuccHasWeights) {
1352 if (!InfLoopBlock) {
1360 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1367 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1369 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1371 DTU->applyUpdates(Updates);
1374 ++NumFoldValueComparisonIntoPredecessors;
1382bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1385 Value *CV = isValueEqualityComparison(TI);
1386 assert(CV &&
"Not a comparison?");
1388 bool Changed =
false;
1391 while (!Preds.empty()) {
1400 Value *PCV = isValueEqualityComparison(PTI);
1406 for (
auto *Succ : FailBlocks) {
1412 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1426 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1427 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1428 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1447 if (
I->mayReadFromMemory())
1451 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1468 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1478 if (
auto *CB = dyn_cast<CallBase>(
I))
1479 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1486 if (
auto *J = dyn_cast<Instruction>(
Op))
1487 if (J->getParent() == BB)
1506 auto *C1 = dyn_cast<CallInst>(I1);
1507 auto *C2 = dyn_cast<CallInst>(I2);
1509 if (C1->isMustTailCall() != C2->isMustTailCall())
1517 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1518 if (CB1->cannotMerge() || CB1->isConvergent())
1520 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1521 if (CB2->cannotMerge() || CB2->isConvergent())
1536 if (!I1->hasDbgRecords())
1538 using CurrentAndEndIt =
1539 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1545 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1546 return Pair.first == Pair.second;
1552 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1558 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1560 if (!
Other->hasDbgRecords())
1563 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1570 while (
none_of(Itrs, atEnd)) {
1571 bool HoistDVRs = allIdentical(Itrs);
1572 for (CurrentAndEndIt &Pair : Itrs) {
1589bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1611 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1615 if (isa<PHINode>(*SuccItr))
1617 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1626 if (!INonDbg->isTerminator())
1636 unsigned NumSkipped = 0;
1639 if (SuccIterPairs.
size() > 2) {
1641 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1642 if (SuccIterPairs.
size() < 2)
1646 bool Changed =
false;
1649 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1650 auto &BB1ItrPair = *SuccIterPairBegin++;
1651 auto OtherSuccIterPairRange =
1658 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1660 return I1->isIdenticalToWhenDefined(I2);
1662 if (!AllDbgInstsAreIdentical) {
1663 while (isa<DbgInfoIntrinsic>(I1))
1664 I1 = &*++BB1ItrPair.first;
1665 for (
auto &SuccIter : OtherSuccIterRange) {
1667 while (isa<DbgInfoIntrinsic>(I2))
1672 bool AllInstsAreIdentical =
true;
1673 bool HasTerminator =
I1->isTerminator();
1674 for (
auto &SuccIter : OtherSuccIterRange) {
1677 if (AllInstsAreIdentical && (!
I1->isIdenticalToWhenDefined(I2) ||
1679 AllInstsAreIdentical =
false;
1683 for (
auto &SuccIter : OtherSuccIterRange)
1688 if (HasTerminator) {
1692 if (NumSkipped || !AllInstsAreIdentical) {
1697 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1701 if (AllInstsAreIdentical) {
1702 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1703 AllInstsAreIdentical =
1705 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1707 unsigned SkipFlagsBB2 = Pair.second;
1717 if (AllInstsAreIdentical) {
1719 if (isa<DbgInfoIntrinsic>(I1)) {
1728 for (
auto &SuccIter : OtherSuccIterRange) {
1729 auto *I2 = &*SuccIter++;
1730 assert(isa<DbgInfoIntrinsic>(I2));
1742 for (
auto &SuccIter : OtherSuccIterRange) {
1756 NumHoistCommonCode += SuccIterPairs.
size();
1758 NumHoistCommonInstrs += SuccIterPairs.
size();
1767 for (
auto &SuccIterPair : SuccIterPairs) {
1776bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1780 auto *BI = dyn_cast<BranchInst>(TI);
1782 bool Changed =
false;
1787 auto *I2 = *OtherSuccTIs.
begin();
1803 if (isa<CallBrInst>(I1))
1808 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1810 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1830 if (!
NT->getType()->isVoidTy()) {
1831 I1->replaceAllUsesWith(NT);
1833 OtherSuccTI->replaceAllUsesWith(NT);
1837 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1843 for (
auto *OtherSuccTI : OtherSuccTIs)
1844 Locs.
push_back(OtherSuccTI->getDebugLoc());
1856 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1859 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1860 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1866 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1870 if (isa<FPMathOperator>(PN))
1879 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1880 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1881 PN.setIncomingValue(i, SI);
1892 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1897 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1901 DTU->applyUpdates(Updates);
1907 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1908 switch (II->getIntrinsicID()) {
1911 case Intrinsic::lifetime_start:
1912 case Intrinsic::lifetime_end:
1923 return !isa<IntrinsicInst>(
I);
1937 bool HasUse = !Insts.
front()->user_empty();
1938 for (
auto *
I : Insts) {
1940 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1941 I->getType()->isTokenTy())
1946 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1953 if (
const auto *
C = dyn_cast<CallBase>(
I))
1954 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1958 if (HasUse && !
I->hasOneUse())
1960 if (!HasUse && !
I->user_empty())
1966 for (
auto *
I : Insts) {
1967 if (!
I->isSameOperationAs(I0))
1973 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1975 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1989 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1992 auto *U = cast<Instruction>(*
I->user_begin());
1994 PNUse->getParent() == Succ &&
1995 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1996 U->getParent() ==
I->getParent();
2011 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2015 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2019 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2027 if (isa<CallBase>(I0)) {
2029 return cast<CallBase>(
I)->isIndirectCall();
2031 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2032 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2033 if (HaveIndirectCalls) {
2034 if (!AllCallsAreIndirect)
2038 Value *Callee =
nullptr;
2040 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2042 Callee = CurrCallee;
2043 else if (Callee != CurrCallee)
2049 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2051 if (
Op->getType()->isTokenTy())
2059 if (!
all_of(Insts, SameAsI0)) {
2064 for (
auto *
I : Insts)
2065 PHIOperands[
I].push_back(
I->getOperand(OI));
2075 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2080 for (
auto *BB :
Blocks) {
2083 I =
I->getPrevNode();
2084 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2085 if (!isa<DbgInfoIntrinsic>(
I))
2095 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2097 auto *U = cast<Instruction>(*
I->user_begin());
2123 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2126 PN->insertBefore(BBEnd->begin());
2127 for (
auto *
I : Insts)
2128 PN->addIncoming(
I->getOperand(O),
I->getParent());
2137 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2140 for (
auto *
I : Insts)
2159 PN->replaceAllUsesWith(I0);
2160 PN->eraseFromParent();
2164 for (
auto *
I : Insts) {
2169 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2170 I->replaceAllUsesWith(I0);
2171 I->eraseFromParent();
2187 class LockstepReverseIterator {
2200 for (
auto *BB : Blocks) {
2202 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2220 for (
auto *&Inst : Insts) {
2221 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2234 for (
auto *&Inst : Insts) {
2235 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2298 bool HaveNonUnconditionalPredecessors =
false;
2300 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2301 if (PredBr && PredBr->isUnconditional())
2304 HaveNonUnconditionalPredecessors =
true;
2306 if (UnconditionalPreds.
size() < 2)
2318 LockstepReverseIterator LRI(UnconditionalPreds);
2319 while (LRI.isValid() &&
2321 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2323 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2334 if (!followedByDeoptOrUnreachable) {
2338 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2339 unsigned NumPHIdValues = 0;
2340 for (
auto *
I : *LRI)
2341 for (
auto *V : PHIOperands[
I]) {
2342 if (!InstructionsToSink.
contains(V))
2348 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2349 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2350 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2353 return NumPHIInsts <= 1;
2370 while (
Idx < ScanIdx) {
2371 if (!ProfitableToSinkInstruction(LRI)) {
2374 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2377 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2387 if (
Idx < ScanIdx) {
2390 InstructionsToSink = InstructionsProfitableToSink;
2396 !ProfitableToSinkInstruction(LRI) &&
2397 "We already know that the last instruction is unprofitable to sink");
2405 for (
auto *
I : *LRI)
2406 InstructionsProfitableToSink.
erase(
I);
2407 if (!ProfitableToSinkInstruction(LRI)) {
2410 InstructionsToSink = InstructionsProfitableToSink;
2422 bool Changed =
false;
2424 if (HaveNonUnconditionalPredecessors) {
2425 if (!followedByDeoptOrUnreachable) {
2433 bool Profitable =
false;
2434 while (
Idx < ScanIdx) {
2468 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2470 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2480 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2484 NumSinkCommonInstrs++;
2488 ++NumSinkCommonCode;
2494struct CompatibleSets {
2512 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2521 getCompatibleSet(II).emplace_back(II);
2525 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2531 if (
any_of(Invokes, IsIllegalToMerge))
2537 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2538 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2539 if (HaveIndirectCalls) {
2540 if (!AllCallsAreIndirect)
2547 assert(CurrCallee &&
"There is always a called operand.");
2550 else if (Callee != CurrCallee)
2560 if (
any_of(Invokes, HasNormalDest)) {
2563 if (!
all_of(Invokes, HasNormalDest))
2570 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2572 NormalBB = CurrNormalBB;
2573 else if (NormalBB != CurrNormalBB)
2581 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2592 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2594 UnwindBB = CurrUnwindBB;
2596 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2603 Invokes.front()->getUnwindDest(),
2604 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2610 for (
auto *II : Invokes.drop_front())
2615 auto IsIllegalToMergeArguments = [](
auto Ops) {
2616 Use &U0 = std::get<0>(Ops);
2617 Use &U1 = std::get<1>(Ops);
2624 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2625 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2626 IsIllegalToMergeArguments))
2638 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2644 bool HasNormalDest =
2645 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2649 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2658 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2660 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2662 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2664 if (!HasNormalDest) {
2668 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2675 return MergedInvoke;
2689 SuccBBOfMergedInvoke});
2696 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2699 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2702 for (
Use &U : MergedInvoke->operands()) {
2704 if (MergedInvoke->isCallee(&U)) {
2705 if (!IsIndirectCall)
2707 }
else if (!MergedInvoke->isDataOperand(&U))
2719 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2731 Invokes.front()->getParent());
2739 if (!MergedDebugLoc)
2748 OrigSuccBB->removePredecessor(II->
getParent());
2754 MergedInvoke->setDebugLoc(MergedDebugLoc);
2755 ++NumInvokeSetsFormed;
2758 DTU->applyUpdates(Updates);
2785 bool Changed =
false;
2791 CompatibleSets Grouper;
2797 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2801 if (Invokes.
size() < 2)
2813class EphemeralValueTracker {
2817 if (isa<AssumeInst>(
I))
2819 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2821 return EphValues.count(cast<Instruction>(U));
2827 if (isEphemeral(
I)) {
2866 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2878 unsigned MaxNumInstToLookAt = 9;
2882 if (!MaxNumInstToLookAt)
2884 --MaxNumInstToLookAt;
2887 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2890 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2894 if (SI->getPointerOperand() == StorePtr &&
2895 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2896 SI->getAlign() >= StoreToHoist->
getAlign())
2898 return SI->getValueOperand();
2902 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2903 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2904 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2927 unsigned &SpeculatedInstructions,
2935 bool HaveRewritablePHIs =
false;
2953 HaveRewritablePHIs =
true;
2956 if (!OrigCE && !ThenCE)
2963 if (OrigCost + ThenCost > MaxCost)
2970 ++SpeculatedInstructions;
2971 if (SpeculatedInstructions > 1)
2975 return HaveRewritablePHIs;
3015bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3022 if (isa<FCmpInst>(BrCond))
3032 bool Invert =
false;
3041 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3044 (TWeight + FWeight) != 0) {
3045 uint64_t EndWeight = Invert ? TWeight : FWeight;
3049 if (BIEndProb >= Likely)
3063 unsigned SpeculatedInstructions = 0;
3064 Value *SpeculatedStoreValue =
nullptr;
3066 EphemeralValueTracker EphTracker;
3069 if (isa<DbgInfoIntrinsic>(
I)) {
3077 if (isa<PseudoProbeInst>(
I)) {
3087 if (EphTracker.track(&
I))
3092 ++SpeculatedInstructions;
3093 if (SpeculatedInstructions > 1)
3099 &
I, BB, ThenBB, EndBB))))
3101 if (!SpeculatedStoreValue &&
3107 if (SpeculatedStoreValue)
3108 SpeculatedStore = cast<StoreInst>(&
I);
3113 for (
Use &
Op :
I.operands()) {
3118 ++SinkCandidateUseCounts[OpI];
3125 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3127 ++SpeculatedInstructions;
3128 if (SpeculatedInstructions > 1)
3134 bool Convert = SpeculatedStore !=
nullptr;
3137 SpeculatedInstructions,
3139 if (!Convert ||
Cost > Budget)
3143 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3146 if (SpeculatedStoreValue) {
3150 Value *FalseV = SpeculatedStoreValue;
3154 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3183 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3185 DbgAssign->replaceVariableLocationOp(OrigV, S);
3198 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3200 if (!isa<DbgAssignIntrinsic>(&
I))
3203 I.dropUBImplyingAttrsAndMetadata();
3206 if (EphTracker.contains(&
I)) {
3208 I.eraseFromParent();
3222 It.dropOneDbgRecord(&DR);
3224 std::prev(ThenBB->
end()));
3241 Value *TrueV = ThenV, *FalseV = OrigV;
3255 if (!isa<DbgAssignIntrinsic>(
I))
3256 I->eraseFromParent();
3266 EphemeralValueTracker EphTracker;
3272 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3273 if (CI->cannotDuplicate() || CI->isConvergent())
3279 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3286 for (
User *U :
I.users()) {
3288 if (UI->
getParent() != BB || isa<PHINode>(UI))
3302 auto *
I = dyn_cast<Instruction>(V);
3303 if (
I &&
I->getParent() == To)
3307 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3319static std::optional<bool>
3335 if (
auto *CB = dyn_cast<ConstantInt>(U))
3340 KnownValues[CB].
insert(Pred);
3344 if (KnownValues.
empty())
3353 for (
const auto &Pair : KnownValues) {
3371 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3374 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3382 EdgeBB->setName(RealDest->
getName() +
".critedge");
3383 EdgeBB->moveBefore(RealDest);
3393 TranslateMap[
Cond] = CB;
3399 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3406 N->insertInto(EdgeBB, InsertPt);
3409 N->setName(BBI->getName() +
".c");
3412 for (
Use &
Op :
N->operands()) {
3414 if (PI != TranslateMap.
end())
3420 if (!BBI->use_empty())
3421 TranslateMap[&*BBI] = V;
3422 if (!
N->mayHaveSideEffects()) {
3423 N->eraseFromParent();
3428 if (!BBI->use_empty())
3429 TranslateMap[&*BBI] =
N;
3435 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3436 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3437 SrcDbgCursor = std::next(BBI);
3439 N->cloneDebugInfoFrom(&*BBI);
3442 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3448 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3449 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3450 InsertPt->cloneDebugInfoFrom(BI);
3453 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3459 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3460 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3471 return std::nullopt;
3481 std::optional<bool> Result;
3482 bool EverChanged =
false;
3486 EverChanged |= Result == std::nullopt || *Result;
3487 }
while (Result == std::nullopt);
3509 if (isa<ConstantInt>(IfCond))
3516 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3519 "Will have either one or two blocks to speculate.");
3526 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3529 (TWeight + FWeight) != 0) {
3534 if (IfBlocks.
size() == 1) {
3536 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3537 if (BIBBProb >= Likely)
3540 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3548 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3549 if (IfCondPhiInst->getParent() == BB)
3557 unsigned NumPhis = 0;
3570 bool Changed =
false;
3572 PHINode *PN = cast<PHINode>(II++);
3589 PN = dyn_cast<PHINode>(BB->
begin());
3595 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3606 auto IsBinOpOrAnd = [](
Value *V) {
3626 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3639 <<
" T: " << IfTrue->
getName()
3640 <<
" F: " << IfFalse->
getName() <<
"\n");
3654 if (isa<FPMathOperator>(PN))
3674 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3692 if (Opc == Instruction::And)
3694 if (Opc == Instruction::Or)
3707 bool PredHasWeights =
3709 bool SuccHasWeights =
3711 if (PredHasWeights || SuccHasWeights) {
3712 if (!PredHasWeights)
3713 PredTrueWeight = PredFalseWeight = 1;
3714 if (!SuccHasWeights)
3715 SuccTrueWeight = SuccFalseWeight = 1;
3725static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3729 "Both blocks must end with a conditional branches.");
3731 "PredBB must be a predecessor of BB.");
3739 (PTWeight + PFWeight) != 0) {
3747 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3748 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3752 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3755 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3756 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3762 return std::nullopt;
3775 bool InvertPredCond;
3776 std::tie(CommonSucc, Opc, InvertPredCond) =
3779 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3786 {LLVMContext::MD_annotation});
3789 if (InvertPredCond) {
3802 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3804 SuccTrueWeight, SuccFalseWeight)) {
3811 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3817 (SuccFalseWeight + SuccTrueWeight) +
3818 PredTrueWeight * SuccFalseWeight);
3824 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3825 PredFalseWeight * SuccTrueWeight);
3827 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3845 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3846 {DominatorTree::Delete, PredBlock, BB}});
3873 ++NumFoldBranchToCommonDest;
3880 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3881 return U->getType()->isVectorTy();
3891 unsigned BonusInstThreshold) {
3905 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3906 !isa<SelectInst>(
Cond)) ||
3907 Cond->getParent() != BB || !
Cond->hasOneUse())
3917 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3928 bool InvertPredCond;
3930 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3962 unsigned NumBonusInsts = 0;
3963 bool SawVectorOp =
false;
3964 const unsigned PredCount = Preds.
size();
3970 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3981 NumBonusInsts += PredCount;
3989 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3990 auto *UI = cast<Instruction>(U.getUser());
3991 if (
auto *PN = dyn_cast<PHINode>(UI))
3993 return UI->
getParent() == BB &&
I.comesBefore(UI);
3997 if (!
all_of(
I.uses(), IsBCSSAUse))
4001 BonusInstThreshold *
4007 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4017 for (
auto *BB : {BB1, BB2}) {
4021 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4033 Value *AlternativeV =
nullptr) {
4051 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4052 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4053 PHI = cast<PHINode>(
I);
4059 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4060 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4068 if (!AlternativeV &&
4069 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4074 PHI->addIncoming(V, BB);
4084 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4093 if (!PStore || !QStore)
4114 if (
I.mayReadOrWriteMemory())
4116 for (
auto &
I : *QFB)
4117 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4120 for (
auto &
I : *QTB)
4121 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4125 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4141 if (
I.isTerminator())
4145 if (
auto *S = dyn_cast<StoreInst>(&
I))
4149 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4159 "When we run out of budget we will eagerly return from within the "
4160 "per-instruction loop.");
4164 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4166 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4167 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4275 bool InvertPCond =
false, InvertQCond =
false;
4281 if (QFB == PostBB) {
4300 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4303 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4311 for (
auto *BB : {PTB, PFB}) {
4316 PStoreAddresses.
insert(SI->getPointerOperand());
4318 for (
auto *BB : {QTB, QFB}) {
4323 QStoreAddresses.
insert(SI->getPointerOperand());
4329 auto &CommonAddresses = PStoreAddresses;
4331 bool Changed =
false;
4332 for (
auto *Address : CommonAddresses)
4335 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4355 if (!IfFalseBB->
phis().empty())
4365 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4376 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4377 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4388 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4389 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4468 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4470 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4474 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4477 if (CommonDestProb >= Likely)
4487 unsigned NumPhis = 0;
4509 if (OtherDest == BB) {
4516 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4517 OtherDest = InfLoopBlock;
4537 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4552 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4553 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4556 SuccTrueWeight, SuccFalseWeight);
4558 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4559 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4560 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4561 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4565 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4566 PredOther * SuccCommon,
4567 PredOther * SuccOther};
4596 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4597 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4598 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4599 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4602 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4603 PredOther * SuccCommon};
4625bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4636 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4643 if (Succ == KeepEdge1)
4644 KeepEdge1 =
nullptr;
4645 else if (Succ == KeepEdge2)
4646 KeepEdge2 =
nullptr;
4651 if (Succ != TrueBB && Succ != FalseBB)
4652 RemovedSuccessors.
insert(Succ);
4660 if (!KeepEdge1 && !KeepEdge2) {
4661 if (TrueBB == FalseBB) {
4669 if (TrueWeight != FalseWeight)
4672 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4694 for (
auto *RemovedSuccessor : RemovedSuccessors)
4695 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4696 DTU->applyUpdates(Updates);
4706bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4711 if (!TrueVal || !FalseVal)
4716 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4717 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4720 uint32_t TrueWeight = 0, FalseWeight = 0;
4725 if (Weights.
size() == 1 +
SI->getNumCases()) {
4727 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4729 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4734 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4743bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4756 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4777bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4797 if (
SI->getCondition() != V)
4803 if (
SI->getDefaultDest() != BB) {
4805 assert(VVal &&
"Should have a unique destination value");
4813 return requestResimplify();
4819 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4829 return requestResimplify();
4836 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4861 auto W0 = SIW.getSuccessorWeight(0);
4865 SIW.setSuccessorWeight(0, *NewW);
4867 SIW.addCase(Cst, NewBB, NewW);
4869 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4878 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4879 DTU->applyUpdates(Updates);
4887bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4899 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4902 Value *CompVal = ConstantCompare.CompValue;
4903 unsigned UsedICmps = ConstantCompare.UsedICmps;
4904 Value *ExtraCase = ConstantCompare.Extra;
4923 if (ExtraCase && Values.
size() < 2)
4938 <<
" cases into SWITCH. BB is:\n"
4948 nullptr,
"switch.early.test");
4972 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4978 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4979 <<
"\nEXTRABB = " << *BB);
4987 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4994 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4995 New->addCase(Values[i], EdgeBB);
5001 PHINode *PN = cast<PHINode>(BBI);
5003 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5010 DTU->applyUpdates(Updates);
5012 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5018 return simplifyCommonResume(RI);
5022 return simplifySingleResume(RI);
5030 auto *II = dyn_cast<IntrinsicInst>(&
I);
5035 switch (IntrinsicID) {
5036 case Intrinsic::dbg_declare:
5037 case Intrinsic::dbg_value:
5038 case Intrinsic::dbg_label:
5039 case Intrinsic::lifetime_end:
5049bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5059 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5062 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5064 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5065 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5069 if (IncomingBB->getUniqueSuccessor() != BB)
5072 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5074 if (IncomingValue != LandingPad)
5078 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5079 TrivialUnwindBlocks.
insert(IncomingBB);
5083 if (TrivialUnwindBlocks.
empty())
5087 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5091 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5105 TrivialBB->getTerminator()->eraseFromParent();
5108 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5115 return !TrivialUnwindBlocks.empty();
5119bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5123 "Resume must unwind the exception that caused control to here");
5127 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5163 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5180 int Idx = DestPN.getBasicBlockIndex(BB);
5194 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5195 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5197 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5201 DestPN.addIncoming(
Incoming, Pred);
5228 std::vector<DominatorTree::UpdateType> Updates;
5232 if (UnwindDest ==
nullptr) {
5244 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5245 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5272 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5273 if (!SuccessorCleanupPad)
5282 SuccessorCleanupPad->eraseFromParent();
5311 bool Changed =
false;
5340 BBI->dropDbgRecords();
5344 BBI->eraseFromParent();
5350 if (&BB->
front() != UI)
5353 std::vector<DominatorTree::UpdateType> Updates;
5356 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5357 auto *Predecessor = Preds[i];
5360 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5364 [BB](
auto *
Successor) { return Successor == BB; })) {
5372 "The destinations are guaranteed to be different here.");
5383 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5389 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5390 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5392 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5393 if (i->getCaseSuccessor() != BB) {
5398 i = SU.removeCase(i);
5403 if (DTU &&
SI->getDefaultDest() != BB)
5404 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5405 }
else if (
auto *II = dyn_cast<InvokeInst>(TI)) {
5408 DTU->applyUpdates(Updates);
5412 if (!CI->doesNotThrow())
5413 CI->setDoesNotThrow();
5416 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5417 if (CSI->getUnwindDest() == BB) {
5419 DTU->applyUpdates(Updates);
5428 E = CSI->handler_end();
5431 CSI->removeHandler(
I);
5438 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5439 if (CSI->getNumHandlers() == 0) {
5440 if (CSI->hasUnwindDest()) {
5444 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5445 Updates.push_back({DominatorTree::Insert,
5446 PredecessorOfPredecessor,
5447 CSI->getUnwindDest()});
5448 Updates.push_back({DominatorTree::Delete,
5449 PredecessorOfPredecessor, Predecessor});
5452 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5456 DTU->applyUpdates(Updates);
5465 CSI->eraseFromParent();
5468 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5470 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5471 "Expected to always have an unwind to BB.");
5473 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5481 DTU->applyUpdates(Updates);
5496 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5497 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5506 auto *BB = Switch->getParent();
5507 auto *OrigDefaultBlock = Switch->getDefaultDest();
5508 OrigDefaultBlock->removePredecessor(BB);
5513 Switch->setDefaultDest(&*NewDefaultBlock);
5516 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5518 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5526bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5528 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5531 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5533 auto *BB =
SI->getParent();
5536 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5541 for (
auto Case :
SI->cases()) {
5545 if (Dest == DestA) {
5551 if (Dest == DestB) {
5561 "Single-destination switch should have been folded.");
5563 assert(DestB !=
SI->getDefaultDest());
5564 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5572 ContiguousCases = &CasesA;
5573 ContiguousDest = DestA;
5576 ContiguousCases = &CasesB;
5577 ContiguousDest = DestB;
5586 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5588 Value *Sub =
SI->getCondition();
5589 if (!
Offset->isNullValue())
5604 if (Weights.
size() == 1 +
SI->getNumCases()) {
5607 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5608 if (
SI->getSuccessor(
I) == ContiguousDest)
5609 TrueWeight += Weights[
I];
5611 FalseWeight += Weights[
I];
5613 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5622 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5623 unsigned PreviousEdges = ContiguousCases->
size();
5624 if (ContiguousDest ==
SI->getDefaultDest())
5626 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5627 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5629 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5630 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5631 if (OtherDest ==
SI->getDefaultDest())
5633 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5634 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5642 auto *UnreachableDefault =
SI->getDefaultDest();
5645 SI->eraseFromParent();
5647 if (!HasDefault && DTU)
5648 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5664 unsigned MaxSignificantBitsInCond =
5671 for (
const auto &Case : SI->cases()) {
5672 auto *
Successor = Case.getCaseSuccessor();
5678 const APInt &CaseVal = Case.getCaseValue()->getValue();
5681 DeadCases.
push_back(Case.getCaseValue());
5694 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5695 const unsigned NumUnknownBits =
5698 if (HasDefault && DeadCases.
empty() &&
5699 NumUnknownBits < 64 &&
5700 SI->getNumCases() == (1ULL << NumUnknownBits)) {
5705 if (DeadCases.
empty())
5711 assert(CaseI != SI->case_default() &&
5712 "Case was not found. Probably mistake in DeadCases forming.");
5714 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5719 std::vector<DominatorTree::UpdateType> Updates;
5720 for (
auto *
Successor : UniqueSuccessors)
5721 if (NumPerSuccessorCases[
Successor] == 0)
5722 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5742 if (!Branch || !Branch->isUnconditional())
5748 int Idx =
PHI.getBasicBlockIndex(BB);
5749 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5752 if (InValue != CaseValue)
5768 ForwardingNodesMap ForwardingNodes;
5770 bool Changed =
false;
5771 for (
const auto &Case : SI->cases()) {
5773 BasicBlock *CaseDest = Case.getCaseSuccessor();
5792 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5793 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5794 count(Phi.blocks(), SwitchBlock) == 1) {
5795 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5803 ForwardingNodes[Phi].push_back(PhiIdx);
5806 for (
auto &ForwardingNode : ForwardingNodes) {
5807 PHINode *Phi = ForwardingNode.first;
5809 if (Indexes.
size() < 2)
5812 for (
int Index : Indexes)
5813 Phi->setIncomingValue(
Index, SI->getCondition());
5823 if (
C->isThreadDependent())
5825 if (
C->isDLLImportDependent())
5828 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5829 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5830 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5836 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5852 if (
Constant *
C = dyn_cast<Constant>(V))
5868 if (
A->isAllOnesValue())
5870 if (
A->isNullValue())
5876 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5901 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5903 if (
I.isTerminator()) {
5905 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5908 CaseDest =
I.getSuccessor(0);
5915 for (
auto &
Use :
I.uses()) {
5918 if (
I->getParent() == CaseDest)
5921 if (Phi->getIncomingBlock(
Use) == CaseDest)
5934 *CommonDest = CaseDest;
5936 if (CaseDest != *CommonDest)
5941 int Idx =
PHI.getBasicBlockIndex(Pred);
5954 Res.push_back(std::make_pair(&
PHI, ConstVal));
5957 return Res.size() > 0;
5963 SwitchCaseResultVectorTy &UniqueResults,
5965 for (
auto &
I : UniqueResults) {
5966 if (
I.first == Result) {
5967 I.second.push_back(CaseVal);
5968 return I.second.size();
5971 UniqueResults.push_back(
5982 SwitchCaseResultVectorTy &UniqueResults,
5986 uintptr_t MaxUniqueResults) {
5987 for (
const auto &
I : SI->cases()) {
6001 const size_t NumCasesForResult =
6009 if (UniqueResults.size() > MaxUniqueResults)
6020 BasicBlock *DefaultDest = SI->getDefaultDest();
6021 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6026 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6027 if ((!DefaultResult &&
6048 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6049 ResultVector[1].second.size() == 1) {
6050 ConstantInt *FirstCase = ResultVector[0].second[0];
6051 ConstantInt *SecondCase = ResultVector[1].second[0];
6052 Value *SelectValue = ResultVector[1].first;
6053 if (DefaultResult) {
6054 Value *ValueCompare =
6055 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6056 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6057 DefaultResult,
"switch.select");
6059 Value *ValueCompare =
6060 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6061 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6062 SelectValue,
"switch.select");
6066 if (ResultVector.size() == 1 && DefaultResult) {
6068 unsigned CaseCount = CaseValues.
size();
6076 for (
auto *Case : CaseValues)
6077 if (Case->getValue().slt(MinCaseVal->
getValue()))
6082 for (
auto *Case : CaseValues)
6083 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6089 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6093 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6098 if (CaseValues.
size() == 2) {
6100 "switch.selectcmp.case1");
6102 "switch.selectcmp.case2");
6103 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6104 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6117 std::vector<DominatorTree::UpdateType> Updates;
6123 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6128 PHI->removeIncomingValueIf(
6129 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6130 PHI->addIncoming(SelectValue, SelectBB);
6133 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6139 if (DTU && RemovedSuccessors.
insert(Succ).second)
6140 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6142 SI->eraseFromParent();
6157 SwitchCaseResultVectorTy UniqueResults;
6163 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6165 Value *SelectValue =
6177class SwitchLookupTable {
6228 bool LinearMapValWrapped =
false;
6236SwitchLookupTable::SwitchLookupTable(
6240 assert(Values.
size() &&
"Can't build lookup table without values!");
6241 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6244 SingleValue = Values.
begin()->second;
6250 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6256 TableContents[
Idx] = CaseRes;
6258 if (CaseRes != SingleValue)
6259 SingleValue =
nullptr;
6263 if (Values.
size() < TableSize) {
6265 "Need a default value to fill the lookup table holes.");
6268 if (!TableContents[
I])
6269 TableContents[
I] = DefaultValue;
6272 if (DefaultValue != SingleValue)
6273 SingleValue =
nullptr;
6279 Kind = SingleValueKind;
6286 bool LinearMappingPossible =
true;
6291 bool NonMonotonic =
false;
6292 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6295 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6299 LinearMappingPossible =
false;
6304 APInt Dist = Val - PrevVal;
6307 }
else if (Dist != DistToPrev) {
6308 LinearMappingPossible =
false;
6316 if (LinearMappingPossible) {
6317 LinearOffset = cast<ConstantInt>(TableContents[0]);
6318 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6319 bool MayWrap =
false;
6320 APInt M = LinearMultiplier->getValue();
6321 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6322 LinearMapValWrapped = NonMonotonic || MayWrap;
6323 Kind = LinearMapKind;
6330 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6332 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6334 TableInt <<=
IT->getBitWidth();
6336 if (!isa<UndefValue>(TableContents[
I - 1])) {
6337 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6338 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6341 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6342 BitMapElementTy =
IT;
6353 GlobalVariable::PrivateLinkage, Initializer,
6354 "switch.table." + FuncName);
6355 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6364 case SingleValueKind:
6366 case LinearMapKind: {
6369 false,
"switch.idx.cast");
6370 if (!LinearMultiplier->isOne())
6371 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6373 !LinearMapValWrapped);
6375 if (!LinearOffset->isZero())
6378 !LinearMapValWrapped);
6394 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6395 "switch.shiftamt",
true,
true);
6398 Value *DownShifted =
6399 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6401 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6407 Array->getInitializer()->getType()->getArrayNumElements();
6408 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6411 "switch.tableidx.zext");
6415 GEPIndices,
"switch.gep");
6417 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6424bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6426 Type *ElementType) {
6427 auto *
IT = dyn_cast<IntegerType>(ElementType);
6434 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6436 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6445 auto *
IT = dyn_cast<IntegerType>(Ty);
6457 DL.fitsInLegalInteger(
IT->getBitWidth());
6469 return NumCases * 100 >= CaseRange * MinDensity;
6490 if (SI->getNumCases() > TableSize)
6493 bool AllTablesFitInRegister =
true;
6494 bool HasIllegalType =
false;
6495 for (
const auto &
I : ResultTypes) {
6496 Type *Ty =
I.second;
6502 AllTablesFitInRegister =
6503 AllTablesFitInRegister &&
6504 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6509 if (HasIllegalType && !AllTablesFitInRegister)
6514 if (AllTablesFitInRegister)
6531 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6534 return all_of(ResultTypes, [&](
const auto &KV) {
6535 return SwitchLookupTable::WouldFitInRegister(
6564 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6586 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6591 for (
auto ValuePair : Values) {
6594 if (!CaseConst || CaseConst == DefaultConst ||
6595 (CaseConst != TrueConst && CaseConst != FalseConst))
6609 if (DefaultConst == FalseConst) {
6612 ++NumTableCmpReuses;
6615 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6616 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6619 ++NumTableCmpReuses;
6629 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6648 if (SI->getNumCases() < 3)
6653 assert(!SI->cases().empty());
6670 MinCaseVal = CaseVal;
6672 MaxCaseVal = CaseVal;
6677 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6687 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6693 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6701 bool HasDefaultResults =
6703 DefaultResultsList,
DL,
TTI);
6705 for (
const auto &
I : DefaultResultsList) {
6708 DefaultResults[
PHI] = Result;
6712 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6714 if (UseSwitchConditionAsTableIndex)
6720 bool TableHasHoles = (NumResults < TableSize);
6721 bool NeedMask = (TableHasHoles && !HasDefaultResults);
6724 if (SI->getNumCases() < 4)
6726 if (!
DL.fitsInLegalInteger(TableSize))
6733 std::vector<DominatorTree::UpdateType> Updates;
6739 assert(MaxTableSize >= TableSize &&
6740 "It is impossible for a switch to have more entries than the max "
6741 "representable value of its input integer type's size.");
6746 bool DefaultIsReachable =
6747 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
6758 if (UseSwitchConditionAsTableIndex) {
6759 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6760 TableIndex = SI->getCondition();
6762 TableIndexOffset = MinCaseVal;
6765 bool MayWrap =
true;
6766 if (!DefaultIsReachable) {
6771 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6772 "switch.tableidx",
false,
6781 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6789 return SwitchLookupTable::WouldFitInRegister(
6790 DL, UpperBound, KV.second );
6794 TableSize = std::max(UpperBound, TableSize);
6797 DefaultIsReachable =
false;
6801 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6802 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6805 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6810 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6812 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6814 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6824 MaskBB->
setName(
"switch.hole_check");
6831 APInt MaskInt(TableSizePowOf2, 0);
6832 APInt One(TableSizePowOf2, 1);
6834 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6835 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6838 MaskInt |= One <<
Idx;
6848 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6851 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6853 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6854 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6860 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6863 SI->getDefaultDest()->removePredecessor(BB,
6866 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6870 const ResultListTy &ResultList = ResultLists[
PHI];
6873 Constant *DV = NeedMask ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6875 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6878 Value *Result = Table.BuildLookup(TableIndex, Builder);
6882 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6885 for (
auto *
User :
PHI->users()) {
6890 PHI->addIncoming(Result, LookupBB);
6895 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6899 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6902 if (Succ == SI->getDefaultDest())
6905 if (DTU && RemovedSuccessors.
insert(Succ).second)
6906 Updates.push_back({DominatorTree::Delete, BB, Succ});
6908 SI->eraseFromParent();
6915 ++NumLookupTablesHoles;
6930 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6931 if (CondTy->getIntegerBitWidth() > 64 ||
6932 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6936 if (SI->getNumCases() < 4)
6944 for (
const auto &
C : SI->cases())
6945 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6953 int64_t
Base = Values[0];
6954 for (
auto &V : Values)
6967 unsigned Shift = 64;
6968 for (
auto &V : Values)
6972 for (
auto &V : Values)
6973 V = (int64_t)((
uint64_t)V >> Shift);
6989 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
6992 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
6994 Ty, Intrinsic::fshl,
6995 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
6996 SI->replaceUsesOfWith(SI->getCondition(), Rot);
6998 for (
auto Case : SI->cases()) {
6999 auto *Orig = Case.getCaseValue();
7000 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
7001 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7017 Value *Condition = SI->getCondition();
7019 auto *CondTy = cast<IntegerType>(Condition->
getType());
7021 if (CondTy->getIntegerBitWidth() > 64 ||
7022 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7036 if (SI->getNumCases() < 4)
7042 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7047 for (
const auto &Case : SI->cases()) {
7048 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7065 for (
auto &Case : SI->cases()) {
7066 auto *OrigValue = Case.getCaseValue();
7067 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7068 OrigValue->getValue().countr_zero()));
7075 SI->setCondition(ConditionTrailingZeros);
7083 if (isValueEqualityComparison(SI)) {
7087 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7088 return requestResimplify();
7092 if (SimplifySwitchOnSelect(SI,
Select))
7093 return requestResimplify();
7098 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7099 return requestResimplify();
7105 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7106 return requestResimplify();
7110 return requestResimplify();
7113 return requestResimplify();
7116 return requestResimplify();
7123 if (
Options.ConvertSwitchToLookupTable &&
7125 return requestResimplify();
7128 return requestResimplify();
7131 return requestResimplify();
7134 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7135 return requestResimplify();
7142 bool Changed =
false;
7151 RemovedSuccs.
insert(Dest);
7161 std::vector<DominatorTree::UpdateType> Updates;
7162 Updates.reserve(RemovedSuccs.
size());
7163 for (
auto *RemovedSucc : RemovedSuccs)
7164 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7165 DTU->applyUpdates(Updates);
7183 if (SimplifyIndirectBrOnSelect(IBI, SI))
7184 return requestResimplify();
7216 if (isa<PHINode>(*Succ->
begin()))
7220 if (BB == OtherPred)
7226 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7232 std::vector<DominatorTree::UpdateType> Updates;
7240 "unexpected successor");
7243 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7244 Updates.push_back({DominatorTree::Delete, Pred, BB});
7251 if (isa<DbgInfoIntrinsic>(Inst))
7258 Updates.push_back({DominatorTree::Delete, BB, Succ});
7272 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7273 : simplifyCondBranch(
Branch, Builder);
7276bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7288 bool NeedCanonicalLoop =
7299 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7301 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7303 if (
I->isTerminator() &&
7304 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7311 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7321 if (
Options.SpeculateBlocks &&
7324 return requestResimplify();
7332 if (!PPred || (PredPred && PredPred != PPred))
7343 "Tautological conditional branch should have been eliminated already.");
7346 if (!
Options.SimplifyCondBranch ||
7351 if (isValueEqualityComparison(BI)) {
7356 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7357 return requestResimplify();
7363 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7364 return requestResimplify();
7367 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7368 return requestResimplify();
7373 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7386 return requestResimplify();
7392 if (
Options.SpeculateBlocks &&
7395 return requestResimplify();
7405 return requestResimplify();
7413 return requestResimplify();
7422 return requestResimplify();
7429 return requestResimplify();
7434 if (PBI != BI && PBI->isConditional())
7436 return requestResimplify();
7441 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7442 if (PBI != BI && PBI->isConditional())
7444 return requestResimplify();
7458 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7460 auto *
Use = cast<Instruction>(*
I->user_begin());
7464 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7478 if (
GEP->getPointerOperand() ==
I) {
7485 if (!
GEP->hasAllZeroIndices() &&
7486 (!
GEP->isInBounds() ||
7488 GEP->getPointerAddressSpace())))
7489 PtrValueMayBeModified =
true;
7495 bool HasNoUndefAttr =
7496 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7498 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7501 if (
C->isNullValue() && HasNoUndefAttr &&
7502 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7503 return !PtrValueMayBeModified;
7513 if (!LI->isVolatile())
7515 LI->getPointerAddressSpace());
7519 if (!SI->isVolatile())
7521 SI->getPointerAddressSpace())) &&
7522 SI->getPointerOperand() ==
I;
7525 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
7527 if (
I == Assume->getArgOperand(0))
7531 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7535 if (CB->getCalledOperand() ==
I)
7538 if (
C->isNullValue()) {
7541 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7542 if (CB->isPassingUndefUB(ArgIdx) &&
7543 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7545 return !PtrValueMayBeModified;
7548 }
else if (isa<UndefValue>(
C)) {
7552 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7553 if (CB->isPassingUndefUB(ArgIdx)) {
7570 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7597 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7599 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7607 for (
const auto &Case : SI->cases())
7608 if (Case.getCaseSuccessor() == BB) {
7610 Case.setSuccessor(Unreachable);
7612 if (SI->getDefaultDest() == BB) {
7614 SI->setDefaultDest(Unreachable);
7619 { { DominatorTree::Insert, Predecessor, Unreachable },
7620 { DominatorTree::Delete, Predecessor, BB } });
7628bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7629 bool Changed =
false;
7653 return requestResimplify();
7674 if (
Options.SpeculateBlocks &&
7678 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7687 case Instruction::Br:
7688 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7690 case Instruction::Resume:
7691 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7693 case Instruction::CleanupRet:
7694 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7696 case Instruction::Switch:
7697 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7699 case Instruction::Unreachable:
7700 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7702 case Instruction::IndirectBr:
7703 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7711 bool Changed =
false;
7719 Changed |= simplifyOnce(BB);
7720 }
while (Resimplify);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static bool ValidLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static Constant * ConstantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static Constant * LookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool SafeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static void GetBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static ConstantInt * GetConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static void EliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static std::optional< bool > FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
static PHINode * FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{Tru...
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
static bool SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool IncomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool FoldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool ForwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static int ConstantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static void FitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static void EraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static unsigned skippedInstrFlags(Instruction *I)
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static bool ValuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< Instruction *, SmallVector< Value *, 4 > > &PHIOperands)
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static void MergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool ShouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool CasesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool isLifeTimeMarker(const Instruction *I)
static bool MergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class represents a no-op cast from one type to another.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
bool isInlineAsm() const
Check if this call is an inline asm statement.
bool cannotMerge() const
Determine if the call cannot be tail merged.
bool isIndirectCall() const
Return true if the callsite is an indirect call.
Value * getCalledOperand() const
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool hasPostDomTree() const
Returns true if it holds a PostDominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
BasicBlock * getUnwindDest() const
void setNormalDest(BasicBlock *B)
void setUnwindDest(BasicBlock *B)
BasicBlock * getNormalDest() const
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
LLVMContext & getContext() const
Get the global data context.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
pred_iterator pred_end(BasicBlock *BB)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void 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.
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.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
unsigned succ_size(const MachineBasicBlock *BB)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void 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.