96#define DEBUG_TYPE "simplifycfg"
99 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
102 "Temporary development switch used to gradually uplift SimplifyCFG "
103 "into preserving DomTree,"));
112 "Control the amount of phi node folding to perform (default = 2)"));
116 cl::desc(
"Control the maximal total instruction cost that we are willing "
117 "to speculatively execute to fold a 2-entry PHI node into a "
118 "select (default = 4)"));
122 cl::desc(
"Hoist common instructions up to the parent block"));
126 cl::desc(
"Hoist loads if the target supports conditional faulting"));
130 cl::desc(
"Hoist stores if the target supports conditional faulting"));
134 cl::desc(
"Control the maximal conditional load/store that we are willing "
135 "to speculatively execute to eliminate conditional branch "
141 cl::desc(
"Allow reordering across at most this many "
142 "instructions when hoisting"));
146 cl::desc(
"Sink common instructions down to the end block"));
150 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
154 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
155 "precede - hoist multiple conditional stores into a single "
156 "predicated store"));
160 cl::desc(
"When merging conditional stores, do so even if the resultant "
161 "basic blocks are unlikely to be if-converted as a result"));
165 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
170 cl::desc(
"Limit maximum recursion depth when calculating costs of "
171 "speculatively executed instructions"));
176 cl::desc(
"Max size of a block which is still considered "
177 "small enough to thread through"));
183 cl::desc(
"Maximum cost of combining conditions when "
184 "folding branches"));
187 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
189 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
190 "to fold branch to common destination when vector operations are "
195 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
199 cl::desc(
"Limit cases to analyze when converting a switch to select"));
203 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
206STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
208 "Number of switch instructions turned into linear mapping");
210 "Number of switch instructions turned into lookup tables");
212 NumLookupTablesHoles,
213 "Number of switch instructions turned into lookup tables (holes checked)");
214STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
216 "Number of value comparisons folded into predecessor basic blocks");
218 "Number of branches folded into predecessor basic block");
221 "Number of common instruction 'blocks' hoisted up to the begin block");
223 "Number of common instructions hoisted up to the begin block");
225 "Number of common instruction 'blocks' sunk down to the end block");
227 "Number of common instructions sunk down to the end block");
228STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
230 "Number of invokes with empty resume blocks simplified into calls");
231STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
232STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
239using SwitchCaseResultVectorTy =
248struct ValueEqualityComparisonCase {
260 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
263class SimplifyCFGOpt {
264 const TargetTransformInfo &TTI;
266 const DataLayout &DL;
268 const SimplifyCFGOptions &Options;
271 Value *isValueEqualityComparison(Instruction *TI);
273 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
274 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
277 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
280 bool foldValueComparisonIntoPredecessors(Instruction *TI,
283 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
284 bool simplifySingleResume(ResumeInst *RI);
285 bool simplifyCommonResume(ResumeInst *RI);
286 bool simplifyCleanupReturn(CleanupReturnInst *RI);
287 bool simplifyUnreachable(UnreachableInst *UI);
288 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
289 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
290 bool simplifyIndirectBr(IndirectBrInst *IBI);
291 bool simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder);
292 bool simplifyUncondBranch(BranchInst *BI,
IRBuilder<> &Builder);
293 bool simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder);
294 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
296 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
299 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
300 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
301 Instruction *TI, Instruction *I1,
302 SmallVectorImpl<Instruction *> &OtherSuccTIs);
303 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
304 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
305 BasicBlock *TrueBB, BasicBlock *FalseBB,
306 uint32_t TrueWeight, uint32_t FalseWeight);
307 bool simplifyBranchOnICmpChain(BranchInst *BI,
IRBuilder<> &Builder,
308 const DataLayout &DL);
309 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
310 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
311 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
314 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
316 const SimplifyCFGOptions &Opts)
317 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
318 assert((!DTU || !DTU->hasPostDomTree()) &&
319 "SimplifyCFG is not yet capable of maintaining validity of a "
320 "PostDomTree, so don't ask for it.");
323 bool simplifyOnce(BasicBlock *BB);
324 bool run(BasicBlock *BB);
327 bool requestResimplify() {
346 "Only for a pair of incoming blocks at the time!");
352 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
353 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
356 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
357 EquivalenceSet->contains(IV1))
380 if (!SI1Succs.
count(Succ))
386 FailBlocks->insert(Succ);
402 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
404 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
405 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
467 if (AggressiveInsts.
count(
I))
483 ZeroCostInstructions.
insert(OverflowInst);
485 }
else if (!ZeroCostInstructions.
contains(
I))
501 for (
Use &
Op :
I->operands())
503 TTI, AC, ZeroCostInstructions,
Depth + 1))
515 if (CI || !
isa<Constant>(V) || !V->getType()->isPointerTy() ||
516 DL.isNonIntegralPointerType(V->getType()))
525 return ConstantInt::get(PtrTy, 0);
529 if (CE->getOpcode() == Instruction::IntToPtr)
553struct ConstantComparesGatherer {
554 const DataLayout &DL;
557 Value *CompValue =
nullptr;
560 Value *Extra =
nullptr;
566 unsigned UsedICmps = 0;
572 bool IgnoreFirstMatch =
false;
573 bool MultipleMatches =
false;
576 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
578 if (CompValue || !MultipleMatches)
583 IgnoreFirstMatch =
true;
587 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
588 ConstantComparesGatherer &
589 operator=(
const ConstantComparesGatherer &) =
delete;
594 bool setValueOnce(
Value *NewVal) {
595 if (IgnoreFirstMatch) {
596 IgnoreFirstMatch =
false;
599 if (CompValue && CompValue != NewVal) {
600 MultipleMatches =
true;
614 bool matchInstruction(Instruction *
I,
bool isEQ) {
621 if (!setValueOnce(Val))
641 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
685 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
687 if (!setValueOnce(RHSVal))
692 ConstantInt::get(
C->getContext(),
693 C->getValue() | Mask));
708 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
710 if (!setValueOnce(RHSVal))
714 Vals.push_back(ConstantInt::get(
C->getContext(),
715 C->getValue() & ~Mask));
736 Value *CandidateVal =
I->getOperand(0);
739 CandidateVal = RHSVal;
754 if (!setValueOnce(CandidateVal))
759 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
770 void gather(
Value *V) {
779 SmallVector<Value *, 8> DFT{Op0, Op1};
780 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
782 while (!DFT.
empty()) {
789 if (Visited.
insert(Op1).second)
791 if (Visited.
insert(Op0).second)
798 if (matchInstruction(
I, IsEq))
825 if (BI->isConditional())
843 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
844 CV =
SI->getCondition();
846 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
851 if (Trunc->hasNoUnsignedWrap())
852 CV = Trunc->getOperand(0);
859 Value *
Ptr = PTII->getPointerOperand();
860 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
869BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
870 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
872 Cases.reserve(
SI->getNumCases());
873 for (
auto Case :
SI->cases())
874 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
875 Case.getCaseSuccessor()));
876 return SI->getDefaultDest();
881 ICmpInst::Predicate Pred;
887 Pred = ICmpInst::ICMP_NE;
892 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
900 std::vector<ValueEqualityComparisonCase> &Cases) {
906 std::vector<ValueEqualityComparisonCase> &C2) {
907 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
910 if (V1->size() > V2->size())
915 if (V1->size() == 1) {
918 for (
const ValueEqualityComparisonCase &
VECC : *V2)
919 if (TheVal ==
VECC.Value)
926 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
927 while (i1 != e1 && i2 != e2) {
948 SI->setMetadata(LLVMContext::MD_prof,
N);
954 uint32_t FalseWeight,
bool IsExpected) {
959 if (TrueWeight || FalseWeight)
962 I->setMetadata(LLVMContext::MD_prof,
N);
970bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
971 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
976 Value *ThisVal = isValueEqualityComparison(TI);
977 assert(ThisVal &&
"This isn't a value comparison!!");
978 if (ThisVal != PredVal)
985 std::vector<ValueEqualityComparisonCase> PredCases;
987 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
991 std::vector<ValueEqualityComparisonCase> ThisCases;
992 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1007 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1013 ThisCases[0].Dest->removePredecessor(PredDef);
1016 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1023 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1030 SmallPtrSet<Constant *, 16> DeadCases;
1031 for (
const ValueEqualityComparisonCase &Case : PredCases)
1032 DeadCases.
insert(Case.Value);
1035 <<
"Through successor TI: " << *TI);
1037 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1040 auto *
Successor = i->getCaseSuccessor();
1043 if (DeadCases.
count(i->getCaseValue())) {
1052 std::vector<DominatorTree::UpdateType> Updates;
1053 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1055 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1065 ConstantInt *TIV =
nullptr;
1067 for (
const auto &[
Value, Dest] : PredCases)
1073 assert(TIV &&
"No edge from pred to succ?");
1078 for (
const auto &[
Value, Dest] : ThisCases)
1086 TheRealDest = ThisDef;
1088 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1093 if (Succ != CheckEdge) {
1094 if (Succ != TheRealDest)
1095 RemovedSuccs.
insert(Succ);
1098 CheckEdge =
nullptr;
1105 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1110 SmallVector<DominatorTree::UpdateType, 2> Updates;
1112 for (
auto *RemovedSucc : RemovedSuccs)
1113 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1124struct ConstantIntOrdering {
1125 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1126 return LHS->getValue().ult(
RHS->getValue());
1138 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1147 assert(MD &&
"Invalid branch-weight metadata");
1167 if (Max > UINT_MAX) {
1182 if (BonusInst.isTerminator())
1212 NewBonusInst->
takeName(&BonusInst);
1213 BonusInst.setName(NewBonusInst->
getName() +
".old");
1214 VMap[&BonusInst] = NewBonusInst;
1223 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1224 "If the user is not a PHI node, then it should be in the same "
1225 "block as, and come after, the original bonus instruction.");
1229 if (PN->getIncomingBlock(U) == BB)
1233 assert(PN->getIncomingBlock(U) == PredBlock &&
1234 "Not in block-closed SSA form?");
1235 U.set(NewBonusInst);
1245 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1246 PredDL.isSameSourceLocation(
DL)) {
1253bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1261 std::vector<ValueEqualityComparisonCase> BBCases;
1262 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1264 std::vector<ValueEqualityComparisonCase> PredCases;
1265 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1270 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1273 SmallVector<uint64_t, 8> Weights;
1277 if (PredHasWeights) {
1280 if (Weights.
size() != 1 + PredCases.size())
1281 PredHasWeights = SuccHasWeights =
false;
1282 }
else if (SuccHasWeights)
1286 Weights.
assign(1 + PredCases.size(), 1);
1288 SmallVector<uint64_t, 8> SuccWeights;
1289 if (SuccHasWeights) {
1292 if (SuccWeights.
size() != 1 + BBCases.size())
1293 PredHasWeights = SuccHasWeights =
false;
1294 }
else if (PredHasWeights)
1295 SuccWeights.
assign(1 + BBCases.size(), 1);
1297 if (PredDefault == BB) {
1300 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1301 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1302 if (PredCases[i].Dest != BB)
1303 PTIHandled.insert(PredCases[i].
Value);
1306 std::swap(PredCases[i], PredCases.back());
1308 if (PredHasWeights || SuccHasWeights) {
1310 Weights[0] += Weights[i + 1];
1315 PredCases.pop_back();
1321 if (PredDefault != BBDefault) {
1323 if (DTU && PredDefault != BB)
1324 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1325 PredDefault = BBDefault;
1326 ++NewSuccessors[BBDefault];
1329 unsigned CasesFromPred = Weights.
size();
1330 uint64_t ValidTotalSuccWeight = 0;
1331 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1332 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1333 PredCases.push_back(BBCases[i]);
1334 ++NewSuccessors[BBCases[i].Dest];
1335 if (SuccHasWeights || PredHasWeights) {
1339 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1340 ValidTotalSuccWeight += SuccWeights[i + 1];
1344 if (SuccHasWeights || PredHasWeights) {
1345 ValidTotalSuccWeight += SuccWeights[0];
1347 for (
unsigned i = 1; i < CasesFromPred; ++i)
1348 Weights[i] *= ValidTotalSuccWeight;
1350 Weights[0] *= SuccWeights[0];
1356 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1357 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1358 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1359 if (PredCases[i].Dest == BB) {
1360 PTIHandled.insert(PredCases[i].
Value);
1362 if (PredHasWeights || SuccHasWeights) {
1363 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1368 std::swap(PredCases[i], PredCases.back());
1369 PredCases.pop_back();
1376 for (
const ValueEqualityComparisonCase &Case : BBCases)
1377 if (PTIHandled.count(Case.Value)) {
1379 if (PredHasWeights || SuccHasWeights)
1380 Weights.
push_back(WeightsForHandled[Case.Value]);
1381 PredCases.push_back(Case);
1382 ++NewSuccessors[Case.Dest];
1383 PTIHandled.erase(Case.Value);
1388 for (ConstantInt *
I : PTIHandled) {
1389 if (PredHasWeights || SuccHasWeights)
1391 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1392 ++NewSuccessors[BBDefault];
1399 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1404 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1406 for (
auto I :
seq(NewSuccessor.second)) {
1410 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1411 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1422 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1424 for (ValueEqualityComparisonCase &V : PredCases)
1427 if (PredHasWeights || SuccHasWeights) {
1444 if (!InfLoopBlock) {
1452 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1459 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1461 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1466 ++NumFoldValueComparisonIntoPredecessors;
1474bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1477 Value *CV = isValueEqualityComparison(TI);
1478 assert(CV &&
"Not a comparison?");
1483 while (!Preds.empty()) {
1492 Value *PCV = isValueEqualityComparison(PTI);
1496 SmallSetVector<BasicBlock *, 4> FailBlocks;
1498 for (
auto *Succ : FailBlocks) {
1504 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1518 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1519 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1520 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1539 if (
I->mayReadFromMemory())
1571 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1579 if (J->getParent() == BB)
1601 if (C1->isMustTailCall() != C2->isMustTailCall())
1604 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1610 if (CB1->cannotMerge() || CB1->isConvergent())
1613 if (CB2->cannotMerge() || CB2->isConvergent())
1628 if (!I1->hasDbgRecords())
1630 using CurrentAndEndIt =
1631 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1637 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1638 return Pair.first == Pair.second;
1644 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1650 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1652 if (!
Other->hasDbgRecords())
1655 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1662 while (
none_of(Itrs, atEnd)) {
1663 bool HoistDVRs = allIdentical(Itrs);
1664 for (CurrentAndEndIt &Pair : Itrs) {
1678 if (I1->isIdenticalToWhenDefined(I2,
true))
1683 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1684 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1685 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1687 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1688 return I1->getOperand(0) == I2->
getOperand(1) &&
1754 auto &Context = BI->
getParent()->getContext();
1759 Value *Mask =
nullptr;
1760 Value *MaskFalse =
nullptr;
1761 Value *MaskTrue =
nullptr;
1762 if (Invert.has_value()) {
1763 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1764 Mask = Builder.CreateBitCast(
1769 MaskFalse = Builder.CreateBitCast(
1771 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1773 auto PeekThroughBitcasts = [](
Value *V) {
1775 V = BitCast->getOperand(0);
1778 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1780 if (!Invert.has_value())
1781 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1786 auto *Op0 =
I->getOperand(0);
1787 CallInst *MaskedLoadStore =
nullptr;
1790 auto *Ty =
I->getType();
1792 Value *PassThru =
nullptr;
1793 if (Invert.has_value())
1794 for (
User *U :
I->users()) {
1796 PassThru = Builder.CreateBitCast(
1800 Sel && Ins->getParent() == BB) {
1805 Builder.SetInsertPoint(Ins);
1808 MaskedLoadStore = Builder.CreateMaskedLoad(
1810 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1813 I->replaceAllUsesWith(NewLoadStore);
1816 auto *StoredVal = Builder.CreateBitCast(
1818 MaskedLoadStore = Builder.CreateMaskedStore(
1829 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1831 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1835 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1836 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1839 I->eraseFromParent();
1846 bool IsStore =
false;
1869bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1870 bool AllInstsEqOnly) {
1890 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1896 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1899 if (AllInstsEqOnly) {
1905 bool AllSame =
none_of(Succs, [&Succs](BasicBlock *Succ) {
1908 return !
Term->isSameOperationAs(Term0) ||
1915 LockstepReverseIterator<true> LRI(Succs);
1916 while (LRI.isValid()) {
1918 if (
any_of(*LRI, [I0](Instruction *
I) {
1933 unsigned NumSkipped = 0;
1936 if (SuccIterPairs.
size() > 2) {
1939 if (SuccIterPairs.
size() < 2)
1946 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1947 auto &BB1ItrPair = *SuccIterPairBegin++;
1948 auto OtherSuccIterPairRange =
1954 bool AllInstsAreIdentical =
true;
1955 bool HasTerminator =
I1->isTerminator();
1956 for (
auto &SuccIter : OtherSuccIterRange) {
1960 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1961 AllInstsAreIdentical =
false;
1964 SmallVector<Instruction *, 8> OtherInsts;
1965 for (
auto &SuccIter : OtherSuccIterRange)
1970 if (HasTerminator) {
1974 if (NumSkipped || !AllInstsAreIdentical) {
1979 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1983 if (AllInstsAreIdentical) {
1984 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1985 AllInstsAreIdentical =
1987 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1989 unsigned SkipFlagsBB2 = Pair.second;
1999 if (AllInstsAreIdentical) {
2009 for (
auto &SuccIter : OtherSuccIterRange) {
2017 assert(
Success &&
"We should not be trying to hoist callbases "
2018 "with non-intersectable attributes");
2030 NumHoistCommonCode += SuccIterPairs.
size();
2032 NumHoistCommonInstrs += SuccIterPairs.
size();
2041 for (
auto &SuccIterPair : SuccIterPairs) {
2050bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2051 Instruction *TI, Instruction *I1,
2052 SmallVectorImpl<Instruction *> &OtherSuccTIs) {
2061 auto *I2 = *OtherSuccTIs.
begin();
2081 for (PHINode &PN : Succ->
phis()) {
2082 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2083 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2084 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2104 if (!
NT->getType()->isVoidTy()) {
2105 I1->replaceAllUsesWith(NT);
2106 for (Instruction *OtherSuccTI : OtherSuccTIs)
2107 OtherSuccTI->replaceAllUsesWith(NT);
2111 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2117 for (
auto *OtherSuccTI : OtherSuccTIs)
2118 Locs.
push_back(OtherSuccTI->getDebugLoc());
2130 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2132 for (PHINode &PN : Succ->
phis()) {
2133 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2134 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2140 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2150 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2151 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2152 PN.setIncomingValue(i, SI);
2163 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2168 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2181 if (
I->isIntDivRem())
2196 std::optional<unsigned> NumUses;
2197 for (
auto *
I : Insts) {
2200 I->getType()->isTokenTy())
2205 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2213 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2217 NumUses =
I->getNumUses();
2218 else if (NumUses !=
I->getNumUses())
2224 for (
auto *
I : Insts) {
2238 for (
const Use &U : I0->
uses()) {
2239 auto It = PHIOperands.find(&U);
2240 if (It == PHIOperands.end())
2243 if (!
equal(Insts, It->second))
2255 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2256 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2257 if (HaveIndirectCalls) {
2258 if (!AllCallsAreIndirect)
2262 Value *Callee =
nullptr;
2266 Callee = CurrCallee;
2267 else if (Callee != CurrCallee)
2273 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2279 if (!
all_of(Insts, SameAsI0)) {
2285 for (
auto *
I : Insts)
2286 Ops.push_back(
I->getOperand(OI));
2296 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2301 for (
auto *BB : Blocks) {
2303 I =
I->getPrevNode();
2328 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2331 PN->insertBefore(BBEnd->begin());
2332 for (
auto *
I : Insts)
2333 PN->addIncoming(
I->getOperand(O),
I->getParent());
2342 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2345 for (
auto *
I : Insts)
2359 assert(
Success &&
"We should not be trying to sink callbases "
2360 "with non-intersectable attributes");
2371 PN->replaceAllUsesWith(I0);
2372 PN->eraseFromParent();
2376 for (
auto *
I : Insts) {
2381 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2382 I->replaceAllUsesWith(I0);
2383 I->eraseFromParent();
2433 bool HaveNonUnconditionalPredecessors =
false;
2436 if (PredBr && PredBr->isUnconditional())
2439 HaveNonUnconditionalPredecessors =
true;
2441 if (UnconditionalPreds.
size() < 2)
2454 for (
const Use &U : PN.incoming_values())
2455 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2456 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2458 Ops.push_back(*IncomingVals[Pred]);
2466 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2479 if (!followedByDeoptOrUnreachable) {
2481 auto IsMemOperand = [](
Use &U) {
2494 unsigned NumPHIInsts = 0;
2495 for (
Use &U : (*LRI)[0]->operands()) {
2496 auto It = PHIOperands.
find(&U);
2497 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2498 return InstructionsToSink.contains(V);
2505 if (IsMemOperand(U) &&
2506 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2513 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2514 return NumPHIInsts <= 1;
2531 while (Idx < ScanIdx) {
2532 if (!ProfitableToSinkInstruction(LRI)) {
2535 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2548 if (Idx < ScanIdx) {
2551 InstructionsToSink = InstructionsProfitableToSink;
2557 !ProfitableToSinkInstruction(LRI) &&
2558 "We already know that the last instruction is unprofitable to sink");
2566 for (
auto *
I : *LRI)
2567 InstructionsProfitableToSink.
erase(
I);
2568 if (!ProfitableToSinkInstruction(LRI)) {
2571 InstructionsToSink = InstructionsProfitableToSink;
2585 if (HaveNonUnconditionalPredecessors) {
2586 if (!followedByDeoptOrUnreachable) {
2594 bool Profitable =
false;
2595 while (Idx < ScanIdx) {
2629 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2631 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2639 NumSinkCommonInstrs++;
2643 ++NumSinkCommonCode;
2649struct CompatibleSets {
2650 using SetTy = SmallVector<InvokeInst *, 2>;
2656 SetTy &getCompatibleSet(InvokeInst *
II);
2658 void insert(InvokeInst *
II);
2661CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2666 for (CompatibleSets::SetTy &Set : Sets) {
2667 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2672 return Sets.emplace_back();
2675void CompatibleSets::insert(InvokeInst *
II) {
2676 getCompatibleSet(
II).emplace_back(
II);
2680 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2683 auto IsIllegalToMerge = [](InvokeInst *
II) {
2684 return II->cannotMerge() ||
II->isInlineAsm();
2686 if (
any_of(Invokes, IsIllegalToMerge))
2691 auto IsIndirectCall = [](InvokeInst *
II) {
return II->isIndirectCall(); };
2692 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2693 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2694 if (HaveIndirectCalls) {
2695 if (!AllCallsAreIndirect)
2700 for (InvokeInst *
II : Invokes) {
2701 Value *CurrCallee =
II->getCalledOperand();
2702 assert(CurrCallee &&
"There is always a called operand.");
2705 else if (Callee != CurrCallee)
2712 auto HasNormalDest = [](InvokeInst *
II) {
2715 if (
any_of(Invokes, HasNormalDest)) {
2718 if (!
all_of(Invokes, HasNormalDest))
2723 for (InvokeInst *
II : Invokes) {
2725 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2727 NormalBB = CurrNormalBB;
2728 else if (NormalBB != CurrNormalBB)
2736 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2745 for (InvokeInst *
II : Invokes) {
2747 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2749 UnwindBB = CurrUnwindBB;
2751 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2758 Invokes.front()->getUnwindDest(),
2759 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2764 const InvokeInst *II0 = Invokes.front();
2765 for (
auto *
II : Invokes.drop_front())
2770 auto IsIllegalToMergeArguments = [](
auto Ops) {
2771 Use &U0 = std::get<0>(
Ops);
2772 Use &U1 = std::get<1>(
Ops);
2778 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2779 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2780 IsIllegalToMergeArguments))
2792 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2798 bool HasNormalDest =
2803 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2807 II0->
getParent()->getIterator()->getNextNode();
2812 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2816 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2818 if (!HasNormalDest) {
2822 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2830 return MergedInvoke;
2844 SuccBBOfMergedInvoke});
2854 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2860 if (!IsIndirectCall)
2867 return II->getOperand(U.getOperandNo()) != U.get();
2886 Invokes.
front()->getParent());
2894 if (!MergedDebugLoc)
2895 MergedDebugLoc =
II->getDebugLoc();
2903 OrigSuccBB->removePredecessor(
II->getParent());
2909 assert(
Success &&
"Merged invokes with incompatible attributes");
2912 II->replaceAllUsesWith(MergedInvoke);
2913 II->eraseFromParent();
2917 ++NumInvokeSetsFormed;
2953 CompatibleSets Grouper;
2963 if (Invokes.
size() < 2)
2975class EphemeralValueTracker {
2976 SmallPtrSet<const Instruction *, 32> EphValues;
2978 bool isEphemeral(
const Instruction *
I) {
2981 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2982 all_of(
I->users(), [&](
const User *U) {
2983 return EphValues.count(cast<Instruction>(U));
2988 bool track(
const Instruction *
I) {
2989 if (isEphemeral(
I)) {
3040 unsigned MaxNumInstToLookAt = 9;
3044 if (!MaxNumInstToLookAt)
3046 --MaxNumInstToLookAt;
3056 if (
SI->getPointerOperand() == StorePtr &&
3057 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3060 return SI->getValueOperand();
3065 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3066 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3068 bool ExplicitlyDereferenceableOnly;
3073 (!ExplicitlyDereferenceableOnly ||
3075 LI->getDataLayout()))) {
3091 unsigned &SpeculatedInstructions,
3099 bool HaveRewritablePHIs =
false;
3101 Value *OrigV = PN.getIncomingValueForBlock(BB);
3102 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3109 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3118 HaveRewritablePHIs =
true;
3121 if (!OrigCE && !ThenCE)
3128 if (OrigCost + ThenCost > MaxCost)
3135 ++SpeculatedInstructions;
3136 if (SpeculatedInstructions > 1)
3140 return HaveRewritablePHIs;
3144 std::optional<bool> Invert,
3148 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3155 if (!Invert.has_value())
3158 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3162 return BIEndProb < Likely;
3202bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3203 BasicBlock *ThenBB) {
3219 bool Invert =
false;
3234 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3236 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3238 unsigned SpeculatedInstructions = 0;
3239 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3240 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3241 Value *SpeculatedStoreValue =
nullptr;
3242 StoreInst *SpeculatedStore =
nullptr;
3243 EphemeralValueTracker EphTracker;
3258 if (EphTracker.track(&
I))
3263 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3265 SpeculatedConditionalLoadsStores.
size() <
3269 if (IsSafeCheapLoadStore)
3270 SpeculatedConditionalLoadsStores.
push_back(&
I);
3272 ++SpeculatedInstructions;
3274 if (SpeculatedInstructions > 1)
3278 if (!IsSafeCheapLoadStore &&
3281 (SpeculatedStoreValue =
3284 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3290 if (!SpeculatedStore && SpeculatedStoreValue)
3296 for (Use &
Op :
I.operands()) {
3301 ++SinkCandidateUseCounts[OpI];
3308 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3309 if (Inst->hasNUses(
Count)) {
3310 ++SpeculatedInstructions;
3311 if (SpeculatedInstructions > 1)
3318 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3321 SpeculatedInstructions,
Cost,
TTI);
3322 if (!Convert ||
Cost > Budget)
3326 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3330 if (SpeculatedStoreValue) {
3334 Value *FalseV = SpeculatedStoreValue;
3338 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3368 for (DbgVariableRecord *DbgAssign :
3371 DbgAssign->replaceVariableLocationOp(OrigV, S);
3381 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3384 I.dropUBImplyingAttrsAndMetadata();
3387 if (EphTracker.contains(&
I)) {
3389 I.eraseFromParent();
3395 for (
auto &It : *ThenBB)
3400 !DVR || !DVR->isDbgAssign())
3401 It.dropOneDbgRecord(&DR);
3403 std::prev(ThenBB->end()));
3405 if (!SpeculatedConditionalLoadsStores.
empty())
3411 for (PHINode &PN : EndBB->
phis()) {
3412 unsigned OrigI = PN.getBasicBlockIndex(BB);
3413 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3414 Value *OrigV = PN.getIncomingValue(OrigI);
3415 Value *ThenV = PN.getIncomingValue(ThenI);
3424 Value *TrueV = ThenV, *FalseV = OrigV;
3428 PN.setIncomingValue(OrigI, V);
3429 PN.setIncomingValue(ThenI, V);
3433 for (Instruction *
I : SpeculatedPseudoProbes)
3434 I->eraseFromParent();
3447 if (!ReachesNonLocalUses.
insert(BB).second)
3462 EphemeralValueTracker EphTracker;
3469 if (CI->cannotDuplicate() || CI->isConvergent())
3482 for (
User *U :
I.users()) {
3485 if (UsedInBB == BB) {
3489 NonLocalUseBlocks.
insert(UsedInBB);
3503 if (
I &&
I->getParent() == To)
3519static std::optional<bool>
3540 KnownValues[CB].
insert(Pred);
3544 if (KnownValues.
empty())
3569 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3572 for (
const auto &Pair : KnownValues) {
3589 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3594 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3597 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3605 EdgeBB->setName(RealDest->
getName() +
".critedge");
3606 EdgeBB->moveBefore(RealDest);
3616 TranslateMap[
Cond] = CB;
3629 N->insertInto(EdgeBB, InsertPt);
3632 N->setName(BBI->getName() +
".c");
3643 if (!BBI->use_empty())
3644 TranslateMap[&*BBI] = V;
3645 if (!
N->mayHaveSideEffects()) {
3646 N->eraseFromParent();
3651 if (!BBI->use_empty())
3652 TranslateMap[&*BBI] =
N;
3658 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3659 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3660 SrcDbgCursor = std::next(BBI);
3662 N->cloneDebugInfoFrom(&*BBI);
3671 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3672 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3673 InsertPt->cloneDebugInfoFrom(BI);
3694 return std::nullopt;
3700bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3707 std::optional<bool>
Result;
3708 bool EverChanged =
false;
3714 }
while (Result == std::nullopt);
3723 bool SpeculateUnpredictables) {
3745 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3748 "Will have either one or two blocks to speculate.");
3755 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3756 if (!IsUnpredictable) {
3759 (TWeight + FWeight) != 0) {
3764 if (IfBlocks.
size() == 1) {
3766 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3767 if (BIBBProb >= Likely)
3770 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3779 if (IfCondPhiInst->getParent() == BB)
3787 unsigned NumPhis = 0;
3800 if (SpeculateUnpredictables && IsUnpredictable)
3801 Budget +=
TTI.getBranchMispredictPenalty();
3814 AggressiveInsts, Cost, Budget,
TTI, AC,
3815 ZeroCostInstructions) ||
3817 AggressiveInsts, Cost, Budget,
TTI, AC,
3818 ZeroCostInstructions))
3830 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3841 auto IsBinOpOrAnd = [](
Value *V) {
3858 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3871 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3873 <<
" F: " << IfFalse->
getName() <<
"\n");
3890 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3895 PN->eraseFromParent();
3901 Builder.CreateBr(BB);
3922 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3923 if (
Opc == Instruction::And)
3924 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3925 if (
Opc == Instruction::Or)
3926 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3938 bool PredHasWeights =
3940 bool SuccHasWeights =
3942 if (PredHasWeights || SuccHasWeights) {
3943 if (!PredHasWeights)
3944 PredTrueWeight = PredFalseWeight = 1;
3945 if (!SuccHasWeights)
3946 SuccTrueWeight = SuccFalseWeight = 1;
3956static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3960 "Both blocks must end with a conditional branches.");
3962 "PredBB must be a predecessor of BB.");
3970 (PTWeight + PFWeight) != 0) {
3973 Likely =
TTI->getPredictableBranchThreshold();
3978 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3979 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3983 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3986 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3987 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3993 return std::nullopt;
4006 bool InvertPredCond;
4007 std::tie(CommonSucc,
Opc, InvertPredCond) =
4010 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4017 {LLVMContext::MD_annotation});
4020 if (InvertPredCond) {
4033 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4035 SuccTrueWeight, SuccFalseWeight)) {
4042 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4048 (SuccFalseWeight + SuccTrueWeight) +
4049 PredTrueWeight * SuccFalseWeight);
4055 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4056 PredFalseWeight * SuccTrueWeight);
4058 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4102 ++NumFoldBranchToCommonDest;
4109 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4110 return U->getType()->isVectorTy();
4120 unsigned BonusInstThreshold) {
4134 Cond->getParent() != BB || !
Cond->hasOneUse())
4155 bool InvertPredCond;
4157 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4189 unsigned NumBonusInsts = 0;
4190 bool SawVectorOp =
false;
4191 const unsigned PredCount = Preds.
size();
4208 NumBonusInsts += PredCount;
4216 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4219 return PN->getIncomingBlock(U) == BB;
4220 return UI->
getParent() == BB &&
I.comesBefore(UI);
4224 if (!
all_of(
I.uses(), IsBCSSAUse))
4228 BonusInstThreshold *
4244 for (
auto *BB : {BB1, BB2}) {
4260 Value *AlternativeV =
nullptr) {
4286 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4287 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4295 if (!AlternativeV &&
4301 PHI->addIncoming(V, BB);
4311 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4320 if (!PStore || !QStore)
4341 if (
I.mayReadOrWriteMemory())
4343 for (
auto &
I : *QFB)
4344 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4347 for (
auto &
I : *QTB)
4348 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4352 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4368 if (
I.isTerminator())
4386 "When we run out of budget we will eagerly return from within the "
4387 "per-instruction loop.");
4391 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4393 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4394 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4430 InvertPCond ^= (PStore->
getParent() != PTB);
4431 InvertQCond ^= (QStore->
getParent() != QTB);
4502 bool InvertPCond =
false, InvertQCond =
false;
4508 if (QFB == PostBB) {
4527 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4530 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4538 for (
auto *BB : {PTB, PFB}) {
4543 PStoreAddresses.
insert(
SI->getPointerOperand());
4545 for (
auto *BB : {QTB, QFB}) {
4550 QStoreAddresses.
insert(
SI->getPointerOperand());
4556 auto &CommonAddresses = PStoreAddresses;
4559 for (
auto *Address : CommonAddresses)
4562 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4580 !BI->
getParent()->getSinglePredecessor())
4582 if (!IfFalseBB->
phis().empty())
4592 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4695 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4697 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4701 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4704 if (CommonDestProb >= Likely)
4714 unsigned NumPhis = 0;
4736 if (OtherDest == BB) {
4744 OtherDest = InfLoopBlock;
4756 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4760 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4764 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4779 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4780 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4783 SuccTrueWeight, SuccFalseWeight);
4785 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4786 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4787 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4788 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4792 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4793 PredOther * SuccCommon,
4794 PredOther * SuccOther};
4810 Value *BIV = PN.getIncomingValueForBlock(BB);
4811 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4812 Value *PBIV = PN.getIncomingValue(PBBIdx);
4816 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4817 PN.setIncomingValue(PBBIdx, NV);
4821 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4822 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4842bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4844 BasicBlock *FalseBB,
4845 uint32_t TrueWeight,
4846 uint32_t FalseWeight) {
4853 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4855 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4858 for (BasicBlock *Succ :
successors(OldTerm)) {
4860 if (Succ == KeepEdge1)
4861 KeepEdge1 =
nullptr;
4862 else if (Succ == KeepEdge2)
4863 KeepEdge2 =
nullptr;
4868 if (Succ != TrueBB && Succ != FalseBB)
4869 RemovedSuccessors.
insert(Succ);
4877 if (!KeepEdge1 && !KeepEdge2) {
4878 if (TrueBB == FalseBB) {
4886 if (TrueWeight != FalseWeight)
4889 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4909 SmallVector<DominatorTree::UpdateType, 2> Updates;
4911 for (
auto *RemovedSuccessor : RemovedSuccessors)
4912 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4923bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4928 if (!TrueVal || !FalseVal)
4933 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4934 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4937 uint32_t TrueWeight = 0, FalseWeight = 0;
4938 SmallVector<uint64_t, 8> Weights;
4942 if (Weights.
size() == 1 +
SI->getNumCases()) {
4944 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4946 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4951 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4960bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
4973 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4994bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5014 if (
SI->getCondition() != V)
5020 if (
SI->getDefaultDest() != BB) {
5021 ConstantInt *VVal =
SI->findCaseDest(BB);
5022 assert(VVal &&
"Should have a unique destination value");
5030 return requestResimplify();
5036 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5046 return requestResimplify();
5053 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5070 SmallVector<DominatorTree::UpdateType, 2> Updates;
5077 SwitchInstProfUpdateWrapper SIW(*SI);
5078 auto W0 = SIW.getSuccessorWeight(0);
5081 NewW = ((uint64_t(*W0) + 1) >> 1);
5082 SIW.setSuccessorWeight(0, *NewW);
5084 SIW.addCase(Cst, NewBB, NewW);
5086 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5095 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5104bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5106 const DataLayout &
DL) {
5116 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5118 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5119 Value *CompVal = ConstantCompare.CompValue;
5120 unsigned UsedICmps = ConstantCompare.UsedICmps;
5121 Value *ExtraCase = ConstantCompare.Extra;
5122 bool TrueWhenEqual = ConstantCompare.IsEq;
5139 if (ExtraCase && Values.
size() < 2)
5154 <<
" cases into SWITCH. BB is:\n"
5157 SmallVector<DominatorTree::UpdateType, 2> Updates;
5164 nullptr,
"switch.early.test");
5175 AssumptionCache *AC =
Options.AC;
5188 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5194 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5195 <<
"\nEXTRABB = " << *BB);
5203 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5210 for (ConstantInt *Val : Values)
5211 New->addCase(Val, EdgeBB);
5219 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5228 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5232bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5234 return simplifyCommonResume(RI);
5238 return simplifySingleResume(RI);
5251 switch (IntrinsicID) {
5252 case Intrinsic::dbg_declare:
5253 case Intrinsic::dbg_value:
5254 case Intrinsic::dbg_label:
5255 case Intrinsic::lifetime_end:
5265bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5274 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5278 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5280 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5281 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5285 if (IncomingBB->getUniqueSuccessor() != BB)
5290 if (IncomingValue != LandingPad)
5294 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5295 TrivialUnwindBlocks.
insert(IncomingBB);
5299 if (TrivialUnwindBlocks.
empty())
5303 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5307 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5310 for (BasicBlock *Pred :
5321 TrivialBB->getTerminator()->eraseFromParent();
5322 new UnreachableInst(RI->
getContext(), TrivialBB);
5324 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5331 return !TrivialUnwindBlocks.empty();
5335bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5339 "Resume must unwind the exception that caused control to here");
5395 int Idx = DestPN.getBasicBlockIndex(BB);
5409 Value *SrcVal = DestPN.getIncomingValue(Idx);
5412 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5416 DestPN.addIncoming(
Incoming, Pred);
5443 std::vector<DominatorTree::UpdateType> Updates;
5447 if (UnwindDest ==
nullptr) {
5488 if (!SuccessorCleanupPad)
5497 SuccessorCleanupPad->eraseFromParent();
5506bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5523bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5555 BBI->dropDbgRecords();
5559 BBI->eraseFromParent();
5565 if (&BB->
front() != UI)
5568 std::vector<DominatorTree::UpdateType> Updates;
5571 for (BasicBlock *Predecessor : Preds) {
5578 [BB](
auto *
Successor) { return Successor == BB; })) {
5586 "The destinations are guaranteed to be different here.");
5587 CallInst *Assumption;
5603 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5605 SwitchInstProfUpdateWrapper SU(*SI);
5606 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5607 if (i->getCaseSuccessor() != BB) {
5612 i = SU.removeCase(i);
5617 if (DTU &&
SI->getDefaultDest() != BB)
5618 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5620 if (
II->getUnwindDest() == BB) {
5626 if (!CI->doesNotThrow())
5627 CI->setDoesNotThrow();
5631 if (CSI->getUnwindDest() == BB) {
5642 E = CSI->handler_end();
5645 CSI->removeHandler(
I);
5652 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5653 if (CSI->getNumHandlers() == 0) {
5654 if (CSI->hasUnwindDest()) {
5658 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5659 Updates.push_back({DominatorTree::Insert,
5660 PredecessorOfPredecessor,
5661 CSI->getUnwindDest()});
5662 Updates.push_back({DominatorTree::Delete,
5663 PredecessorOfPredecessor, Predecessor});
5666 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5673 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5674 for (BasicBlock *EHPred : EHPreds)
5678 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5679 CSI->eraseFromParent();
5684 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5685 "Expected to always have an unwind to BB.");
5687 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5710 for (
size_t I = 1,
E = Cases.
size();
I !=
E; ++
I) {
5711 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5719 bool RemoveOrigDefaultBlock =
true) {
5721 auto *BB = Switch->getParent();
5722 auto *OrigDefaultBlock = Switch->getDefaultDest();
5723 if (RemoveOrigDefaultBlock)
5724 OrigDefaultBlock->removePredecessor(BB);
5728 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5730 Switch->setDefaultDest(&*NewDefaultBlock);
5734 if (RemoveOrigDefaultBlock &&
5744bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5746 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5748 bool HasDefault = !
SI->defaultDestUnreachable();
5750 auto *BB =
SI->getParent();
5753 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5758 for (
auto Case :
SI->cases()) {
5762 if (Dest == DestA) {
5768 if (Dest == DestB) {
5778 "Single-destination switch should have been folded.");
5780 assert(DestB !=
SI->getDefaultDest());
5781 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5785 SmallVectorImpl<ConstantInt *> *ContiguousCases =
nullptr;
5789 ContiguousCases = &CasesA;
5790 ContiguousDest = DestA;
5793 ContiguousCases = &CasesB;
5794 ContiguousDest = DestB;
5803 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5806 if (!
Offset->isNullValue())
5815 BranchInst *NewBI = Builder.
CreateCondBr(Cmp, ContiguousDest, OtherDest);
5819 SmallVector<uint64_t, 8> Weights;
5821 if (Weights.
size() == 1 +
SI->getNumCases()) {
5822 uint64_t TrueWeight = 0;
5823 uint64_t FalseWeight = 0;
5824 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
5825 if (
SI->getSuccessor(
I) == ContiguousDest)
5826 TrueWeight += Weights[
I];
5828 FalseWeight += Weights[
I];
5830 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5840 unsigned PreviousEdges = ContiguousCases->
size();
5841 if (ContiguousDest ==
SI->getDefaultDest())
5843 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5847 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5848 if (OtherDest ==
SI->getDefaultDest())
5850 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5859 auto *UnreachableDefault =
SI->getDefaultDest();
5862 SI->eraseFromParent();
5864 if (!HasDefault && DTU)
5865 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5881 unsigned MaxSignificantBitsInCond =
5888 for (
const auto &Case :
SI->cases()) {
5889 auto *
Successor = Case.getCaseSuccessor();
5896 const APInt &CaseVal = Case.getCaseValue()->getValue();
5899 DeadCases.
push_back(Case.getCaseValue());
5911 bool HasDefault = !
SI->defaultDestUnreachable();
5912 const unsigned NumUnknownBits =
5915 if (HasDefault && DeadCases.
empty() &&
5916 NumUnknownBits < 64 ) {
5917 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5918 if (
SI->getNumCases() == AllNumCases) {
5925 if (
SI->getNumCases() == AllNumCases - 1) {
5926 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5933 for (
const auto &Case :
SI->cases())
5934 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5945 if (DeadCases.
empty())
5951 assert(CaseI !=
SI->case_default() &&
5952 "Case was not found. Probably mistake in DeadCases forming.");
5954 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
5959 std::vector<DominatorTree::UpdateType> Updates;
5960 for (
auto *
Successor : UniqueSuccessors)
5961 if (NumPerSuccessorCases[
Successor] == 0)
5982 if (!Branch || !Branch->isUnconditional())
5988 int Idx =
PHI.getBasicBlockIndex(BB);
5989 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
5991 Value *InValue =
PHI.getIncomingValue(Idx);
5992 if (InValue != CaseValue)
6008 ForwardingNodesMap ForwardingNodes;
6011 for (
const auto &Case :
SI->cases()) {
6013 BasicBlock *CaseDest = Case.getCaseSuccessor();
6032 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6033 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6034 count(Phi.blocks(), SwitchBlock) == 1) {
6035 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6043 ForwardingNodes[Phi].push_back(PhiIdx);
6046 for (
auto &ForwardingNode : ForwardingNodes) {
6047 PHINode *Phi = ForwardingNode.first;
6053 for (
int Index : Indexes)
6054 Phi->setIncomingValue(Index,
SI->getCondition());
6064 if (
C->isThreadDependent())
6066 if (
C->isDLLImportDependent())
6082 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6109 if (
A->isAllOnesValue())
6111 if (
A->isNullValue())
6117 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6142 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6144 if (
I.isTerminator()) {
6146 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6149 CaseDest =
I.getSuccessor(0);
6156 for (
auto &
Use :
I.uses()) {
6159 if (
I->getParent() == CaseDest)
6162 if (Phi->getIncomingBlock(
Use) == CaseDest)
6175 *CommonDest = CaseDest;
6177 if (CaseDest != *CommonDest)
6182 int Idx =
PHI.getBasicBlockIndex(Pred);
6195 Res.push_back(std::make_pair(&
PHI, ConstVal));
6198 return Res.
size() > 0;
6204 SwitchCaseResultVectorTy &UniqueResults,
6206 for (
auto &
I : UniqueResults) {
6207 if (
I.first == Result) {
6208 I.second.push_back(CaseVal);
6209 return I.second.size();
6212 UniqueResults.push_back(
6223 SwitchCaseResultVectorTy &UniqueResults,
6227 uintptr_t MaxUniqueResults) {
6228 for (
const auto &
I :
SI->cases()) {
6242 const size_t NumCasesForResult =
6250 if (UniqueResults.size() > MaxUniqueResults)
6266 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6268 return DefaultResult ||
SI->defaultDestUnreachable();
6285 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6286 ResultVector[1].second.size() == 1) {
6287 ConstantInt *FirstCase = ResultVector[0].second[0];
6288 ConstantInt *SecondCase = ResultVector[1].second[0];
6289 Value *SelectValue = ResultVector[1].first;
6290 if (DefaultResult) {
6291 Value *ValueCompare =
6292 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6293 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6294 DefaultResult,
"switch.select");
6296 Value *ValueCompare =
6297 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6298 return Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6299 SelectValue,
"switch.select");
6303 if (ResultVector.size() == 1 && DefaultResult) {
6305 unsigned CaseCount = CaseValues.
size();
6318 for (
auto *Case : CaseValues) {
6319 if (Case->getValue().slt(MinCaseVal->
getValue()))
6321 AndMask &= Case->getValue();
6331 if (FreeBits ==
Log2_32(CaseCount)) {
6332 Value *
And = Builder.CreateAnd(Condition, AndMask);
6333 Value *Cmp = Builder.CreateICmpEQ(
6335 return Builder.CreateSelect(Cmp, ResultVector[0].first,
6342 for (
auto *Case : CaseValues)
6343 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6349 Condition = Builder.CreateSub(Condition, MinCaseVal);
6350 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6351 Value *Cmp = Builder.CreateICmpEQ(
6353 return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6358 if (CaseValues.
size() == 2) {
6359 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6360 "switch.selectcmp.case1");
6361 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6362 "switch.selectcmp.case2");
6363 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6364 return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6377 std::vector<DominatorTree::UpdateType> Updates;
6384 Builder.CreateBr(DestBB);
6388 PHI->removeIncomingValueIf(
6389 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6390 PHI->addIncoming(SelectValue, SelectBB);
6393 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6399 if (DTU && RemovedSuccessors.
insert(Succ).second)
6402 SI->eraseFromParent();
6417 SwitchCaseResultVectorTy UniqueResults;
6423 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6424 Builder.SetInsertPoint(
SI);
6425 Value *SelectValue =
6438class SwitchReplacement {
6445 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6446 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6455 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6462 bool isLookupTable();
6496 ConstantInt *BitMap =
nullptr;
6497 IntegerType *BitMapElementTy =
nullptr;
6500 ConstantInt *LinearOffset =
nullptr;
6501 ConstantInt *LinearMultiplier =
nullptr;
6502 bool LinearMapValWrapped =
false;
6510SwitchReplacement::SwitchReplacement(
6512 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6513 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6514 : DefaultValue(DefaultValue) {
6515 assert(Values.size() &&
"Can't build lookup table without values!");
6516 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6519 SingleValue = Values.begin()->second;
6521 ValueType = Values.begin()->second->getType();
6525 for (
const auto &[CaseVal, CaseRes] : Values) {
6528 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6529 TableContents[Idx] = CaseRes;
6536 if (Values.size() < TableSize) {
6538 "Need a default value to fill the lookup table holes.");
6541 if (!TableContents[
I])
6542 TableContents[
I] = DefaultValue;
6548 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6549 SingleValue =
nullptr;
6555 Kind = SingleValueKind;
6562 bool LinearMappingPossible =
true;
6567 bool NonMonotonic =
false;
6568 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6585 LinearMappingPossible =
false;
6590 APInt Dist = Val - PrevVal;
6593 }
else if (Dist != DistToPrev) {
6594 LinearMappingPossible =
false;
6602 if (LinearMappingPossible) {
6604 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6605 APInt M = LinearMultiplier->getValue();
6606 bool MayWrap =
true;
6607 if (
isIntN(M.getBitWidth(), TableSize - 1))
6608 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6609 LinearMapValWrapped = NonMonotonic || MayWrap;
6610 Kind = LinearMapKind;
6616 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6618 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6620 TableInt <<=
IT->getBitWidth();
6624 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6627 BitMap = ConstantInt::get(M.getContext(), TableInt);
6628 BitMapElementTy =
IT;
6637 Kind = LookupTableKind;
6643 case SingleValueKind:
6645 case LinearMapKind: {
6649 false,
"switch.idx.cast");
6650 if (!LinearMultiplier->
isOne())
6651 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6653 !LinearMapValWrapped);
6655 if (!LinearOffset->
isZero())
6658 !LinearMapValWrapped);
6675 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
6676 "switch.shiftamt",
true,
true);
6679 Value *DownShifted =
6680 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6682 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6684 case LookupTableKind: {
6687 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
6688 true, GlobalVariable::PrivateLinkage,
6689 Initializer,
"switch.table." +
Func->getName());
6690 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6693 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
6694 Type *IndexTy =
DL.getIndexType(Table->getType());
6697 if (
Index->getType() != IndexTy) {
6698 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6702 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6705 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6708 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6714bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
6716 Type *ElementType) {
6724 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6726 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6732 if (
TTI.isTypeLegal(Ty))
6747 DL.fitsInLegalInteger(
IT->getBitWidth());
6750Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
6752bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
6763 return NumCases * 100 >= CaseRange * MinDensity;
6784 if (
SI->getNumCases() > TableSize)
6787 bool AllTablesFitInRegister =
true;
6788 bool HasIllegalType =
false;
6789 for (
const auto &Ty : ResultTypes) {
6794 AllTablesFitInRegister =
6795 AllTablesFitInRegister &&
6796 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
6801 if (HasIllegalType && !AllTablesFitInRegister)
6806 if (AllTablesFitInRegister)
6823 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6826 return all_of(ResultTypes, [&](
const auto &ResultType) {
6827 return SwitchReplacement::wouldFitInRegister(
6855 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6877 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6882 for (
auto ValuePair : Values) {
6885 if (!CaseConst || CaseConst == DefaultConst ||
6886 (CaseConst != TrueConst && CaseConst != FalseConst))
6900 if (DefaultConst == FalseConst) {
6903 ++NumTableCmpReuses;
6906 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6907 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6910 ++NumTableCmpReuses;
6920 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6934 if (
SI->getNumCases() < 3)
6956 MinCaseVal = CaseVal;
6958 MaxCaseVal = CaseVal;
6975 It->second.push_back(std::make_pair(CaseVal,
Value));
6983 bool HasDefaultResults =
6985 DefaultResultsList,
DL,
TTI);
6986 for (
const auto &
I : DefaultResultsList) {
6989 DefaultResults[
PHI] = Result;
6993 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6996 if (UseSwitchConditionAsTableIndex) {
6998 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7003 TableIndexOffset = MinCaseVal;
7010 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7012 bool TableHasHoles = (NumResults < TableSize);
7017 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7025 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7028 if (
SI->getNumCases() < 4)
7030 if (!
DL.fitsInLegalInteger(TableSize))
7039 if (UseSwitchConditionAsTableIndex) {
7040 TableIndex =
SI->getCondition();
7041 if (HasDefaultResults) {
7053 all_of(ResultTypes, [&](
const auto &ResultType) {
7054 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7059 TableSize = std::max(UpperBound, TableSize);
7062 DefaultIsReachable =
false;
7070 const auto &ResultList = ResultLists[
PHI];
7072 Type *ResultType = ResultList.begin()->second->getType();
7077 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7079 PhiToReplacementMap.
insert({
PHI, Replacement});
7082 bool AnyLookupTables =
any_of(
7083 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7091 if (AnyLookupTables &&
7092 (!
TTI.shouldBuildLookupTables() ||
7096 Builder.SetInsertPoint(
SI);
7099 if (!UseSwitchConditionAsTableIndex) {
7102 bool MayWrap =
true;
7103 if (!DefaultIsReachable) {
7108 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7109 "switch.tableidx",
false,
7113 std::vector<DominatorTree::UpdateType> Updates;
7119 assert(MaxTableSize >= TableSize &&
7120 "It is impossible for a switch to have more entries than the max "
7121 "representable value of its input integer type's size.");
7126 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7130 Builder.SetInsertPoint(
SI);
7131 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7132 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7133 Builder.CreateBr(LookupBB);
7139 Value *Cmp = Builder.CreateICmpULT(
7140 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7142 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7148 Builder.SetInsertPoint(LookupBB);
7154 MaskBB->
setName(
"switch.hole_check");
7161 APInt MaskInt(TableSizePowOf2, 0);
7162 APInt One(TableSizePowOf2, 1);
7164 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7165 for (
const auto &Result : ResultList) {
7168 MaskInt |= One << Idx;
7170 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7177 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7178 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7179 Value *LoBit = Builder.CreateTrunc(
7181 Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7186 Builder.SetInsertPoint(LookupBB);
7190 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7193 SI->getDefaultDest()->removePredecessor(BB,
7200 const ResultListTy &ResultList = ResultLists[
PHI];
7201 auto Replacement = PhiToReplacementMap.
at(
PHI);
7202 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7205 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7208 for (
auto *
User :
PHI->users()) {
7210 Replacement.getDefaultValue(), ResultList);
7214 PHI->addIncoming(Result, LookupBB);
7217 Builder.CreateBr(CommonDest);
7223 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
7226 if (Succ ==
SI->getDefaultDest())
7229 if (DTU && RemovedSuccessors.
insert(Succ).second)
7232 SI->eraseFromParent();
7238 ++NumLookupTablesHoles;
7254 if (CondTy->getIntegerBitWidth() > 64 ||
7255 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7259 if (
SI->getNumCases() < 4)
7267 for (
const auto &
C :
SI->cases())
7268 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7276 int64_t
Base = Values[0];
7277 for (
auto &V : Values)
7290 unsigned Shift = 64;
7291 for (
auto &V : Values)
7295 for (
auto &V : Values)
7296 V = (int64_t)((
uint64_t)V >> Shift);
7313 Builder.SetInsertPoint(
SI);
7315 Builder.CreateSub(
SI->getCondition(), ConstantInt::get(Ty,
Base));
7316 Value *Rot = Builder.CreateIntrinsic(
7317 Ty, Intrinsic::fshl,
7318 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7319 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7321 for (
auto Case :
SI->cases()) {
7322 auto *Orig = Case.getCaseValue();
7323 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7342 Value *Condition =
SI->getCondition();
7346 if (CondTy->getIntegerBitWidth() > 64 ||
7347 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7359 if (
SI->getNumCases() < 4)
7365 if (!
SI->defaultDestUnreachable())
7370 for (
const auto &Case :
SI->cases()) {
7371 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7385 Builder.SetInsertPoint(
SI);
7388 for (
auto &Case :
SI->cases()) {
7389 auto *OrigValue = Case.getCaseValue();
7390 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7391 OrigValue->getValue().countr_zero()));
7395 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7398 SI->setCondition(ConditionTrailingZeros);
7408 if (!Cmp || !Cmp->hasOneUse())
7419 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7422 if (
SI->getNumCases() == 2) {
7429 Succ =
SI->getDefaultDest();
7430 SuccWeight = Weights[0];
7432 for (
auto &Case :
SI->cases()) {
7433 std::optional<int64_t> Val =
7437 if (!Missing.erase(*Val))
7442 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7445 assert(Missing.size() == 1 &&
"Should have one case left");
7446 Res = *Missing.begin();
7447 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7449 Unreachable =
SI->getDefaultDest();
7451 for (
auto &Case :
SI->cases()) {
7452 BasicBlock *NewSucc = Case.getCaseSuccessor();
7453 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7456 OtherSuccWeight += Weight;
7459 SuccWeight = Weight;
7460 }
else if (Succ == NewSucc) {
7466 for (
auto &Case :
SI->cases()) {
7467 std::optional<int64_t> Val =
7469 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7471 if (Case.getCaseSuccessor() == Succ) {
7493 if (Cmp->isSigned())
7496 MDNode *NewWeights =
nullptr;
7502 Builder.SetInsertPoint(
SI->getIterator());
7503 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7504 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7505 SI->getMetadata(LLVMContext::MD_unpredictable));
7509 SI->eraseFromParent();
7510 Cmp->eraseFromParent();
7511 if (DTU && Unreachable)
7543 "Only supporting unconditional branches for now");
7545 "Expected unconditional branches to have one successor");
7546 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7567 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
7583 "Only supporting unconditional branches for now");
7590 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
7591 if (PredIVs[
A] != PredIVs[
B])
7600bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
7601 DomTreeUpdater *DTU) {
7607 SmallPtrSet<PHINode *, 8> Phis;
7608 SmallPtrSet<BasicBlock *, 8> Seen;
7609 DenseMap<PHINode *, SmallDenseMap<BasicBlock *, Value *, 8>> PhiPredIVs;
7610 DenseMap<BasicBlock *, SmallVector<unsigned, 32>> BBToSuccessorIndexes;
7614 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7619 if (BB->
size() != 1)
7629 if (!Seen.
insert(BB).second) {
7630 auto It = BBToSuccessorIndexes.
find(BB);
7631 if (It != BBToSuccessorIndexes.
end())
7632 It->second.emplace_back(
I);
7646 Cases.
emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
7647 BBToSuccessorIndexes[BB].emplace_back(
I);
7653 for (PHINode *Phi : Phis) {
7655 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
7656 for (
auto &
IV :
Phi->incoming_values())
7657 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
7668 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
7673 bool MadeChange =
false;
7674 for (
auto &SSW : Cases) {
7681 Updates.
push_back({DominatorTree::Delete,
SI->getParent(), SSW.Dest});
7682 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7683 for (
unsigned Idx : Successors)
7684 SI->setSuccessor(Idx, (*It)->Dest);
7695bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
7698 if (isValueEqualityComparison(SI)) {
7702 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7703 return requestResimplify();
7707 if (simplifySwitchOnSelect(SI,
Select))
7708 return requestResimplify();
7713 if (foldValueComparisonIntoPredecessors(SI, Builder))
7714 return requestResimplify();
7720 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7721 return requestResimplify();
7725 return requestResimplify();
7728 return requestResimplify();
7731 return requestResimplify();
7734 return requestResimplify();
7741 if (
Options.ConvertSwitchToLookupTable &&
7743 return requestResimplify();
7746 return requestResimplify();
7749 return requestResimplify();
7752 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7753 return requestResimplify();
7755 if (simplifyDuplicateSwitchArms(SI, DTU))
7756 return requestResimplify();
7761bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
7766 SmallPtrSet<Value *, 8> Succs;
7767 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
7772 RemovedSuccs.
insert(Dest);
7782 std::vector<DominatorTree::UpdateType> Updates;
7783 Updates.reserve(RemovedSuccs.
size());
7784 for (
auto *RemovedSucc : RemovedSuccs)
7785 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7804 if (simplifyIndirectBrOnSelect(IBI, SI))
7805 return requestResimplify();
7841 if (BB == OtherPred)
7852 std::vector<DominatorTree::UpdateType> Updates;
7859 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7860 "unexpected successor");
7861 II->setUnwindDest(OtherPred);
7876 Builder.CreateUnreachable();
7885bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder) {
7886 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7887 : simplifyCondBranch(
Branch, Builder);
7890bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
7902 bool NeedCanonicalLoop =
7916 if (
I->isTerminator() &&
7917 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7933 if (
Options.SpeculateBlocks &&
7936 return requestResimplify();
7944 if (!PPred || (PredPred && PredPred != PPred))
7981 if (!SuccBI || !SuccBI->isConditional())
7985 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7989 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8015 bool HasWeight =
false;
8020 BBTWeight = BBFWeight = 1;
8025 BB1TWeight = BB1FWeight = 1;
8030 BB2TWeight = BB2FWeight = 1;
8032 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8033 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8040bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder) {
8044 "Tautological conditional branch should have been eliminated already.");
8047 if (!
Options.SimplifyCondBranch ||
8052 if (isValueEqualityComparison(BI)) {
8057 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8058 return requestResimplify();
8064 if (foldValueComparisonIntoPredecessors(BI, Builder))
8065 return requestResimplify();
8068 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8069 return requestResimplify();
8074 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8087 return requestResimplify();
8093 if (
Options.SpeculateBlocks &&
8096 return requestResimplify();
8105 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8106 return requestResimplify();
8108 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8110 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8111 auto CanSpeculateConditionalLoadsStores = [&]() {
8113 for (Instruction &
I : *Succ) {
8114 if (
I.isTerminator()) {
8115 if (
I.getNumSuccessors() > 1)
8119 SpeculatedConditionalLoadsStores.
size() ==
8123 SpeculatedConditionalLoadsStores.
push_back(&
I);
8126 return !SpeculatedConditionalLoadsStores.
empty();
8129 if (CanSpeculateConditionalLoadsStores()) {
8131 std::nullopt,
nullptr);
8132 return requestResimplify();
8142 return requestResimplify();
8151 return requestResimplify();
8157 if (foldCondBranchOnValueKnownInPredecessor(BI))
8158 return requestResimplify();
8163 if (PBI != BI && PBI->isConditional())
8165 return requestResimplify();
8171 if (PBI != BI && PBI->isConditional())
8173 return requestResimplify();
8177 return requestResimplify();
8184 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8196 auto *Use = cast<Instruction>(U.getUser());
8198 switch (Use->getOpcode()) {
8201 case Instruction::GetElementPtr:
8202 case Instruction::Ret:
8203 case Instruction::BitCast:
8204 case Instruction::Load:
8205 case Instruction::Store:
8206 case Instruction::Call:
8207 case Instruction::CallBr:
8208 case Instruction::Invoke:
8209 case Instruction::UDiv:
8210 case Instruction::URem:
8214 case Instruction::SDiv:
8215 case Instruction::SRem:
8219 if (FindUse ==
I->use_end())
8221 auto &
Use = *FindUse;
8226 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8227 User->comesBefore(
I))
8241 if (
GEP->getPointerOperand() ==
I) {
8244 if (
GEP->getType()->isVectorTy())
8252 if (!
GEP->hasAllZeroIndices() &&
8253 (!
GEP->isInBounds() ||
8255 GEP->getPointerAddressSpace())))
8256 PtrValueMayBeModified =
true;
8262 bool HasNoUndefAttr =
8263 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8268 if (
C->isNullValue() && HasNoUndefAttr &&
8269 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8270 return !PtrValueMayBeModified;
8276 if (!LI->isVolatile())
8278 LI->getPointerAddressSpace());
8282 if (!
SI->isVolatile())
8284 SI->getPointerAddressSpace())) &&
8285 SI->getPointerOperand() ==
I;
8290 if (
I == Assume->getArgOperand(0))
8298 if (CB->getCalledOperand() ==
I)
8301 if (CB->isArgOperand(&
Use)) {
8302 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8305 CB->paramHasNonNullAttr(ArgIdx,
false))
8306 return !PtrValueMayBeModified;
8325 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8335 Builder.CreateUnreachable();
8342 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8344 Assumption = Builder.CreateAssumption(
Cond);
8359 Builder.SetInsertPoint(Unreachable);
8361 Builder.CreateUnreachable();
8362 for (
const auto &Case :
SI->cases())
8363 if (Case.getCaseSuccessor() == BB) {
8365 Case.setSuccessor(Unreachable);
8367 if (
SI->getDefaultDest() == BB) {
8369 SI->setDefaultDest(Unreachable);
8383bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8408 return requestResimplify();
8429 if (
Options.SpeculateBlocks &&
8436 Options.SpeculateUnpredictables))
8443 case Instruction::Br:
8446 case Instruction::Resume:
8449 case Instruction::CleanupRet:
8452 case Instruction::Switch:
8455 case Instruction::Unreachable:
8458 case Instruction::IndirectBr:
8466bool SimplifyCFGOpt::run(BasicBlock *BB) {
8476 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
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...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool simplifySwitchLookup(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 bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
static 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 void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL)
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
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}...
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static void fitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool casesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
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...
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static 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 bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI 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 isZero() const
Determine if this value is zero, i.e. all bits are clear.
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.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
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.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
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.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI 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.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI 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,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
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...
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
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 LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI 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.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI 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...
LLVM_ABI 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 LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
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.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
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.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
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.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
LLVM_ABI 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 SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
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...
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...
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)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
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 * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
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.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI 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.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI 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.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
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.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
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)
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()
static unsigned getPointerOperandIndex()
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...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
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.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI 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.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI 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.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
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)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
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< 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.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
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)
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find 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.
LLVM_ABI 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)
LLVM_ABI 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 @...
LLVM_ABI 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...
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
auto pred_end(const MachineBasicBlock *BB)
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<>...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI 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.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
auto reverse(ContainerTy &&C)
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
LLVM_ABI 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...
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI 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.
LLVM_ABI 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...
@ Sub
Subtraction 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 RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI 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.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
LLVM_ABI bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI 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 ...
LLVM_ABI 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.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI 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...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI 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.
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
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.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.