50#define DEBUG_TYPE "lazy-value-info"
59 "Lazy Value Information Analysis",
false,
true)
93 class LazyValueInfoCache;
94 struct LVIValueHandle final :
public CallbackVH {
95 LazyValueInfoCache *Parent;
97 LVIValueHandle(
Value *
V, LazyValueInfoCache *
P =
nullptr)
98 : CallbackVH(
V), Parent(
P) { }
100 void deleted()
override;
101 void allUsesReplacedWith(
Value *
V)
override {
109using BBLatticeElementMap =
111using PredecessorValueLatticeMap =
116class LazyValueInfoCache {
121 struct BlockCacheEntry {
122 SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
123 SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
126 std::optional<NonNullPointerSet> NonNullPointers;
130 std::optional<PredecessorValueLatticeMap> PredecessorLatticeElements;
133 const bool PerPredRanges;
138 DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
140 unsigned BlockNumberEpoch;
142 const BlockCacheEntry *getBlockEntry(BasicBlock *BB)
const {
145 return BlockCache[BB->
getNumber()].get();
149 BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {
155 if (BlockCacheEntry *Entry = BlockCache[
Number].
get())
158 BlockCache[
Number] = std::make_unique<BlockCacheEntry>();
160 BlockCache[
Number]->PredecessorLatticeElements =
161 std::make_optional<PredecessorValueLatticeMap>();
163 return BlockCache[
Number].get();
166 void addValueHandle(
Value *Val) {
167 auto HandleIt = ValueHandles.
find_as(Val);
168 if (HandleIt == ValueHandles.
end())
169 ValueHandles.
insert({Val,
this});
173 LazyValueInfoCache(
const Function *
F,
bool PerPredRanges)
174 : PerPredRanges(PerPredRanges),
175 BlockNumberEpoch(
F->getBlockNumberEpoch()) {}
177 void insertResult(
Value *Val, BasicBlock *BB,
178 const ValueLatticeElement &Result) {
179 BlockCacheEntry *
Entry = getOrCreateBlockEntry(BB);
183 if (
Result.isOverdefined())
184 Entry->OverDefined.insert(Val);
191 void insertPredecessorResults(
Value *Val, BasicBlock *BB,
192 BBLatticeElementMap &PredLatticeElements) {
193 BlockCacheEntry *
Entry = getOrCreateBlockEntry(BB);
195 Entry->PredecessorLatticeElements->insert({Val, PredLatticeElements});
200 std::optional<BBLatticeElementMap>
201 getCachedPredecessorInfo(
Value *
V, BasicBlock *BB)
const {
202 const BlockCacheEntry *
Entry = getBlockEntry(BB);
206 auto LatticeIt =
Entry->PredecessorLatticeElements->find_as(
V);
207 if (LatticeIt ==
Entry->PredecessorLatticeElements->end())
210 return LatticeIt->second;
213 std::optional<ValueLatticeElement> getCachedValueInfo(
Value *
V,
214 BasicBlock *BB)
const {
215 const BlockCacheEntry *
Entry = getBlockEntry(BB);
219 if (
Entry->OverDefined.count(
V))
222 auto LatticeIt =
Entry->LatticeElements.find_as(
V);
223 if (LatticeIt ==
Entry->LatticeElements.end())
226 return LatticeIt->second;
230 isNonNullAtEndOfBlock(
Value *
V, BasicBlock *BB,
231 function_ref<NonNullPointerSet(BasicBlock *)> InitFn) {
232 BlockCacheEntry *
Entry = getOrCreateBlockEntry(BB);
233 if (!
Entry->NonNullPointers) {
234 Entry->NonNullPointers = InitFn(BB);
239 return Entry->NonNullPointers->count(
V);
245 ValueHandles.
clear();
249 void eraseValue(
Value *
V);
258 void threadEdgeImpl(BasicBlock *OldSucc, BasicBlock *NewSucc);
262void LazyValueInfoCache::eraseValue(
Value *
V) {
263 for (
auto &Elem : BlockCache) {
267 Elem->LatticeElements.erase(
V);
268 Elem->OverDefined.erase(
V);
269 if (Elem->NonNullPointers)
270 Elem->NonNullPointers->erase(
V);
272 Elem->PredecessorLatticeElements->erase(
V);
275 auto HandleIt = ValueHandles.
find_as(
V);
276 if (HandleIt != ValueHandles.
end())
277 ValueHandles.
erase(HandleIt);
280void LVIValueHandle::deleted() {
283 Parent->eraseValue(*
this);
286void LazyValueInfoCache::eraseBlock(
BasicBlock *BB) {
290 for (
auto &Elem : BlockCache)
292 Elem->PredecessorLatticeElements->clear();
297void LazyValueInfoCache::threadEdgeImpl(
BasicBlock *OldSucc,
309 std::vector<BasicBlock*> worklist;
310 worklist.push_back(OldSucc);
312 const BlockCacheEntry *
Entry = getBlockEntry(OldSucc);
313 if (!Entry ||
Entry->OverDefined.empty())
316 Entry->OverDefined.end());
322 while (!worklist.empty()) {
327 if (ToUpdate == NewSucc)
continue;
330 BlockCacheEntry *WorklistEntry =
331 ToUpdate->
getNumber() < BlockCache.size()
332 ? BlockCache[ToUpdate->
getNumber()].get()
334 if (!WorklistEntry || WorklistEntry->OverDefined.empty())
336 auto &ValueSet = WorklistEntry->OverDefined;
338 bool changed =
false;
339 for (
Value *
V : ValsToClear) {
340 if (!ValueSet.erase(
V))
348 if (!changed)
continue;
359 LazyValueInfoImpl *LVIImpl;
365 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
366 : LVIImpl(
L), DT(DTree) {}
368 void emitBasicBlockStartAnnot(
const BasicBlock *BB,
369 formatted_raw_ostream &OS)
override;
371 void emitInstructionAnnot(
const Instruction *
I,
372 formatted_raw_ostream &OS)
override;
377 const bool PerPredRanges;
380 LazyValueInfoCache TheCache;
392 bool pushBlockValue(
const std::pair<BasicBlock *, Value *> &BV) {
393 if (!BlockValueSet.insert(BV).second)
397 << BV.first->getName() <<
"\n");
398 BlockValueStack.push_back(BV);
409 std::optional<ValueLatticeElement> getBlockValue(
Value *Val,
BasicBlock *BB,
419 std::optional<ValueLatticeElement> solveBlockValueImpl(
Value *Val,
421 std::optional<ValueLatticeElement> solveBlockValueNonLocal(
Value *Val,
423 std::optional<ValueLatticeElement> solveBlockValuePHINode(
PHINode *PN,
425 std::optional<ValueLatticeElement> solveBlockValueSelect(
SelectInst *S,
429 std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
433 std::optional<ValueLatticeElement>
435 std::optional<ValueLatticeElement> solveBlockValueCast(
CastInst *CI,
437 std::optional<ValueLatticeElement>
439 std::optional<ValueLatticeElement> solveBlockValueIntrinsic(
IntrinsicInst *
II,
441 std::optional<ValueLatticeElement>
443 std::optional<ValueLatticeElement>
446 void intersectAssumeOrGuardBlockValueConstantRange(
Value *Val,
456 std::optional<ValueLatticeElement>
461 std::optional<ValueLatticeElement>
462 getValueFromICmpCondition(
Value *Val,
ICmpInst *ICI,
bool isTrueDest,
467 std::optional<ValueLatticeElement>
469 bool UseBlockValue,
unsigned Depth = 0);
471 std::optional<ValueLatticeElement> getEdgeValueLocal(
Value *Val,
498 bool AssumeFrozen =
false);
507 LazyValueInfoAnnotatedWriter Writer(
this, DTree);
508 F.print(OS, &Writer);
518 TheCache.eraseBlock(BB);
528 TheCache(
F, PerPredRanges), AC(AC), DL(DL), GuardDecl(GuardDecl) {}
532void LazyValueInfoImpl::solve() {
536 unsigned processedCount = 0;
537 while (!BlockValueStack.empty()) {
549 dbgs() <<
"Giving up on stack because we are getting too deep\n");
551 while (!StartingStack.
empty()) {
552 std::pair<BasicBlock *, Value *> &
e = StartingStack.
back();
553 TheCache.insertResult(
e.second,
e.first,
557 BlockValueSet.clear();
558 BlockValueStack.clear();
561 std::pair<BasicBlock *, Value *>
e = BlockValueStack.back();
562 assert(BlockValueSet.count(e) &&
"Stack value should be in BlockValueSet!");
563 unsigned StackSize = BlockValueStack.size();
566 if (solveBlockValue(
e.second,
e.first)) {
568 assert(BlockValueStack.size() == StackSize &&
569 BlockValueStack.back() == e &&
"Nothing should have been pushed!");
571 std::optional<ValueLatticeElement> BBLV =
572 TheCache.getCachedValueInfo(
e.second,
e.first);
573 assert(BBLV &&
"Result should be in cache!");
575 dbgs() <<
"POP " << *
e.second <<
" in " <<
e.first->getName() <<
" = "
579 BlockValueStack.pop_back();
580 BlockValueSet.erase(e);
583 assert(BlockValueStack.size() == StackSize + 1 &&
584 "Exactly one element should have been pushed!");
589std::optional<ValueLatticeElement>
596 if (std::optional<ValueLatticeElement> OptLatticeVal =
597 TheCache.getCachedValueInfo(Val, BB)) {
598 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CtxI);
599 return OptLatticeVal;
603 if (!pushBlockValue({ BB, Val }))
614 case Instruction::Call:
615 case Instruction::Invoke:
619 case Instruction::Load:
633 assert(!TheCache.getCachedValueInfo(Val, BB) &&
634 "Value should not be in cache");
638 std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
643 TheCache.insertResult(Val, BB, *Res);
647std::optional<ValueLatticeElement>
651 return solveBlockValueNonLocal(Val, BB);
654 return solveBlockValuePHINode(PN, BB);
657 return solveBlockValueSelect(SI, BB);
674 return solveBlockValueCast(CI, BB);
677 return solveBlockValueBinaryOp(BO, BB);
680 return solveBlockValueInsertElement(IEI, BB);
683 return solveBlockValueExtractValue(EVI, BB);
686 return solveBlockValueIntrinsic(
II, BB);
690 <<
"' - unknown inst def found.\n");
695 bool IsDereferenced =
true) {
709 if (
MI->isVolatile())
return;
713 if (!Len || Len->isZero())
return;
719 for (
auto &U : CB->args()) {
720 if (U->getType()->isPointerTy() &&
721 CB->paramHasNonNullAttr(CB->getArgOperandNo(&U),
728bool LazyValueInfoImpl::isNonNullAtEndOfBlock(
Value *Val,
BasicBlock *BB) {
734 return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
735 NonNullPointerSet NonNullPointers;
736 for (Instruction &
I : *BB)
738 return NonNullPointers;
742std::optional<ValueLatticeElement>
743LazyValueInfoImpl::solveBlockValueNonLocal(
Value *Val,
BasicBlock *BB) {
744 ValueLatticeElement
Result;
763 std::optional<BBLatticeElementMap> PredLatticeElements;
765 PredLatticeElements = std::make_optional<BBLatticeElementMap>();
770 std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val,
Pred, BB);
775 Result.mergeIn(*EdgeResult);
779 if (
Result.isOverdefined()) {
781 <<
"' - overdefined because of pred '"
782 <<
Pred->getName() <<
"' (non local).\n");
786 PredLatticeElements->insert({
Pred, *EdgeResult});
790 TheCache.insertPredecessorResults(Val, BB, *PredLatticeElements);
797std::optional<ValueLatticeElement>
799 ValueLatticeElement
Result;
804 std::optional<BBLatticeElementMap> PredLatticeElements;
806 PredLatticeElements = std::make_optional<BBLatticeElementMap>();
813 std::optional<ValueLatticeElement> EdgeResult =
814 getEdgeValue(PhiVal, PhiBB, BB, PN);
819 Result.mergeIn(*EdgeResult);
823 if (
Result.isOverdefined()) {
825 <<
"' - overdefined because of pred (local).\n");
831 PredLatticeElements->insert({PhiBB, *EdgeResult});
835 TheCache.insertPredecessorResults(PN, BB, *PredLatticeElements);
838 assert(!
Result.isOverdefined() &&
"Possible PHI in entry block?");
844void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
851 for (
auto &AssumeVH : AC->assumptionsFor(Val)) {
864 auto OBU =
I->getOperandBundleAt(AssumeVH.Index);
866 case BundleAttr::Range: {
875 I->getOperandBundleAt(AssumeVH.Index)))
880 BBLV = BBLV.
intersect(*getValueFromCondition(Val,
I->getArgOperand(0),
887 if (GuardDecl && !GuardDecl->use_empty() &&
889 for (Instruction &
I :
904 isNonNullAtEndOfBlock(Val, BB))
909std::optional<ValueLatticeElement>
912 std::optional<ValueLatticeElement> OptTrueVal =
913 getBlockValue(
SI->getTrueValue(), BB, SI);
916 ValueLatticeElement &
TrueVal = *OptTrueVal;
918 std::optional<ValueLatticeElement> OptFalseVal =
919 getBlockValue(
SI->getFalseValue(), BB, SI);
922 ValueLatticeElement &
FalseVal = *OptFalseVal;
925 const ConstantRange &TrueCR =
TrueVal.asConstantRange(
SI->getType());
926 const ConstantRange &FalseCR =
FalseVal.asConstantRange(
SI->getType());
933 ((
LHS ==
SI->getTrueValue() &&
RHS ==
SI->getFalseValue()) ||
934 (
RHS ==
SI->getTrueValue() &&
LHS ==
SI->getFalseValue()))) {
935 ConstantRange ResultCR = [&]() {
940 return TrueCR.
smin(FalseCR);
942 return TrueCR.
umin(FalseCR);
944 return TrueCR.
smax(FalseCR);
946 return TrueCR.
umax(FalseCR);
950 ResultCR,
TrueVal.isConstantRangeIncludingUndef() ||
951 FalseVal.isConstantRangeIncludingUndef());
955 if (
LHS ==
SI->getTrueValue())
957 TrueCR.
abs(),
TrueVal.isConstantRangeIncludingUndef());
958 if (
LHS ==
SI->getFalseValue())
960 FalseCR.
abs(),
FalseVal.isConstantRangeIncludingUndef());
965 if (
LHS ==
SI->getTrueValue())
968 if (
LHS ==
SI->getFalseValue())
982 TrueVal.intersect(*getValueFromCondition(
SI->getTrueValue(),
Cond,
986 FalseVal.intersect(*getValueFromCondition(
SI->getFalseValue(),
Cond,
995std::optional<ConstantRange>
997 std::optional<ValueLatticeElement> OptVal = getBlockValue(
V, BB, CtxI);
1000 return OptVal->asConstantRange(
V->getType());
1003std::optional<ValueLatticeElement>
1009 case Instruction::Trunc:
1010 case Instruction::SExt:
1011 case Instruction::ZExt:
1016 <<
"' - overdefined (unknown cast).\n");
1023 std::optional<ConstantRange> LHSRes = getRangeFor(CI->
getOperand(0), CI, BB);
1026 return std::nullopt;
1027 const ConstantRange &LHSRange = *LHSRes;
1034 ConstantRange Res = ConstantRange::getEmpty(ResultBitWidth);
1036 Res = LHSRange.
truncate(ResultBitWidth, Trunc->getNoWrapKind());
1043std::optional<ValueLatticeElement>
1044LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
1051 auto ThreadBinOpOverSelect =
1052 [&](
Value *
X,
const ConstantRange &CRX, SelectInst *
Y,
1053 bool XIsLHS) -> std::optional<ValueLatticeElement> {
1058 return std::nullopt;
1061 return std::nullopt;
1063 return std::nullopt;
1065 ConstantRange TrueX =
1066 CRX.intersectWith(getValueFromCondition(
X,
Cond,
true,
1068 ->asConstantRange(
X->getType()));
1069 ConstantRange FalseX =
1070 CRX.intersectWith(getValueFromCondition(
X,
Cond,
false,
1072 ->asConstantRange(
X->getType()));
1078 OpFn(TrueX, TrueY).unionWith(OpFn(FalseX, FalseY)));
1080 OpFn(TrueY, TrueX).unionWith(OpFn(FalseY, FalseX)));
1087 std::optional<ConstantRange> LHSRes = getRangeFor(
LHS,
I, BB);
1089 return std::nullopt;
1093 if (
auto Res = ThreadBinOpOverSelect(
LHS, *LHSRes, SI,
true))
1097 std::optional<ConstantRange> RHSRes = getRangeFor(
RHS,
I, BB);
1099 return std::nullopt;
1103 if (
auto Res = ThreadBinOpOverSelect(
RHS, *RHSRes, SI,
false))
1107 const ConstantRange &LHSRange = *LHSRes;
1108 const ConstantRange &RHSRange = *RHSRes;
1110 std::optional<ValueLatticeElement> MergedResult =
1114 return MergedResult;
1116 std::optional<BBLatticeElementMap> PredLHS =
1117 TheCache.getCachedPredecessorInfo(
LHS, BB);
1119 return MergedResult;
1120 std::optional<BBLatticeElementMap> PredRHS =
1121 TheCache.getCachedPredecessorInfo(
RHS, BB);
1123 return MergedResult;
1125 const BBLatticeElementMap &LHSPredMap = *PredLHS;
1126 const BBLatticeElementMap &RHSPredMap = *PredRHS;
1128 BBLatticeElementMap PredLatticeElements;
1129 ValueLatticeElement OverallPredResult;
1131 auto LHSIt = LHSPredMap.find_as(
Pred);
1132 if (LHSIt == LHSPredMap.end())
1133 return MergedResult;
1134 const ValueLatticeElement &LHSFromPred = LHSIt->second;
1135 std::optional<ConstantRange> LHSFromPredRes =
1137 if (!LHSFromPredRes)
1138 return MergedResult;
1140 auto RHSIt = RHSPredMap.find_as(
Pred);
1141 if (RHSIt == RHSPredMap.end())
1142 return MergedResult;
1143 const ValueLatticeElement &RHSFromPred = RHSIt->second;
1144 std::optional<ConstantRange> RHSFromPredRes =
1146 if (!RHSFromPredRes)
1147 return MergedResult;
1149 const ConstantRange &LHSFromPredRange = *LHSFromPredRes;
1150 const ConstantRange &RHSFromPredRange = *RHSFromPredRes;
1151 std::optional<ValueLatticeElement> PredResult =
1154 return MergedResult;
1155 if (PredResult->isOverdefined()) {
1157 dbgs() <<
" pred BB '" <<
Pred->getName() <<
"' for BB '"
1159 <<
"' overdefined. Discarding all predecessor intervals.\n");
1160 return MergedResult;
1162 PredLatticeElements.insert({
Pred, *PredResult});
1163 OverallPredResult.
mergeIn(*PredResult);
1169 TheCache.insertPredecessorResults(
I, BB, PredLatticeElements);
1172 <<
" to: " << OverallPredResult <<
".\n");
1175 return OverallPredResult;
1178 << OverallPredResult <<
" and " << MergedResult <<
".\n");
1179 return MergedResult->intersect(OverallPredResult);
1182std::optional<ValueLatticeElement>
1185 "all operands to binary operators are sized");
1187 return solveBlockValueBinaryOpImpl(
1188 BO, BB, [BO](
const ConstantRange &CR1,
const ConstantRange &CR2) {
1193std::optional<ValueLatticeElement>
1196 return solveBlockValueBinaryOpImpl(
1197 WO, BB, [WO](
const ConstantRange &CR1,
const ConstantRange &CR2) {
1202std::optional<ValueLatticeElement>
1207 <<
"' - unknown intrinsic.\n");
1213 std::optional<ConstantRange>
Range = getRangeFor(
Op,
II, BB);
1215 return std::nullopt;
1224std::optional<ValueLatticeElement>
1227 std::optional<ValueLatticeElement> OptEltVal =
1230 return std::nullopt;
1231 ValueLatticeElement &Res = *OptEltVal;
1233 std::optional<ValueLatticeElement> OptVecVal =
1236 return std::nullopt;
1242 if (OptEltVal->isConstant())
1249std::optional<ValueLatticeElement>
1254 return solveBlockValueOverflowIntrinsic(WO, BB);
1261 return getBlockValue(
V, BB, EVI);
1264 <<
"' - overdefined (unknown extractvalue).\n");
1302std::optional<ValueLatticeElement>
1307 bool UseBlockValue) {
1311 RHSRange =
C->toConstantRange();
1312 }
else if (UseBlockValue) {
1313 std::optional<ValueLatticeElement>
R =
1316 return std::nullopt;
1320 ConstantRange TrueValues =
1325static std::optional<ConstantRange>
1328 bool Invert =
false;
1335 if (
RHS.isMaxSignedValue())
1336 return std::nullopt;
1340 if (
auto CR = Fn(
RHS))
1341 return Invert ? CR->inverse() : CR;
1342 return std::nullopt;
1348 unsigned BitWidth =
RHS->getType()->getScalarSizeInBits();
1367static std::optional<ConstantRange>
1370 if (!
V->getType()->isIntegerTy())
1371 return std::nullopt;
1375 return std::nullopt;
1382 ConstantRange::getFull(
V->getType()->getScalarSizeInBits());
1389 return std::nullopt;
1393std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(
1394 Value *Val,
ICmpInst *ICI,
bool isTrueDest,
bool UseBlockValue) {
1421 return getValueFromSimpleICmpCondition(EdgePred,
RHS,
Offset, ICI,
1426 return getValueFromSimpleICmpCondition(SwappedPred,
LHS,
Offset, ICI,
1432 const APInt *
Mask, *
C;
1466 const APInt *ShAmtC;
1471 EdgePred, *
C, [&](
const APInt &
RHS) -> std::optional<ConstantRange> {
1472 APInt
New =
RHS << *ShAmtC;
1473 if ((
New.ashr(*ShAmtC)) !=
RHS)
1474 return std::nullopt;
1542std::optional<ValueLatticeElement>
1544 bool IsTrueDest,
bool UseBlockValue,
1547 return getValueFromICmpCondition(Val, ICI, IsTrueDest, UseBlockValue);
1550 return getValueFromTrunc(Val, Trunc, IsTrueDest);
1562 return getValueFromCondition(Val,
N, !IsTrueDest, UseBlockValue,
Depth);
1573 std::optional<ValueLatticeElement> LV =
1574 getValueFromCondition(Val, L, IsTrueDest, UseBlockValue,
Depth);
1576 return std::nullopt;
1577 std::optional<ValueLatticeElement> RV =
1578 getValueFromCondition(Val, R, IsTrueDest, UseBlockValue,
Depth);
1580 return std::nullopt;
1586 if (IsTrueDest ^ IsAnd) {
1591 return LV->intersect(*RV);
1612 const APInt &OpConstVal,
1627 assert((Op0Match || Op1Match) &&
1628 "Operand 0 nor Operand 1 isn't a match");
1643std::optional<ValueLatticeElement>
1651 if (BI->getSuccessor(0) != BI->getSuccessor(1)) {
1652 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1653 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1654 "BBTo isn't a successor of BBFrom");
1655 Value *Condition = BI->getCondition();
1660 if (Condition == Val)
1666 std::optional<ValueLatticeElement>
Result =
1667 getValueFromCondition(Val, Condition, isTrueDest, UseBlockValue);
1669 return std::nullopt;
1671 if (!
Result->isOverdefined())
1675 assert(
Result->isOverdefined() &&
"Result isn't overdefined");
1681 Value *TempCond = Condition;
1692 APInt ConditionVal(1, isTrueDest ^ (TempCond != Condition) ? 1 : 0);
1695 ValueLatticeElement OpLatticeVal =
1696 *getValueFromCondition(Usr->getOperand(0), Condition,
1700 const unsigned ResultBitWidth =
1701 Usr->getType()->getScalarSizeInBits();
1726 for (
unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1727 Value *
Op = Usr->getOperand(i);
1728 ValueLatticeElement OpLatticeVal = *getValueFromCondition(
1729 Op, Condition, isTrueDest,
false);
1730 if (std::optional<APInt> OpConst =
1739 if (!
Result->isOverdefined())
1747 Value *Condition =
SI->getCondition();
1750 bool ValUsesConditionAndMayBeFoldable =
false;
1751 if (Condition != Val) {
1756 if (!ValUsesConditionAndMayBeFoldable)
1759 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1760 "Condition != Val nor Val doesn't use Condition");
1762 bool DefaultCase =
SI->getDefaultDest() == BBTo;
1764 ConstantRange EdgesVals(
BitWidth, DefaultCase);
1766 for (
auto Case :
SI->cases()) {
1767 APInt CaseValue = Case.getCaseValue()->getValue();
1768 ConstantRange EdgeVal(CaseValue);
1769 if (ValUsesConditionAndMayBeFoldable) {
1772 ValueLatticeElement EdgeLatticeVal =
1785 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1786 EdgesVals = EdgesVals.difference(EdgeVal);
1787 }
else if (Case.getCaseSuccessor() == BBTo)
1788 EdgesVals = EdgesVals.unionWith(EdgeVal);
1797std::optional<ValueLatticeElement>
1804 std::optional<ValueLatticeElement> LocalResult =
1805 getEdgeValueLocal(Val, BBFrom, BBTo,
true);
1807 return std::nullopt;
1813 std::optional<ValueLatticeElement> OptInBlock =
1816 return std::nullopt;
1817 ValueLatticeElement &
InBlock = *OptInBlock;
1827 intersectAssumeOrGuardBlockValueConstantRange(Val,
InBlock, CtxI);
1829 return LocalResult->intersect(
InBlock);
1834 LLVM_DEBUG(
dbgs() <<
"LVI Getting block end value " << *V <<
" at '"
1837 assert(BlockValueStack.empty() && BlockValueSet.empty());
1838 std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CtxI);
1841 OptResult = getBlockValue(V, BB, CtxI);
1842 assert(OptResult &&
"Value not available after solving");
1859 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CtxI);
1868 LLVM_DEBUG(
dbgs() <<
"LVI Getting edge value " << *V <<
" from '"
1872 std::optional<ValueLatticeElement> Result =
1873 getEdgeValue(V, FromBB, ToBB, CtxI);
1879 Result = getEdgeValue(V, FromBB, ToBB, CtxI);
1888 bool AssumeFrozen) {
1896 const Use *CurrU = &U;
1898 const unsigned MaxUsesToInspect = 3;
1899 for (
unsigned I = 0;
I < MaxUsesToInspect; ++
I) {
1900 std::optional<ValueLatticeElement> CondVal;
1904 if (DebugUsers && CurrU != &U)
1912 if (
I != 0 && !
isa<PHINode>(CurrI) && CurrI->getParent() != LastQueriedBB) {
1925 if (CurrU->getOperandNo() == 1)
1927 *getValueFromCondition(V,
SI->getCondition(),
true,
1929 else if (CurrU->getOperandNo() == 2)
1931 *getValueFromCondition(V,
SI->getCondition(),
false,
1935 CondVal = *getEdgeValueLocal(V,
PHI->getIncomingBlock(*CurrU),
1936 PHI->getParent(),
false);
1950 if (!CurrI->hasOneUse() ||
1966 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1977 if (
auto *Impl = Info.getImpl())
1997 F->getParent(), Intrinsic::experimental_guard);
2009 if (
auto *Impl = getImpl()) {
2016 FunctionAnalysisManager::Invalidator &Inv) {
2042 V =
V->stripPointerCasts();
2057 if (Result.isConstant())
2058 return Result.getConstant();
2059 if (Result.isConstantRange()) {
2062 return ConstantInt::get(V->getType(), *SingleVal);
2068 bool UndefAllowed) {
2071 return Result.asConstantRange(V->getType(), UndefAllowed);
2075 const Use &U,
bool UndefAllowed,
2078 getOrCreateImpl().getValueAtUse(U, DebugUsers, AssumeFrozen);
2079 return Result.asConstantRange(U->getType(), UndefAllowed);
2088 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CtxI);
2090 if (Result.isConstant())
2091 return Result.getConstant();
2092 if (Result.isConstantRange()) {
2095 return ConstantInt::get(V->getType(), *SingleVal);
2105 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CtxI);
2107 return Result.asConstantRange(V->getType(),
true);
2157 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CtxI);
2164 bool UseBlockValue) {
2174 if (V->getType()->isPointerTy() &&
C->isNullValue() &&
2183 auto &Impl = getOrCreateImpl();
2185 UseBlockValue ? Impl.getValueInBlock(V, CtxI->
getParent(), CtxI)
2186 : Impl.getValueAt(V, CtxI);
2226 if (
PHI->getParent() == BB) {
2228 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i < e; i++) {
2229 Value *Incoming =
PHI->getIncomingValue(i);
2237 Baseline = (i == 0) ? Result
2238 : (Baseline == Result ? Baseline
2257 while (++PI != PE) {
2259 if (Ret != Baseline)
2274 bool UseBlockValue) {
2284 if (UseBlockValue) {
2286 getOrCreateImpl().getValueInBlock(LHS, CtxI->
getParent(), CtxI);
2287 if (L.isOverdefined())
2291 getOrCreateImpl().getValueInBlock(RHS, CtxI->
getParent(), CtxI);
2300 if (
auto *Impl = getImpl())
2301 Impl->threadEdge(PredBB, OldSucc, NewSucc);
2305 if (
auto *Impl = getImpl())
2306 Impl->forgetValue(V);
2310 if (
auto *Impl = getImpl())
2311 Impl->eraseBlock(BB);
2315 if (
auto *Impl = getImpl())
2320 if (
auto *Impl = getImpl())
2321 Impl->printLVI(F, DTree, OS);
2325void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
2329 for (
const auto &Arg :
F->args()) {
2332 if (Result.isUnknown())
2334 OS <<
"; LatticeVal for: '" << Arg <<
"' is: " << Result <<
"\n";
2342void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2343 const Instruction *
I, formatted_raw_ostream &OS) {
2346 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
2352 auto printResult = [&](
const BasicBlock *BB) {
2353 if (!BlocksContainingLVI.
insert(BB).second)
2357 OS <<
"; LatticeVal for: '" << *
I <<
"' in BB: '";
2359 OS <<
"' is: " <<
Result <<
"\n";
2362 printResult(ParentBB);
2365 for (
const auto *BBSucc :
successors(ParentBB))
2367 printResult(BBSucc);
2370 for (
const auto *U :
I->users())
2373 printResult(UseI->getParent());
2379 OS <<
"LVI for function '" <<
F.getName() <<
"':\n";
2382 LVI.printLVI(
F, DTree, OS);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseSet and SmallDenseSet classes.
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.
static bool isOperationFoldable(User *Usr)
static std::optional< ConstantRange > getRangeForNUWMulSquare(const Value *V, CmpInst::Predicate Pred, const Value *LHS, const Value *RHS)
Get the unsigned range for V from a mul nuw V, V comparison.
static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet, bool IsDereferenced=true)
static void AddNonNullPointersByInstruction(Instruction *I, NonNullPointerSet &PtrSet)
static std::optional< ConstantRange > getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS, function_ref< std::optional< ConstantRange >(const APInt &)> Fn)
static const unsigned MaxProcessedPerValue
static ValueLatticeElement getValueFromICmpCtpop(ICmpInst::Predicate Pred, Value *RHS)
Get value range for a "ctpop(Val) Pred RHS" condition.
static bool usesOperand(User *Usr, Value *Op)
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)
static Constant * getPredicateResult(CmpInst::Predicate Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL)
static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
static bool isKnownNonConstant(Value *V)
Returns true if we can statically tell that this value will never be a "useful" constant.
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
static void eraseBlock(MachineBasicBlock *MBB, LiveIntervals &LIS, MachineDomTreeUpdater &MDTU)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
SmallVector< MachineOperand, 4 > Cond
static bool InBlock(const Value *V, const BasicBlock *BB)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
Class for arbitrary precision integers.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
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.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
This class represents an incoming formal argument to a Function.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
unsigned getNumber() const
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI bool isEntryBlock() const
Return true if this is the entry block of the containing function.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
Value handle with callbacks on RAUW and destruction.
This is the base class for all instructions that perform data casts.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Type * getDestTy() const
Return the destination type, as a convenience.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This class represents a range of values.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
static LLVM_ABI ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
LLVM_ABI ConstantRange sqrtFloor() const
Calculate sqrtFloor range. See APInt::sqrtFloor().
LLVM_ABI ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
LLVM_ABI ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
static LLVM_ABI ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
static LLVM_ABI bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
bool isSingleElement() const
Return true if this set contains exactly one member.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
static LLVM_ABI ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
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 LLVM_ABI ConstantRange makeMaskNotEqualRange(const APInt &Mask, const APInt &C)
Initialize a range containing all values X that satisfy (X & Mask) / != C.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
LLVM_ABI ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
LLVM_ABI ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
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...
LLVM_ABI ConstantRange toConstantRange() const
Convert constant to an approximate constant range.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
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.
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FunctionPass class - This class is used to implement most global optimizations.
unsigned getMaxBlockNumber() const
Return a value larger than the largest block number.
unsigned getBlockNumberEpoch() const
Return the "epoch" of current block numbers.
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
This instruction inserts a single (scalar) element into a VectorType value.
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.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
A wrapper class for inspecting calls to intrinsic functions.
Analysis to compute lazy value information.
LLVM_ABI Result run(Function &F, FunctionAnalysisManager &FAM)
LazyValueInfoImpl(Function *F, AssumptionCache *AC, const DataLayout &DL, Function *GuardDecl)
ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CtxI=nullptr)
This is the query interface to determine the lattice value for the specified Value* that is true on t...
ValueLatticeElement getValueAt(Value *V, Instruction *CtxI)
This is the query interface to determine the lattice value for the specified Value* at the specified ...
ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB, Instruction *CtxI=nullptr)
This is the query interface to determine the lattice value for the specified Value* at the context in...
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
This is the update interface to inform the cache that an edge from PredBB to OldSucc has been threade...
ValueLatticeElement getValueAtUse(const Use &U, SmallVectorImpl< DbgVariableRecord * > *DebugUsers=nullptr, bool AssumeFrozen=false)
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Printing the LazyValueInfo Analysis.
void forgetValue(Value *V)
This is part of the update interface to remove information related to this value from the cache.
void eraseBlock(BasicBlock *BB)
This is part of the update interface to inform the cache that a block has been deleted.
void clear()
Complete flush all previously computed values.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Wrapper around LazyValueInfo.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LazyValueInfoWrapperPass()
This pass computes, caches, and vends lazy value constraint information.
LLVM_ABI ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed, SmallVectorImpl< DbgVariableRecord * > *DebugUsers=nullptr, bool AssumeFrozen=false)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
LLVM_ABI void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
LLVM_ABI Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CtxI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
LLVM_ABI void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
LLVM_ABI void releaseMemory()
LLVM_ABI Constant * getConstant(Value *V, Instruction *CtxI)
Determine whether the specified value is known to be a constant at the specified instruction.
LLVM_ABI void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Print the \LazyValueInfo Analysis.
LLVM_ABI Constant * getPredicateAt(CmpInst::Predicate Pred, Value *V, Constant *C, Instruction *CtxI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
LLVM_ABI void forgetValue(Value *V)
Remove information related to this value from the cache.
LLVM_ABI ConstantRange getConstantRange(Value *V, Instruction *CtxI, bool UndefAllowed)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
LLVM_ABI void clear()
Complete flush all previously computed values.
LLVM_ABI ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CtxI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
LLVM_ABI ~LazyValueInfo()
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
LLVM_ABI Constant * getPredicateOnEdge(CmpInst::Predicate Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CtxI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
An instruction for reading from memory.
This is the common base class for memset/memcpy/memmove.
This class wraps the llvm.memcpy/memmove intrinsics.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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.
This class represents a truncation of integer types.
unsigned getNoWrapKind() const
Returns the no-wrap kind of the operation.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
bool isSized() const
Return true if it makes sense to take the size of this type.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
This class represents lattice values for constants.
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
bool isOverdefined() const
static ValueLatticeElement getNot(Constant *C)
ConstantRange asConstantRange(unsigned BW, bool UndefAllowed=false) const
bool isNotConstant() const
std::optional< APInt > asConstantInteger() const
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
static ValueLatticeElement get(Constant *C)
Constant * getNotConstant() const
LLVM_ABI ValueLatticeElement intersect(const ValueLatticeElement &Other) const
Combine two sets of facts about the same value into a single set of facts.
Constant * getConstant() const
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
static ValueLatticeElement getOverdefined()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
bool erase(const ValueT &V)
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive,...
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#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.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
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)
PtrToIntSameSize_match< OpTy > m_PtrToIntSameSize(const DataLayout &DL, const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(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.
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_Ctpop(const Opnd0 &Op0)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
@ User
could "use" a pointer
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
BundleAttr getBundleAttrFromOBU(OperandBundleUse OBU)
@ Known
Known to have no common set bits.
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
static ConstantRange getRange(Value *Op, SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues)
Helper for getting ranges from Solver.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
LLVM_ABI bool assumeBundleImpliesNonNull(const Value *Val, const Function *Context, OperandBundleUse OBU)
LLVM_ABI bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be undef, but may be poison.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
LLVM_ABI FunctionPass * createLazyValueInfoPass()
createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.
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.
LLVM_ABI bool isValidAssumeForContext(const Instruction *I, const Instruction *CtxI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
auto dyn_cast_or_null(const Y &Val)
constexpr unsigned MaxAnalysisRecursionDepth
@ SPF_ABS
Floating point maxnum.
@ SPF_NABS
Absolute value.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMAX
Unsigned minimum.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
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.
LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
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...
LLVM_ABI Value * simplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
LLVM_ABI bool isNotCrossLaneOperation(const Instruction *I)
Return true if the instruction doesn't potentially cross vector lanes.
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
LLVM_ABI Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
DWARFExpression::Operation Op
bool isSafeToSpeculativelyExecuteWithVariableReplaced(const Instruction *I, bool IgnoreUBImplyingAttrs=true)
Don't use information from its non-constant operands.
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
static bool hasSingleValue(const ValueLatticeElement &Val)
constexpr unsigned BitWidth
auto pred_begin(const MachineBasicBlock *BB)
LLVM_ABI AssumeRangeInfo getAssumeRangeInfo(OperandBundleUse)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
LLVM_ABI void findDbgUsers(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the debug info records describing a value.
A special type used by analysis passes to provide an address that identifies that particular analysis...
SelectPatternFlavor Flavor
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?