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(
292 :
TTI(
TTI), DTU(DTU),
DL(
DL), LoopHeaders(LoopHeaders), Options(Opts) {
294 "SimplifyCFG is not yet capable of maintaining validity of a "
295 "PostDomTree, so don't ask for it.");
302 bool requestResimplify() {
321 "Only for a pair of incoming blocks at the time!");
327 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
328 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
331 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
332 EquivalenceSet->contains(IV1))
355 if (!SI1Succs.
count(Succ))
361 FailBlocks->insert(Succ);
377 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
379 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
380 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
389 assert((!isa<Instruction>(
I) ||
391 "Instruction is not safe to speculatively execute!");
417 unsigned Depth = 0) {
446 if (AggressiveInsts.
count(
I))
470 for (
Use &
Op :
I->operands())
484 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
485 DL.isNonIntegralPointerType(V->getType()))
490 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
493 if (isa<ConstantPointerNull>(V))
494 return ConstantInt::get(PtrTy, 0);
498 if (CE->getOpcode() == Instruction::IntToPtr)
499 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
504 return cast<ConstantInt>(
522struct ConstantComparesGatherer {
526 Value *CompValue =
nullptr;
529 Value *Extra =
nullptr;
535 unsigned UsedICmps = 0;
542 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
543 ConstantComparesGatherer &
544 operator=(
const ConstantComparesGatherer &) =
delete;
549 bool setValueOnce(
Value *NewVal) {
550 if (CompValue && CompValue != NewVal)
553 return (CompValue !=
nullptr);
567 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
578 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
622 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
624 if (!setValueOnce(RHSVal))
629 ConstantInt::get(
C->getContext(),
630 C->getValue() | Mask));
645 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
647 if (!setValueOnce(RHSVal))
651 Vals.
push_back(ConstantInt::get(
C->getContext(),
652 C->getValue() & ~Mask));
673 Value *CandidateVal =
I->getOperand(0);
676 CandidateVal = RHSVal;
691 if (!setValueOnce(CandidateVal))
696 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
707 void gather(
Value *V) {
718 while (!DFT.
empty()) {
726 if (Visited.
insert(Op1).second)
728 if (Visited.
insert(Op0).second)
735 if (matchInstruction(
I, isEQ))
759 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
760 Cond = dyn_cast<Instruction>(SI->getCondition());
761 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
762 if (BI->isConditional())
763 Cond = dyn_cast<Instruction>(BI->getCondition());
765 Cond = dyn_cast<Instruction>(IBI->getAddress());
777 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
780 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
781 CV =
SI->getCondition();
782 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
783 if (BI->isConditional() && BI->getCondition()->hasOneUse())
784 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
792 Value *
Ptr = PTII->getPointerOperand();
793 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
802BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
803 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
804 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
805 Cases.reserve(
SI->getNumCases());
806 for (
auto Case :
SI->cases())
807 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
808 Case.getCaseSuccessor()));
809 return SI->getDefaultDest();
815 Cases.push_back(ValueEqualityComparisonCase(
824 std::vector<ValueEqualityComparisonCase> &Cases) {
830 std::vector<ValueEqualityComparisonCase> &C2) {
831 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
834 if (V1->size() > V2->size())
839 if (V1->size() == 1) {
842 for (
const ValueEqualityComparisonCase &VECC : *V2)
843 if (TheVal == VECC.
Value)
850 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
851 while (i1 != e1 && i2 != e2) {
872 SI->setMetadata(LLVMContext::MD_prof,
N);
878 uint32_t FalseWeight,
bool IsExpected) {
879 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
883 if (TrueWeight || FalseWeight)
886 I->setMetadata(LLVMContext::MD_prof,
N);
894bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
900 Value *ThisVal = isValueEqualityComparison(TI);
901 assert(ThisVal &&
"This isn't a value comparison!!");
902 if (ThisVal != PredVal)
909 std::vector<ValueEqualityComparisonCase> PredCases;
911 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
915 std::vector<ValueEqualityComparisonCase> ThisCases;
916 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
928 if (isa<BranchInst>(TI)) {
931 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
937 ThisCases[0].Dest->removePredecessor(PredDef);
940 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
947 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
955 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
959 <<
"Through successor TI: " << *TI);
967 if (DeadCases.
count(i->getCaseValue())) {
976 std::vector<DominatorTree::UpdateType> Updates;
977 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
979 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
980 DTU->applyUpdates(Updates);
991 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
992 if (PredCases[i].Dest == TIBB) {
995 TIV = PredCases[i].
Value;
997 assert(TIV &&
"No edge from pred to succ?");
1002 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1003 if (ThisCases[i].
Value == TIV) {
1004 TheRealDest = ThisCases[i].Dest;
1010 TheRealDest = ThisDef;
1017 if (Succ != CheckEdge) {
1018 if (Succ != TheRealDest)
1019 RemovedSuccs.
insert(Succ);
1022 CheckEdge =
nullptr;
1029 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1036 for (
auto *RemovedSucc : RemovedSuccs)
1037 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1038 DTU->applyUpdates(Updates);
1048struct ConstantIntOrdering {
1050 return LHS->getValue().ult(
RHS->getValue());
1062 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1071 assert(MD &&
"Invalid branch-weight metadata");
1077 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1088 if (Max > UINT_MAX) {
1103 if (BonusInst.isTerminator())
1108 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1132 if (isa<DbgInfoIntrinsic>(BonusInst))
1135 NewBonusInst->
takeName(&BonusInst);
1136 BonusInst.setName(NewBonusInst->
getName() +
".old");
1137 VMap[&BonusInst] = NewBonusInst;
1143 auto *UI = cast<Instruction>(U.getUser());
1144 auto *PN = dyn_cast<PHINode>(UI);
1146 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1147 "If the user is not a PHI node, then it should be in the same "
1148 "block as, and come after, the original bonus instruction.");
1152 if (PN->getIncomingBlock(U) == BB)
1156 assert(PN->getIncomingBlock(U) == PredBlock &&
1157 "Not in block-closed SSA form?");
1158 U.set(NewBonusInst);
1163bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1171 std::vector<ValueEqualityComparisonCase> BBCases;
1172 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1174 std::vector<ValueEqualityComparisonCase> PredCases;
1175 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1187 if (PredHasWeights) {
1190 if (Weights.
size() != 1 + PredCases.size())
1191 PredHasWeights = SuccHasWeights =
false;
1192 }
else if (SuccHasWeights)
1196 Weights.
assign(1 + PredCases.size(), 1);
1199 if (SuccHasWeights) {
1202 if (SuccWeights.
size() != 1 + BBCases.size())
1203 PredHasWeights = SuccHasWeights =
false;
1204 }
else if (PredHasWeights)
1205 SuccWeights.
assign(1 + BBCases.size(), 1);
1207 if (PredDefault == BB) {
1210 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1211 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1212 if (PredCases[i].Dest != BB)
1213 PTIHandled.insert(PredCases[i].
Value);
1216 std::swap(PredCases[i], PredCases.back());
1218 if (PredHasWeights || SuccHasWeights) {
1220 Weights[0] += Weights[i + 1];
1225 PredCases.pop_back();
1231 if (PredDefault != BBDefault) {
1233 if (DTU && PredDefault != BB)
1234 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1235 PredDefault = BBDefault;
1236 ++NewSuccessors[BBDefault];
1239 unsigned CasesFromPred = Weights.
size();
1241 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1242 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1243 PredCases.push_back(BBCases[i]);
1244 ++NewSuccessors[BBCases[i].Dest];
1245 if (SuccHasWeights || PredHasWeights) {
1249 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1250 ValidTotalSuccWeight += SuccWeights[i + 1];
1254 if (SuccHasWeights || PredHasWeights) {
1255 ValidTotalSuccWeight += SuccWeights[0];
1257 for (
unsigned i = 1; i < CasesFromPred; ++i)
1258 Weights[i] *= ValidTotalSuccWeight;
1260 Weights[0] *= SuccWeights[0];
1266 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1267 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1268 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1269 if (PredCases[i].Dest == BB) {
1272 if (PredHasWeights || SuccHasWeights) {
1273 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1278 std::swap(PredCases[i], PredCases.back());
1279 PredCases.pop_back();
1286 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1287 if (PTIHandled.count(BBCases[i].Value)) {
1289 if (PredHasWeights || SuccHasWeights)
1291 PredCases.push_back(BBCases[i]);
1292 ++NewSuccessors[BBCases[i].Dest];
1299 if (PredHasWeights || SuccHasWeights)
1301 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1302 ++NewSuccessors[BBDefault];
1314 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1316 for (
auto I :
seq(NewSuccessor.second)) {
1320 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1321 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1334 for (ValueEqualityComparisonCase &V : PredCases)
1337 if (PredHasWeights || SuccHasWeights) {
1354 if (!InfLoopBlock) {
1362 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1369 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1371 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1373 DTU->applyUpdates(Updates);
1376 ++NumFoldValueComparisonIntoPredecessors;
1384bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(
Instruction *TI,
1387 Value *CV = isValueEqualityComparison(TI);
1388 assert(CV &&
"Not a comparison?");
1390 bool Changed =
false;
1393 while (!Preds.empty()) {
1402 Value *PCV = isValueEqualityComparison(PTI);
1408 for (
auto *Succ : FailBlocks) {
1414 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1428 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1429 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1430 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1449 if (
I->mayReadFromMemory())
1453 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1470 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1480 if (
auto *CB = dyn_cast<CallBase>(
I))
1481 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1488 if (
auto *J = dyn_cast<Instruction>(
Op))
1489 if (J->getParent() == BB)
1508 auto *C1 = dyn_cast<CallInst>(I1);
1509 auto *C2 = dyn_cast<CallInst>(I2);
1511 if (C1->isMustTailCall() != C2->isMustTailCall())
1519 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1520 if (CB1->cannotMerge() || CB1->isConvergent())
1522 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1523 if (CB2->cannotMerge() || CB2->isConvergent())
1538 if (!I1->hasDbgRecords())
1540 using CurrentAndEndIt =
1541 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1547 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1548 return Pair.first == Pair.second;
1554 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1560 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1562 if (!
Other->hasDbgRecords())
1565 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1572 while (
none_of(Itrs, atEnd)) {
1573 bool HoistDVRs = allIdentical(Itrs);
1574 for (CurrentAndEndIt &Pair : Itrs) {
1588 if (I1->isIdenticalToWhenDefined(I2))
1591 if (
auto *Cmp1 = dyn_cast<CmpInst>(I1))
1592 if (
auto *Cmp2 = dyn_cast<CmpInst>(I2))
1593 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1594 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1595 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1597 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1598 return I1->getOperand(0) == I2->
getOperand(1) &&
1611bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1633 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1637 if (isa<PHINode>(*SuccItr))
1639 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1648 if (!INonDbg->isTerminator())
1658 unsigned NumSkipped = 0;
1661 if (SuccIterPairs.
size() > 2) {
1663 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1664 if (SuccIterPairs.
size() < 2)
1668 bool Changed =
false;
1671 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1672 auto &BB1ItrPair = *SuccIterPairBegin++;
1673 auto OtherSuccIterPairRange =
1680 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1682 return I1->isIdenticalToWhenDefined(I2);
1684 if (!AllDbgInstsAreIdentical) {
1685 while (isa<DbgInfoIntrinsic>(I1))
1686 I1 = &*++BB1ItrPair.first;
1687 for (
auto &SuccIter : OtherSuccIterRange) {
1689 while (isa<DbgInfoIntrinsic>(I2))
1694 bool AllInstsAreIdentical =
true;
1695 bool HasTerminator =
I1->isTerminator();
1696 for (
auto &SuccIter : OtherSuccIterRange) {
1701 AllInstsAreIdentical =
false;
1705 for (
auto &SuccIter : OtherSuccIterRange)
1710 if (HasTerminator) {
1714 if (NumSkipped || !AllInstsAreIdentical) {
1719 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1723 if (AllInstsAreIdentical) {
1724 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1725 AllInstsAreIdentical =
1727 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1729 unsigned SkipFlagsBB2 = Pair.second;
1739 if (AllInstsAreIdentical) {
1741 if (isa<DbgInfoIntrinsic>(I1)) {
1750 for (
auto &SuccIter : OtherSuccIterRange) {
1751 auto *I2 = &*SuccIter++;
1752 assert(isa<DbgInfoIntrinsic>(I2));
1764 for (
auto &SuccIter : OtherSuccIterRange) {
1778 NumHoistCommonCode += SuccIterPairs.
size();
1780 NumHoistCommonInstrs += SuccIterPairs.
size();
1789 for (
auto &SuccIterPair : SuccIterPairs) {
1798bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1802 auto *BI = dyn_cast<BranchInst>(TI);
1804 bool Changed =
false;
1809 auto *I2 = *OtherSuccTIs.
begin();
1825 if (isa<CallBrInst>(I1))
1830 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1832 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1852 if (!
NT->getType()->isVoidTy()) {
1853 I1->replaceAllUsesWith(NT);
1855 OtherSuccTI->replaceAllUsesWith(NT);
1859 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1865 for (
auto *OtherSuccTI : OtherSuccTIs)
1866 Locs.
push_back(OtherSuccTI->getDebugLoc());
1878 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1881 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1882 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1888 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1892 if (isa<FPMathOperator>(PN))
1901 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1902 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1903 PN.setIncomingValue(i, SI);
1914 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1919 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1923 DTU->applyUpdates(Updates);
1929 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1930 switch (
II->getIntrinsicID()) {
1933 case Intrinsic::lifetime_start:
1934 case Intrinsic::lifetime_end:
1945 return !isa<IntrinsicInst>(
I);
1958 std::optional<unsigned> NumUses;
1959 for (
auto *
I : Insts) {
1961 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1962 I->getType()->isTokenTy())
1967 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1974 if (
const auto *
C = dyn_cast<CallBase>(
I))
1975 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1979 NumUses =
I->getNumUses();
1980 else if (NumUses !=
I->getNumUses())
1986 for (
auto *
I : Insts) {
1987 if (!
I->isSameOperationAs(I0))
1993 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1995 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
2008 for (
const Use &U : I0->
uses()) {
2009 auto It = PHIOperands.find(&U);
2010 if (It == PHIOperands.end())
2013 if (!
equal(Insts, It->second))
2021 if (isa<CallBase>(I0)) {
2023 return cast<CallBase>(
I)->isIndirectCall();
2025 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2026 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2027 if (HaveIndirectCalls) {
2028 if (!AllCallsAreIndirect)
2032 Value *Callee =
nullptr;
2034 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2036 Callee = CurrCallee;
2037 else if (Callee != CurrCallee)
2043 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2045 if (
Op->getType()->isTokenTy())
2053 if (!
all_of(Insts, SameAsI0)) {
2059 if (isa<StoreInst>(I0) && OI == 1 &&
2061 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2064 if (isa<LoadInst>(I0) && OI == 0 &&
2066 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2071 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2080 for (
auto *
I : Insts)
2081 Ops.push_back(
I->getOperand(OI));
2091 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2096 for (
auto *BB :
Blocks) {
2099 I =
I->getPrevNode();
2100 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2101 if (!isa<DbgInfoIntrinsic>(
I))
2126 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2129 PN->insertBefore(BBEnd->begin());
2130 for (
auto *
I : Insts)
2131 PN->addIncoming(
I->getOperand(O),
I->getParent());
2140 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2143 for (
auto *
I : Insts)
2161 auto *PN = cast<PHINode>(U);
2162 PN->replaceAllUsesWith(I0);
2163 PN->eraseFromParent();
2167 for (
auto *
I : Insts) {
2172 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2173 I->replaceAllUsesWith(I0);
2174 I->eraseFromParent();
2188 class LockstepReverseIterator {
2201 for (
auto *BB : Blocks) {
2203 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2221 for (
auto *&Inst : Insts) {
2222 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2235 for (
auto *&Inst : Insts) {
2236 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2299 bool HaveNonUnconditionalPredecessors =
false;
2301 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2302 if (PredBr && PredBr->isUnconditional())
2305 HaveNonUnconditionalPredecessors =
true;
2307 if (UnconditionalPreds.
size() < 2)
2320 for (
const Use &U : PN.incoming_values())
2321 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2322 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2324 Ops.push_back(*IncomingVals[Pred]);
2329 LockstepReverseIterator LRI(UnconditionalPreds);
2330 while (LRI.isValid() &&
2332 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2334 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2345 if (!followedByDeoptOrUnreachable) {
2349 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2350 unsigned NumPHIInsts = 0;
2351 for (
Use &U : (*LRI)[0]->operands()) {
2352 auto It = PHIOperands.
find(&U);
2353 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2354 return InstructionsToSink.contains(V);
2362 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2363 return NumPHIInsts <= 1;
2380 while (
Idx < ScanIdx) {
2381 if (!ProfitableToSinkInstruction(LRI)) {
2384 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2387 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2397 if (
Idx < ScanIdx) {
2400 InstructionsToSink = InstructionsProfitableToSink;
2406 !ProfitableToSinkInstruction(LRI) &&
2407 "We already know that the last instruction is unprofitable to sink");
2415 for (
auto *
I : *LRI)
2416 InstructionsProfitableToSink.
erase(
I);
2417 if (!ProfitableToSinkInstruction(LRI)) {
2420 InstructionsToSink = InstructionsProfitableToSink;
2432 bool Changed =
false;
2434 if (HaveNonUnconditionalPredecessors) {
2435 if (!followedByDeoptOrUnreachable) {
2443 bool Profitable =
false;
2444 while (
Idx < ScanIdx) {
2478 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2480 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2488 NumSinkCommonInstrs++;
2492 ++NumSinkCommonCode;
2498struct CompatibleSets {
2516 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2521 return Sets.emplace_back();
2525 getCompatibleSet(
II).emplace_back(
II);
2529 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2533 return II->cannotMerge() ||
II->isInlineAsm();
2535 if (
any_of(Invokes, IsIllegalToMerge))
2540 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2541 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2542 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2543 if (HaveIndirectCalls) {
2544 if (!AllCallsAreIndirect)
2550 Value *CurrCallee =
II->getCalledOperand();
2551 assert(CurrCallee &&
"There is always a called operand.");
2554 else if (Callee != CurrCallee)
2562 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2564 if (
any_of(Invokes, HasNormalDest)) {
2567 if (!
all_of(Invokes, HasNormalDest))
2574 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2576 NormalBB = CurrNormalBB;
2577 else if (NormalBB != CurrNormalBB)
2585 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2596 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2598 UnwindBB = CurrUnwindBB;
2600 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2607 Invokes.front()->getUnwindDest(),
2608 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2614 for (
auto *
II : Invokes.drop_front())
2615 if (!
II->isSameOperationAs(II0))
2619 auto IsIllegalToMergeArguments = [](
auto Ops) {
2620 Use &U0 = std::get<0>(Ops);
2621 Use &U1 = std::get<1>(Ops);
2628 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2629 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2630 IsIllegalToMergeArguments))
2642 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2648 bool HasNormalDest =
2649 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2653 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2657 II0->
getParent()->getIterator()->getNextNode();
2662 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2664 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2666 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2668 if (!HasNormalDest) {
2672 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2679 return MergedInvoke;
2687 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2693 SuccBBOfMergedInvoke});
2700 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2703 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2706 for (
Use &U : MergedInvoke->operands()) {
2708 if (MergedInvoke->isCallee(&U)) {
2709 if (!IsIndirectCall)
2711 }
else if (!MergedInvoke->isDataOperand(&U))
2716 return II->getOperand(
U.getOperandNo()) !=
U.get();
2723 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2735 Invokes.front()->getParent());
2743 if (!MergedDebugLoc)
2744 MergedDebugLoc =
II->getDebugLoc();
2752 OrigSuccBB->removePredecessor(
II->getParent());
2754 II->replaceAllUsesWith(MergedInvoke);
2755 II->eraseFromParent();
2758 MergedInvoke->setDebugLoc(MergedDebugLoc);
2759 ++NumInvokeSetsFormed;
2762 DTU->applyUpdates(Updates);
2789 bool Changed =
false;
2795 CompatibleSets Grouper;
2801 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2805 if (Invokes.
size() < 2)
2817class EphemeralValueTracker {
2821 if (isa<AssumeInst>(
I))
2823 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2825 return EphValues.count(cast<Instruction>(U));
2831 if (isEphemeral(
I)) {
2870 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2882 unsigned MaxNumInstToLookAt = 9;
2886 if (!MaxNumInstToLookAt)
2888 --MaxNumInstToLookAt;
2891 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2894 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2898 if (SI->getPointerOperand() == StorePtr &&
2899 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2900 SI->getAlign() >= StoreToHoist->
getAlign())
2902 return SI->getValueOperand();
2906 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2907 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2908 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2931 unsigned &SpeculatedInstructions,
2939 bool HaveRewritablePHIs =
false;
2957 HaveRewritablePHIs =
true;
2960 if (!OrigCE && !ThenCE)
2967 if (OrigCost + ThenCost > MaxCost)
2974 ++SpeculatedInstructions;
2975 if (SpeculatedInstructions > 1)
2979 return HaveRewritablePHIs;
2986 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
2993 uint64_t EndWeight = Invert ? TWeight : FWeight;
2997 return BIEndProb < Likely;
3037bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3044 if (isa<FCmpInst>(BrCond))
3054 bool Invert =
false;
3073 unsigned SpeculatedInstructions = 0;
3074 Value *SpeculatedStoreValue =
nullptr;
3076 EphemeralValueTracker EphTracker;
3079 if (isa<DbgInfoIntrinsic>(
I)) {
3087 if (isa<PseudoProbeInst>(
I)) {
3097 if (EphTracker.track(&
I))
3102 ++SpeculatedInstructions;
3103 if (SpeculatedInstructions > 1)
3109 &
I, BB, ThenBB, EndBB))))
3111 if (!SpeculatedStoreValue &&
3117 if (SpeculatedStoreValue)
3118 SpeculatedStore = cast<StoreInst>(&
I);
3123 for (
Use &
Op :
I.operands()) {
3128 ++SinkCandidateUseCounts[OpI];
3135 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3137 ++SpeculatedInstructions;
3138 if (SpeculatedInstructions > 1)
3144 bool Convert = SpeculatedStore !=
nullptr;
3147 SpeculatedInstructions,
3149 if (!Convert ||
Cost > Budget)
3153 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3156 if (SpeculatedStoreValue) {
3160 Value *FalseV = SpeculatedStoreValue;
3164 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3193 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3195 DbgAssign->replaceVariableLocationOp(OrigV, S);
3208 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3210 if (!isa<DbgAssignIntrinsic>(&
I))
3213 I.dropUBImplyingAttrsAndMetadata();
3216 if (EphTracker.contains(&
I)) {
3218 I.eraseFromParent();
3232 It.dropOneDbgRecord(&DR);
3234 std::prev(ThenBB->
end()));
3251 Value *TrueV = ThenV, *FalseV = OrigV;
3265 if (!isa<DbgAssignIntrinsic>(
I))
3266 I->eraseFromParent();
3276 EphemeralValueTracker EphTracker;
3282 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3283 if (CI->cannotDuplicate() || CI->isConvergent())
3289 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3296 for (
User *U :
I.users()) {
3298 if (UI->
getParent() != BB || isa<PHINode>(UI))
3312 auto *
I = dyn_cast<Instruction>(V);
3313 if (
I &&
I->getParent() == To)
3317 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3329static std::optional<bool>
3345 if (
auto *CB = dyn_cast<ConstantInt>(U))
3350 KnownValues[CB].
insert(Pred);
3354 if (KnownValues.
empty())
3363 for (
const auto &Pair : KnownValues) {
3381 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3384 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3392 EdgeBB->setName(RealDest->
getName() +
".critedge");
3393 EdgeBB->moveBefore(RealDest);
3403 TranslateMap[
Cond] = CB;
3409 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3416 N->insertInto(EdgeBB, InsertPt);
3419 N->setName(BBI->getName() +
".c");
3422 for (
Use &
Op :
N->operands()) {
3424 if (PI != TranslateMap.
end())
3430 if (!BBI->use_empty())
3431 TranslateMap[&*BBI] = V;
3432 if (!
N->mayHaveSideEffects()) {
3433 N->eraseFromParent();
3438 if (!BBI->use_empty())
3439 TranslateMap[&*BBI] =
N;
3445 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3446 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3447 SrcDbgCursor = std::next(BBI);
3449 N->cloneDebugInfoFrom(&*BBI);
3452 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3458 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3459 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3460 InsertPt->cloneDebugInfoFrom(BI);
3463 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3469 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3470 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3481 return std::nullopt;
3491 std::optional<bool> Result;
3492 bool EverChanged =
false;
3496 EverChanged |= Result == std::nullopt || *Result;
3497 }
while (Result == std::nullopt);
3505 bool SpeculateUnpredictables) {
3520 if (isa<ConstantInt>(IfCond))
3527 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3530 "Will have either one or two blocks to speculate.");
3537 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3538 if (!IsUnpredictable) {
3541 (TWeight + FWeight) != 0) {
3546 if (IfBlocks.
size() == 1) {
3548 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3549 if (BIBBProb >= Likely)
3552 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3560 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3561 if (IfCondPhiInst->getParent() == BB)
3569 unsigned NumPhis = 0;
3581 if (SpeculateUnpredictables && IsUnpredictable)
3584 bool Changed =
false;
3603 PN = dyn_cast<PHINode>(BB->
begin());
3609 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3620 auto IsBinOpOrAnd = [](
Value *V) {
3640 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3653 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3655 <<
" F: " << IfFalse->
getName() <<
"\n");
3669 if (isa<FPMathOperator>(PN))
3689 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3707 if (Opc == Instruction::And)
3709 if (Opc == Instruction::Or)
3722 bool PredHasWeights =
3724 bool SuccHasWeights =
3726 if (PredHasWeights || SuccHasWeights) {
3727 if (!PredHasWeights)
3728 PredTrueWeight = PredFalseWeight = 1;
3729 if (!SuccHasWeights)
3730 SuccTrueWeight = SuccFalseWeight = 1;
3740static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3744 "Both blocks must end with a conditional branches.");
3746 "PredBB must be a predecessor of BB.");
3754 (PTWeight + PFWeight) != 0) {
3762 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3763 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3767 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3770 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3771 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3777 return std::nullopt;
3790 bool InvertPredCond;
3791 std::tie(CommonSucc, Opc, InvertPredCond) =
3794 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3801 {LLVMContext::MD_annotation});
3804 if (InvertPredCond) {
3817 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3819 SuccTrueWeight, SuccFalseWeight)) {
3826 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3832 (SuccFalseWeight + SuccTrueWeight) +
3833 PredTrueWeight * SuccFalseWeight);
3839 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3840 PredFalseWeight * SuccTrueWeight);
3842 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3860 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3861 {DominatorTree::Delete, PredBlock, BB}});
3888 ++NumFoldBranchToCommonDest;
3895 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3896 return U->getType()->isVectorTy();
3906 unsigned BonusInstThreshold) {
3920 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3921 !isa<SelectInst>(
Cond)) ||
3922 Cond->getParent() != BB || !
Cond->hasOneUse())
3932 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3943 bool InvertPredCond;
3945 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3977 unsigned NumBonusInsts = 0;
3978 bool SawVectorOp =
false;
3979 const unsigned PredCount = Preds.
size();
3985 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3996 NumBonusInsts += PredCount;
4004 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4005 auto *UI = cast<Instruction>(U.getUser());
4006 if (
auto *PN = dyn_cast<PHINode>(UI))
4008 return UI->
getParent() == BB &&
I.comesBefore(UI);
4012 if (!
all_of(
I.uses(), IsBCSSAUse))
4016 BonusInstThreshold *
4022 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4032 for (
auto *BB : {BB1, BB2}) {
4036 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4048 Value *AlternativeV =
nullptr) {
4066 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4067 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4068 PHI = cast<PHINode>(
I);
4074 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4075 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4083 if (!AlternativeV &&
4084 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4089 PHI->addIncoming(V, BB);
4099 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4108 if (!PStore || !QStore)
4129 if (
I.mayReadOrWriteMemory())
4131 for (
auto &
I : *QFB)
4132 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4135 for (
auto &
I : *QTB)
4136 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4140 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4156 if (
I.isTerminator())
4160 if (
auto *S = dyn_cast<StoreInst>(&
I))
4164 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4174 "When we run out of budget we will eagerly return from within the "
4175 "per-instruction loop.");
4179 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4181 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4182 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4290 bool InvertPCond =
false, InvertQCond =
false;
4296 if (QFB == PostBB) {
4315 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4318 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4326 for (
auto *BB : {PTB, PFB}) {
4331 PStoreAddresses.
insert(SI->getPointerOperand());
4333 for (
auto *BB : {QTB, QFB}) {
4338 QStoreAddresses.
insert(SI->getPointerOperand());
4344 auto &CommonAddresses = PStoreAddresses;
4346 bool Changed =
false;
4347 for (
auto *Address : CommonAddresses)
4350 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4368 !BI->
getParent()->getSinglePredecessor())
4370 if (!IfFalseBB->
phis().empty())
4380 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4391 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4392 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4403 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4404 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4483 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4485 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4489 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4492 if (CommonDestProb >= Likely)
4502 unsigned NumPhis = 0;
4524 if (OtherDest == BB) {
4531 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4532 OtherDest = InfLoopBlock;
4552 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4567 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4568 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4571 SuccTrueWeight, SuccFalseWeight);
4573 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4574 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4575 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4576 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4580 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4581 PredOther * SuccCommon,
4582 PredOther * SuccOther};
4611 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4612 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4613 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4614 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4617 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4618 PredOther * SuccCommon};
4641bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4652 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4659 if (Succ == KeepEdge1)
4660 KeepEdge1 =
nullptr;
4661 else if (Succ == KeepEdge2)
4662 KeepEdge2 =
nullptr;
4667 if (Succ != TrueBB && Succ != FalseBB)
4668 RemovedSuccessors.
insert(Succ);
4676 if (!KeepEdge1 && !KeepEdge2) {
4677 if (TrueBB == FalseBB) {
4685 if (TrueWeight != FalseWeight)
4688 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4710 for (
auto *RemovedSuccessor : RemovedSuccessors)
4711 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4712 DTU->applyUpdates(Updates);
4722bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4727 if (!TrueVal || !FalseVal)
4732 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4733 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4736 uint32_t TrueWeight = 0, FalseWeight = 0;
4741 if (Weights.
size() == 1 +
SI->getNumCases()) {
4743 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4745 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4750 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4759bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4772 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4793bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4813 if (
SI->getCondition() != V)
4819 if (
SI->getDefaultDest() != BB) {
4821 assert(VVal &&
"Should have a unique destination value");
4829 return requestResimplify();
4835 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4845 return requestResimplify();
4852 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4877 auto W0 = SIW.getSuccessorWeight(0);
4881 SIW.setSuccessorWeight(0, *NewW);
4883 SIW.addCase(Cst, NewBB, NewW);
4885 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4894 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4895 DTU->applyUpdates(Updates);
4903bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
4915 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4918 Value *CompVal = ConstantCompare.CompValue;
4919 unsigned UsedICmps = ConstantCompare.UsedICmps;
4920 Value *ExtraCase = ConstantCompare.Extra;
4939 if (ExtraCase && Values.
size() < 2)
4954 <<
" cases into SWITCH. BB is:\n"
4964 nullptr,
"switch.early.test");
4988 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4994 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4995 <<
"\nEXTRABB = " << *BB);
5003 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5010 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
5011 New->addCase(Values[i], EdgeBB);
5017 PHINode *PN = cast<PHINode>(BBI);
5019 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5026 DTU->applyUpdates(Updates);
5028 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5034 return simplifyCommonResume(RI);
5035 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHI()) &&
5038 return simplifySingleResume(RI);
5046 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5051 switch (IntrinsicID) {
5052 case Intrinsic::dbg_declare:
5053 case Intrinsic::dbg_value:
5054 case Intrinsic::dbg_label:
5055 case Intrinsic::lifetime_end:
5065bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5075 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5078 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5080 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5081 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5085 if (IncomingBB->getUniqueSuccessor() != BB)
5088 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5090 if (IncomingValue != LandingPad)
5094 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5095 TrivialUnwindBlocks.
insert(IncomingBB);
5099 if (TrivialUnwindBlocks.
empty())
5103 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5107 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5121 TrivialBB->getTerminator()->eraseFromParent();
5124 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5131 return !TrivialUnwindBlocks.empty();
5135bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5139 "Resume must unwind the exception that caused control to here");
5143 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5179 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5196 int Idx = DestPN.getBasicBlockIndex(BB);
5210 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5211 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5213 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5217 DestPN.addIncoming(
Incoming, Pred);
5244 std::vector<DominatorTree::UpdateType> Updates;
5248 if (UnwindDest ==
nullptr) {
5260 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5261 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5288 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5289 if (!SuccessorCleanupPad)
5298 SuccessorCleanupPad->eraseFromParent();
5327 bool Changed =
false;
5356 BBI->dropDbgRecords();
5360 BBI->eraseFromParent();
5366 if (&BB->
front() != UI)
5369 std::vector<DominatorTree::UpdateType> Updates;
5375 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5379 [BB](
auto *
Successor) { return Successor == BB; })) {
5387 "The destinations are guaranteed to be different here.");
5398 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5404 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5405 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5407 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5408 if (i->getCaseSuccessor() != BB) {
5413 i = SU.removeCase(i);
5418 if (DTU &&
SI->getDefaultDest() != BB)
5419 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5420 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5421 if (
II->getUnwindDest() == BB) {
5423 DTU->applyUpdates(Updates);
5427 if (!CI->doesNotThrow())
5428 CI->setDoesNotThrow();
5431 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5432 if (CSI->getUnwindDest() == BB) {
5434 DTU->applyUpdates(Updates);
5443 E = CSI->handler_end();
5446 CSI->removeHandler(
I);
5453 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5454 if (CSI->getNumHandlers() == 0) {
5455 if (CSI->hasUnwindDest()) {
5459 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5460 Updates.push_back({DominatorTree::Insert,
5461 PredecessorOfPredecessor,
5462 CSI->getUnwindDest()});
5463 Updates.push_back({DominatorTree::Delete,
5464 PredecessorOfPredecessor, Predecessor});
5467 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5471 DTU->applyUpdates(Updates);
5480 CSI->eraseFromParent();
5483 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5485 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5486 "Expected to always have an unwind to BB.");
5488 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5496 DTU->applyUpdates(Updates);
5511 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5512 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5520 bool RemoveOrigDefaultBlock =
true) {
5522 auto *BB = Switch->getParent();
5523 auto *OrigDefaultBlock = Switch->getDefaultDest();
5524 if (RemoveOrigDefaultBlock)
5525 OrigDefaultBlock->removePredecessor(BB);
5530 Switch->setDefaultDest(&*NewDefaultBlock);
5533 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5534 if (RemoveOrigDefaultBlock &&
5536 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5544bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5546 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5549 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5551 auto *BB =
SI->getParent();
5554 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5559 for (
auto Case :
SI->cases()) {
5563 if (Dest == DestA) {
5569 if (Dest == DestB) {
5579 "Single-destination switch should have been folded.");
5581 assert(DestB !=
SI->getDefaultDest());
5582 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5590 ContiguousCases = &CasesA;
5591 ContiguousDest = DestA;
5594 ContiguousCases = &CasesB;
5595 ContiguousDest = DestB;
5604 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5606 Value *Sub =
SI->getCondition();
5607 if (!
Offset->isNullValue())
5622 if (Weights.
size() == 1 +
SI->getNumCases()) {
5625 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5626 if (
SI->getSuccessor(
I) == ContiguousDest)
5627 TrueWeight += Weights[
I];
5629 FalseWeight += Weights[
I];
5631 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5640 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5641 unsigned PreviousEdges = ContiguousCases->
size();
5642 if (ContiguousDest ==
SI->getDefaultDest())
5644 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5645 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5647 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5648 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5649 if (OtherDest ==
SI->getDefaultDest())
5651 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5652 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5660 auto *UnreachableDefault =
SI->getDefaultDest();
5663 SI->eraseFromParent();
5665 if (!HasDefault && DTU)
5666 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5682 unsigned MaxSignificantBitsInCond =
5689 for (
const auto &Case : SI->cases()) {
5690 auto *
Successor = Case.getCaseSuccessor();
5696 const APInt &CaseVal = Case.getCaseValue()->getValue();
5699 DeadCases.
push_back(Case.getCaseValue());
5712 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5713 const unsigned NumUnknownBits =
5716 if (HasDefault && DeadCases.
empty() &&
5717 NumUnknownBits < 64 ) {
5718 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5719 if (SI->getNumCases() == AllNumCases) {
5726 if (SI->getNumCases() == AllNumCases - 1) {
5727 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5734 for (
const auto &Case : SI->cases())
5735 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5737 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5746 if (DeadCases.
empty())
5752 assert(CaseI != SI->case_default() &&
5753 "Case was not found. Probably mistake in DeadCases forming.");
5755 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5760 std::vector<DominatorTree::UpdateType> Updates;
5761 for (
auto *
Successor : UniqueSuccessors)
5762 if (NumPerSuccessorCases[
Successor] == 0)
5763 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5783 if (!Branch || !Branch->isUnconditional())
5789 int Idx =
PHI.getBasicBlockIndex(BB);
5790 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5793 if (InValue != CaseValue)
5809 ForwardingNodesMap ForwardingNodes;
5811 bool Changed =
false;
5812 for (
const auto &Case : SI->cases()) {
5814 BasicBlock *CaseDest = Case.getCaseSuccessor();
5833 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5834 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5835 count(Phi.blocks(), SwitchBlock) == 1) {
5836 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5844 ForwardingNodes[Phi].push_back(PhiIdx);
5847 for (
auto &ForwardingNode : ForwardingNodes) {
5848 PHINode *Phi = ForwardingNode.first;
5854 for (
int Index : Indexes)
5855 Phi->setIncomingValue(
Index, SI->getCondition());
5865 if (
C->isThreadDependent())
5867 if (
C->isDLLImportDependent())
5870 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5871 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5872 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5878 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5894 if (
Constant *
C = dyn_cast<Constant>(V))
5910 if (
A->isAllOnesValue())
5912 if (
A->isNullValue())
5918 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5943 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5945 if (
I.isTerminator()) {
5947 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5950 CaseDest =
I.getSuccessor(0);
5957 for (
auto &
Use :
I.uses()) {
5960 if (
I->getParent() == CaseDest)
5963 if (Phi->getIncomingBlock(
Use) == CaseDest)
5976 *CommonDest = CaseDest;
5978 if (CaseDest != *CommonDest)
5983 int Idx =
PHI.getBasicBlockIndex(Pred);
5996 Res.push_back(std::make_pair(&
PHI, ConstVal));
5999 return Res.size() > 0;
6005 SwitchCaseResultVectorTy &UniqueResults,
6007 for (
auto &
I : UniqueResults) {
6008 if (
I.first == Result) {
6009 I.second.push_back(CaseVal);
6010 return I.second.size();
6013 UniqueResults.push_back(
6024 SwitchCaseResultVectorTy &UniqueResults,
6028 uintptr_t MaxUniqueResults) {
6029 for (
const auto &
I : SI->cases()) {
6043 const size_t NumCasesForResult =
6051 if (UniqueResults.size() > MaxUniqueResults)
6062 BasicBlock *DefaultDest = SI->getDefaultDest();
6063 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6068 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6069 if ((!DefaultResult &&
6090 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6091 ResultVector[1].second.size() == 1) {
6092 ConstantInt *FirstCase = ResultVector[0].second[0];
6093 ConstantInt *SecondCase = ResultVector[1].second[0];
6094 Value *SelectValue = ResultVector[1].first;
6095 if (DefaultResult) {
6096 Value *ValueCompare =
6097 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6098 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6099 DefaultResult,
"switch.select");
6101 Value *ValueCompare =
6102 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6103 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6104 SelectValue,
"switch.select");
6108 if (ResultVector.size() == 1 && DefaultResult) {
6110 unsigned CaseCount = CaseValues.
size();
6118 for (
auto *Case : CaseValues)
6119 if (Case->getValue().slt(MinCaseVal->
getValue()))
6124 for (
auto *Case : CaseValues)
6125 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6131 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6135 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6140 if (CaseValues.
size() == 2) {
6142 "switch.selectcmp.case1");
6144 "switch.selectcmp.case2");
6145 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6146 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6159 std::vector<DominatorTree::UpdateType> Updates;
6165 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6170 PHI->removeIncomingValueIf(
6171 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6172 PHI->addIncoming(SelectValue, SelectBB);
6175 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6181 if (DTU && RemovedSuccessors.
insert(Succ).second)
6182 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6184 SI->eraseFromParent();
6199 SwitchCaseResultVectorTy UniqueResults;
6205 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6207 Value *SelectValue =
6219class SwitchLookupTable {
6270 bool LinearMapValWrapped =
false;
6278SwitchLookupTable::SwitchLookupTable(
6282 assert(Values.
size() &&
"Can't build lookup table without values!");
6283 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6286 SingleValue = Values.
begin()->second;
6292 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6298 TableContents[
Idx] = CaseRes;
6300 if (CaseRes != SingleValue)
6301 SingleValue =
nullptr;
6305 if (Values.
size() < TableSize) {
6307 "Need a default value to fill the lookup table holes.");
6310 if (!TableContents[
I])
6311 TableContents[
I] = DefaultValue;
6314 if (DefaultValue != SingleValue)
6315 SingleValue =
nullptr;
6321 Kind = SingleValueKind;
6328 bool LinearMappingPossible =
true;
6333 bool NonMonotonic =
false;
6334 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6337 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6341 LinearMappingPossible =
false;
6346 APInt Dist = Val - PrevVal;
6349 }
else if (Dist != DistToPrev) {
6350 LinearMappingPossible =
false;
6358 if (LinearMappingPossible) {
6359 LinearOffset = cast<ConstantInt>(TableContents[0]);
6360 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6361 bool MayWrap =
false;
6362 APInt M = LinearMultiplier->getValue();
6363 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6364 LinearMapValWrapped = NonMonotonic || MayWrap;
6365 Kind = LinearMapKind;
6372 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6374 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6376 TableInt <<=
IT->getBitWidth();
6378 if (!isa<UndefValue>(TableContents[
I - 1])) {
6379 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6380 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6383 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6384 BitMapElementTy =
IT;
6395 GlobalVariable::PrivateLinkage, Initializer,
6396 "switch.table." + FuncName);
6397 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6406 case SingleValueKind:
6408 case LinearMapKind: {
6411 false,
"switch.idx.cast");
6412 if (!LinearMultiplier->isOne())
6413 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6415 !LinearMapValWrapped);
6417 if (!LinearOffset->isZero())
6420 !LinearMapValWrapped);
6436 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6437 "switch.shiftamt",
true,
true);
6440 Value *DownShifted =
6441 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6443 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6449 Array->getInitializer()->getType()->getArrayNumElements();
6450 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6453 "switch.tableidx.zext");
6457 GEPIndices,
"switch.gep");
6459 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6466bool SwitchLookupTable::wouldFitInRegister(
const DataLayout &
DL,
6468 Type *ElementType) {
6469 auto *
IT = dyn_cast<IntegerType>(ElementType);
6476 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6478 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6487 auto *
IT = dyn_cast<IntegerType>(Ty);
6499 DL.fitsInLegalInteger(
IT->getBitWidth());
6511 return NumCases * 100 >= CaseRange * MinDensity;
6532 if (SI->getNumCases() > TableSize)
6535 bool AllTablesFitInRegister =
true;
6536 bool HasIllegalType =
false;
6537 for (
const auto &
I : ResultTypes) {
6538 Type *Ty =
I.second;
6544 AllTablesFitInRegister =
6545 AllTablesFitInRegister &&
6546 SwitchLookupTable::wouldFitInRegister(
DL, TableSize, Ty);
6551 if (HasIllegalType && !AllTablesFitInRegister)
6556 if (AllTablesFitInRegister)
6573 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6576 return all_of(ResultTypes, [&](
const auto &KV) {
6577 return SwitchLookupTable::wouldFitInRegister(
6606 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6628 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6633 for (
auto ValuePair : Values) {
6636 if (!CaseConst || CaseConst == DefaultConst ||
6637 (CaseConst != TrueConst && CaseConst != FalseConst))
6651 if (DefaultConst == FalseConst) {
6654 ++NumTableCmpReuses;
6657 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6658 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6661 ++NumTableCmpReuses;
6671 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6690 if (SI->getNumCases() < 3)
6695 assert(!SI->cases().empty());
6712 MinCaseVal = CaseVal;
6714 MaxCaseVal = CaseVal;
6719 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6729 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6735 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6743 bool HasDefaultResults =
6745 DefaultResultsList,
DL,
TTI);
6747 for (
const auto &
I : DefaultResultsList) {
6750 DefaultResults[
PHI] = Result;
6754 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6756 if (UseSwitchConditionAsTableIndex)
6765 bool DefaultIsReachable = !SI->defaultDestUndefined();
6767 bool TableHasHoles = (NumResults < TableSize);
6772 bool AllHolesAreUndefined = TableHasHoles && !HasDefaultResults;
6780 bool NeedMask = AllHolesAreUndefined && DefaultIsReachable;
6783 if (SI->getNumCases() < 4)
6785 if (!
DL.fitsInLegalInteger(TableSize))
6792 std::vector<DominatorTree::UpdateType> Updates;
6798 assert(MaxTableSize >= TableSize &&
6799 "It is impossible for a switch to have more entries than the max "
6800 "representable value of its input integer type's size.");
6805 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
6811 if (UseSwitchConditionAsTableIndex) {
6812 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6813 TableIndex = SI->getCondition();
6815 TableIndexOffset = MinCaseVal;
6818 bool MayWrap =
true;
6819 if (!DefaultIsReachable) {
6824 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6825 "switch.tableidx",
false,
6834 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6842 return SwitchLookupTable::wouldFitInRegister(
6843 DL, UpperBound, KV.second );
6847 TableSize = std::max(UpperBound, TableSize);
6850 DefaultIsReachable =
false;
6854 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6855 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6858 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6863 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6865 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6867 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6877 MaskBB->
setName(
"switch.hole_check");
6884 APInt MaskInt(TableSizePowOf2, 0);
6885 APInt One(TableSizePowOf2, 1);
6887 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6888 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6891 MaskInt |= One <<
Idx;
6893 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
6901 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6904 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6906 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6907 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6913 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6916 SI->getDefaultDest()->removePredecessor(BB,
6919 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6923 const ResultListTy &ResultList = ResultLists[
PHI];
6927 AllHolesAreUndefined ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6929 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6932 Value *Result = Table.buildLookup(TableIndex, Builder);
6936 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6939 for (
auto *
User :
PHI->users()) {
6944 PHI->addIncoming(Result, LookupBB);
6949 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6953 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6956 if (Succ == SI->getDefaultDest())
6959 if (DTU && RemovedSuccessors.
insert(Succ).second)
6960 Updates.push_back({DominatorTree::Delete, BB, Succ});
6962 SI->eraseFromParent();
6969 ++NumLookupTablesHoles;
6984 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6985 if (CondTy->getIntegerBitWidth() > 64 ||
6986 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6990 if (SI->getNumCases() < 4)
6998 for (
const auto &
C : SI->cases())
6999 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7007 int64_t
Base = Values[0];
7008 for (
auto &V : Values)
7021 unsigned Shift = 64;
7022 for (
auto &V : Values)
7026 for (
auto &V : Values)
7027 V = (int64_t)((
uint64_t)V >> Shift);
7043 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7046 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7048 Ty, Intrinsic::fshl,
7049 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7050 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7052 for (
auto Case : SI->cases()) {
7053 auto *Orig = Case.getCaseValue();
7054 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
7055 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7071 Value *Condition = SI->getCondition();
7073 auto *CondTy = cast<IntegerType>(Condition->
getType());
7075 if (CondTy->getIntegerBitWidth() > 64 ||
7076 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7090 if (SI->getNumCases() < 4)
7096 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7101 for (
const auto &Case : SI->cases()) {
7102 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7119 for (
auto &Case : SI->cases()) {
7120 auto *OrigValue = Case.getCaseValue();
7121 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7122 OrigValue->getValue().countr_zero()));
7129 SI->setCondition(ConditionTrailingZeros);
7137 if (isValueEqualityComparison(SI)) {
7141 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7142 return requestResimplify();
7146 if (simplifySwitchOnSelect(SI,
Select))
7147 return requestResimplify();
7152 if (foldValueComparisonIntoPredecessors(SI, Builder))
7153 return requestResimplify();
7159 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7160 return requestResimplify();
7164 return requestResimplify();
7167 return requestResimplify();
7170 return requestResimplify();
7177 if (
Options.ConvertSwitchToLookupTable &&
7179 return requestResimplify();
7182 return requestResimplify();
7185 return requestResimplify();
7188 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7189 return requestResimplify();
7196 bool Changed =
false;
7205 RemovedSuccs.
insert(Dest);
7215 std::vector<DominatorTree::UpdateType> Updates;
7216 Updates.reserve(RemovedSuccs.
size());
7217 for (
auto *RemovedSucc : RemovedSuccs)
7218 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7219 DTU->applyUpdates(Updates);
7237 if (simplifyIndirectBrOnSelect(IBI, SI))
7238 return requestResimplify();
7270 if (isa<PHINode>(*Succ->
begin()))
7274 if (BB == OtherPred)
7280 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7286 std::vector<DominatorTree::UpdateType> Updates;
7293 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7294 "unexpected successor");
7295 II->setUnwindDest(OtherPred);
7297 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7298 Updates.push_back({DominatorTree::Delete, Pred, BB});
7305 if (isa<DbgInfoIntrinsic>(Inst))
7312 Updates.push_back({DominatorTree::Delete, BB, Succ});
7326 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7327 : simplifyCondBranch(
Branch, Builder);
7330bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7342 bool NeedCanonicalLoop =
7353 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7355 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7357 if (
I->isTerminator() &&
7358 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7365 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7375 if (
Options.SpeculateBlocks &&
7378 return requestResimplify();
7386 if (!PPred || (PredPred && PredPred != PPred))
7423 if (!SuccBI || !SuccBI->isConditional())
7427 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7428 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7431 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7450 Updates.
push_back({DominatorTree::Delete, BB, BB1});
7451 Updates.
push_back({DominatorTree::Insert, BB, BB4});
7452 Updates.
push_back({DominatorTree::Delete, BB, BB2});
7453 Updates.
push_back({DominatorTree::Insert, BB, BB3});
7457 bool HasWeight =
false;
7462 BBTWeight = BBFWeight = 1;
7467 BB1TWeight = BB1FWeight = 1;
7472 BB2TWeight = BB2FWeight = 1;
7474 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
7475 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
7486 "Tautological conditional branch should have been eliminated already.");
7489 if (!
Options.SimplifyCondBranch ||
7494 if (isValueEqualityComparison(BI)) {
7499 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7500 return requestResimplify();
7506 if (foldValueComparisonIntoPredecessors(BI, Builder))
7507 return requestResimplify();
7510 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
7511 return requestResimplify();
7516 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
7529 return requestResimplify();
7535 if (
Options.SpeculateBlocks &&
7538 return requestResimplify();
7548 return requestResimplify();
7556 return requestResimplify();
7565 return requestResimplify();
7572 return requestResimplify();
7577 if (PBI != BI && PBI->isConditional())
7579 return requestResimplify();
7584 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7585 if (PBI != BI && PBI->isConditional())
7587 return requestResimplify();
7591 return requestResimplify();
7605 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7609 auto *Use = cast<Instruction>(U);
7611 switch (Use->getOpcode()) {
7614 case Instruction::GetElementPtr:
7615 case Instruction::Ret:
7616 case Instruction::BitCast:
7617 case Instruction::Load:
7618 case Instruction::Store:
7619 case Instruction::Call:
7620 case Instruction::CallBr:
7621 case Instruction::Invoke:
7625 if (FindUse ==
I->user_end())
7627 auto *
Use = cast<Instruction>(*FindUse);
7631 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7645 if (
GEP->getPointerOperand() ==
I) {
7652 if (!
GEP->hasAllZeroIndices() &&
7653 (!
GEP->isInBounds() ||
7655 GEP->getPointerAddressSpace())))
7656 PtrValueMayBeModified =
true;
7662 bool HasNoUndefAttr =
7663 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7665 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7668 if (
C->isNullValue() && HasNoUndefAttr &&
7669 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7670 return !PtrValueMayBeModified;
7676 if (!LI->isVolatile())
7678 LI->getPointerAddressSpace());
7682 if (!SI->isVolatile())
7684 SI->getPointerAddressSpace())) &&
7685 SI->getPointerOperand() ==
I;
7688 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
7690 if (
I == Assume->getArgOperand(0))
7694 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7698 if (CB->getCalledOperand() ==
I)
7701 if (
C->isNullValue()) {
7704 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7705 if (CB->isPassingUndefUB(ArgIdx) &&
7706 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7708 return !PtrValueMayBeModified;
7711 }
else if (isa<UndefValue>(
C)) {
7715 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7716 if (CB->isPassingUndefUB(ArgIdx)) {
7733 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7760 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7762 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7770 for (
const auto &Case : SI->cases())
7771 if (Case.getCaseSuccessor() == BB) {
7773 Case.setSuccessor(Unreachable);
7775 if (SI->getDefaultDest() == BB) {
7777 SI->setDefaultDest(Unreachable);
7782 { { DominatorTree::Insert, Predecessor, Unreachable },
7783 { DominatorTree::Delete, Predecessor, BB } });
7791bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7792 bool Changed =
false;
7816 return requestResimplify();
7837 if (
Options.SpeculateBlocks &&
7841 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7844 Options.SpeculateUnpredictables))
7851 case Instruction::Br:
7852 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7854 case Instruction::Resume:
7855 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7857 case Instruction::CleanupRet:
7858 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7860 case Instruction::Switch:
7861 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7863 case Instruction::Unreachable:
7864 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7866 case Instruction::IndirectBr:
7867 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7875 bool Changed =
false;
7883 Changed |= simplifyOnce(BB);
7884 }
while (Resimplify);
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
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 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 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 StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
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 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 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 bool isProfitableToSpeculate(const BranchInst *BI, bool Invert, const TargetTransformInfo &TTI)
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 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 void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
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 bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
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 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
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 Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
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 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 > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
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 forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
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 void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights, bool IsExpected)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool 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 mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
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.
@ 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 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 trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static void fitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool casesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
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 Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static 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 bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static unsigned skippedInstrFlags(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 bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
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 void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
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 size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
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 bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool isLifeTimeMarker(const Instruction *I)
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static 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 bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
bool hasPostDomTree() const
Returns true if it holds a PostDomTreeT.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
pred_iterator pred_end(BasicBlock *BB)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
auto unique(Range &&R, Predicate P)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
pred_iterator pred_begin(BasicBlock *BB)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It)
Advance It while it points to a debug instruction and return the result.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
constexpr unsigned BitWidth
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool 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 pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
unsigned succ_size(const MachineBasicBlock *BB)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
A MapVector that performs no allocations if smaller than a certain size.