91using namespace PatternMatch;
93#define DEBUG_TYPE "simplifycfg"
96 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
98 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
99 "into preserving DomTree,"));
108 "Control the amount of phi node folding to perform (default = 2)"));
112 cl::desc(
"Control the maximal total instruction cost that we are willing "
113 "to speculatively execute to fold a 2-entry PHI node into a "
114 "select (default = 4)"));
118 cl::desc(
"Hoist common instructions up to the parent block"));
123 cl::desc(
"Allow reordering across at most this many "
124 "instructions when hoisting"));
128 cl::desc(
"Sink common instructions down to the end block"));
132 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
136 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
137 "precede - hoist multiple conditional stores into a single "
138 "predicated store"));
142 cl::desc(
"When merging conditional stores, do so even if the resultant "
143 "basic blocks are unlikely to be if-converted as a result"));
147 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
152 cl::desc(
"Limit maximum recursion depth when calculating costs of "
153 "speculatively executed instructions"));
158 cl::desc(
"Max size of a block which is still considered "
159 "small enough to thread through"));
165 cl::desc(
"Maximum cost of combining conditions when "
166 "folding branches"));
169 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
171 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
172 "to fold branch to common destination when vector operations are "
177 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
181 cl::desc(
"Limit cases to analyze when converting a switch to select"));
183STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
185 "Number of switch instructions turned into linear mapping");
187 "Number of switch instructions turned into lookup tables");
189 NumLookupTablesHoles,
190 "Number of switch instructions turned into lookup tables (holes checked)");
191STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
193 "Number of value comparisons folded into predecessor basic blocks");
195 "Number of branches folded into predecessor basic block");
198 "Number of common instruction 'blocks' hoisted up to the begin block");
200 "Number of common instructions hoisted up to the begin block");
202 "Number of common instruction 'blocks' sunk down to the end block");
204 "Number of common instructions sunk down to the end block");
205STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
207 "Number of invokes with empty resume blocks simplified into calls");
208STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
209STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
216using SwitchCaseResultVectorTy =
225struct ValueEqualityComparisonCase {
232 bool operator<(ValueEqualityComparisonCase RHS)
const {
240class SimplifyCFGOpt {
250 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
251 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
254 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
257 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
271 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
274 bool hoistCommonCodeFromSuccessors(
BasicBlock *BB,
bool EqTermsOnly);
275 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
294 "SimplifyCFG is not yet capable of maintaining validity of a "
295 "PostDomTree, so don't ask for it.");
302 bool requestResimplify() {
321 "Only for a pair of incoming blocks at the time!");
327 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
328 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
331 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
332 EquivalenceSet->contains(IV1))
355 if (!SI1Succs.
count(Succ))
361 FailBlocks->insert(Succ);
377 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
379 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
380 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
389 assert((!isa<Instruction>(
I) ||
391 "Instruction is not safe to speculatively execute!");
417 unsigned Depth = 0) {
446 if (AggressiveInsts.
count(
I))
470 for (
Use &
Op :
I->operands())
484 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
485 DL.isNonIntegralPointerType(V->getType()))
490 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
493 if (isa<ConstantPointerNull>(V))
494 return ConstantInt::get(PtrTy, 0);
498 if (CE->getOpcode() == Instruction::IntToPtr)
499 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
504 return cast<ConstantInt>(
522struct ConstantComparesGatherer {
526 Value *CompValue =
nullptr;
529 Value *Extra =
nullptr;
535 unsigned UsedICmps = 0;
542 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
543 ConstantComparesGatherer &
544 operator=(
const ConstantComparesGatherer &) =
delete;
549 bool setValueOnce(
Value *NewVal) {
550 if (CompValue && CompValue != NewVal)
553 return (CompValue !=
nullptr);
567 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
578 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
622 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
624 if (!setValueOnce(RHSVal))
629 ConstantInt::get(
C->getContext(),
630 C->getValue() | Mask));
645 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
647 if (!setValueOnce(RHSVal))
651 Vals.
push_back(ConstantInt::get(
C->getContext(),
652 C->getValue() & ~Mask));
673 Value *CandidateVal =
I->getOperand(0);
676 CandidateVal = RHSVal;
691 if (!setValueOnce(CandidateVal))
696 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
707 void gather(
Value *V) {
718 while (!DFT.
empty()) {
726 if (Visited.
insert(Op1).second)
728 if (Visited.
insert(Op0).second)
735 if (matchInstruction(
I, isEQ))
759 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
760 Cond = dyn_cast<Instruction>(SI->getCondition());
761 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
762 if (BI->isConditional())
763 Cond = dyn_cast<Instruction>(BI->getCondition());
765 Cond = dyn_cast<Instruction>(IBI->getAddress());
777 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
780 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
781 CV =
SI->getCondition();
782 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
783 if (BI->isConditional() && BI->getCondition()->hasOneUse())
784 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
792 Value *
Ptr = PTII->getPointerOperand();
793 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
802BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
803 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
804 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
805 Cases.reserve(
SI->getNumCases());
806 for (
auto Case :
SI->cases())
807 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
808 Case.getCaseSuccessor()));
809 return SI->getDefaultDest();
815 Cases.push_back(ValueEqualityComparisonCase(
824 std::vector<ValueEqualityComparisonCase> &Cases) {
830 std::vector<ValueEqualityComparisonCase> &C2) {
831 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
834 if (V1->size() > V2->size())
839 if (V1->size() == 1) {
842 for (
const ValueEqualityComparisonCase &VECC : *V2)
843 if (TheVal == VECC.
Value)
850 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
851 while (i1 != e1 && i2 != e2) {
870 SI->setMetadata(LLVMContext::MD_prof,
N);
877 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
881 if (TrueWeight || FalseWeight)
884 I->setMetadata(LLVMContext::MD_prof,
N);
892bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
898 Value *ThisVal = isValueEqualityComparison(TI);
899 assert(ThisVal &&
"This isn't a value comparison!!");
900 if (ThisVal != PredVal)
907 std::vector<ValueEqualityComparisonCase> PredCases;
909 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
913 std::vector<ValueEqualityComparisonCase> ThisCases;
914 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
926 if (isa<BranchInst>(TI)) {
929 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
935 ThisCases[0].Dest->removePredecessor(PredDef);
938 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
945 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
953 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
957 <<
"Through successor TI: " << *TI);
965 if (DeadCases.
count(i->getCaseValue())) {
974 std::vector<DominatorTree::UpdateType> Updates;
975 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
977 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
978 DTU->applyUpdates(Updates);
989 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
990 if (PredCases[i].Dest == TIBB) {
993 TIV = PredCases[i].
Value;
995 assert(TIV &&
"No edge from pred to succ?");
1000 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1001 if (ThisCases[i].
Value == TIV) {
1002 TheRealDest = ThisCases[i].Dest;
1008 TheRealDest = ThisDef;
1015 if (Succ != CheckEdge) {
1016 if (Succ != TheRealDest)
1017 RemovedSuccs.
insert(Succ);
1020 CheckEdge =
nullptr;
1027 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1034 for (
auto *RemovedSucc : RemovedSuccs)
1035 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1036 DTU->applyUpdates(Updates);
1046struct ConstantIntOrdering {
1048 return LHS->getValue().ult(
RHS->getValue());
1060 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1069 assert(MD &&
"Invalid branch-weight metadata");
1075 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1086 if (Max > UINT_MAX) {
1101 if (BonusInst.isTerminator())
1106 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1131 if (isa<DbgInfoIntrinsic>(BonusInst))
1134 NewBonusInst->
takeName(&BonusInst);
1135 BonusInst.setName(NewBonusInst->
getName() +
".old");
1136 VMap[&BonusInst] = NewBonusInst;
1142 auto *UI = cast<Instruction>(U.getUser());
1143 auto *PN = dyn_cast<PHINode>(UI);
1145 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1146 "If the user is not a PHI node, then it should be in the same "
1147 "block as, and come after, the original bonus instruction.");
1151 if (PN->getIncomingBlock(U) == BB)
1155 assert(PN->getIncomingBlock(U) == PredBlock &&
1156 "Not in block-closed SSA form?");
1157 U.set(NewBonusInst);
1162bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1170 std::vector<ValueEqualityComparisonCase> BBCases;
1171 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1173 std::vector<ValueEqualityComparisonCase> PredCases;
1174 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1186 if (PredHasWeights) {
1189 if (Weights.
size() != 1 + PredCases.size())
1190 PredHasWeights = SuccHasWeights =
false;
1191 }
else if (SuccHasWeights)
1195 Weights.
assign(1 + PredCases.size(), 1);
1198 if (SuccHasWeights) {
1201 if (SuccWeights.
size() != 1 + BBCases.size())
1202 PredHasWeights = SuccHasWeights =
false;
1203 }
else if (PredHasWeights)
1204 SuccWeights.
assign(1 + BBCases.size(), 1);
1206 if (PredDefault == BB) {
1209 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1210 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1211 if (PredCases[i].Dest != BB)
1212 PTIHandled.insert(PredCases[i].
Value);
1215 std::swap(PredCases[i], PredCases.back());
1217 if (PredHasWeights || SuccHasWeights) {
1219 Weights[0] += Weights[i + 1];
1224 PredCases.pop_back();
1230 if (PredDefault != BBDefault) {
1232 if (DTU && PredDefault != BB)
1233 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1234 PredDefault = BBDefault;
1235 ++NewSuccessors[BBDefault];
1238 unsigned CasesFromPred = Weights.
size();
1240 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1241 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1242 PredCases.push_back(BBCases[i]);
1243 ++NewSuccessors[BBCases[i].Dest];
1244 if (SuccHasWeights || PredHasWeights) {
1248 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1249 ValidTotalSuccWeight += SuccWeights[i + 1];
1253 if (SuccHasWeights || PredHasWeights) {
1254 ValidTotalSuccWeight += SuccWeights[0];
1256 for (
unsigned i = 1; i < CasesFromPred; ++i)
1257 Weights[i] *= ValidTotalSuccWeight;
1259 Weights[0] *= SuccWeights[0];
1265 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1266 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1267 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1268 if (PredCases[i].Dest == BB) {
1271 if (PredHasWeights || SuccHasWeights) {
1272 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1277 std::swap(PredCases[i], PredCases.back());
1278 PredCases.pop_back();
1285 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1286 if (PTIHandled.count(BBCases[i].Value)) {
1288 if (PredHasWeights || SuccHasWeights)
1290 PredCases.push_back(BBCases[i]);
1291 ++NewSuccessors[BBCases[i].Dest];
1298 if (PredHasWeights || SuccHasWeights)
1300 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1301 ++NewSuccessors[BBDefault];
1313 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1315 for (
auto I :
seq(NewSuccessor.second)) {
1319 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1320 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1333 for (ValueEqualityComparisonCase &V : PredCases)
1336 if (PredHasWeights || SuccHasWeights) {
1353 if (!InfLoopBlock) {
1361 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1368 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1370 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1372 DTU->applyUpdates(Updates);
1375 ++NumFoldValueComparisonIntoPredecessors;
1383bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1386 Value *CV = isValueEqualityComparison(TI);
1387 assert(CV &&
"Not a comparison?");
1389 bool Changed =
false;
1392 while (!Preds.empty()) {
1401 Value *PCV = isValueEqualityComparison(PTI);
1407 for (
auto *Succ : FailBlocks) {
1413 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1427 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1428 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1429 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1448 if (
I->mayReadFromMemory())
1452 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1469 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1479 if (
auto *CB = dyn_cast<CallBase>(
I))
1480 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1487 if (
auto *J = dyn_cast<Instruction>(
Op))
1488 if (J->getParent() == BB)
1507 auto *C1 = dyn_cast<CallInst>(I1);
1508 auto *C2 = dyn_cast<CallInst>(I2);
1510 if (C1->isMustTailCall() != C2->isMustTailCall())
1518 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1519 if (CB1->cannotMerge() || CB1->isConvergent())
1521 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1522 if (CB2->cannotMerge() || CB2->isConvergent())
1537 if (!I1->hasDbgRecords())
1539 using CurrentAndEndIt =
1540 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1546 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1547 return Pair.first == Pair.second;
1553 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1559 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1561 if (!
Other->hasDbgRecords())
1564 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1571 while (
none_of(Itrs, atEnd)) {
1572 bool HoistDVRs = allIdentical(Itrs);
1573 for (CurrentAndEndIt &Pair : Itrs) {
1590bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1612 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1616 if (isa<PHINode>(*SuccItr))
1618 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1627 if (!INonDbg->isTerminator())
1637 unsigned NumSkipped = 0;
1640 if (SuccIterPairs.
size() > 2) {
1642 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1643 if (SuccIterPairs.
size() < 2)
1647 bool Changed =
false;
1650 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1651 auto &BB1ItrPair = *SuccIterPairBegin++;
1652 auto OtherSuccIterPairRange =
1659 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1661 return I1->isIdenticalToWhenDefined(I2);
1663 if (!AllDbgInstsAreIdentical) {
1664 while (isa<DbgInfoIntrinsic>(I1))
1665 I1 = &*++BB1ItrPair.first;
1666 for (
auto &SuccIter : OtherSuccIterRange) {
1668 while (isa<DbgInfoIntrinsic>(I2))
1673 bool AllInstsAreIdentical =
true;
1674 bool HasTerminator =
I1->isTerminator();
1675 for (
auto &SuccIter : OtherSuccIterRange) {
1678 if (AllInstsAreIdentical && (!
I1->isIdenticalToWhenDefined(I2) ||
1680 AllInstsAreIdentical =
false;
1684 for (
auto &SuccIter : OtherSuccIterRange)
1689 if (HasTerminator) {
1693 if (NumSkipped || !AllInstsAreIdentical) {
1698 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1702 if (AllInstsAreIdentical) {
1703 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1704 AllInstsAreIdentical =
1706 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1708 unsigned SkipFlagsBB2 = Pair.second;
1718 if (AllInstsAreIdentical) {
1720 if (isa<DbgInfoIntrinsic>(I1)) {
1729 for (
auto &SuccIter : OtherSuccIterRange) {
1730 auto *I2 = &*SuccIter++;
1731 assert(isa<DbgInfoIntrinsic>(I2));
1743 for (
auto &SuccIter : OtherSuccIterRange) {
1757 NumHoistCommonCode += SuccIterPairs.
size();
1759 NumHoistCommonInstrs += SuccIterPairs.
size();
1768 for (
auto &SuccIterPair : SuccIterPairs) {
1777bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1781 auto *BI = dyn_cast<BranchInst>(TI);
1783 bool Changed =
false;
1788 auto *I2 = *OtherSuccTIs.
begin();
1804 if (isa<CallBrInst>(I1))
1809 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1811 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1831 if (!
NT->getType()->isVoidTy()) {
1832 I1->replaceAllUsesWith(NT);
1834 OtherSuccTI->replaceAllUsesWith(NT);
1838 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1844 for (
auto *OtherSuccTI : OtherSuccTIs)
1845 Locs.
push_back(OtherSuccTI->getDebugLoc());
1857 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1860 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1861 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1867 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1871 if (isa<FPMathOperator>(PN))
1880 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1881 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1882 PN.setIncomingValue(i, SI);
1893 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1898 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1902 DTU->applyUpdates(Updates);
1908 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1909 switch (II->getIntrinsicID()) {
1912 case Intrinsic::lifetime_start:
1913 case Intrinsic::lifetime_end:
1924 return !isa<IntrinsicInst>(
I);
1938 bool HasUse = !Insts.
front()->user_empty();
1939 for (
auto *
I : Insts) {
1941 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1942 I->getType()->isTokenTy())
1947 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1954 if (
const auto *
C = dyn_cast<CallBase>(
I))
1955 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1959 if (HasUse && !
I->hasOneUse())
1961 if (!HasUse && !
I->user_empty())
1967 for (
auto *
I : Insts) {
1968 if (!
I->isSameOperationAs(I0))
1974 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1976 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1990 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1993 auto *U = cast<Instruction>(*
I->user_begin());
1995 PNUse->getParent() == Succ &&
1996 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1997 U->getParent() ==
I->getParent();
2012 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2016 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2020 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2028 if (isa<CallBase>(I0)) {
2030 return cast<CallBase>(
I)->isIndirectCall();
2032 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2033 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2034 if (HaveIndirectCalls) {
2035 if (!AllCallsAreIndirect)
2039 Value *Callee =
nullptr;
2041 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2043 Callee = CurrCallee;
2044 else if (Callee != CurrCallee)
2050 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2052 if (
Op->getType()->isTokenTy())
2060 if (!
all_of(Insts, SameAsI0)) {
2065 for (
auto *
I : Insts)
2066 PHIOperands[
I].push_back(
I->getOperand(OI));
2076 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2081 for (
auto *BB :
Blocks) {
2084 I =
I->getPrevNode();
2085 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2086 if (!isa<DbgInfoIntrinsic>(
I))
2096 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2098 auto *U = cast<Instruction>(*
I->user_begin());
2124 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2127 PN->insertBefore(BBEnd->begin());
2128 for (
auto *
I : Insts)
2129 PN->addIncoming(
I->getOperand(O),
I->getParent());
2138 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2141 for (
auto *
I : Insts)
2160 PN->replaceAllUsesWith(I0);
2161 PN->eraseFromParent();
2165 for (
auto *
I : Insts) {
2170 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2171 I->replaceAllUsesWith(I0);
2172 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)
2319 LockstepReverseIterator LRI(UnconditionalPreds);
2320 while (LRI.isValid() &&
2322 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2324 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2335 if (!followedByDeoptOrUnreachable) {
2339 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2340 unsigned NumPHIdValues = 0;
2341 for (
auto *
I : *LRI)
2342 for (
auto *V : PHIOperands[
I]) {
2343 if (!InstructionsToSink.
contains(V))
2349 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2350 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2351 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2354 return NumPHIInsts <= 1;
2371 while (
Idx < ScanIdx) {
2372 if (!ProfitableToSinkInstruction(LRI)) {
2375 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2378 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2388 if (
Idx < ScanIdx) {
2391 InstructionsToSink = InstructionsProfitableToSink;
2397 !ProfitableToSinkInstruction(LRI) &&
2398 "We already know that the last instruction is unprofitable to sink");
2406 for (
auto *
I : *LRI)
2407 InstructionsProfitableToSink.
erase(
I);
2408 if (!ProfitableToSinkInstruction(LRI)) {
2411 InstructionsToSink = InstructionsProfitableToSink;
2423 bool Changed =
false;
2425 if (HaveNonUnconditionalPredecessors) {
2426 if (!followedByDeoptOrUnreachable) {
2434 bool Profitable =
false;
2435 while (
Idx < ScanIdx) {
2469 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2471 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2481 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2485 NumSinkCommonInstrs++;
2489 ++NumSinkCommonCode;
2495struct CompatibleSets {
2513 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2522 getCompatibleSet(II).emplace_back(II);
2526 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2532 if (
any_of(Invokes, IsIllegalToMerge))
2538 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2539 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2540 if (HaveIndirectCalls) {
2541 if (!AllCallsAreIndirect)
2548 assert(CurrCallee &&
"There is always a called operand.");
2551 else if (Callee != CurrCallee)
2561 if (
any_of(Invokes, HasNormalDest)) {
2564 if (!
all_of(Invokes, HasNormalDest))
2571 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2573 NormalBB = CurrNormalBB;
2574 else if (NormalBB != CurrNormalBB)
2582 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2593 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2595 UnwindBB = CurrUnwindBB;
2597 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2604 Invokes.front()->getUnwindDest(),
2605 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2611 for (
auto *II : Invokes.drop_front())
2616 auto IsIllegalToMergeArguments = [](
auto Ops) {
2617 Use &U0 = std::get<0>(Ops);
2618 Use &U1 = std::get<1>(Ops);
2625 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2626 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2627 IsIllegalToMergeArguments))
2639 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2645 bool HasNormalDest =
2646 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2650 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2659 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2661 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2663 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2665 if (!HasNormalDest) {
2669 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2676 return MergedInvoke;
2690 SuccBBOfMergedInvoke});
2697 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2700 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2703 for (
Use &U : MergedInvoke->operands()) {
2705 if (MergedInvoke->isCallee(&U)) {
2706 if (!IsIndirectCall)
2708 }
else if (!MergedInvoke->isDataOperand(&U))
2720 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2732 Invokes.front()->getParent());
2740 if (!MergedDebugLoc)
2749 OrigSuccBB->removePredecessor(II->
getParent());
2755 MergedInvoke->setDebugLoc(MergedDebugLoc);
2756 ++NumInvokeSetsFormed;
2759 DTU->applyUpdates(Updates);
2786 bool Changed =
false;
2792 CompatibleSets Grouper;
2798 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2802 if (Invokes.
size() < 2)
2814class EphemeralValueTracker {
2818 if (isa<AssumeInst>(
I))
2820 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2822 return EphValues.count(cast<Instruction>(U));
2828 if (isEphemeral(
I)) {
2867 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2879 unsigned MaxNumInstToLookAt = 9;
2883 if (!MaxNumInstToLookAt)
2885 --MaxNumInstToLookAt;
2888 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2891 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2895 if (SI->getPointerOperand() == StorePtr &&
2896 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2897 SI->getAlign() >= StoreToHoist->
getAlign())
2899 return SI->getValueOperand();
2903 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2904 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2905 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2928 unsigned &SpeculatedInstructions,
2936 bool HaveRewritablePHIs =
false;
2954 HaveRewritablePHIs =
true;
2957 if (!OrigCE && !ThenCE)
2964 if (OrigCost + ThenCost > MaxCost)
2971 ++SpeculatedInstructions;
2972 if (SpeculatedInstructions > 1)
2976 return HaveRewritablePHIs;
3016bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3023 if (isa<FCmpInst>(BrCond))
3033 bool Invert =
false;
3042 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3045 (TWeight + FWeight) != 0) {
3046 uint64_t EndWeight = Invert ? TWeight : FWeight;
3050 if (BIEndProb >= Likely)
3064 unsigned SpeculatedInstructions = 0;
3065 Value *SpeculatedStoreValue =
nullptr;
3067 EphemeralValueTracker EphTracker;
3070 if (isa<DbgInfoIntrinsic>(
I)) {
3078 if (isa<PseudoProbeInst>(
I)) {
3088 if (EphTracker.track(&
I))
3093 ++SpeculatedInstructions;
3094 if (SpeculatedInstructions > 1)
3100 &
I, BB, ThenBB, EndBB))))
3102 if (!SpeculatedStoreValue &&
3108 if (SpeculatedStoreValue)
3109 SpeculatedStore = cast<StoreInst>(&
I);
3114 for (
Use &
Op :
I.operands()) {
3119 ++SinkCandidateUseCounts[OpI];
3126 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3128 ++SpeculatedInstructions;
3129 if (SpeculatedInstructions > 1)
3135 bool Convert = SpeculatedStore !=
nullptr;
3138 SpeculatedInstructions,
3140 if (!Convert ||
Cost > Budget)
3144 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3147 if (SpeculatedStoreValue) {
3151 Value *FalseV = SpeculatedStoreValue;
3155 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3184 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3186 DbgAssign->replaceVariableLocationOp(OrigV, S);
3199 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3201 if (!isa<DbgAssignIntrinsic>(&
I))
3204 I.dropUBImplyingAttrsAndMetadata();
3207 if (EphTracker.contains(&
I)) {
3209 I.eraseFromParent();
3223 It.dropOneDbgRecord(&DR);
3225 std::prev(ThenBB->
end()));
3242 Value *TrueV = ThenV, *FalseV = OrigV;
3256 if (!isa<DbgAssignIntrinsic>(
I))
3257 I->eraseFromParent();
3267 EphemeralValueTracker EphTracker;
3273 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3274 if (CI->cannotDuplicate() || CI->isConvergent())
3280 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3287 for (
User *U :
I.users()) {
3289 if (UI->
getParent() != BB || isa<PHINode>(UI))
3303 auto *
I = dyn_cast<Instruction>(V);
3304 if (
I &&
I->getParent() == To)
3308 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3320static std::optional<bool>
3336 if (
auto *CB = dyn_cast<ConstantInt>(U))
3341 KnownValues[CB].
insert(Pred);
3345 if (KnownValues.
empty())
3354 for (
const auto &Pair : KnownValues) {
3372 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3375 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3383 EdgeBB->setName(RealDest->
getName() +
".critedge");
3384 EdgeBB->moveBefore(RealDest);
3394 TranslateMap[
Cond] = CB;
3400 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3407 N->insertInto(EdgeBB, InsertPt);
3410 N->setName(BBI->getName() +
".c");
3413 for (
Use &
Op :
N->operands()) {
3415 if (PI != TranslateMap.
end())
3421 if (!BBI->use_empty())
3422 TranslateMap[&*BBI] = V;
3423 if (!
N->mayHaveSideEffects()) {
3424 N->eraseFromParent();
3429 if (!BBI->use_empty())
3430 TranslateMap[&*BBI] =
N;
3436 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3437 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3438 SrcDbgCursor = std::next(BBI);
3440 N->cloneDebugInfoFrom(&*BBI);
3443 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3449 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3450 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3451 InsertPt->cloneDebugInfoFrom(BI);
3454 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3460 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3461 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3472 return std::nullopt;
3482 std::optional<bool> Result;
3483 bool EverChanged =
false;
3487 EverChanged |= Result == std::nullopt || *Result;
3488 }
while (Result == std::nullopt);
3510 if (isa<ConstantInt>(IfCond))
3517 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3520 "Will have either one or two blocks to speculate.");
3527 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3530 (TWeight + FWeight) != 0) {
3535 if (IfBlocks.
size() == 1) {
3537 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3538 if (BIBBProb >= Likely)
3541 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3549 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3550 if (IfCondPhiInst->getParent() == BB)
3558 unsigned NumPhis = 0;
3571 bool Changed =
false;
3573 PHINode *PN = cast<PHINode>(II++);
3590 PN = dyn_cast<PHINode>(BB->
begin());
3596 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3607 auto IsBinOpOrAnd = [](
Value *V) {
3627 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3640 <<
" T: " << IfTrue->
getName()
3641 <<
" F: " << IfFalse->
getName() <<
"\n");
3655 if (isa<FPMathOperator>(PN))
3675 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3693 if (Opc == Instruction::And)
3695 if (Opc == Instruction::Or)
3708 bool PredHasWeights =
3710 bool SuccHasWeights =
3712 if (PredHasWeights || SuccHasWeights) {
3713 if (!PredHasWeights)
3714 PredTrueWeight = PredFalseWeight = 1;
3715 if (!SuccHasWeights)
3716 SuccTrueWeight = SuccFalseWeight = 1;
3726static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3730 "Both blocks must end with a conditional branches.");
3732 "PredBB must be a predecessor of BB.");
3740 (PTWeight + PFWeight) != 0) {
3748 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3749 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3753 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3756 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3757 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3763 return std::nullopt;
3776 bool InvertPredCond;
3777 std::tie(CommonSucc, Opc, InvertPredCond) =
3780 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3787 {LLVMContext::MD_annotation});
3790 if (InvertPredCond) {
3803 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3805 SuccTrueWeight, SuccFalseWeight)) {
3812 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3818 (SuccFalseWeight + SuccTrueWeight) +
3819 PredTrueWeight * SuccFalseWeight);
3825 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3826 PredFalseWeight * SuccTrueWeight);
3828 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3846 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3847 {DominatorTree::Delete, PredBlock, BB}});
3874 ++NumFoldBranchToCommonDest;
3881 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3882 return U->getType()->isVectorTy();
3892 unsigned BonusInstThreshold) {
3906 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3907 !isa<SelectInst>(
Cond)) ||
3908 Cond->getParent() != BB || !
Cond->hasOneUse())
3918 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3929 bool InvertPredCond;
3931 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3963 unsigned NumBonusInsts = 0;
3964 bool SawVectorOp =
false;
3965 const unsigned PredCount = Preds.
size();
3971 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3982 NumBonusInsts += PredCount;
3990 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3991 auto *UI = cast<Instruction>(U.getUser());
3992 if (
auto *PN = dyn_cast<PHINode>(UI))
3994 return UI->
getParent() == BB &&
I.comesBefore(UI);
3998 if (!
all_of(
I.uses(), IsBCSSAUse))
4002 BonusInstThreshold *
4008 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4018 for (
auto *BB : {BB1, BB2}) {
4022 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4034 Value *AlternativeV =
nullptr) {
4052 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4053 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4054 PHI = cast<PHINode>(
I);
4060 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4061 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4069 if (!AlternativeV &&
4070 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4075 PHI->addIncoming(V, BB);
4085 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4094 if (!PStore || !QStore)
4115 if (
I.mayReadOrWriteMemory())
4117 for (
auto &
I : *QFB)
4118 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4121 for (
auto &
I : *QTB)
4122 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4126 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4142 if (
I.isTerminator())
4146 if (
auto *S = dyn_cast<StoreInst>(&
I))
4150 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4160 "When we run out of budget we will eagerly return from within the "
4161 "per-instruction loop.");
4165 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4167 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4168 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4276 bool InvertPCond =
false, InvertQCond =
false;
4282 if (QFB == PostBB) {
4301 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4304 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4312 for (
auto *BB : {PTB, PFB}) {
4317 PStoreAddresses.
insert(SI->getPointerOperand());
4319 for (
auto *BB : {QTB, QFB}) {
4324 QStoreAddresses.
insert(SI->getPointerOperand());
4330 auto &CommonAddresses = PStoreAddresses;
4332 bool Changed =
false;
4333 for (
auto *Address : CommonAddresses)
4336 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4356 if (!IfFalseBB->
phis().empty())
4366 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4377 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4378 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4389 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4390 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4469 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4471 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4475 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4478 if (CommonDestProb >= Likely)
4488 unsigned NumPhis = 0;
4510 if (OtherDest == BB) {
4517 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4518 OtherDest = InfLoopBlock;
4538 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4553 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4554 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4557 SuccTrueWeight, SuccFalseWeight);
4559 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4560 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4561 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4562 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4566 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4567 PredOther * SuccCommon,
4568 PredOther * SuccOther};
4597 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4598 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4599 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4600 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4603 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4604 PredOther * SuccCommon};
4626bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4637 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4644 if (Succ == KeepEdge1)
4645 KeepEdge1 =
nullptr;
4646 else if (Succ == KeepEdge2)
4647 KeepEdge2 =
nullptr;
4652 if (Succ != TrueBB && Succ != FalseBB)
4653 RemovedSuccessors.
insert(Succ);
4661 if (!KeepEdge1 && !KeepEdge2) {
4662 if (TrueBB == FalseBB) {
4670 if (TrueWeight != FalseWeight)
4673 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4695 for (
auto *RemovedSuccessor : RemovedSuccessors)
4696 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4697 DTU->applyUpdates(Updates);
4707bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4712 if (!TrueVal || !FalseVal)
4717 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4718 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4721 uint32_t TrueWeight = 0, FalseWeight = 0;
4726 if (Weights.
size() == 1 +
SI->getNumCases()) {
4728 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4730 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4735 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4744bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4757 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4778bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4798 if (
SI->getCondition() != V)
4804 if (
SI->getDefaultDest() != BB) {
4806 assert(VVal &&
"Should have a unique destination value");
4814 return requestResimplify();
4820 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4830 return requestResimplify();
4837 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4862 auto W0 = SIW.getSuccessorWeight(0);
4866 SIW.setSuccessorWeight(0, *NewW);
4868 SIW.addCase(Cst, NewBB, NewW);
4870 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4879 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4880 DTU->applyUpdates(Updates);
4888bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4900 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4903 Value *CompVal = ConstantCompare.CompValue;
4904 unsigned UsedICmps = ConstantCompare.UsedICmps;
4905 Value *ExtraCase = ConstantCompare.Extra;
4924 if (ExtraCase && Values.
size() < 2)
4939 <<
" cases into SWITCH. BB is:\n"
4949 nullptr,
"switch.early.test");
4973 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4979 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4980 <<
"\nEXTRABB = " << *BB);
4988 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4995 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4996 New->addCase(Values[i], EdgeBB);
5002 PHINode *PN = cast<PHINode>(BBI);
5004 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5011 DTU->applyUpdates(Updates);
5013 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5019 return simplifyCommonResume(RI);
5023 return simplifySingleResume(RI);
5031 auto *II = dyn_cast<IntrinsicInst>(&
I);
5036 switch (IntrinsicID) {
5037 case Intrinsic::dbg_declare:
5038 case Intrinsic::dbg_value:
5039 case Intrinsic::dbg_label:
5040 case Intrinsic::lifetime_end:
5050bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5060 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5063 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5065 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5066 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5070 if (IncomingBB->getUniqueSuccessor() != BB)
5073 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5075 if (IncomingValue != LandingPad)
5079 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5080 TrivialUnwindBlocks.
insert(IncomingBB);
5084 if (TrivialUnwindBlocks.
empty())
5088 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5092 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5106 TrivialBB->getTerminator()->eraseFromParent();
5109 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5116 return !TrivialUnwindBlocks.empty();
5120bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5124 "Resume must unwind the exception that caused control to here");
5128 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5164 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5181 int Idx = DestPN.getBasicBlockIndex(BB);
5195 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5196 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5198 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5202 DestPN.addIncoming(
Incoming, Pred);
5229 std::vector<DominatorTree::UpdateType> Updates;
5233 if (UnwindDest ==
nullptr) {
5245 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5246 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5273 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5274 if (!SuccessorCleanupPad)
5283 SuccessorCleanupPad->eraseFromParent();
5312 bool Changed =
false;
5341 BBI->dropDbgRecords();
5345 BBI->eraseFromParent();
5351 if (&BB->
front() != UI)
5354 std::vector<DominatorTree::UpdateType> Updates;
5357 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5358 auto *Predecessor = Preds[i];
5361 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5365 [BB](
auto *
Successor) { return Successor == BB; })) {
5373 "The destinations are guaranteed to be different here.");
5384 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5390 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5391 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5393 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5394 if (i->getCaseSuccessor() != BB) {
5399 i = SU.removeCase(i);
5404 if (DTU &&
SI->getDefaultDest() != BB)
5405 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5406 }
else if (
auto *II = dyn_cast<InvokeInst>(TI)) {
5409 DTU->applyUpdates(Updates);
5413 if (!CI->doesNotThrow())
5414 CI->setDoesNotThrow();
5417 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5418 if (CSI->getUnwindDest() == BB) {
5420 DTU->applyUpdates(Updates);
5429 E = CSI->handler_end();
5432 CSI->removeHandler(
I);
5439 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5440 if (CSI->getNumHandlers() == 0) {
5441 if (CSI->hasUnwindDest()) {
5445 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5446 Updates.push_back({DominatorTree::Insert,
5447 PredecessorOfPredecessor,
5448 CSI->getUnwindDest()});
5449 Updates.push_back({DominatorTree::Delete,
5450 PredecessorOfPredecessor, Predecessor});
5453 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5457 DTU->applyUpdates(Updates);
5466 CSI->eraseFromParent();
5469 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5471 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5472 "Expected to always have an unwind to BB.");
5474 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5482 DTU->applyUpdates(Updates);
5497 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5498 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5507 auto *BB = Switch->getParent();
5508 auto *OrigDefaultBlock = Switch->getDefaultDest();
5509 OrigDefaultBlock->removePredecessor(BB);
5514 Switch->setDefaultDest(&*NewDefaultBlock);
5517 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5519 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5527bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5529 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5532 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5534 auto *BB =
SI->getParent();
5537 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5542 for (
auto Case :
SI->cases()) {
5546 if (Dest == DestA) {
5552 if (Dest == DestB) {
5562 "Single-destination switch should have been folded.");
5564 assert(DestB !=
SI->getDefaultDest());
5565 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5573 ContiguousCases = &CasesA;
5574 ContiguousDest = DestA;
5577 ContiguousCases = &CasesB;
5578 ContiguousDest = DestB;
5587 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5589 Value *Sub =
SI->getCondition();
5590 if (!
Offset->isNullValue())
5605 if (Weights.
size() == 1 +
SI->getNumCases()) {
5608 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5609 if (
SI->getSuccessor(
I) == ContiguousDest)
5610 TrueWeight += Weights[
I];
5612 FalseWeight += Weights[
I];
5614 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5623 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5624 unsigned PreviousEdges = ContiguousCases->
size();
5625 if (ContiguousDest ==
SI->getDefaultDest())
5627 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5628 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5630 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5631 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5632 if (OtherDest ==
SI->getDefaultDest())
5634 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5635 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5643 auto *UnreachableDefault =
SI->getDefaultDest();
5646 SI->eraseFromParent();
5648 if (!HasDefault && DTU)
5649 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5665 unsigned MaxSignificantBitsInCond =
5672 for (
const auto &Case : SI->cases()) {
5673 auto *
Successor = Case.getCaseSuccessor();
5679 const APInt &CaseVal = Case.getCaseValue()->getValue();
5682 DeadCases.
push_back(Case.getCaseValue());
5695 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5696 const unsigned NumUnknownBits =
5699 if (HasDefault && DeadCases.
empty() &&
5700 NumUnknownBits < 64 &&
5701 SI->getNumCases() == (1ULL << NumUnknownBits)) {
5706 if (DeadCases.
empty())
5712 assert(CaseI != SI->case_default() &&
5713 "Case was not found. Probably mistake in DeadCases forming.");
5715 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5720 std::vector<DominatorTree::UpdateType> Updates;
5721 for (
auto *
Successor : UniqueSuccessors)
5722 if (NumPerSuccessorCases[
Successor] == 0)
5723 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5743 if (!Branch || !Branch->isUnconditional())
5749 int Idx =
PHI.getBasicBlockIndex(BB);
5750 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5753 if (InValue != CaseValue)
5769 ForwardingNodesMap ForwardingNodes;
5771 bool Changed =
false;
5772 for (
const auto &Case : SI->cases()) {
5774 BasicBlock *CaseDest = Case.getCaseSuccessor();
5793 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5794 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5795 count(Phi.blocks(), SwitchBlock) == 1) {
5796 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5804 ForwardingNodes[Phi].push_back(PhiIdx);
5807 for (
auto &ForwardingNode : ForwardingNodes) {
5808 PHINode *Phi = ForwardingNode.first;
5810 if (Indexes.
size() < 2)
5813 for (
int Index : Indexes)
5814 Phi->setIncomingValue(
Index, SI->getCondition());
5824 if (
C->isThreadDependent())
5826 if (
C->isDLLImportDependent())
5829 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5830 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5831 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5837 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5853 if (
Constant *
C = dyn_cast<Constant>(V))
5869 if (
A->isAllOnesValue())
5871 if (
A->isNullValue())
5877 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5902 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5904 if (
I.isTerminator()) {
5906 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5909 CaseDest =
I.getSuccessor(0);
5916 for (
auto &
Use :
I.uses()) {
5919 if (
I->getParent() == CaseDest)
5922 if (Phi->getIncomingBlock(
Use) == CaseDest)
5935 *CommonDest = CaseDest;
5937 if (CaseDest != *CommonDest)
5942 int Idx =
PHI.getBasicBlockIndex(Pred);
5955 Res.push_back(std::make_pair(&
PHI, ConstVal));
5958 return Res.size() > 0;
5964 SwitchCaseResultVectorTy &UniqueResults,
5966 for (
auto &
I : UniqueResults) {
5967 if (
I.first == Result) {
5968 I.second.push_back(CaseVal);
5969 return I.second.size();
5972 UniqueResults.push_back(
5983 SwitchCaseResultVectorTy &UniqueResults,
5987 uintptr_t MaxUniqueResults) {
5988 for (
const auto &
I : SI->cases()) {
6002 const size_t NumCasesForResult =
6010 if (UniqueResults.size() > MaxUniqueResults)
6021 BasicBlock *DefaultDest = SI->getDefaultDest();
6022 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6027 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6028 if ((!DefaultResult &&
6049 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6050 ResultVector[1].second.size() == 1) {
6051 ConstantInt *FirstCase = ResultVector[0].second[0];
6052 ConstantInt *SecondCase = ResultVector[1].second[0];
6053 Value *SelectValue = ResultVector[1].first;
6054 if (DefaultResult) {
6055 Value *ValueCompare =
6056 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6057 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6058 DefaultResult,
"switch.select");
6060 Value *ValueCompare =
6061 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6062 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6063 SelectValue,
"switch.select");
6067 if (ResultVector.size() == 1 && DefaultResult) {
6069 unsigned CaseCount = CaseValues.
size();
6077 for (
auto *Case : CaseValues)
6078 if (Case->getValue().slt(MinCaseVal->
getValue()))
6083 for (
auto *Case : CaseValues)
6084 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6090 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6094 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6099 if (CaseValues.
size() == 2) {
6101 "switch.selectcmp.case1");
6103 "switch.selectcmp.case2");
6104 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6105 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6118 std::vector<DominatorTree::UpdateType> Updates;
6124 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6129 PHI->removeIncomingValueIf(
6130 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6131 PHI->addIncoming(SelectValue, SelectBB);
6134 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6140 if (DTU && RemovedSuccessors.
insert(Succ).second)
6141 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6143 SI->eraseFromParent();
6158 SwitchCaseResultVectorTy UniqueResults;
6164 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6166 Value *SelectValue =
6178class SwitchLookupTable {
6229 bool LinearMapValWrapped =
false;
6237SwitchLookupTable::SwitchLookupTable(
6241 assert(Values.
size() &&
"Can't build lookup table without values!");
6242 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6245 SingleValue = Values.
begin()->second;
6251 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6257 TableContents[
Idx] = CaseRes;
6259 if (CaseRes != SingleValue)
6260 SingleValue =
nullptr;
6264 if (Values.
size() < TableSize) {
6266 "Need a default value to fill the lookup table holes.");
6269 if (!TableContents[
I])
6270 TableContents[
I] = DefaultValue;
6273 if (DefaultValue != SingleValue)
6274 SingleValue =
nullptr;
6280 Kind = SingleValueKind;
6287 bool LinearMappingPossible =
true;
6292 bool NonMonotonic =
false;
6293 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6296 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6300 LinearMappingPossible =
false;
6305 APInt Dist = Val - PrevVal;
6308 }
else if (Dist != DistToPrev) {
6309 LinearMappingPossible =
false;
6317 if (LinearMappingPossible) {
6318 LinearOffset = cast<ConstantInt>(TableContents[0]);
6319 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6320 bool MayWrap =
false;
6321 APInt M = LinearMultiplier->getValue();
6322 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6323 LinearMapValWrapped = NonMonotonic || MayWrap;
6324 Kind = LinearMapKind;
6331 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6333 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6335 TableInt <<=
IT->getBitWidth();
6337 if (!isa<UndefValue>(TableContents[
I - 1])) {
6338 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6339 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6342 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6343 BitMapElementTy =
IT;
6354 GlobalVariable::PrivateLinkage, Initializer,
6355 "switch.table." + FuncName);
6356 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6365 case SingleValueKind:
6367 case LinearMapKind: {
6370 false,
"switch.idx.cast");
6371 if (!LinearMultiplier->isOne())
6372 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6374 !LinearMapValWrapped);
6376 if (!LinearOffset->isZero())
6379 !LinearMapValWrapped);
6395 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6396 "switch.shiftamt",
true,
true);
6399 Value *DownShifted =
6400 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6402 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6408 Array->getInitializer()->getType()->getArrayNumElements();
6409 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6412 "switch.tableidx.zext");
6416 GEPIndices,
"switch.gep");
6418 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6425bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6427 Type *ElementType) {
6428 auto *
IT = dyn_cast<IntegerType>(ElementType);
6435 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6437 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6446 auto *
IT = dyn_cast<IntegerType>(Ty);
6458 DL.fitsInLegalInteger(
IT->getBitWidth());
6470 return NumCases * 100 >= CaseRange * MinDensity;
6491 if (SI->getNumCases() > TableSize)
6494 bool AllTablesFitInRegister =
true;
6495 bool HasIllegalType =
false;
6496 for (
const auto &
I : ResultTypes) {
6497 Type *Ty =
I.second;
6503 AllTablesFitInRegister =
6504 AllTablesFitInRegister &&
6505 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6510 if (HasIllegalType && !AllTablesFitInRegister)
6515 if (AllTablesFitInRegister)
6532 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6535 return all_of(ResultTypes, [&](
const auto &KV) {
6536 return SwitchLookupTable::WouldFitInRegister(
6565 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6585 DefaultValue, CmpOp1,
true);
6586 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6591 for (
auto ValuePair : Values) {
6593 ValuePair.second, CmpOp1,
true);
6594 if (!CaseConst || CaseConst == DefaultConst ||
6595 (CaseConst != TrueConst && CaseConst != FalseConst))
6609 if (DefaultConst == FalseConst) {
6612 ++NumTableCmpReuses;
6615 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6616 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6619 ++NumTableCmpReuses;
6629 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6648 if (SI->getNumCases() < 3)
6653 assert(!SI->cases().empty());
6670 MinCaseVal = CaseVal;
6672 MaxCaseVal = CaseVal;
6677 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6687 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6693 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6701 bool HasDefaultResults =
6703 DefaultResultsList,
DL,
TTI);
6705 for (
const auto &
I : DefaultResultsList) {
6708 DefaultResults[
PHI] = Result;
6712 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6714 if (UseSwitchConditionAsTableIndex)
6720 bool TableHasHoles = (NumResults < TableSize);
6721 bool NeedMask = (TableHasHoles && !HasDefaultResults);
6724 if (SI->getNumCases() < 4)
6726 if (!
DL.fitsInLegalInteger(TableSize))
6733 std::vector<DominatorTree::UpdateType> Updates;
6739 assert(MaxTableSize >= TableSize &&
6740 "It is impossible for a switch to have more entries than the max "
6741 "representable value of its input integer type's size.");
6746 bool DefaultIsReachable =
6747 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
6758 if (UseSwitchConditionAsTableIndex) {
6759 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6760 TableIndex = SI->getCondition();
6762 TableIndexOffset = MinCaseVal;
6765 bool MayWrap =
true;
6766 if (!DefaultIsReachable) {
6771 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6772 "switch.tableidx",
false,
6781 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6789 return SwitchLookupTable::WouldFitInRegister(
6790 DL, UpperBound, KV.second );
6794 TableSize = std::max(UpperBound, TableSize);
6797 DefaultIsReachable =
false;
6801 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6802 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6805 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6810 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6812 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6814 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6824 MaskBB->
setName(
"switch.hole_check");
6831 APInt MaskInt(TableSizePowOf2, 0);
6832 APInt One(TableSizePowOf2, 1);
6834 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6835 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6838 MaskInt |= One <<
Idx;
6848 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6851 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6853 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6854 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6860 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6863 SI->getDefaultDest()->removePredecessor(BB,
6866 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6870 const ResultListTy &ResultList = ResultLists[
PHI];
6873 Constant *DV = NeedMask ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6875 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6878 Value *Result = Table.BuildLookup(TableIndex, Builder);
6882 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6885 for (
auto *
User :
PHI->users()) {
6890 PHI->addIncoming(Result, LookupBB);
6895 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6899 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6902 if (Succ == SI->getDefaultDest())
6905 if (DTU && RemovedSuccessors.
insert(Succ).second)
6906 Updates.push_back({DominatorTree::Delete, BB, Succ});
6908 SI->eraseFromParent();
6915 ++NumLookupTablesHoles;
6930 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6931 if (CondTy->getIntegerBitWidth() > 64 ||
6932 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6936 if (SI->getNumCases() < 4)
6944 for (
const auto &
C : SI->cases())
6945 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6953 int64_t
Base = Values[0];
6954 for (
auto &V : Values)
6967 unsigned Shift = 64;
6968 for (
auto &V : Values)
6972 for (
auto &V : Values)
6973 V = (int64_t)((
uint64_t)V >> Shift);
6989 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
6992 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
6994 Ty, Intrinsic::fshl,
6995 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
6996 SI->replaceUsesOfWith(SI->getCondition(), Rot);
6998 for (
auto Case : SI->cases()) {
6999 auto *Orig = Case.getCaseValue();
7000 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
7001 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7017 Value *Condition = SI->getCondition();
7019 auto *CondTy = cast<IntegerType>(Condition->
getType());
7021 if (CondTy->getIntegerBitWidth() > 64 ||
7022 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7036 if (SI->getNumCases() < 4)
7042 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7047 for (
const auto &Case : SI->cases()) {
7048 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7065 for (
auto &Case : SI->cases()) {
7066 auto *OrigValue = Case.getCaseValue();
7067 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7068 OrigValue->getValue().countr_zero()));
7075 SI->setCondition(ConditionTrailingZeros);
7083 if (isValueEqualityComparison(SI)) {
7087 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7088 return requestResimplify();
7092 if (SimplifySwitchOnSelect(SI,
Select))
7093 return requestResimplify();
7098 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7099 return requestResimplify();
7105 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7106 return requestResimplify();
7110 return requestResimplify();
7113 return requestResimplify();
7116 return requestResimplify();
7123 if (
Options.ConvertSwitchToLookupTable &&
7125 return requestResimplify();
7128 return requestResimplify();
7131 return requestResimplify();
7134 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7135 return requestResimplify();
7142 bool Changed =
false;
7151 RemovedSuccs.
insert(Dest);
7161 std::vector<DominatorTree::UpdateType> Updates;
7162 Updates.reserve(RemovedSuccs.
size());
7163 for (
auto *RemovedSucc : RemovedSuccs)
7164 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7165 DTU->applyUpdates(Updates);
7183 if (SimplifyIndirectBrOnSelect(IBI, SI))
7184 return requestResimplify();
7216 if (isa<PHINode>(*Succ->
begin()))
7220 if (BB == OtherPred)
7226 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7232 std::vector<DominatorTree::UpdateType> Updates;
7240 "unexpected successor");
7243 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7244 Updates.push_back({DominatorTree::Delete, Pred, BB});
7251 if (isa<DbgInfoIntrinsic>(Inst))
7258 Updates.push_back({DominatorTree::Delete, BB, Succ});
7272 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7273 : simplifyCondBranch(
Branch, Builder);
7276bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7288 bool NeedCanonicalLoop =
7299 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7301 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7303 if (
I->isTerminator() &&
7304 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7311 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7321 if (
Options.SpeculateBlocks &&
7324 return requestResimplify();
7332 if (!PPred || (PredPred && PredPred != PPred))
7343 "Tautological conditional branch should have been eliminated already.");
7346 if (!
Options.SimplifyCondBranch ||
7351 if (isValueEqualityComparison(BI)) {
7356 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7357 return requestResimplify();
7363 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7364 return requestResimplify();
7367 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7368 return requestResimplify();
7373 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7386 return requestResimplify();
7392 if (
Options.SpeculateBlocks &&
7395 return requestResimplify();
7405 return requestResimplify();
7413 return requestResimplify();
7422 return requestResimplify();
7429 return requestResimplify();
7434 if (PBI != BI && PBI->isConditional())
7436 return requestResimplify();
7441 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7442 if (PBI != BI && PBI->isConditional())
7444 return requestResimplify();
7458 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7460 auto *
Use = cast<Instruction>(*
I->user_begin());
7464 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7478 if (
GEP->getPointerOperand() ==
I) {
7485 if (!
GEP->hasAllZeroIndices() &&
7486 (!
GEP->isInBounds() ||
7488 GEP->getPointerAddressSpace())))
7489 PtrValueMayBeModified =
true;
7495 bool HasNoUndefAttr =
7496 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7498 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7501 if (
C->isNullValue() && HasNoUndefAttr &&
7502 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7503 return !PtrValueMayBeModified;
7513 if (!LI->isVolatile())
7515 LI->getPointerAddressSpace());
7519 if (!SI->isVolatile())
7521 SI->getPointerAddressSpace())) &&
7522 SI->getPointerOperand() ==
I;
7525 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
7527 if (
I == Assume->getArgOperand(0))
7531 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7535 if (CB->getCalledOperand() ==
I)
7538 if (
C->isNullValue()) {
7541 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7542 if (CB->isPassingUndefUB(ArgIdx) &&
7543 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7545 return !PtrValueMayBeModified;
7548 }
else if (isa<UndefValue>(
C)) {
7552 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7553 if (CB->isPassingUndefUB(ArgIdx)) {
7570 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7597 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7599 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7607 for (
const auto &Case : SI->cases())
7608 if (Case.getCaseSuccessor() == BB) {
7610 Case.setSuccessor(Unreachable);
7612 if (SI->getDefaultDest() == BB) {
7614 SI->setDefaultDest(Unreachable);
7619 { { DominatorTree::Insert, Predecessor, Unreachable },
7620 { DominatorTree::Delete, Predecessor, BB } });
7628bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7629 bool Changed =
false;
7653 return requestResimplify();
7674 if (
Options.SpeculateBlocks &&
7678 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7687 case Instruction::Br:
7688 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7690 case Instruction::Resume:
7691 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7693 case Instruction::CleanupRet:
7694 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7696 case Instruction::Switch:
7697 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7699 case Instruction::Unreachable:
7700 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7702 case Instruction::IndirectBr:
7703 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7711 bool Changed =
false;
7719 Changed |= simplifyOnce(BB);
7720 }
while (Resimplify);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static bool ValidLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static Constant * ConstantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static Constant * LookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool SafeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static void GetBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static ConstantInt * GetConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static void EliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static std::optional< bool > FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
static PHINode * FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{Tru...
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
static bool SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool IncomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool FoldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool ForwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static int ConstantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static void FitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static void EraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static unsigned skippedInstrFlags(Instruction *I)
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static bool ValuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< Instruction *, SmallVector< Value *, 4 > > &PHIOperands)
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static void MergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool ShouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool CasesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool isLifeTimeMarker(const Instruction *I)
static bool MergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class represents a no-op cast from one type to another.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
bool isInlineAsm() const
Check if this call is an inline asm statement.
bool cannotMerge() const
Determine if the call cannot be tail merged.
bool isIndirectCall() const
Return true if the callsite is an indirect call.
Value * getCalledOperand() const
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static Constant * getICmp(unsigned short pred, Constant *LHS, Constant *RHS, bool OnlyIfReduced=false)
get* - Return some common constants without having to specify the full Instruction::OPCODE identifier...
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool hasPostDomTree() const
Returns true if it holds a PostDominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
BasicBlock * getUnwindDest() const
void setNormalDest(BasicBlock *B)
void setUnwindDest(BasicBlock *B)
BasicBlock * getNormalDest() const
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
LLVMContext & getContext() const
Get the global data context.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
pred_iterator pred_end(BasicBlock *BB)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void RemapDbgVariableRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
pred_iterator pred_begin(BasicBlock *BB)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It)
Advance It while it points to a debug instruction and return the result.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
bool FoldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void RemapDbgVariableRecord(Module *M, DbgVariableRecord *V, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
unsigned succ_size(const MachineBasicBlock *BB)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void 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.