96#define DEBUG_TYPE "simplifycfg"
101 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
104 "Temporary development switch used to gradually uplift SimplifyCFG "
105 "into preserving DomTree,"));
114 "Control the amount of phi node folding to perform (default = 2)"));
118 cl::desc(
"Control the maximal total instruction cost that we are willing "
119 "to speculatively execute to fold a 2-entry PHI node into a "
120 "select (default = 4)"));
124 cl::desc(
"Hoist common instructions up to the parent block"));
128 cl::desc(
"Hoist loads if the target supports conditional faulting"));
132 cl::desc(
"Hoist stores if the target supports conditional faulting"));
136 cl::desc(
"Control the maximal conditional load/store that we are willing "
137 "to speculatively execute to eliminate conditional branch "
143 cl::desc(
"Allow reordering across at most this many "
144 "instructions when hoisting"));
148 cl::desc(
"Sink common instructions down to the end block"));
152 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
156 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
157 "precede - hoist multiple conditional stores into a single "
158 "predicated store"));
162 cl::desc(
"When merging conditional stores, do so even if the resultant "
163 "basic blocks are unlikely to be if-converted as a result"));
167 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
172 cl::desc(
"Limit maximum recursion depth when calculating costs of "
173 "speculatively executed instructions"));
178 cl::desc(
"Max size of a block which is still considered "
179 "small enough to thread through"));
185 cl::desc(
"Maximum cost of combining conditions when "
186 "folding branches"));
189 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
191 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
192 "to fold branch to common destination when vector operations are "
197 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
201 cl::desc(
"Limit cases to analyze when converting a switch to select"));
205 cl::desc(
"Limit number of blocks searched to prove that threading through "
206 "a loop header keeps the loop canonical"));
210 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
217STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
219 "Number of switch instructions turned into linear mapping");
221 "Number of switch instructions turned into lookup tables");
223 NumLookupTablesHoles,
224 "Number of switch instructions turned into lookup tables (holes checked)");
225STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
227 "Number of value comparisons folded into predecessor basic blocks");
229 "Number of branches folded into predecessor basic block");
232 "Number of common instruction 'blocks' hoisted up to the begin block");
234 "Number of common instructions hoisted up to the begin block");
236 "Number of common instruction 'blocks' sunk down to the end block");
238 "Number of common instructions sunk down to the end block");
239STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
241 "Number of invokes with empty resume blocks simplified into calls");
242STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
243STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
250using SwitchCaseResultVectorTy =
259struct ValueEqualityComparisonCase {
271 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
274class SimplifyCFGOpt {
275 const TargetTransformInfo &TTI;
277 const DataLayout &DL;
279 const SimplifyCFGOptions &Options;
282 Value *isValueEqualityComparison(Instruction *TI);
284 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
285 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
288 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
291 bool foldValueComparisonIntoPredecessors(Instruction *TI,
294 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
295 bool simplifySingleResume(ResumeInst *RI);
296 bool simplifyCommonResume(ResumeInst *RI);
297 bool simplifyCleanupReturn(CleanupReturnInst *RI);
298 bool simplifyUnreachable(UnreachableInst *UI);
299 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
300 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
301 bool simplifyIndirectBr(IndirectBrInst *IBI);
302 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
303 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
304 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
306 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
308 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
311 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
312 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
313 Instruction *TI, Instruction *I1,
314 SmallVectorImpl<Instruction *> &OtherSuccTIs,
316 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
317 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
318 BasicBlock *TrueBB, BasicBlock *FalseBB,
319 uint32_t TrueWeight, uint32_t FalseWeight);
320 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
321 const DataLayout &DL);
322 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
323 bool simplifySwitchOnSelectRemap(SwitchInst *SI, SelectInst *
Select,
Value *
X,
324 ConstantInt *
C,
bool Negate);
325 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
326 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
327 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
330 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
332 const SimplifyCFGOptions &Opts)
333 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
334 assert((!DTU || !DTU->hasPostDomTree()) &&
335 "SimplifyCFG is not yet capable of maintaining validity of a "
336 "PostDomTree, so don't ask for it.");
339 bool simplifyOnce(BasicBlock *BB);
340 bool run(BasicBlock *BB);
343 bool requestResimplify() {
353isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
373 "Only for a pair of incoming blocks at the time!");
379 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
380 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
383 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
384 EquivalenceSet->contains(IV1))
407 if (!SI1Succs.
count(Succ))
413 FailBlocks->insert(Succ);
429 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
431 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
432 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
494 if (AggressiveInsts.
count(
I))
510 ZeroCostInstructions.
insert(OverflowInst);
512 }
else if (!ZeroCostInstructions.
contains(
I))
528 for (
Use &
Op :
I->operands())
530 TTI, AC, ZeroCostInstructions,
Depth + 1))
547 if (
DL.hasUnstableRepresentation(
V->getType()))
556 return ConstantInt::get(
IntPtrTy, 0);
561 if (CE->getOpcode() == Instruction::IntToPtr)
585struct ConstantComparesGatherer {
586 const DataLayout &DL;
589 Value *CompValue =
nullptr;
592 Value *Extra =
nullptr;
598 unsigned UsedICmps = 0;
604 bool IgnoreFirstMatch =
false;
605 bool MultipleMatches =
false;
608 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
610 if (CompValue || !MultipleMatches)
615 IgnoreFirstMatch =
true;
619 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
620 ConstantComparesGatherer &
621 operator=(
const ConstantComparesGatherer &) =
delete;
626 bool setValueOnce(
Value *NewVal) {
627 if (IgnoreFirstMatch) {
628 IgnoreFirstMatch =
false;
631 if (CompValue && CompValue != NewVal) {
632 MultipleMatches =
true;
646 bool matchInstruction(Instruction *
I,
bool isEQ) {
653 if (!setValueOnce(Val))
673 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
717 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
719 if (!setValueOnce(RHSVal))
724 ConstantInt::get(
C->getContext(),
725 C->getValue() | Mask));
740 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
742 if (!setValueOnce(RHSVal))
746 Vals.push_back(ConstantInt::get(
C->getContext(),
747 C->getValue() & ~Mask));
768 Value *CandidateVal =
I->getOperand(0);
771 CandidateVal = RHSVal;
786 if (!setValueOnce(CandidateVal))
792 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
813 SmallVector<Value *, 8> DFT{Op0, Op1};
814 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
816 while (!DFT.
empty()) {
823 if (Visited.
insert(Op1).second)
825 if (Visited.
insert(Op0).second)
832 if (matchInstruction(
I, IsEq))
873 CV =
SI->getCondition();
875 if (BI->getCondition()->hasOneUse()) {
880 if (Trunc->hasNoUnsignedWrap())
881 CV = Trunc->getOperand(0);
888 Value *Ptr = PTII->getPointerOperand();
889 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
891 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
900BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
901 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
903 Cases.reserve(
SI->getNumCases());
904 for (
auto Case :
SI->cases())
905 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
906 Case.getCaseSuccessor()));
907 return SI->getDefaultDest();
912 ICmpInst::Predicate
Pred;
918 Pred = ICmpInst::ICMP_NE;
923 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
931 std::vector<ValueEqualityComparisonCase> &Cases) {
937 std::vector<ValueEqualityComparisonCase> &C2) {
938 std::vector<ValueEqualityComparisonCase> *
V1 = &
C1, *V2 = &C2;
941 if (
V1->size() > V2->size())
946 if (
V1->size() == 1) {
949 for (
const ValueEqualityComparisonCase &
VECC : *V2)
950 if (TheVal ==
VECC.Value)
957 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
958 while (i1 != e1 && i2 != e2) {
976bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
978 Value *PredVal = isValueEqualityComparison(
Pred->getTerminator());
982 Value *ThisVal = isValueEqualityComparison(TI);
983 assert(ThisVal &&
"This isn't a value comparison!!");
984 if (ThisVal != PredVal)
991 std::vector<ValueEqualityComparisonCase> PredCases;
993 getValueEqualityComparisonCases(
Pred->getTerminator(), PredCases);
998 std::vector<ValueEqualityComparisonCase> ThisCases;
999 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1007 if (PredDef == TIBB) {
1018 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1024 ThisCases[0].Dest->removePredecessor(TIBB);
1027 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1033 DTU->
applyUpdates({{DominatorTree::Delete, TIBB, ThisCases[0].Dest}});
1040 SmallPtrSet<Constant *, 16> DeadCases;
1041 for (
const ValueEqualityComparisonCase &Case : PredCases)
1042 DeadCases.
insert(Case.Value);
1045 <<
"Through successor TI: " << *TI);
1047 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1050 auto *
Successor = i->getCaseSuccessor();
1053 if (DeadCases.
count(i->getCaseValue())) {
1062 std::vector<DominatorTree::UpdateType> Updates;
1063 for (
const auto &
I : NumPerSuccessorCases)
1065 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1075 ConstantInt *TIV =
nullptr;
1076 for (
const auto &[
Value, Dest] : PredCases)
1082 assert(TIV &&
"No edge from pred to succ?");
1086 for (
const auto &[
Value, Dest] : ThisCases)
1094 TheRealDest = ThisDef;
1096 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1101 if (Succ != CheckEdge) {
1102 if (Succ != TheRealDest)
1103 RemovedSuccs.
insert(Succ);
1106 CheckEdge =
nullptr;
1113 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1118 SmallVector<DominatorTree::UpdateType, 2> Updates;
1120 for (
auto *RemovedSucc : RemovedSuccs)
1121 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1132struct ConstantIntOrdering {
1133 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1134 return LHS->getValue().ult(
RHS->getValue());
1146 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1155 assert(MD &&
"Invalid branch-weight metadata");
1180 if (BonusInst.isTerminator())
1215 NewBonusInst->
takeName(&BonusInst);
1216 BonusInst.setName(NewBonusInst->
getName() +
".old");
1217 VMap[&BonusInst] = NewBonusInst;
1226 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1227 "If the user is not a PHI node, then it should be in the same "
1228 "block as, and come after, the original bonus instruction.");
1232 if (PN->getIncomingBlock(U) == BB)
1236 assert(PN->getIncomingBlock(U) == PredBlock &&
1237 "Not in block-closed SSA form?");
1238 U.set(NewBonusInst);
1248 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1249 PredDL.isSameSourceLocation(
DL)) {
1256bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1264 std::vector<ValueEqualityComparisonCase> BBCases;
1265 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1267 std::vector<ValueEqualityComparisonCase> PredCases;
1268 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1273 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1276 SmallVector<uint64_t, 8> Weights;
1280 if (PredHasWeights) {
1283 if (Weights.
size() != 1 + PredCases.size())
1284 PredHasWeights = SuccHasWeights =
false;
1285 }
else if (SuccHasWeights)
1289 Weights.
assign(1 + PredCases.size(), 1);
1291 SmallVector<uint64_t, 8> SuccWeights;
1292 if (SuccHasWeights) {
1295 if (SuccWeights.
size() != 1 + BBCases.size())
1296 PredHasWeights = SuccHasWeights =
false;
1297 }
else if (PredHasWeights)
1298 SuccWeights.
assign(1 + BBCases.size(), 1);
1300 if (PredDefault == BB) {
1303 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1304 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1305 if (PredCases[i].Dest != BB)
1306 PTIHandled.insert(PredCases[i].
Value);
1309 std::swap(PredCases[i], PredCases.back());
1311 if (PredHasWeights || SuccHasWeights) {
1313 Weights[0] += Weights[i + 1];
1318 PredCases.pop_back();
1324 if (PredDefault != BBDefault) {
1326 if (DTU && PredDefault != BB)
1327 Updates.
push_back({DominatorTree::Delete,
Pred, PredDefault});
1328 PredDefault = BBDefault;
1329 ++NewSuccessors[BBDefault];
1332 unsigned CasesFromPred = Weights.
size();
1334 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1335 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1336 PredCases.push_back(BBCases[i]);
1337 ++NewSuccessors[BBCases[i].Dest];
1338 if (SuccHasWeights || PredHasWeights) {
1342 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1343 ValidTotalSuccWeight += SuccWeights[i + 1];
1347 if (SuccHasWeights || PredHasWeights) {
1348 ValidTotalSuccWeight += SuccWeights[0];
1350 for (
unsigned i = 1; i < CasesFromPred; ++i)
1351 Weights[i] *= ValidTotalSuccWeight;
1353 Weights[0] *= SuccWeights[0];
1359 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1360 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1361 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1362 if (PredCases[i].Dest == BB) {
1363 PTIHandled.insert(PredCases[i].
Value);
1365 if (PredHasWeights || SuccHasWeights) {
1366 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1371 std::swap(PredCases[i], PredCases.back());
1372 PredCases.pop_back();
1379 for (
const ValueEqualityComparisonCase &Case : BBCases)
1380 if (PTIHandled.count(Case.Value)) {
1382 if (PredHasWeights || SuccHasWeights)
1383 Weights.
push_back(WeightsForHandled[Case.Value]);
1384 PredCases.push_back(Case);
1385 ++NewSuccessors[Case.Dest];
1386 PTIHandled.erase(Case.Value);
1391 for (ConstantInt *
I : PTIHandled) {
1392 if (PredHasWeights || SuccHasWeights)
1394 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1395 ++NewSuccessors[BBDefault];
1402 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1407 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1409 for (
auto I :
seq(NewSuccessor.second)) {
1413 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1414 Updates.
push_back({DominatorTree::Insert,
Pred, NewSuccessor.first});
1421 "Should not end up here with unstable pointers");
1427 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1429 for (ValueEqualityComparisonCase &
V : PredCases)
1432 if (PredHasWeights || SuccHasWeights)
1440 if (MDNode *Unpredictable = PTI->
getMetadata(LLVMContext::MD_unpredictable))
1441 if (TI->
hasMetadata(LLVMContext::MD_unpredictable))
1442 NewSI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
1452 if (!InfLoopBlock) {
1460 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1467 Updates.
push_back({DominatorTree::Insert,
Pred, InfLoopBlock});
1474 ++NumFoldValueComparisonIntoPredecessors;
1482bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1485 Value *CV = isValueEqualityComparison(TI);
1486 assert(CV &&
"Not a comparison?");
1497 while (!Preds.empty()) {
1506 Value *PCV = isValueEqualityComparison(PTI);
1510 SmallSetVector<BasicBlock *, 4> FailBlocks;
1512 for (
auto *Succ : FailBlocks) {
1518 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1532 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1533 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1534 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1556 if (
I->mayReadFromMemory())
1588 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1596 if (J->getParent() == BB)
1618 if (
C1->isMustTailCall() != C2->isMustTailCall())
1621 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1627 if (CB1->cannotMerge() || CB1->isConvergent())
1630 if (CB2->cannotMerge() || CB2->isConvergent())
1645 if (!I1->hasDbgRecords())
1647 using CurrentAndEndIt =
1648 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1654 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1655 return Pair.first == Pair.second;
1661 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1667 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1669 if (!
Other->hasDbgRecords())
1672 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1679 while (
none_of(Itrs, atEnd)) {
1680 bool HoistDVRs = allIdentical(Itrs);
1681 for (CurrentAndEndIt &Pair : Itrs) {
1695 if (I1->isIdenticalToWhenDefined(I2,
true))
1700 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1701 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1702 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1704 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1705 return I1->getOperand(0) == I2->
getOperand(1) &&
1771 auto &Context = BI->
getParent()->getContext();
1776 Value *Mask =
nullptr;
1777 Value *MaskFalse =
nullptr;
1778 Value *MaskTrue =
nullptr;
1779 if (Invert.has_value()) {
1780 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1781 Mask = Builder.CreateBitCast(
1786 MaskFalse = Builder.CreateBitCast(
1788 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1790 auto PeekThroughBitcasts = [](
Value *
V) {
1792 V = BitCast->getOperand(0);
1795 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1797 if (!Invert.has_value())
1798 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1803 auto *Op0 =
I->getOperand(0);
1804 CallInst *MaskedLoadStore =
nullptr;
1807 auto *Ty =
I->getType();
1809 Value *PassThru =
nullptr;
1810 if (Invert.has_value())
1811 for (
User *U :
I->users()) {
1813 PassThru = Builder.CreateBitCast(
1822 Builder.SetInsertPoint(Ins);
1825 MaskedLoadStore = Builder.CreateMaskedLoad(
1827 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range)) {
1836 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1839 I->replaceAllUsesWith(NewLoadStore);
1842 auto *StoredVal = Builder.CreateBitCast(
1844 MaskedLoadStore = Builder.CreateMaskedStore(
1853 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1857 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1858 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1861 I->eraseFromParent();
1868 bool IsStore =
false;
1891bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1892 bool AllInstsEqOnly) {
1908 for (
auto *Succ : UniqueSuccessors) {
1924 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1926 for (
auto *Succ : UniqueSuccessors) {
1930 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1933 if (AllInstsEqOnly) {
1939 unsigned Size0 = UniqueSuccessors[0]->size();
1940 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1944 Succ->
size() == Size0;
1948 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1949 while (LRI.isValid()) {
1951 if (
any_of(*LRI, [I0](Instruction *
I) {
1965 unsigned NumSkipped = 0;
1968 if (SuccIterPairs.
size() > 2) {
1971 if (SuccIterPairs.
size() < 2)
1978 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1979 auto &BB1ItrPair = *SuccIterPairBegin++;
1980 auto OtherSuccIterPairRange =
1986 bool AllInstsAreIdentical =
true;
1987 bool HasTerminator =
I1->isTerminator();
1988 for (
auto &SuccIter : OtherSuccIterRange) {
1992 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1993 AllInstsAreIdentical =
false;
1996 SmallVector<Instruction *, 8> OtherInsts;
1997 for (
auto &SuccIter : OtherSuccIterRange)
2002 if (HasTerminator) {
2006 if (NumSkipped || !AllInstsAreIdentical) {
2011 return hoistSuccIdenticalTerminatorToSwitchOrIf(
2012 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
2016 if (AllInstsAreIdentical) {
2017 unsigned SkipFlagsBB1 = BB1ItrPair.second;
2018 AllInstsAreIdentical =
2020 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
2022 unsigned SkipFlagsBB2 = Pair.second;
2037 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2038 AllInstsAreIdentical =
2039 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2044 if (AllInstsAreIdentical) {
2054 for (
auto &SuccIter : OtherSuccIterRange) {
2062 assert(
Success &&
"We should not be trying to hoist callbases "
2063 "with non-intersectable attributes");
2081 unsigned SkippedFlags = 0;
2082 for (
const SuccIterPair &
P : SuccIterPairs)
2083 SkippedFlags |=
P.second;
2086 I1->dropUBImplyingAttrsAndMetadata();
2089 NumHoistCommonCode += SuccIterPairs.size();
2091 NumHoistCommonInstrs += SuccIterPairs.size();
2100 for (
auto &SuccIterPair : SuccIterPairs) {
2109bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2110 Instruction *TI, Instruction *I1,
2111 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2121 auto *I2 = *OtherSuccTIs.
begin();
2141 for (PHINode &PN : Succ->
phis()) {
2142 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2143 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2144 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2164 if (!
NT->getType()->isVoidTy()) {
2165 I1->replaceAllUsesWith(NT);
2166 for (Instruction *OtherSuccTI : OtherSuccTIs)
2167 OtherSuccTI->replaceAllUsesWith(NT);
2171 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2177 for (
auto *OtherSuccTI : OtherSuccTIs)
2178 Locs.
push_back(OtherSuccTI->getDebugLoc());
2190 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2192 for (PHINode &PN : Succ->
phis()) {
2193 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2194 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2200 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2210 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2211 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2212 PN.setIncomingValue(i, SI);
2220 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2224 if (DTU && VisitedSuccs.
insert(Succ).second)
2225 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2231 for (BasicBlock *Succ : UniqueSuccessors)
2232 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2246 if (
I->isIntDivRem())
2261 std::optional<unsigned> NumUses;
2262 for (
auto *
I : Insts) {
2265 I->getType()->isTokenTy())
2270 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2278 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2282 NumUses =
I->getNumUses();
2283 else if (NumUses !=
I->getNumUses())
2289 for (
auto *
I : Insts) {
2303 for (
const Use &U : I0->
uses()) {
2304 auto It = PHIOperands.find(&U);
2305 if (It == PHIOperands.end())
2308 if (!
equal(Insts, It->second))
2322 if (HaveIndirectCalls) {
2323 if (!AllCallsAreIndirect)
2327 Value *Callee =
nullptr;
2331 Callee = CurrCallee;
2332 else if (Callee != CurrCallee)
2338 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2344 if (!
all_of(Insts, SameAsI0)) {
2349 !
all_of(Insts, CanReplaceOperand))
2353 for (
auto *
I : Insts)
2354 Ops.push_back(
I->getOperand(OI));
2364 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2369 for (
auto *BB : Blocks) {
2371 I =
I->getPrevNode();
2396 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2399 PN->insertBefore(BBEnd->begin());
2400 for (
auto *
I : Insts)
2401 PN->addIncoming(
I->getOperand(O),
I->getParent());
2410 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2413 for (
auto *
I : Insts)
2433 assert(
Success &&
"We should not be trying to sink callbases "
2434 "with non-intersectable attributes");
2445 PN->replaceAllUsesWith(I0);
2446 PN->eraseFromParent();
2450 for (
auto *
I : Insts) {
2455 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2456 I->replaceAllUsesWith(I0);
2457 I->eraseFromParent();
2507 bool HaveNonUnconditionalPredecessors =
false;
2513 HaveNonUnconditionalPredecessors =
true;
2515 if (UnconditionalPreds.
size() < 2)
2528 for (
const Use &U : PN.incoming_values())
2529 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2530 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2532 Ops.push_back(*IncomingVals[
Pred]);
2540 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2553 if (!followedByDeoptOrUnreachable) {
2555 auto IsMemOperand = [](
Use &U) {
2568 unsigned NumPHIInsts = 0;
2569 for (
Use &U : (*LRI)[0]->operands()) {
2570 auto It = PHIOperands.
find(&U);
2572 return InstructionsToSink.contains(V);
2579 if (IsMemOperand(U) &&
2580 any_of(It->second, [](
Value *
V) { return isa<GEPOperator>(V); }))
2587 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2588 return NumPHIInsts <= 1;
2605 while (Idx < ScanIdx) {
2606 if (!ProfitableToSinkInstruction(LRI)) {
2609 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2622 if (Idx < ScanIdx) {
2625 InstructionsToSink = InstructionsProfitableToSink;
2631 !ProfitableToSinkInstruction(LRI) &&
2632 "We already know that the last instruction is unprofitable to sink");
2640 for (
auto *
I : *LRI)
2641 InstructionsProfitableToSink.
erase(
I);
2642 if (!ProfitableToSinkInstruction(LRI)) {
2645 InstructionsToSink = InstructionsProfitableToSink;
2659 if (HaveNonUnconditionalPredecessors) {
2660 if (!followedByDeoptOrUnreachable) {
2668 bool Profitable =
false;
2669 while (Idx < ScanIdx) {
2703 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2705 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2713 NumSinkCommonInstrs++;
2717 ++NumSinkCommonCode;
2723struct CompatibleSets {
2724 using SetTy = SmallVector<InvokeInst *, 2>;
2730 SetTy &getCompatibleSet(InvokeInst *
II);
2732 void insert(InvokeInst *
II);
2735CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2740 for (CompatibleSets::SetTy &Set : Sets) {
2741 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2746 return Sets.emplace_back();
2749void CompatibleSets::insert(InvokeInst *
II) {
2750 getCompatibleSet(
II).emplace_back(
II);
2754 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2757 auto IsIllegalToMerge = [](InvokeInst *
II) {
2758 return II->cannotMerge() ||
II->isInlineAsm();
2760 if (
any_of(Invokes, IsIllegalToMerge))
2768 if (HaveIndirectCalls) {
2769 if (!AllCallsAreIndirect)
2774 for (InvokeInst *
II : Invokes) {
2775 Value *CurrCallee =
II->getCalledOperand();
2776 assert(CurrCallee &&
"There is always a called operand.");
2779 else if (Callee != CurrCallee)
2786 auto HasNormalDest = [](InvokeInst *
II) {
2789 if (
any_of(Invokes, HasNormalDest)) {
2792 if (!
all_of(Invokes, HasNormalDest))
2797 for (InvokeInst *
II : Invokes) {
2799 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2801 NormalBB = CurrNormalBB;
2802 else if (NormalBB != CurrNormalBB)
2810 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2819 for (InvokeInst *
II : Invokes) {
2821 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2823 UnwindBB = CurrUnwindBB;
2825 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2832 Invokes.front()->getUnwindDest(),
2833 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2838 const InvokeInst *II0 = Invokes.front();
2839 for (
auto *
II : Invokes.drop_front())
2844 auto IsIllegalToMergeArguments = [](
auto Ops) {
2845 Use &U0 = std::get<0>(
Ops);
2846 Use &U1 = std::get<1>(
Ops);
2852 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2853 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2854 IsIllegalToMergeArguments))
2866 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2872 bool HasNormalDest =
2877 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2881 II0->
getParent()->getIterator()->getNextNode();
2886 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2890 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2892 if (!HasNormalDest) {
2896 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2904 return MergedInvoke;
2918 SuccBBOfMergedInvoke});
2941 return II->getOperand(U.getOperandNo()) != U.get();
2960 Invokes.
front()->getParent());
2968 if (!MergedDebugLoc)
2969 MergedDebugLoc =
II->getDebugLoc();
2977 OrigSuccBB->removePredecessor(
II->getParent());
2983 assert(
Success &&
"Merged invokes with incompatible attributes");
2986 II->replaceAllUsesWith(MergedInvoke);
2987 II->eraseFromParent();
2991 ++NumInvokeSetsFormed;
3027 CompatibleSets Grouper;
3037 if (Invokes.
size() < 2)
3049class EphemeralValueTracker {
3050 SmallPtrSet<const Instruction *, 32> EphValues;
3052 bool isEphemeral(
const Instruction *
I) {
3055 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3056 all_of(
I->users(), [&](
const User *U) {
3057 return EphValues.count(cast<Instruction>(U));
3062 bool track(
const Instruction *
I) {
3063 if (isEphemeral(
I)) {
3116 unsigned MaxNumInstToLookAt = 9;
3120 if (!MaxNumInstToLookAt)
3122 --MaxNumInstToLookAt;
3135 if (
SI->getPointerOperand() == StorePtr &&
3136 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3137 SI->getAlign() >= StoreToHoist->
getAlign()) {
3139 PreviousAccess =
SI;
3140 return SI->getValueOperand();
3146 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3147 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3149 bool ExplicitlyDereferenceableOnly;
3157 (!ExplicitlyDereferenceableOnly ||
3161 PreviousAccess = LI;
3176 unsigned &SpeculatedInstructions,
3184 bool HaveRewritablePHIs =
false;
3186 Value *OrigV = PN.getIncomingValueForBlock(BB);
3187 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3194 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3203 HaveRewritablePHIs =
true;
3206 if (!OrigCE && !ThenCE)
3213 if (OrigCost + ThenCost > MaxCost)
3220 ++SpeculatedInstructions;
3221 if (SpeculatedInstructions > 1)
3225 return HaveRewritablePHIs;
3229 std::optional<bool> Invert,
3233 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3240 if (!Invert.has_value())
3243 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3247 return BIEndProb < Likely;
3287bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3288 BasicBlock *ThenBB) {
3299 bool Invert =
false;
3314 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3316 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3318 unsigned SpeculatedInstructions = 0;
3319 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3320 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3321 Value *SpeculatedStoreValue =
nullptr;
3322 StoreInst *SpeculatedStore =
nullptr;
3324 EphemeralValueTracker EphTracker;
3339 if (EphTracker.track(&
I))
3344 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3346 SpeculatedConditionalLoadsStores.
size() <
3350 if (IsSafeCheapLoadStore)
3351 SpeculatedConditionalLoadsStores.
push_back(&
I);
3353 ++SpeculatedInstructions;
3355 if (SpeculatedInstructions > 1)
3359 if (!IsSafeCheapLoadStore &&
3363 PreviousStoreAccess))))
3365 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3371 if (!SpeculatedStore && SpeculatedStoreValue)
3377 for (Use &
Op :
I.operands()) {
3382 ++SinkCandidateUseCounts[OpI];
3389 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3390 if (Inst->hasNUses(
Count)) {
3391 ++SpeculatedInstructions;
3392 if (SpeculatedInstructions > 1)
3399 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3402 SpeculatedInstructions,
Cost,
TTI);
3403 if (!Convert ||
Cost > Budget)
3407 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3412 if (SpeculatedStoreValue) {
3416 Value *FalseV = SpeculatedStoreValue;
3420 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3450 for (DbgVariableRecord *DbgAssign :
3453 DbgAssign->replaceVariableLocationOp(OrigV, S);
3463 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3465 I.dropUBImplyingAttrsAndMetadata();
3467 assert(PreviousStoreAccess &&
"Missing previous store access");
3470 I.dropUBImplyingAttrsAndMetadata();
3471 I.setAAMetadata(MergedAA);
3475 if (EphTracker.contains(&
I)) {
3477 I.eraseFromParent();
3483 for (
auto &It : *ThenBB)
3488 !DVR || !DVR->isDbgAssign())
3489 It.dropOneDbgRecord(&DR);
3491 std::prev(ThenBB->end()));
3493 if (!SpeculatedConditionalLoadsStores.
empty())
3499 for (PHINode &PN : EndBB->
phis()) {
3500 unsigned OrigI = PN.getBasicBlockIndex(BB);
3501 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3502 Value *OrigV = PN.getIncomingValue(OrigI);
3503 Value *ThenV = PN.getIncomingValue(ThenI);
3512 Value *TrueV = ThenV, *FalseV = OrigV;
3517 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3518 PN.setIncomingValue(OrigI,
V);
3519 PN.setIncomingValue(ThenI,
V);
3523 for (Instruction *
I : SpeculatedPseudoProbes)
3524 I->eraseFromParent();
3537 if (!ReachesNonLocalUses.
insert(BB).second)
3556 if (!Header->hasNPredecessors(2))
3560 while (!Worklist.
empty()) {
3562 if (BB == Header || !Visited.
insert(BB).second)
3579 EphemeralValueTracker EphTracker;
3586 if (CI->cannotDuplicate() || CI->isConvergent())
3599 for (
User *U :
I.users()) {
3602 if (UsedInBB == BB) {
3606 NonLocalUseBlocks.
insert(UsedInBB);
3620 if (
I &&
I->getParent() == To)
3640 static constexpr unsigned MaxInstructionsToScan = 512;
3654 unsigned NumScannedInstructions = 0;
3655 while (!Worklist.
empty()) {
3659 if (!CanReachStop.
insert(BB).second)
3663 if (++NumScannedInstructions > MaxInstructionsToScan)
3667 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3681 while (!Worklist.
empty()) {
3683 if (BB == StopBB || !CanReachStop.
contains(BB))
3686 if (!Visited.
insert(BB).second)
3689 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3725 if (KnownValues.
empty())
3750 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3753 for (
const auto &Pair : KnownValues) {
3770 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3773 if (KeepCanonicalLoop &&
3787 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3790 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3800 EdgeBB->setName(RealDest->
getName() +
".critedge");
3801 EdgeBB->moveBefore(RealDest);
3811 TranslateMap[
Cond] = CB;
3824 N->insertInto(EdgeBB, InsertPt);
3827 N->setName(BBI->getName() +
".c");
3838 if (!BBI->use_empty())
3839 TranslateMap[&*BBI] =
V;
3840 if (!
N->mayHaveSideEffects()) {
3841 N->eraseFromParent();
3846 if (!BBI->use_empty())
3847 TranslateMap[&*BBI] =
N;
3853 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3854 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3855 SrcDbgCursor = std::next(BBI);
3857 N->cloneDebugInfoFrom(&*BBI);
3866 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3867 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3868 InsertPt->cloneDebugInfoFrom(BI);
3889 return std::nullopt;
3895bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3898 bool KeepCanonicalLoop =
3901 std::optional<bool>
Result;
3902 bool EverChanged =
false;
3908 }
while (Result == std::nullopt);
3917 bool SpeculateUnpredictables) {
3939 return isa<UncondBrInst>(IfBlock->getTerminator());
3942 "Will have either one or two blocks to speculate.");
3949 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3950 if (!IsUnpredictable) {
3953 (TWeight + FWeight) != 0) {
3958 if (IfBlocks.
size() == 1) {
3960 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3961 if (BIBBProb >= Likely)
3964 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3973 if (IfCondPhiInst->getParent() == BB)
3981 unsigned NumPhis = 0;
3994 if (SpeculateUnpredictables && IsUnpredictable)
3995 Budget +=
TTI.getBranchMispredictPenalty();
4008 AggressiveInsts, Cost, Budget,
TTI, AC,
4009 ZeroCostInstructions) ||
4011 AggressiveInsts, Cost, Budget,
TTI, AC,
4012 ZeroCostInstructions))
4025 auto IsBinOpOrAndEq = [](
Value *
V) {
4061 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
4063 <<
" F: " << IfFalse->
getName() <<
"\n");
4080 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
4085 PN->eraseFromParent();
4091 Builder.CreateBr(BB);
4112 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4113 if (
Opc == Instruction::And)
4114 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4115 if (
Opc == Instruction::Or)
4116 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4128 bool PredHasWeights =
4130 bool SuccHasWeights =
4132 if (PredHasWeights || SuccHasWeights) {
4133 if (!PredHasWeights)
4134 PredTrueWeight = PredFalseWeight = 1;
4135 if (!SuccHasWeights)
4136 SuccTrueWeight = SuccFalseWeight = 1;
4146static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4149 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4151 "PredBB must be a predecessor of BB.");
4159 (PTWeight + PFWeight) != 0) {
4162 Likely =
TTI->getPredictableBranchThreshold();
4167 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4168 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4172 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4175 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4176 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4182 return std::nullopt;
4195 bool InvertPredCond;
4196 std::tie(CommonSucc,
Opc, InvertPredCond) =
4199 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4207 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4212 if (InvertPredCond) {
4225 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4228 SuccTrueWeight, SuccFalseWeight)) {
4234 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4239 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4240 PredTrueWeight * SuccFalseWeight);
4246 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4247 PredFalseWeight * SuccTrueWeight);
4249 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4292 if (!MDWeights.
empty()) {
4293 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4301 ++NumFoldBranchToCommonDest;
4308 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4309 return U->getType()->isVectorTy();
4320 unsigned BonusInstThreshold) {
4329 Cond->getParent() != BB || !
Cond->hasOneUse())
4350 bool InvertPredCond;
4352 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4363 Cost +=
TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
4384 unsigned NumBonusInsts = 0;
4385 bool SawVectorOp =
false;
4386 const unsigned PredCount = Preds.
size();
4390 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4408 if (!
TTI ||
TTI->getInstructionCost(&
I, CostKind) !=
4410 NumBonusInsts += PredCount;
4418 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4421 return PN->getIncomingBlock(U) == BB;
4422 return UI->
getParent() == BB &&
I.comesBefore(UI);
4426 if (!
all_of(
I.uses(), IsBCSSAUse))
4430 BonusInstThreshold *
4446 for (
auto *BB : {BB1, BB2}) {
4462 Value *AlternativeV =
nullptr) {
4488 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4489 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4497 if (!AlternativeV &&
4503 PHI->addIncoming(
V, BB);
4513 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4522 if (!PStore || !QStore)
4545 if (
I.mayReadOrWriteMemory())
4547 for (
auto &
I : *QFB)
4548 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4551 for (
auto &
I : *QTB)
4552 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4556 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4570 for (
auto &
I : *BB) {
4572 if (
I.isTerminator())
4590 "When we run out of budget we will eagerly return from within the "
4591 "per-instruction loop.");
4595 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4597 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4598 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4632 InvertPCond ^= (PStore->
getParent() != PTB);
4633 InvertQCond ^= (QStore->
getParent() != QTB);
4653 {CombinedWeights[0], CombinedWeights[1]},
4660 SI->copyMetadata(*QStore);
4666 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4669 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4732 bool InvertPCond =
false, InvertQCond =
false;
4738 if (QFB == PostBB) {
4757 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4760 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4768 for (
auto *BB : {PTB, PFB}) {
4773 PStoreAddresses.
insert(
SI->getPointerOperand());
4775 for (
auto *BB : {QTB, QFB}) {
4780 QStoreAddresses.
insert(
SI->getPointerOperand());
4786 auto &CommonAddresses = PStoreAddresses;
4789 for (
auto *Address : CommonAddresses)
4792 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4810 !BI->
getParent()->getSinglePredecessor())
4812 if (!IfFalseBB->
phis().empty())
4822 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4896 if (&*BB->
begin() != BI)
4924 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4926 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4930 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4933 if (CommonDestProb >= Likely)
4943 unsigned NumPhis = 0;
4965 if (OtherDest == BB) {
4973 OtherDest = InfLoopBlock;
4985 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4989 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4993 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
5008 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
5009 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
5012 SuccTrueWeight, SuccFalseWeight);
5014 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
5015 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
5016 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
5017 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
5021 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
5022 PredOther * SuccCommon,
5023 PredOther * SuccOther};
5030 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
5032 assert(
SI->getCondition() == PBICond);
5049 Value *BIV = PN.getIncomingValueForBlock(BB);
5050 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
5051 Value *PBIV = PN.getIncomingValue(PBBIdx);
5055 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
5056 PN.setIncomingValue(PBBIdx, NV);
5060 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
5061 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
5081bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
5083 BasicBlock *FalseBB,
5084 uint32_t TrueWeight,
5085 uint32_t FalseWeight) {
5092 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5094 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5097 for (BasicBlock *Succ :
successors(OldTerm)) {
5099 if (Succ == KeepEdge1)
5100 KeepEdge1 =
nullptr;
5101 else if (Succ == KeepEdge2)
5102 KeepEdge2 =
nullptr;
5107 if (Succ != TrueBB && Succ != FalseBB)
5108 RemovedSuccessors.
insert(Succ);
5116 if (!KeepEdge1 && !KeepEdge2) {
5117 if (TrueBB == FalseBB) {
5128 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5148 SmallVector<DominatorTree::UpdateType, 2> Updates;
5150 for (
auto *RemovedSuccessor : RemovedSuccessors)
5151 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5166bool SimplifyCFGOpt::simplifySwitchOnSelectRemap(SwitchInst *SI,
5168 ConstantInt *
C,
bool Negate) {
5179 BasicBlock *DestFork =
SI->findCaseValue(K)->getCaseSuccessor();
5180 auto CaseC =
SI->findCaseValue(
C);
5181 bool IsDefault = CaseC ==
SI->case_default();
5183 BasicBlock *OldDest = CaseC->getCaseSuccessor();
5188 SI->setCondition(
X);
5190 if (OldDest != DestFork) {
5194 SI->addCase(
C, DestFork);
5196 CaseC->setSuccessor(DestFork);
5203 bool OldDestStillTargeted =
any_of(
5204 successors(SI), [&](BasicBlock *Succ) {
return Succ == OldDest; });
5205 if (DTU && !OldDestStillTargeted)
5206 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
5211 SmallVector<uint32_t> SwitchWeights;
5219 bool SelectHasBranchWeights =
5224 if (SwitchHasBranchWeights && SelectHasBranchWeights &&
5232 SmallVector<uint64_t> NewSwitchWeights;
5233 NewSwitchWeights.reserve(SwitchWeights.
size());
5234 NewSwitchWeights.push_back(SwitchWeights[0] * SelectTotalWeight);
5235 for (
const auto &[SwitchCase, SwitchWeight] :
5237 if (SwitchCase.getCaseValue() ==
C) {
5239 }
else if (SwitchCase.getCaseValue() == K) {
5243 uint64_t ProbabilityKeyEqualsK = SwitchWeight * SelectTotalWeight;
5246 ProbabilityKeyEqualsK > ProbabilityXEqualsC
5247 ? ProbabilityKeyEqualsK - ProbabilityXEqualsC
5249 NewSwitchWeights.push_back(ProbabilityXEqualsK);
5251 NewSwitchWeights.push_back(SwitchWeight * SelectTotalWeight);
5255 }
else if (SwitchHasBranchWeights) {
5261 SI->setMetadata(LLVMContext::MD_prof,
nullptr);
5275bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5280 if (
Select->hasOneUse() &&
5284 simplifySwitchOnSelectRemap(SI,
Select,
X,
C,
Pred == ICmpInst::ICMP_NE))
5290 if (!TrueVal || !FalseVal)
5295 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5296 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5299 uint32_t TrueWeight = 0, FalseWeight = 0;
5300 SmallVector<uint64_t, 8> Weights;
5304 if (Weights.
size() == 1 +
SI->getNumCases()) {
5306 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5308 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5313 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5322bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5336 SmallVector<uint32_t> SelectBranchWeights(2);
5339 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5340 SelectBranchWeights[0],
5341 SelectBranchWeights[1]);
5361bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5365 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5411bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5430 ConstantInt *NewCaseVal;
5438 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5444 SelectTrueVal = Builder.
getTrue();
5445 SelectFalseVal = Builder.
getFalse();
5448 SelectCond =
Select->getCondition();
5450 if (SelectCond != ICI)
5452 SelectTrueVal =
Select->getTrueValue();
5453 SelectFalseVal =
Select->getFalseValue();
5458 if (
SI->getCondition() != IcmpCond)
5464 if (
SI->getDefaultDest() != BB) {
5465 ConstantInt *VVal =
SI->findCaseDest(BB);
5466 assert(VVal &&
"Should have a unique destination value");
5474 return requestResimplify();
5480 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5482 if (Predicate == ICmpInst::ICMP_EQ)
5490 return requestResimplify();
5497 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5503 Value *DefaultCst = SelectFalseVal;
5504 Value *NewCst = SelectTrueVal;
5512 Select->replaceAllUsesWith(DefaultCst);
5513 Select->eraseFromParent();
5519 SmallVector<DominatorTree::UpdateType, 2> Updates;
5526 SwitchInstProfUpdateWrapper SIW(*SI);
5527 auto W0 = SIW.getSuccessorWeight(0);
5531 SIW.setSuccessorWeight(0, *NewW);
5533 SIW.addCase(NewCaseVal, NewBB, NewW);
5544 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5552bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5554 const DataLayout &
DL) {
5564 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5566 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5567 Value *CompVal = ConstantCompare.CompValue;
5568 unsigned UsedICmps = ConstantCompare.UsedICmps;
5569 Value *ExtraCase = ConstantCompare.Extra;
5570 bool TrueWhenEqual = ConstantCompare.IsEq;
5587 if (ExtraCase &&
Values.size() < 2)
5590 SmallVector<uint32_t> BranchWeights;
5596 if (!TrueWhenEqual) {
5599 std::swap(BranchWeights[0], BranchWeights[1]);
5605 <<
" cases into SWITCH. BB is:\n"
5608 SmallVector<DominatorTree::UpdateType, 2> Updates;
5615 nullptr,
"switch.early.test");
5626 AssumptionCache *AC =
Options.AC;
5632 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5639 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5645 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5646 <<
"\nEXTRABB = " << *BB);
5654 "Should not end up here with unstable pointers");
5656 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5661 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5664 Values.back()->getValue(),
Values.front()->getValue() + 1);
5666 ICmpInst::Predicate
Pred;
5678 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5679 NewBI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5684 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5685 New->setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5690 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5691 NewWeights[0] = BranchWeights[1];
5694 V = BranchWeights[0] /
Values.size();
5701 for (ConstantInt *Val :
Values)
5702 New->addCase(Val, EdgeBB);
5710 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5720 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5724bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5726 return simplifyCommonResume(RI);
5730 return simplifySingleResume(RI);
5739 if (!
II ||
II->getIntrinsicID() != Intrinsic::lifetime_end)
5746bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5755 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5759 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues(); Idx !=
End;
5761 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5762 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5766 if (IncomingBB->getUniqueSuccessor() != BB)
5771 if (IncomingValue != LandingPad)
5775 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5776 TrivialUnwindBlocks.
insert(IncomingBB);
5780 if (TrivialUnwindBlocks.
empty())
5784 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5788 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5791 for (BasicBlock *
Pred :
5802 TrivialBB->getTerminator()->eraseFromParent();
5803 new UnreachableInst(RI->
getContext(), TrivialBB);
5805 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5812 return !TrivialUnwindBlocks.empty();
5816bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5820 "Resume must unwind the exception that caused control to here");
5876 int Idx = DestPN.getBasicBlockIndex(BB);
5890 Value *SrcVal = DestPN.getIncomingValue(Idx);
5893 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5897 DestPN.addIncoming(Incoming,
Pred);
5924 std::vector<DominatorTree::UpdateType> Updates;
5928 if (UnwindDest ==
nullptr) {
5969 if (!SuccessorCleanupPad)
5978 SuccessorCleanupPad->eraseFromParent();
5987bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
6004bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
6036 BBI->dropDbgRecords();
6040 BBI->eraseFromParent();
6046 if (&BB->
front() != UI)
6049 std::vector<DominatorTree::UpdateType> Updates;
6052 for (BasicBlock *Predecessor : Preds) {
6060 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6071 "The destinations are guaranteed to be different here.");
6088 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6090 SwitchInstProfUpdateWrapper SU(*SI);
6091 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
6092 if (i->getCaseSuccessor() != BB) {
6097 i = SU.removeCase(i);
6102 if (DTU &&
SI->getDefaultDest() != BB)
6103 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6105 if (
II->getUnwindDest() == BB) {
6111 if (!CI->doesNotThrow())
6112 CI->setDoesNotThrow();
6116 if (CSI->getUnwindDest() == BB) {
6127 E = CSI->handler_end();
6130 CSI->removeHandler(
I);
6137 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6138 if (CSI->getNumHandlers() == 0) {
6139 if (CSI->hasUnwindDest()) {
6143 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
6144 Updates.push_back({DominatorTree::Insert,
6145 PredecessorOfPredecessor,
6146 CSI->getUnwindDest()});
6147 Updates.push_back({DominatorTree::Delete,
6148 PredecessorOfPredecessor, Predecessor});
6151 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
6158 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
6159 for (BasicBlock *EHPred : EHPreds)
6163 new UnreachableInst(CSI->getContext(), CSI->getIterator());
6164 CSI->eraseFromParent();
6169 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
6170 "Expected to always have an unwind to BB.");
6172 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6200static std::optional<ContiguousCasesResult>
6207 const APInt &Min = Cases.
back()->getValue();
6208 const APInt &Max = Cases.
front()->getValue();
6210 size_t ContiguousOffset = Cases.
size() - 1;
6211 if (
Offset == ContiguousOffset) {
6230 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6231 return L->getValue() != R->getValue() + 1;
6233 if (It == Cases.
end())
6234 return std::nullopt;
6235 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6236 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6240 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6243 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6251 return std::nullopt;
6256 bool RemoveOrigDefaultBlock =
true) {
6258 auto *BB = Switch->getParent();
6259 auto *OrigDefaultBlock = Switch->getDefaultDest();
6260 if (RemoveOrigDefaultBlock)
6261 OrigDefaultBlock->removePredecessor(BB);
6265 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6267 Switch->setDefaultDest(&*NewDefaultBlock);
6271 if (RemoveOrigDefaultBlock &&
6281bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6283 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6285 bool HasDefault = !
SI->defaultDestUnreachable();
6287 auto *BB =
SI->getParent();
6289 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6294 for (
auto Case :
SI->cases()) {
6298 if (Dest == DestA) {
6304 if (Dest == DestB) {
6314 "Single-destination switch should have been folded.");
6316 assert(DestB !=
SI->getDefaultDest());
6317 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6321 std::optional<ContiguousCasesResult> ContiguousCases;
6324 if (!HasDefault && CasesA.
size() == 1)
6325 ContiguousCases = ContiguousCasesResult{
6333 else if (CasesB.
size() == 1)
6334 ContiguousCases = ContiguousCasesResult{
6343 else if (!HasDefault)
6347 if (!ContiguousCases)
6351 if (!ContiguousCases)
6354 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6360 Max->getValue() - Min->getValue() + 1);
6363 assert(
Max->getValue() == Min->getValue());
6368 else if (NumCases->
isNullValue() && !Cases->empty()) {
6372 if (!
Offset->isNullValue())
6380 SmallVector<uint64_t, 8> Weights;
6382 if (Weights.
size() == 1 +
SI->getNumCases()) {
6385 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6386 if (
SI->getSuccessor(
I) == Dest)
6387 TrueWeight += Weights[
I];
6389 FalseWeight += Weights[
I];
6391 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6402 unsigned PreviousEdges = Cases->size();
6403 if (Dest ==
SI->getDefaultDest())
6405 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6406 PHI.removeIncomingValue(
SI->getParent());
6409 unsigned PreviousEdges = OtherCases->size();
6410 if (OtherDest ==
SI->getDefaultDest())
6412 unsigned E = PreviousEdges - 1;
6416 for (
unsigned I = 0;
I !=
E; ++
I)
6417 PHI.removeIncomingValue(
SI->getParent());
6421 SmallVector<DominatorTree::UpdateType, 2> Updates;
6425 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6429 SI->eraseFromParent();
6432 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6452 unsigned MaxSignificantBitsInCond =
6459 for (
const auto &Case :
SI->cases()) {
6460 auto *
Successor = Case.getCaseSuccessor();
6469 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6471 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6477 }
else if (IsKnownValuesValid)
6478 KnownValues.
erase(CaseC);
6485 bool HasDefault = !
SI->defaultDestUnreachable();
6486 const unsigned NumUnknownBits =
6489 if (HasDefault && DeadCases.
empty()) {
6495 if (NumUnknownBits < 64 ) {
6496 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6497 if (
SI->getNumCases() == AllNumCases) {
6504 if (
SI->getNumCases() == AllNumCases - 1) {
6505 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6507 if (CondTy->getIntegerBitWidth() > 64 ||
6508 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6512 for (
const auto &Case :
SI->cases())
6513 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6515 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6517 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6527 if (DeadCases.
empty())
6533 assert(CaseI !=
SI->case_default() &&
6534 "Case was not found. Probably mistake in DeadCases forming.");
6536 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6541 std::vector<DominatorTree::UpdateType> Updates;
6542 for (
auto *
Successor : UniqueSuccessors)
6543 if (NumPerSuccessorCases[
Successor] == 0)
6570 int Idx =
PHI.getBasicBlockIndex(BB);
6571 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6573 Value *InValue =
PHI.getIncomingValue(Idx);
6574 if (InValue != CaseValue)
6590 ForwardingNodesMap ForwardingNodes;
6593 for (
const auto &Case :
SI->cases()) {
6595 BasicBlock *CaseDest = Case.getCaseSuccessor();
6614 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6615 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6616 count(Phi.blocks(), SwitchBlock) == 1) {
6617 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6625 ForwardingNodes[Phi].push_back(PhiIdx);
6628 for (
auto &ForwardingNode : ForwardingNodes) {
6629 PHINode *Phi = ForwardingNode.first;
6635 for (
int Index : Indexes)
6636 Phi->setIncomingValue(Index,
SI->getCondition());
6646 if (
C->isThreadDependent())
6648 if (
C->isDLLImportDependent())
6656 if (
C->getType()->isScalableTy())
6667 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6694 if (
A->isAllOnesValue())
6696 if (
A->isNullValue())
6702 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6727 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6729 if (
I.isTerminator()) {
6731 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6734 CaseDest =
I.getSuccessor(0);
6741 for (
auto &
Use :
I.uses()) {
6744 if (
I->getParent() == CaseDest)
6747 if (Phi->getIncomingBlock(
Use) == CaseDest)
6760 *CommonDest = CaseDest;
6762 if (CaseDest != *CommonDest)
6767 int Idx =
PHI.getBasicBlockIndex(
Pred);
6776 Res.push_back(std::make_pair(&
PHI, ConstVal));
6779 return Res.
size() > 0;
6785 SwitchCaseResultVectorTy &UniqueResults,
6787 for (
auto &
I : UniqueResults) {
6788 if (
I.first == Result) {
6789 I.second.push_back(CaseVal);
6790 return I.second.size();
6793 UniqueResults.push_back(
6804 SwitchCaseResultVectorTy &UniqueResults,
6808 for (
const auto &
I :
SI->cases()) {
6822 const size_t NumCasesForResult =
6830 if (UniqueResults.size() > MaxUniqueResults)
6846 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6848 return DefaultResult ||
SI->defaultDestUnreachable();
6869 const bool HasBranchWeights = !BranchWeights.
empty();
6871 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6872 ResultVector[1].second.size() == 1) {
6873 ConstantInt *FirstCase = ResultVector[0].second[0];
6874 ConstantInt *SecondCase = ResultVector[1].second[0];
6875 Value *SelectValue = ResultVector[1].first;
6876 if (DefaultResult) {
6877 Value *ValueCompare =
6878 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6879 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6880 DefaultResult,
"switch.select");
6882 SI && HasBranchWeights) {
6889 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6893 Value *ValueCompare =
6894 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6895 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6896 SelectValue,
"switch.select");
6902 size_t FirstCasePos = (Condition !=
nullptr);
6903 size_t SecondCasePos = FirstCasePos + 1;
6904 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6906 {BranchWeights[FirstCasePos],
6907 DefaultCase + BranchWeights[SecondCasePos]},
6914 if (ResultVector.size() == 1 && DefaultResult) {
6916 unsigned CaseCount = CaseValues.
size();
6929 for (
auto *Case : CaseValues) {
6930 if (Case->getValue().slt(MinCaseVal->
getValue()))
6932 AndMask &= Case->getValue();
6936 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6938 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6942 if (FreeBits ==
Log2_32(CaseCount)) {
6943 Value *
And = Builder.CreateAnd(Condition, AndMask);
6944 Value *Cmp = Builder.CreateICmpEQ(
6947 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6963 for (
auto *Case : CaseValues)
6964 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6970 Condition = Builder.CreateSub(Condition, MinCaseVal);
6971 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6972 Value *Cmp = Builder.CreateICmpEQ(
6975 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6988 if (CaseValues.
size() == 2) {
6989 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6990 "switch.selectcmp.case1");
6991 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6992 "switch.selectcmp.case2");
6993 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6995 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
7015 std::vector<DominatorTree::UpdateType> Updates;
7022 Builder.CreateBr(DestBB);
7026 PHI->removeIncomingValueIf(
7027 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
7028 PHI->addIncoming(SelectValue, SelectBB);
7031 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
7037 if (DTU && RemovedSuccessors.
insert(Succ).second)
7040 SI->eraseFromParent();
7054 SwitchCaseResultVectorTy UniqueResults;
7060 assert(
PHI !=
nullptr &&
"PHI for value select not found");
7061 Builder.SetInsertPoint(
SI);
7063 [[maybe_unused]]
auto HasWeights =
7067 (BranchWeights.
size() >=
7068 UniqueResults.size() + (DefaultResult !=
nullptr)));
7071 Builder,
DL, BranchWeights);
7083class SwitchReplacement {
7091 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7092 Constant *DefaultValue,
const DataLayout &
DL,
7093 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
7102 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
7109 bool isLookupTable();
7115 bool isValid()
const {
return Kind != InvalidKind; }
7152 ConstantInt *BitMap =
nullptr;
7153 IntegerType *BitMapElementTy =
nullptr;
7156 ConstantInt *LinearOffset =
nullptr;
7157 ConstantInt *LinearMultiplier =
nullptr;
7158 bool LinearMapValWrapped =
false;
7166SwitchReplacement::SwitchReplacement(
7168 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7169 Constant *DefaultValue,
const DataLayout &
DL,
7170 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
7171 : DefaultValue(DefaultValue) {
7172 assert(
Values.size() &&
"Can't build lookup table without values!");
7173 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
7176 SingleValue =
Values.begin()->second;
7182 for (
const auto &[CaseVal, CaseRes] :
Values) {
7186 TableContents[
Idx] = CaseRes;
7193 if (
Values.size() < TableSize) {
7195 "Need a default value to fill the lookup table holes.");
7198 if (!TableContents[
I])
7199 TableContents[
I] = DefaultValue;
7205 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7206 SingleValue =
nullptr;
7212 Kind = SingleValueKind;
7219 bool LinearMappingPossible =
true;
7224 bool NonMonotonic =
false;
7225 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7241 LinearMappingPossible =
false;
7246 APInt Dist = Val - PrevVal;
7249 }
else if (Dist != DistToPrev) {
7250 LinearMappingPossible =
false;
7258 if (LinearMappingPossible) {
7260 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7261 APInt M = LinearMultiplier->getValue();
7262 bool MayWrap =
true;
7263 if (
isIntN(M.getBitWidth(), TableSize - 1))
7264 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7265 LinearMapValWrapped = NonMonotonic || MayWrap;
7266 Kind = LinearMapKind;
7273 if (wouldFitInRegister(
DL, TableSize,
ValueType) &&
7276 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7278 TableInt <<=
IT->getBitWidth();
7282 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7285 BitMap = ConstantInt::get(M.getContext(), TableInt);
7286 BitMapElementTy =
IT;
7292 if (!
all_of(TableContents,
7304 unsigned NeededBitWidth =
7305 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7318 Kind = LookupTableKind;
7326 case SingleValueKind:
7328 case LinearMapKind: {
7332 false,
"switch.idx.cast");
7333 if (!LinearMultiplier->
isOne())
7334 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7336 !LinearMapValWrapped);
7338 if (!LinearOffset->
isZero())
7341 !LinearMapValWrapped);
7358 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7359 "switch.shiftamt",
true,
true);
7362 Value *DownShifted =
7363 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7365 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7367 case LookupTableKind: {
7370 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7371 true, GlobalVariable::PrivateLinkage,
7372 Initializer,
"switch.table." +
Func->getName());
7373 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7377 Type *IndexTy =
DL.getIndexType(
Table->getType());
7380 if (
Index->getType() != IndexTy) {
7381 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7385 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7388 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7392 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7401bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7403 Type *ElementType) {
7411 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7413 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7419 if (
TTI.isTypeLegal(Ty))
7434 DL.fitsInLegalInteger(
IT->getBitWidth());
7437Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7439bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7441bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7448 const uint64_t MinDensity = OptSize ? 40 : 10;
7453 return NumCases * 100 >= CaseRange * MinDensity;
7465static std::optional<unsigned>
7468 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7470 return std::nullopt;
7475 for (
auto &
V : ReducedValues) {
7477 ReducedValuesOr |= Reduced;
7478 V = (int64_t)Reduced;
7491 for (
auto &
V : ReducedValues)
7495 return std::nullopt;
7509 if (
SI->getNumCases() > TableSize)
7512 bool AllTablesFitInRegister =
true;
7513 bool HasIllegalType =
false;
7514 for (
const auto &Ty : ResultTypes) {
7519 AllTablesFitInRegister =
7520 AllTablesFitInRegister &&
7521 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7526 if (HasIllegalType && !AllTablesFitInRegister)
7531 if (AllTablesFitInRegister)
7539 SI->getFunction()->hasOptSize());
7549 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7552 return all_of(ResultTypes, [&](
const auto &ResultType) {
7553 return SwitchReplacement::wouldFitInRegister(
7603 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7608 for (
auto ValuePair :
Values) {
7611 if (!CaseConst || CaseConst == DefaultConst ||
7612 (CaseConst != TrueConst && CaseConst != FalseConst))
7622 if (
Pred != BranchBlock &&
Pred->getUniquePredecessor() != BranchBlock)
7626 if (DefaultConst == FalseConst) {
7629 ++NumTableCmpReuses;
7632 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7633 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7636 ++NumTableCmpReuses;
7646 bool ConvertSwitchToLookupTable) {
7647 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7661 if (
SI->getNumCases() < 3)
7683 MinCaseVal = CaseVal;
7685 MaxCaseVal = CaseVal;
7702 It->second.push_back(std::make_pair(CaseVal,
Value));
7711 &CommonDest, DefaultResultsList,
DL);
7712 for (
const auto &
I : DefaultResultsList) {
7715 DefaultResults[
PHI] = Result;
7719 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7722 if (UseSwitchConditionAsTableIndex) {
7724 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7729 TableIndexOffset = MinCaseVal;
7736 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7738 bool TableHasHoles = (NumResults < TableSize);
7743 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7751 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7754 if (
SI->getNumCases() < 4)
7756 if (!
DL.fitsInLegalInteger(TableSize))
7765 if (UseSwitchConditionAsTableIndex) {
7766 TableIndex =
SI->getCondition();
7767 if (HasDefaultResults) {
7779 all_of(ResultTypes, [&](
const auto &ResultType) {
7780 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7785 TableSize = std::max(UpperBound, TableSize);
7788 DefaultIsReachable =
false;
7796 const auto &ResultList = ResultLists[
PHI];
7798 Type *ResultType = ResultList.begin()->second->getType();
7803 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7804 ResultList, DefaultVal,
DL,
TTI, FuncName);
7805 if (!Replacement.isValid())
7807 PhiToReplacementMap.
insert({
PHI, Replacement});
7810 bool AnyLookupTables =
any_of(
7811 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7812 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7813 [](
auto &KV) {
return KV.second.isBitMap(); });
7821 if (AnyLookupTables &&
7822 (!
TTI.shouldBuildLookupTables() ||
7828 if (!ConvertSwitchToLookupTable &&
7829 (AnyLookupTables || AnyBitMaps || NeedMask))
7832 Builder.SetInsertPoint(
SI);
7835 if (!UseSwitchConditionAsTableIndex) {
7838 bool MayWrap =
true;
7839 if (!DefaultIsReachable) {
7844 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7845 "switch.tableidx",
false,
7849 std::vector<DominatorTree::UpdateType> Updates;
7855 assert(MaxTableSize >= TableSize &&
7856 "It is impossible for a switch to have more entries than the max "
7857 "representable value of its input integer type's size.");
7862 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7867 Builder.SetInsertPoint(
SI);
7868 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7869 const bool IsFullyCoveredLookupTable =
7870 !DefaultIsReachable || GeneratingCoveredLookupTable;
7871 if (IsFullyCoveredLookupTable) {
7872 Builder.CreateBr(LookupBB);
7878 Value *Cmp = Builder.CreateICmpULT(
7879 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7881 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7882 CondBranch = RangeCheckBranch;
7888 Builder.SetInsertPoint(LookupBB);
7894 MaskBB->
setName(
"switch.hole_check");
7901 APInt MaskInt(TableSizePowOf2, 0);
7902 APInt One(TableSizePowOf2, 1);
7904 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7905 for (
const auto &Result : ResultList) {
7908 MaskInt |= One << Idx;
7910 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7917 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7918 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7919 Value *LoBit = Builder.CreateTrunc(
7921 if (!IsFullyCoveredLookupTable)
7923 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7928 Builder.SetInsertPoint(LookupBB);
7932 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7935 SI->getDefaultDest()->removePredecessor(BB,
7942 const ResultListTy &ResultList = ResultLists[
PHI];
7943 auto Replacement = PhiToReplacementMap.
at(
PHI);
7944 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7947 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7950 for (
auto *
User :
PHI->users()) {
7952 Replacement.getDefaultValue(), ResultList);
7956 PHI->addIncoming(Result, LookupBB);
7959 Builder.CreateBr(CommonDest);
7964 const bool HasBranchWeights =
7971 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7974 if (Succ ==
SI->getDefaultDest()) {
7975 if (HasBranchWeights)
7976 ToDefaultWeight += BranchWeights[
I];
7980 if (DTU && RemovedSuccessors.
insert(Succ).second)
7982 if (HasBranchWeights)
7983 ToLookupWeight += BranchWeights[
I];
7985 SI->eraseFromParent();
7990 if ((NeedMask && !IsFullyCoveredLookupTable) &&
7993 else if (HasBranchWeights)
8000 ++NumLookupTablesHoles;
8016 if (CondTy->getIntegerBitWidth() > 64 ||
8017 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8021 if (
SI->getNumCases() < 4)
8029 for (
const auto &
C :
SI->cases())
8030 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
8034 bool OptSize =
SI->getFunction()->hasOptSize();
8041 std::optional<unsigned> Shift;
8071 Builder.SetInsertPoint(
SI);
8075 Value *Rot = Builder.CreateIntrinsic(
8076 Ty, Intrinsic::fshl,
8077 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
8078 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
8080 for (
auto Case :
SI->cases()) {
8081 auto *Orig = Case.getCaseValue();
8082 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
8127 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
8128 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
8145 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
8148 return !Updates.
empty();
8168 if (
SI->defaultDestUnreachable())
8179 if (!
Known.isConstant())
8186 ConstantInt::get(
SI->getContext(),
Known.getConstant());
8188 if (CaseIt ==
SI->case_default()) {
8197 SI->case_default());
8199 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
8200 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
8201 "Proven value should have a dedicated case");
8202 assert(
SI->defaultDestUnreachable());
8220 Value *Condition =
SI->getCondition();
8224 if (CondTy->getIntegerBitWidth() > 64 ||
8225 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8237 if (
SI->getNumCases() < 4)
8242 for (
const auto &Case :
SI->cases()) {
8243 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8245 Values.push_back(CaseValue);
8255 SI->getFunction()->hasOptSize()))
8259 Builder.SetInsertPoint(
SI);
8261 if (!
SI->defaultDestUnreachable()) {
8264 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8265 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8267 auto *OrigBB =
SI->getParent();
8268 auto *DefaultCaseBB =
SI->getDefaultDest();
8270 auto It = OrigBB->getTerminator()->getIterator();
8282 NewWeights[1] = Weights[0] / 2;
8283 NewWeights[0] = OrigDenominator - NewWeights[1];
8295 Weights[0] = NewWeights[1];
8296 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8298 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8304 It->eraseFromParent();
8312 for (
auto &Case :
SI->cases()) {
8313 auto *OrigValue = Case.getCaseValue();
8314 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8315 OrigValue->getValue().countr_zero()));
8319 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8322 SI->setCondition(ConditionTrailingZeros);
8332 if (!Cmp || !Cmp->hasOneUse())
8343 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8346 if (
SI->getNumCases() == 2) {
8353 Succ =
SI->getDefaultDest();
8354 SuccWeight = Weights[0];
8356 for (
auto &Case :
SI->cases()) {
8357 std::optional<int64_t> Val =
8361 if (!Missing.erase(*Val))
8366 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8369 assert(Missing.size() == 1 &&
"Should have one case left");
8370 Res = *Missing.begin();
8371 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8373 Unreachable =
SI->getDefaultDest();
8375 for (
auto &Case :
SI->cases()) {
8376 BasicBlock *NewSucc = Case.getCaseSuccessor();
8377 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8380 OtherSuccWeight += Weight;
8383 SuccWeight = Weight;
8384 }
else if (Succ == NewSucc) {
8390 for (
auto &Case :
SI->cases()) {
8391 std::optional<int64_t> Val =
8393 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8395 if (Case.getCaseSuccessor() == Succ) {
8417 if (Cmp->isSigned())
8420 MDNode *NewWeights =
nullptr;
8426 Builder.SetInsertPoint(
SI->getIterator());
8427 Value *ICmp = Builder.CreateICmp(
Pred, Cmp->getLHS(), Cmp->getRHS());
8428 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8429 SI->getMetadata(LLVMContext::MD_unpredictable));
8433 SI->eraseFromParent();
8434 Cmp->eraseFromParent();
8435 if (DTU && Unreachable)
8460 assert(
BB &&
"Expected non-null BB");
8462 if (
BB->isEntryBlock())
8475 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8480 if (&
BB->front() != &
BB->back())
8495 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8506 return (*EBW->PhiPredIVs)[&Phi][BB];
8528 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8531 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8532 return PredIVs[
A] == PredIVs[
B];
8541 if (Candidates.
size() < 2)
8556 assert(Succ &&
"Expected unconditional BB");
8566 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8569 for (
auto &
IV : Phi->incoming_values())
8570 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8588 bool MadeChange =
false;
8602 if (!LivePreds.
contains(PredOfDead))
8609 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8610 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8615 T->replaceSuccessorWith(
Dead, Live);
8620 for (
const auto &EBW : BBs2Merge) {
8623 const auto &[It, Inserted] =
Keep.insert(&EBW);
8632 if (KeepBB == DeadBB)
8636 RedirectIncomingEdges(DeadBB, KeepBB);
8645 if (DTU && !Updates.
empty())
8651bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8652 DomTreeUpdater *DTU) {
8654 SmallSetVector<BasicBlock *, 16> FilteredArms(
8660bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8661 DomTreeUpdater *DTU) {
8672 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8678bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8681 if (isValueEqualityComparison(SI)) {
8686 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8687 return requestResimplify();
8691 if (simplifySwitchOnSelect(SI,
Select))
8692 return requestResimplify();
8696 if (SI == &*BB->
begin())
8697 if (foldValueComparisonIntoPredecessors(SI, Builder))
8698 return requestResimplify();
8704 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8705 return requestResimplify();
8709 return requestResimplify();
8712 return requestResimplify();
8715 return requestResimplify();
8718 return requestResimplify();
8723 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8725 Options.ConvertSwitchToLookupTable))
8726 return requestResimplify();
8729 return requestResimplify();
8732 return requestResimplify();
8735 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8736 return requestResimplify();
8740 if (simplifyDuplicateSwitchArms(SI, DTU))
8741 return requestResimplify();
8744 return requestResimplify();
8747 return requestResimplify();
8752bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8755 SmallVector<uint32_t> BranchWeights;
8758 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8759 if (HasBranchWeights)
8764 SmallPtrSet<Value *, 8> Succs;
8765 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8770 RemovedSuccs.
insert(Dest);
8780 std::vector<DominatorTree::UpdateType> Updates;
8781 Updates.reserve(RemovedSuccs.
size());
8782 for (
auto *RemovedSucc : RemovedSuccs)
8783 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8800 if (HasBranchWeights) {
8807 if (simplifyIndirectBrOnSelect(IBI, SI))
8808 return requestResimplify();
8840 if (BB == OtherPred)
8853 Value *V = PN.getIncomingValueForBlock(BB);
8854 Value *V2 = PN.getIncomingValueForBlock(OtherPred);
8855 return V == V2 || (V == LPad && V2 == LPad2);
8863 return PN.getIncomingValueForBlock(BB) == LPad;
8868 std::vector<DominatorTree::UpdateType> Updates;
8875 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8876 "unexpected successor");
8877 II->setUnwindDest(OtherPred);
8892 Builder.CreateUnreachable();
8901bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8913 bool NeedCanonicalLoop =
8927 if (
I->isTerminator() &&
8928 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8952 if (!PPred || (PredPred && PredPred != PPred))
8993 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8997 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
9027 bool HasWeight =
false;
9032 BBTWeight = BBFWeight = 1;
9037 BB1TWeight = BB1FWeight = 1;
9042 BB2TWeight = BB2FWeight = 1;
9044 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
9045 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
9052bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
9056 "Tautological conditional branch should have been eliminated already.");
9059 if (!
Options.SimplifyCondBranch ||
9064 if (isValueEqualityComparison(BI)) {
9069 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
9070 return requestResimplify();
9074 for (
auto &
I : *BB) {
9079 if (foldValueComparisonIntoPredecessors(BI, Builder))
9080 return requestResimplify();
9086 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
9099 return requestResimplify();
9105 if (
Options.SpeculateBlocks &&
9108 return requestResimplify();
9117 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
9118 return requestResimplify();
9120 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
9122 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
9123 auto CanSpeculateConditionalLoadsStores = [&]() {
9125 for (Instruction &
I : *Succ) {
9126 if (
I.isTerminator()) {
9127 if (
I.getNumSuccessors() > 1)
9131 SpeculatedConditionalLoadsStores.
size() ==
9135 SpeculatedConditionalLoadsStores.
push_back(&
I);
9138 return !SpeculatedConditionalLoadsStores.
empty();
9141 if (CanSpeculateConditionalLoadsStores()) {
9143 std::nullopt,
nullptr);
9144 return requestResimplify();
9154 return requestResimplify();
9163 return requestResimplify();
9169 if (foldCondBranchOnValueKnownInPredecessor(BI))
9170 return requestResimplify();
9177 return requestResimplify();
9185 return requestResimplify();
9189 return requestResimplify();
9196 assert(
V->getType() ==
I->getType() &&
"Mismatched types");
9208 auto *Use = cast<Instruction>(U.getUser());
9211 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
9214 switch (Use->getOpcode()) {
9217 case Instruction::GetElementPtr:
9218 case Instruction::Ret:
9219 case Instruction::BitCast:
9220 case Instruction::Load:
9221 case Instruction::Store:
9222 case Instruction::Call:
9223 case Instruction::CallBr:
9224 case Instruction::Invoke:
9225 case Instruction::UDiv:
9226 case Instruction::URem:
9230 case Instruction::SDiv:
9231 case Instruction::SRem:
9235 if (FindUse ==
I->use_end())
9237 auto &
Use = *FindUse;
9251 if (
GEP->getPointerOperand() ==
I) {
9254 if (
GEP->getType()->isVectorTy())
9262 if (!
GEP->hasAllZeroIndices() &&
9263 (!
GEP->isInBounds() ||
9265 GEP->getPointerAddressSpace())))
9266 PtrValueMayBeModified =
true;
9272 bool HasNoUndefAttr =
9273 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9278 if (
C->isNullValue() && HasNoUndefAttr &&
9279 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9280 return !PtrValueMayBeModified;
9286 if (!LI->isVolatile())
9288 LI->getPointerAddressSpace());
9292 if (!
SI->isVolatile())
9294 SI->getPointerAddressSpace())) &&
9295 SI->getPointerOperand() ==
I;
9300 if (
I == Assume->getArgOperand(0))
9308 if (CB->getCalledOperand() ==
I)
9311 if (CB->isArgOperand(&
Use)) {
9312 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9315 CB->paramHasNonNullAttr(ArgIdx,
false))
9316 return !PtrValueMayBeModified;
9335 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9343 Builder.CreateUnreachable();
9344 T->eraseFromParent();
9356 Builder.CreateUnreachable();
9363 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9365 Assumption = Builder.CreateAssumption(
Cond);
9380 Builder.SetInsertPoint(Unreachable);
9382 Builder.CreateUnreachable();
9383 for (
const auto &Case :
SI->cases())
9384 if (Case.getCaseSuccessor() == BB) {
9386 Case.setSuccessor(Unreachable);
9388 if (
SI->getDefaultDest() == BB) {
9390 SI->setDefaultDest(Unreachable);
9404bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9429 return requestResimplify();
9448 if (simplifyDuplicatePredecessors(BB, DTU))
9452 if (
Options.SpeculateBlocks &&
9459 Options.SpeculateUnpredictables))
9467 case Instruction::UncondBr:
9470 case Instruction::CondBr:
9473 case Instruction::Resume:
9476 case Instruction::CleanupRet:
9479 case Instruction::Switch:
9482 case Instruction::Unreachable:
9485 case Instruction::IndirectBr:
9493bool SimplifyCFGOpt::run(BasicBlock *BB) {
9503 }
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< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
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...
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
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.
static constexpr Value * getValue(Ty &ValueOrUse)
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...
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.
static cl::opt< uint32_t > SelectFalseWeight("profcheck-default-select-false-weight", cl::init(3U), cl::desc("When annotating `select` instructions, this value will be used " "for the second ('false') case."))
static cl::opt< uint32_t > SelectTrueWeight("profcheck-default-select-true-weight", cl::init(2U), cl::desc("When annotating `select` instructions, this value will be used " "for the first ('true') case."))
SmallVector< MachineOperand, 4 > Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
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 std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
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 isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
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 bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
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 isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
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 bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
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 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 Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
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 reachesUncontrolledConvergentCallBeforeBlock(BasicBlock *From, BasicBlock *StopBB)
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static bool isSafeToThreadThroughLoopHeader(BasicBlock *Header, ArrayRef< BasicBlock * > PredBBs, BasicBlock *RealDest)
Return true if threading PredBBs through Header to RealDest eliminates the loop's single backedge.
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 void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
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 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 bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
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 void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
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 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 extractPredSuccWeights(CondBrInst *PBI, CondBrInst *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 bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static std::optional< unsigned > getDenseSwitchRangeReductionShift(ArrayRef< int64_t > Values, int64_t Base, bool OptSize)
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 bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *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 bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, uintptr_t MaxUniqueResults)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB, Instruction *&PreviousAccess)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool SimplifyCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *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 canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
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 bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isUncontrolledConvergentCall(CallBase *CB)
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool KeepCanonicalLoop)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
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...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
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 SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
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 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 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
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
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.
bool hasTerminator() const LLVM_READONLY
Returns whether the block has a terminator.
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 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 InstListType::const_iterator getFirstNonPHIOrPseudoProbe() const
Returns an iterator to the first instruction in this block that is not a PHINode or a pseudo operatio...
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; assumes that the block is well-formed.
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
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
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 isConvergent() const
Determine if the invoke is convergent.
Value * getConvergenceControlToken() const
Return the convergence control token for this call, if it exists.
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.
bool isEquality() const
Determine if this is an equals/not equals predicate.
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.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
ConstantFolder - Create constants with minimum, target independent, folding.
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)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
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.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
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 APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
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.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
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.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
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...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
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.
iterator find(const_arg_type_t< KeyT > Val)
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
void reserve(size_type NumEntries)
Grow the DenseMap so that it can contain at least NumEntries items before resizing again.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Implements a dense probed hash-table based set.
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.
bool isEquality() const
Return true if this predicate is either EQ or NE.
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.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
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="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
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="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
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 * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
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)
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
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.
LLVM_ABI void dropLocation()
Drop the instruction's debug location.
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.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
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()
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
iterator_range< user_iterator > users()
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.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
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.
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.
void insert_range(Range &&R)
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)
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.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
bool isAtomic() const
Return true if this store has an atomic ordering.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Value * getPointerOperand()
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)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
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.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
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.
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.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
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.
LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
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.
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.
@ 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)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
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_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
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.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
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)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
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.
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
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)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, AssumptionCache *AC=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 ...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > MaxLoopHeaderThreadingSearchBlocks("simplifycfg-max-loop-header-threading-search", cl::Hidden, cl::init(1024), cl::desc("Limit number of blocks searched to prove that threading through " "a loop header keeps the loop canonical"))
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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...
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"))
RelativeUniformCounterPtr Values
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"))
@ Known
Known to have no common set bits.
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<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
@ Load
The value being inserted comes from a load (InsertElement only).
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
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.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
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...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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...
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)
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"))
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.
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)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
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"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given 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.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
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"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI CondBrInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
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.
LLVM_ABI void InvertBranch(CondBrInst *PBI, IRBuilderBase &Builder)
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
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)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ 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 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.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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...
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"))
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.
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"))
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...
LLVM_ABI bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
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"))
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
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 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"))
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.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
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
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
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
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...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
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.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
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)
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 cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
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)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
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...
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.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
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"))
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.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
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.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
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...
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
An information struct used to provide DenseMap with the various necessary components for a given valu...
A MapVector that performs no allocations if smaller than a certain size.