42using namespace PatternMatch;
44#define DEBUG_TYPE "lazy-value-info"
55 "Lazy Value Information Analysis",
false,
true)
105 if (
A.isOverdefined())
107 if (
B.isOverdefined())
117 if (!
A.isConstantRange() || !
B.isConstantRange()) {
124 A.getConstantRange().intersectWith(
B.getConstantRange());
128 std::move(Range),
A.isConstantRangeIncludingUndef() ||
129 B.isConstantRangeIncludingUndef());
138 class LazyValueInfoCache;
139 struct LVIValueHandle final :
public CallbackVH {
140 LazyValueInfoCache *Parent;
142 LVIValueHandle(
Value *V, LazyValueInfoCache *
P =
nullptr)
145 void deleted()
override;
146 void allUsesReplacedWith(
Value *V)
override {
157 class LazyValueInfoCache {
162 struct BlockCacheEntry {
167 std::optional<NonNullPointerSet> NonNullPointers;
176 const BlockCacheEntry *getBlockEntry(
BasicBlock *BB)
const {
177 auto It = BlockCache.
find_as(BB);
178 if (It == BlockCache.
end())
180 return It->second.get();
183 BlockCacheEntry *getOrCreateBlockEntry(
BasicBlock *BB) {
184 auto It = BlockCache.
find_as(BB);
185 if (It == BlockCache.
end())
186 It = BlockCache.
insert({ BB, std::make_unique<BlockCacheEntry>() })
189 return It->second.get();
192 void addValueHandle(
Value *Val) {
193 auto HandleIt = ValueHandles.
find_as(Val);
194 if (HandleIt == ValueHandles.
end())
195 ValueHandles.
insert({ Val,
this });
201 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
205 if (
Result.isOverdefined())
206 Entry->OverDefined.insert(Val);
208 Entry->LatticeElements.insert({ Val,
Result });
213 std::optional<ValueLatticeElement>
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;
229 bool isNonNullAtEndOfBlock(
232 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
233 if (!Entry->NonNullPointers) {
234 Entry->NonNullPointers = InitFn(BB);
235 for (
Value *V : *Entry->NonNullPointers)
239 return Entry->NonNullPointers->count(V);
245 ValueHandles.
clear();
249 void eraseValue(
Value *V);
262void LazyValueInfoCache::eraseValue(
Value *V) {
263 for (
auto &Pair : BlockCache) {
264 Pair.second->LatticeElements.erase(V);
265 Pair.second->OverDefined.erase(V);
266 if (Pair.second->NonNullPointers)
267 Pair.second->NonNullPointers->erase(V);
270 auto HandleIt = ValueHandles.
find_as(V);
271 if (HandleIt != ValueHandles.
end())
272 ValueHandles.
erase(HandleIt);
275void LVIValueHandle::deleted() {
278 Parent->eraseValue(*
this);
281void LazyValueInfoCache::eraseBlock(
BasicBlock *BB) {
282 BlockCache.erase(BB);
285void LazyValueInfoCache::threadEdgeImpl(
BasicBlock *OldSucc,
297 std::vector<BasicBlock*> worklist;
298 worklist.push_back(OldSucc);
300 const BlockCacheEntry *Entry = getBlockEntry(OldSucc);
301 if (!Entry || Entry->OverDefined.empty())
304 Entry->OverDefined.end());
310 while (!worklist.empty()) {
315 if (ToUpdate == NewSucc)
continue;
318 auto OI = BlockCache.find_as(ToUpdate);
319 if (OI == BlockCache.end() || OI->second->OverDefined.empty())
321 auto &ValueSet = OI->second->OverDefined;
323 bool changed =
false;
324 for (
Value *V : ValsToClear) {
325 if (!ValueSet.erase(V))
333 if (!changed)
continue;
343class LazyValueInfoImpl;
345 LazyValueInfoImpl *LVIImpl;
351 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L,
DominatorTree &DTree)
352 : LVIImpl(
L), DT(DTree) {}
354 void emitBasicBlockStartAnnot(
const BasicBlock *BB,
365class LazyValueInfoImpl {
368 LazyValueInfoCache TheCache;
380 bool pushBlockValue(
const std::pair<BasicBlock *, Value *> &BV) {
381 if (!BlockValueSet.
insert(BV).second)
385 << BV.first->getName() <<
"\n");
397 std::optional<ValueLatticeElement> getBlockValue(
Value *Val,
BasicBlock *BB,
407 std::optional<ValueLatticeElement> solveBlockValueImpl(
Value *Val,
409 std::optional<ValueLatticeElement> solveBlockValueNonLocal(
Value *Val,
411 std::optional<ValueLatticeElement> solveBlockValuePHINode(
PHINode *PN,
413 std::optional<ValueLatticeElement> solveBlockValueSelect(
SelectInst *S,
417 std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
421 std::optional<ValueLatticeElement>
423 std::optional<ValueLatticeElement> solveBlockValueCast(
CastInst *CI,
425 std::optional<ValueLatticeElement>
427 std::optional<ValueLatticeElement> solveBlockValueIntrinsic(
IntrinsicInst *II,
429 std::optional<ValueLatticeElement>
432 void intersectAssumeOrGuardBlockValueConstantRange(
Value *Val,
464 LazyValueInfoAnnotatedWriter Writer(
this, DTree);
465 F.print(
OS, &Writer);
471 TheCache.eraseBlock(BB);
480 : AC(AC),
DL(
DL), GuardDecl(GuardDecl) {}
485void LazyValueInfoImpl::solve() {
487 BlockValueStack.
begin(), BlockValueStack.
end());
489 unsigned processedCount = 0;
490 while (!BlockValueStack.
empty()) {
502 dbgs() <<
"Giving up on stack because we are getting too deep\n");
504 while (!StartingStack.empty()) {
505 std::pair<BasicBlock *, Value *> &
e = StartingStack.back();
506 TheCache.insertResult(
e.second,
e.first,
508 StartingStack.pop_back();
510 BlockValueSet.
clear();
511 BlockValueStack.
clear();
514 std::pair<BasicBlock *, Value *>
e = BlockValueStack.
back();
515 assert(BlockValueSet.
count(e) &&
"Stack value should be in BlockValueSet!");
517 if (solveBlockValue(
e.second,
e.first)) {
519 assert(BlockValueStack.
back() == e &&
"Nothing should have been pushed!");
521 std::optional<ValueLatticeElement> BBLV =
522 TheCache.getCachedValueInfo(
e.second,
e.first);
523 assert(BBLV &&
"Result should be in cache!");
525 dbgs() <<
"POP " << *
e.second <<
" in " <<
e.first->getName() <<
" = "
530 BlockValueSet.
erase(e);
533 assert(BlockValueStack.
back() != e &&
"Stack should have been pushed!");
538std::optional<ValueLatticeElement>
542 if (
Constant *VC = dyn_cast<Constant>(Val))
545 if (std::optional<ValueLatticeElement> OptLatticeVal =
546 TheCache.getCachedValueInfo(Val, BB)) {
547 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
548 return OptLatticeVal;
552 if (!pushBlockValue({ BB, Val }))
562 case Instruction::Load:
563 case Instruction::Call:
564 case Instruction::Invoke:
566 if (isa<IntegerType>(BBI->
getType())) {
577 assert(!isa<Constant>(Val) &&
"Value should not be constant");
578 assert(!TheCache.getCachedValueInfo(Val, BB) &&
579 "Value should not be in cache");
583 std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
588 TheCache.insertResult(Val, BB, *Res);
592std::optional<ValueLatticeElement>
596 return solveBlockValueNonLocal(Val, BB);
598 if (
PHINode *PN = dyn_cast<PHINode>(BBI))
599 return solveBlockValuePHINode(PN, BB);
601 if (
auto *SI = dyn_cast<SelectInst>(BBI))
602 return solveBlockValueSelect(SI, BB);
618 if (
auto *CI = dyn_cast<CastInst>(BBI))
619 return solveBlockValueCast(CI, BB);
622 return solveBlockValueBinaryOp(BO, BB);
624 if (
auto *EVI = dyn_cast<ExtractValueInst>(BBI))
625 return solveBlockValueExtractValue(EVI, BB);
627 if (
auto *II = dyn_cast<IntrinsicInst>(BBI))
628 return solveBlockValueIntrinsic(II, BB);
632 <<
"' - unknown inst def found.\n");
638 if (
Ptr->getType()->getPointerAddressSpace() == 0)
644 if (
LoadInst *L = dyn_cast<LoadInst>(
I)) {
646 }
else if (
StoreInst *S = dyn_cast<StoreInst>(
I)) {
649 if (
MI->isVolatile())
return;
653 if (!Len || Len->isZero())
return;
661bool LazyValueInfoImpl::isNonNullAtEndOfBlock(
Value *Val,
BasicBlock *BB) {
667 return TheCache.isNonNullAtEndOfBlock(Val, BB, [](
BasicBlock *BB) {
668 NonNullPointerSet NonNullPointers;
671 return NonNullPointers;
675std::optional<ValueLatticeElement>
676LazyValueInfoImpl::solveBlockValueNonLocal(
Value *Val,
BasicBlock *BB) {
682 assert(isa<Argument>(Val) &&
"Unknown live-in to the entry block");
696 std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
701 Result.mergeIn(*EdgeResult);
705 if (
Result.isOverdefined()) {
707 <<
"' - overdefined because of pred '"
708 << Pred->getName() <<
"' (non local).\n");
718std::optional<ValueLatticeElement>
731 std::optional<ValueLatticeElement> EdgeResult =
732 getEdgeValue(PhiVal, PhiBB, BB, PN);
737 Result.mergeIn(*EdgeResult);
741 if (
Result.isOverdefined()) {
743 <<
"' - overdefined because of pred (local).\n");
750 assert(!
Result.isOverdefined() &&
"Possible PHI in entry block?");
755 bool isTrueDest =
true);
759void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
761 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
773 auto *
I = cast<CallInst>(AssumeVH);
781 if (GuardDecl && !GuardDecl->
use_empty() &&
796 isNonNullAtEndOfBlock(Val, BB))
805 return ConstantRange::getFull(
DL.getTypeSizeInBits(Ty));
808std::optional<ValueLatticeElement>
811 std::optional<ValueLatticeElement> OptTrueVal =
812 getBlockValue(
SI->getTrueValue(), BB, SI);
817 std::optional<ValueLatticeElement> OptFalseVal =
818 getBlockValue(
SI->getFalseValue(), BB, SI);
834 ((LHS ==
SI->getTrueValue() && RHS ==
SI->getFalseValue()) ||
835 (RHS ==
SI->getTrueValue() && LHS ==
SI->getFalseValue()))) {
841 return TrueCR.
smin(FalseCR);
843 return TrueCR.
umin(FalseCR);
845 return TrueCR.
smax(FalseCR);
847 return TrueCR.
umax(FalseCR);
851 ResultCR,
TrueVal.isConstantRangeIncludingUndef() ||
852 FalseVal.isConstantRangeIncludingUndef());
856 if (LHS ==
SI->getTrueValue())
858 TrueCR.
abs(),
TrueVal.isConstantRangeIncludingUndef());
859 if (LHS ==
SI->getFalseValue())
861 FalseCR.
abs(),
FalseVal.isConstantRangeIncludingUndef());
866 if (LHS ==
SI->getTrueValue())
869 if (LHS ==
SI->getFalseValue())
893std::optional<ConstantRange>
895 std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
901std::optional<ValueLatticeElement>
912 case Instruction::Trunc:
913 case Instruction::SExt:
914 case Instruction::ZExt:
915 case Instruction::BitCast:
920 <<
"' - overdefined (unknown cast).\n");
927 std::optional<ConstantRange> LHSRes = getRangeFor(CI->
getOperand(0), CI, BB);
942std::optional<ValueLatticeElement>
943LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
951 std::optional<ConstantRange> LHSRes = getRangeFor(
I->getOperand(0),
I, BB);
952 std::optional<ConstantRange> RHSRes = getRangeFor(
I->getOperand(1),
I, BB);
953 if (!LHSRes || !RHSRes)
962std::optional<ValueLatticeElement>
965 "all operands to binary operators are sized");
966 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
967 unsigned NoWrapKind = 0;
968 if (OBO->hasNoUnsignedWrap())
970 if (OBO->hasNoSignedWrap())
973 return solveBlockValueBinaryOpImpl(
980 return solveBlockValueBinaryOpImpl(
986std::optional<ValueLatticeElement>
989 return solveBlockValueBinaryOpImpl(
995std::optional<ValueLatticeElement>
1000 <<
"' - unknown intrinsic.\n");
1006 std::optional<ConstantRange>
Range = getRangeFor(Op, II, BB);
1008 return std::nullopt;
1017std::optional<ValueLatticeElement>
1022 return solveBlockValueOverflowIntrinsic(WO, BB);
1029 return getBlockValue(V, BB, EVI);
1032 <<
"' - overdefined (unknown extractvalue).\n");
1077 if (
auto *Ranges =
I->getMetadata(LLVMContext::MD_range))
1094 if (isa<Constant>(
RHS)) {
1098 else if (!isa<UndefValue>(
RHS))
1123 Known.
Zero = ~*
C & *Mask;
1124 Known.
One = *
C & *Mask;
1184 bool isTrueDest = CondVal.
getInt();
1189 if (
auto *EVI = dyn_cast<ExtractValueInst>(
Cond))
1198 auto NV = Visited.
find(NKey);
1199 if (NV == Visited.
end()) {
1201 return std::nullopt;
1222 if ((isTrueDest ^ IsAnd) && (LV != Visited.
end())) {
1224 if (V.isOverdefined())
1226 if (RV != Visited.
end()) {
1227 V.mergeIn(RV->second);
1232 if (LV == Visited.
end() || RV == Visited.
end()) {
1234 if (LV == Visited.
end())
1236 if (RV == Visited.
end())
1238 return std::nullopt;
1241 return intersect(LV->second, RV->second);
1261 bool isRevisit = !Iter.second;
1263 Val, CurrentCond, isRevisit, Visited, Worklist);
1265 Visited[CurrentCond] = *Result;
1268 }
while (!Worklist.
empty());
1270 auto Result = Visited.
find(CondKey);
1272 return Result->second;
1285 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1293 const APInt &OpConstVal,
1298 if (
auto *CI = dyn_cast<CastInst>(Usr)) {
1300 if (
auto *
C = dyn_cast_or_null<ConstantInt>(
1305 }
else if (
auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1308 assert((Op0Match || Op1Match) &&
1309 "Operand 0 nor Operand 1 isn't a match");
1312 if (
auto *
C = dyn_cast_or_null<ConstantInt>(
1316 }
else if (isa<FreezeInst>(Usr)) {
1317 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op &&
"Operand 0 isn't Op");
1334 if (BI->isConditional() &&
1335 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1336 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1337 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1338 "BBTo isn't a successor of BBFrom");
1339 Value *Condition = BI->getCondition();
1343 if (Condition == Val)
1351 if (!Result.isOverdefined())
1354 if (
User *Usr = dyn_cast<User>(Val)) {
1355 assert(Result.isOverdefined() &&
"Result isn't overdefined");
1369 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1379 for (
unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1380 Value *Op = Usr->getOperand(i);
1383 if (std::optional<APInt> OpConst =
1392 if (!Result.isOverdefined())
1400 Value *Condition =
SI->getCondition();
1401 if (!isa<IntegerType>(Val->
getType()))
1402 return std::nullopt;
1403 bool ValUsesConditionAndMayBeFoldable =
false;
1404 if (Condition != Val) {
1406 if (
User *Usr = dyn_cast<User>(Val))
1409 if (!ValUsesConditionAndMayBeFoldable)
1410 return std::nullopt;
1412 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1413 "Condition != Val nor Val doesn't use Condition");
1415 bool DefaultCase =
SI->getDefaultDest() == BBTo;
1419 for (
auto Case :
SI->cases()) {
1420 APInt CaseValue = Case.getCaseValue()->getValue();
1422 if (ValUsesConditionAndMayBeFoldable) {
1423 User *Usr = cast<User>(Val);
1428 return std::nullopt;
1438 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1440 }
else if (Case.getCaseSuccessor() == BBTo)
1441 EdgesVals = EdgesVals.
unionWith(EdgeVal);
1445 return std::nullopt;
1450std::optional<ValueLatticeElement>
1454 if (
Constant *VC = dyn_cast<Constant>(Val))
1464 std::optional<ValueLatticeElement> OptInBlock =
1467 return std::nullopt;
1478 intersectAssumeOrGuardBlockValueConstantRange(Val,
InBlock, CxtI);
1485 LLVM_DEBUG(
dbgs() <<
"LVI Getting block end value " << *V <<
" at '"
1489 std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
1492 OptResult = getBlockValue(V, BB, CxtI);
1493 assert(OptResult &&
"Value not available after solving");
1505 if (
auto *
C = dyn_cast<Constant>(V))
1509 if (
auto *
I = dyn_cast<Instruction>(V))
1511 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1520 LLVM_DEBUG(
dbgs() <<
"LVI Getting edge value " << *V <<
" from '"
1524 std::optional<ValueLatticeElement>
Result =
1525 getEdgeValue(V, FromBB, ToBB, CxtI);
1528 Result = getEdgeValue(V, FromBB, ToBB, CxtI);
1529 assert(Result &&
"More work to do after problem solved?");
1538 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1549 assert(M &&
"getCache() called with a null Module");
1551 Function *GuardDecl = M->getFunction(
1553 PImpl =
new LazyValueInfoImpl(AC,
DL, GuardDecl);
1555 return *
static_cast<LazyValueInfoImpl*
>(PImpl);
1559 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1560 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1563 getImpl(Info.PImpl, Info.AC,
F.getParent()).clear();
1582 delete &
getImpl(PImpl, AC,
nullptr);
1605 return LazyValueInfo(&AC, &
F.getParent()->getDataLayout(), &TLI);
1615 V = V->stripPointerCasts();
1617 if (isa<AllocaInst>(V))
1631 if (Result.isConstant())
1632 return Result.getConstant();
1633 if (Result.isConstantRange()) {
1642 bool UndefAllowed) {
1643 assert(V->getType()->isIntegerTy());
1644 unsigned Width = V->getType()->getIntegerBitWidth();
1648 if (Result.isUnknown())
1649 return ConstantRange::getEmpty(Width);
1650 if (Result.isConstantRange(UndefAllowed))
1651 return Result.getConstantRange(UndefAllowed);
1654 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1655 "ConstantInt value must be represented as constantrange");
1656 return ConstantRange::getFull(Width);
1660 bool UndefAllowed) {
1667 const Use *CurrU = &U;
1669 const unsigned MaxUsesToInspect = 3;
1670 for (
unsigned I = 0;
I < MaxUsesToInspect; ++
I) {
1671 std::optional<ValueLatticeElement> CondVal;
1672 auto *CurrI = cast<Instruction>(CurrU->getUser());
1673 if (
auto *
SI = dyn_cast<SelectInst>(CurrI)) {
1678 if (CurrU->getOperandNo() == 1)
1680 else if (CurrU->getOperandNo() == 2)
1682 }
else if (
auto *
PHI = dyn_cast<PHINode>(CurrI)) {
1687 if (CondVal && CondVal->isConstantRange())
1713 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1715 if (Result.isConstant())
1716 return Result.getConstant();
1717 if (Result.isConstantRange()) {
1729 unsigned Width = V->getType()->getIntegerBitWidth();
1732 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1734 if (Result.isUnknown())
1735 return ConstantRange::getEmpty(Width);
1736 if (Result.isConstantRange())
1737 return Result.getConstantRange();
1740 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1741 "ConstantInt value must be represented as constantrange");
1742 return ConstantRange::getFull(Width);
1752 if (
ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1818 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1832 if (V->getType()->isPointerTy() &&
C->isNullValue() &&
1842 :
getImpl(PImpl, AC, M).getValueAt(V, CxtI);
1881 if (
auto *
PHI = dyn_cast<PHINode>(V))
1882 if (
PHI->getParent() == BB) {
1884 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i < e; i++) {
1885 Value *Incoming =
PHI->getIncomingValue(i);
1893 Baseline = (i == 0) ? Result
1894 : (Baseline == Result ? Baseline
1906 if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
1913 while (++PI != PE) {
1915 if (Ret != Baseline)
1931 bool UseBlockValue) {
1934 if (
auto *
C = dyn_cast<Constant>(
RHS))
1936 if (
auto *
C = dyn_cast<Constant>(
LHS))
1943 if (UseBlockValue) {
1947 if (L.isOverdefined())
1954 M->getDataLayout())) {
1955 if (Res->isNullValue())
1957 if (Res->isOneValue())
1968 .threadEdge(PredBB, OldSucc, NewSucc);
1980 getImpl(PImpl, AC, M).clear();
1986 getImpl(PImpl, AC,
F.getParent()).printLVI(
F, DTree,
OS);
1991void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1995 for (
const auto &
Arg :
F->args()) {
1998 if (Result.isUnknown())
2000 OS <<
"; LatticeVal for: '" <<
Arg <<
"' is: " << Result <<
"\n";
2008void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2011 auto *ParentBB =
I->getParent();
2018 auto printResult = [&](
const BasicBlock *BB) {
2019 if (!BlocksContainingLVI.
insert(BB).second)
2023 OS <<
"; LatticeVal for: '" << *
I <<
"' in BB: '";
2028 printResult(ParentBB);
2031 for (
const auto *BBSucc :
successors(ParentBB))
2032 if (DT.dominates(ParentBB, BBSucc))
2033 printResult(BBSucc);
2036 for (
const auto *U :
I->users())
2037 if (
auto *UseI = dyn_cast<Instruction>(U))
2038 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
2039 printResult(UseI->getParent());
2061 dbgs() <<
"LVI for function '" <<
F.getName() <<
"':\n";
2062 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
2063 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2064 LVI.printLVI(
F, DTree,
dbgs());
2070char LazyValueInfoPrinter::ID = 0;
2072 "Lazy Value Info Printer Pass",
false,
false)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
SmallVector< MachineOperand, 4 > Cond
block Block Frequency Analysis
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
Given that RA is a live value
This file defines the DenseSet and SmallDenseSet classes.
static bool runOnFunction(Function &F, bool PostInlining)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool isOperationFoldable(User *Usr)
static ValueLatticeElement getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS, const APInt &Offset)
Get value range for a "(Val + Offset) Pred RHS" condition.
static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest=true)
static std::optional< ValueLatticeElement > getValueFromConditionImpl(Value *Val, CondValue CondVal, bool isRevisit, SmallDenseMap< CondValue, ValueLatticeElement > &Visited, SmallVectorImpl< CondValue > &Worklist)
static void AddNonNullPointersByInstruction(Instruction *I, NonNullPointerSet &PtrSet)
static bool hasSingleValue(const ValueLatticeElement &Val)
Returns true if this lattice value represents at most one possible value.
static const unsigned MaxProcessedPerValue
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const Module *M)
This lazily constructs the LazyValueInfoImpl.
static std::optional< ValueLatticeElement > getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo)
Compute the value of Val on the edge BBFrom -> BBTo.
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest)
static bool usesOperand(User *Usr, Value *Op)
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)
static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet)
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val, Type *Ty, const DataLayout &DL)
static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL, TargetLibraryInfo *TLI)
static bool isKnownNonConstant(Value *V)
Returns true if we can statically tell that this value will never be a "useful" constant.
PointerIntPair< Value *, 1, bool > CondValue
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
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)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool InBlock(const Value *V, const BasicBlock *BB)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
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.
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
const Instruction & back() const
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
Conditional or Unconditional Branch instruction.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
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_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
@ 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 Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
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...
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind) const
Return a new range representing the possible values resulting from an application of the specified ov...
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
static 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...
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
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.
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
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 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 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.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
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.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
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.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Analysis to compute lazy value information.
Result run(Function &F, FunctionAnalysisManager &FAM)
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.
ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
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...
Tristate
This is used to return true/false/dunno results.
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
void clear(const Module *M)
Complete flush all previously computed values.
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Print the \LazyValueInfo Analysis.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
An instruction for reading from memory.
This is the common base class for memset/memcpy/memmove.
This class wraps the llvm.memcpy/memmove intrinsics.
A Module instance is used to store all the information related to an LLVM module.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
PointerIntPair - This class implements a pair of a pointer and small integer.
PointerTy getPointer() const
A set of analyses that are preserved following a run of a transformation pass.
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.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
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.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
static IntegerType * getInt1Ty(LLVMContext &C)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
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)
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
Constant * getConstant() const
static ValueLatticeElement getOverdefined()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
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.
LLVMContext & getContext() const
All values hold a context through their type.
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)
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive,...
bool erase(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
An efficient, type-erasing, non-owning reference to a callable.
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Solution solve(PBQPRAGraph &G)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
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.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
This is an optimization pass for GlobalISel generic memory operations.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
auto successors(const MachineBasicBlock *BB)
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 a range to a container.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
void initializeLazyValueInfoPrinterPass(PassRegistry &)
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
FunctionPass * createLazyValueInfoPass()
createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.
Interval::pred_iterator pred_end(Interval *I)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
@ SPF_ABS
Floating point maxnum.
@ SPF_NABS
Absolute value.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMAX
Unsigned minimum.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Value * simplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void initializeLazyValueInfoWrapperPassPass(PassRegistry &)
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
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?