Go to the documentation of this file.
42 using 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 {
176 const BlockCacheEntry *getBlockEntry(
BasicBlock *
BB)
const {
178 if (It == BlockCache.
end())
180 return It->second.get();
183 BlockCacheEntry *getOrCreateBlockEntry(
BasicBlock *
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 });
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);
262 void 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);
275 void LVIValueHandle::deleted() {
278 Parent->eraseValue(*
this);
282 BlockCache.erase(
BB);
285 void 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;
343 class LazyValueInfoImpl;
345 LazyValueInfoImpl *LVIImpl;
351 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L,
DominatorTree &DTree)
352 : LVIImpl(L), DT(DTree) {}
365 class LazyValueInfoImpl {
368 LazyValueInfoCache TheCache;
380 bool pushBlockValue(
const std::pair<BasicBlock *, Value *> &BV) {
381 if (!BlockValueSet.
insert(BV).second)
385 << BV.first->getName() <<
"\n");
386 BlockValueStack.push_back(BV);
430 void intersectAssumeOrGuardBlockValueConstantRange(
Value *Val,
462 LazyValueInfoAnnotatedWriter Writer(
this, DTree);
463 F.print(OS, &Writer);
469 TheCache.eraseBlock(
BB);
478 : AC(AC),
DL(
DL), GuardDecl(GuardDecl) {}
485 BlockValueStack.begin(), BlockValueStack.end());
487 unsigned processedCount = 0;
488 while (!BlockValueStack.empty()) {
500 dbgs() <<
"Giving up on stack because we are getting too deep\n");
502 while (!StartingStack.empty()) {
503 std::pair<BasicBlock *, Value *> &
e = StartingStack.back();
504 TheCache.insertResult(
e.second,
e.first,
506 StartingStack.pop_back();
508 BlockValueSet.
clear();
509 BlockValueStack.
clear();
512 std::pair<BasicBlock *, Value *>
e = BlockValueStack.back();
513 assert(BlockValueSet.
count(
e) &&
"Stack value should be in BlockValueSet!");
515 if (solveBlockValue(
e.second,
e.first)) {
517 assert(BlockValueStack.back() ==
e &&
"Nothing should have been pushed!");
520 TheCache.getCachedValueInfo(
e.second,
e.first);
521 assert(BBLV &&
"Result should be in cache!");
523 dbgs() <<
"POP " << *
e.second <<
" in " <<
e.first->getName() <<
" = "
527 BlockValueStack.pop_back();
531 assert(BlockValueStack.back() !=
e &&
"Stack should have been pushed!");
543 TheCache.getCachedValueInfo(Val,
BB)) {
544 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
545 return OptLatticeVal;
549 if (!pushBlockValue({
BB, Val }))
561 case Instruction::Invoke:
563 if (isa<IntegerType>(BBI->
getType())) {
574 assert(!isa<Constant>(Val) &&
"Value should not be constant");
575 assert(!TheCache.getCachedValueInfo(Val,
BB) &&
576 "Value should not be in cache");
585 TheCache.insertResult(Val,
BB, *Res);
593 return solveBlockValueNonLocal(Val,
BB);
595 if (
PHINode *PN = dyn_cast<PHINode>(BBI))
596 return solveBlockValuePHINode(PN,
BB);
598 if (
auto *
SI = dyn_cast<SelectInst>(BBI))
599 return solveBlockValueSelect(
SI,
BB);
615 if (
auto *CI = dyn_cast<CastInst>(BBI))
616 return solveBlockValueCast(CI,
BB);
619 return solveBlockValueBinaryOp(BO,
BB);
621 if (
auto *EVI = dyn_cast<ExtractValueInst>(BBI))
622 return solveBlockValueExtractValue(EVI,
BB);
624 if (
auto *II = dyn_cast<IntrinsicInst>(BBI))
625 return solveBlockValueIntrinsic(II,
BB);
629 <<
"' - unknown inst def found.\n");
641 if (
LoadInst *L = dyn_cast<LoadInst>(
I)) {
643 }
else if (
StoreInst *
S = dyn_cast<StoreInst>(
I)) {
646 if (
MI->isVolatile())
return;
650 if (!Len || Len->
isZero())
return;
664 return TheCache.isNonNullAtEndOfBlock(Val,
BB, [](
BasicBlock *
BB) {
665 NonNullPointerSet NonNullPointers;
668 return NonNullPointers;
678 if (
BB->isEntryBlock()) {
679 assert(isa<Argument>(Val) &&
"Unknown live-in to the entry block");
698 Result.mergeIn(*EdgeResult);
702 if (
Result.isOverdefined()) {
704 <<
"' - overdefined because of pred (non local).\n");
728 getEdgeValue(PhiVal, PhiBB,
BB, PN);
733 Result.mergeIn(*EdgeResult);
737 if (
Result.isOverdefined()) {
739 <<
"' - overdefined because of pred (local).\n");
746 assert(!
Result.isOverdefined() &&
"Possible PHI in entry block?");
751 bool isTrueDest =
true);
755 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
757 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
769 auto *
I = cast<CallInst>(AssumeVH);
777 if (GuardDecl && !GuardDecl->
use_empty() &&
791 if (PTy &&
BB->getTerminator() == BBI &&
792 isNonNullAtEndOfBlock(Val,
BB))
801 return ConstantRange::getFull(
DL.getTypeSizeInBits(Ty));
808 getBlockValue(
SI->getTrueValue(),
BB,
SI);
814 getBlockValue(
SI->getFalseValue(),
BB,
SI);
830 ((
LHS ==
SI->getTrueValue() &&
RHS ==
SI->getFalseValue()) ||
831 (
RHS ==
SI->getTrueValue() &&
LHS ==
SI->getFalseValue()))) {
837 return TrueCR.
smin(FalseCR);
839 return TrueCR.
umin(FalseCR);
841 return TrueCR.
smax(FalseCR);
843 return TrueCR.
umax(FalseCR);
847 ResultCR,
TrueVal.isConstantRangeIncludingUndef() ||
848 FalseVal.isConstantRangeIncludingUndef());
852 if (
LHS ==
SI->getTrueValue())
854 TrueCR.
abs(),
TrueVal.isConstantRangeIncludingUndef());
855 if (
LHS ==
SI->getFalseValue())
857 FalseCR.
abs(),
FalseVal.isConstantRangeIncludingUndef());
862 if (
LHS ==
SI->getTrueValue())
864 Zero.sub(TrueCR.
abs()),
FalseVal.isConstantRangeIncludingUndef());
865 if (
LHS ==
SI->getFalseValue())
867 Zero.sub(FalseCR.
abs()),
FalseVal.isConstantRangeIncludingUndef());
905 case Instruction::Trunc:
906 case Instruction::SExt:
907 case Instruction::ZExt:
908 case Instruction::BitCast:
913 <<
"' - overdefined (unknown cast).\n");
957 "all operands to binary operators are sized");
958 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
959 unsigned NoWrapKind = 0;
960 if (OBO->hasNoUnsignedWrap())
962 if (OBO->hasNoSignedWrap())
965 return solveBlockValueBinaryOpImpl(
972 return solveBlockValueBinaryOpImpl(
981 return solveBlockValueBinaryOpImpl(
991 <<
"' - unknown intrinsic.\n");
1000 OpRanges.push_back(*Range);
1011 return solveBlockValueOverflowIntrinsic(WO,
BB);
1018 return getBlockValue(V,
BB, EVI);
1021 <<
"' - overdefined (unknown extractvalue).\n");
1066 if (
auto *Ranges =
I->getMetadata(LLVMContext::MD_range))
1083 if (isa<Constant>(
RHS)) {
1087 else if (!isa<UndefValue>(
RHS))
1173 if (
auto *EVI = dyn_cast<ExtractValueInst>(
Cond))
1188 auto LV = Visited.
find(L);
1189 auto RV = Visited.
find(R);
1195 if ((isTrueDest ^ IsAnd) && (LV != Visited.
end())) {
1199 if (RV != Visited.
end()) {
1205 if (LV == Visited.
end() || RV == Visited.
end()) {
1207 if (LV == Visited.
end())
1208 Worklist.push_back(L);
1209 if (RV == Visited.
end())
1210 Worklist.push_back(R);
1214 return intersect(LV->second, RV->second);
1223 Worklist.push_back(
Cond);
1225 Value *CurrentCond = Worklist.back();
1233 bool isRevisit = !Iter.second;
1235 Val, CurrentCond, isTrueDest, isRevisit, Visited, Worklist);
1237 Visited[CurrentCond] = *Result;
1238 Worklist.pop_back();
1240 }
while (!Worklist.empty());
1244 return Result->second;
1257 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1265 const APInt &OpConstVal,
1270 if (
auto *CI = dyn_cast<CastInst>(Usr)) {
1272 if (
auto *
C = dyn_cast_or_null<ConstantInt>(
1277 }
else if (
auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1280 assert((Op0Match || Op1Match) &&
1281 "Operand 0 nor Operand 1 isn't a match");
1284 if (
auto *
C = dyn_cast_or_null<ConstantInt>(
1288 }
else if (isa<FreezeInst>(Usr)) {
1289 assert(cast<FreezeInst>(Usr)->getOperand(0) ==
Op &&
"Operand 0 isn't Op");
1306 if (BI->isConditional() &&
1307 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1308 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1309 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1310 "BBTo isn't a successor of BBFrom");
1311 Value *Condition = BI->getCondition();
1315 if (Condition == Val)
1323 if (!Result.isOverdefined())
1326 if (
User *Usr = dyn_cast<User>(Val)) {
1327 assert(Result.isOverdefined() &&
"Result isn't overdefined");
1341 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1351 for (
unsigned i = 0;
i < Usr->getNumOperands(); ++
i) {
1363 if (!Result.isOverdefined())
1371 Value *Condition =
SI->getCondition();
1372 if (!isa<IntegerType>(Val->
getType()))
1374 bool ValUsesConditionAndMayBeFoldable =
false;
1375 if (Condition != Val) {
1377 if (
User *Usr = dyn_cast<User>(Val))
1380 if (!ValUsesConditionAndMayBeFoldable)
1383 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1384 "Condition != Val nor Val doesn't use Condition");
1386 bool DefaultCase =
SI->getDefaultDest() == BBTo;
1390 for (
auto Case :
SI->cases()) {
1391 APInt CaseValue = Case.getCaseValue()->getValue();
1393 if (ValUsesConditionAndMayBeFoldable) {
1394 User *Usr = cast<User>(Val);
1409 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1411 }
else if (Case.getCaseSuccessor() == BBTo)
1412 EdgesVals = EdgesVals.
unionWith(EdgeVal);
1447 intersectAssumeOrGuardBlockValueConstantRange(Val,
InBlock, CxtI);
1454 LLVM_DEBUG(
dbgs() <<
"LVI Getting block end value " << *V <<
" at '"
1455 <<
BB->getName() <<
"'\n");
1457 assert(BlockValueStack.empty() && BlockValueSet.
empty());
1461 OptResult = getBlockValue(V,
BB, CxtI);
1462 assert(OptResult &&
"Value not available after solving");
1474 if (
auto *
C = dyn_cast<Constant>(V))
1478 if (
auto *
I = dyn_cast<Instruction>(V))
1480 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1489 LLVM_DEBUG(
dbgs() <<
"LVI Getting edge value " << *V <<
" from '"
1496 Result = getEdgeValue(V, FromBB, ToBB, CxtI);
1497 assert(Result &&
"More work to do after problem solved?");
1506 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1517 assert(
M &&
"getCache() called with a null Module");
1521 PImpl =
new LazyValueInfoImpl(AC,
DL, GuardDecl);
1523 return *
static_cast<LazyValueInfoImpl*
>(PImpl);
1527 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1528 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1531 getImpl(Info.PImpl, Info.AC,
F.getParent()).clear();
1550 delete &
getImpl(PImpl, AC,
nullptr);
1573 return LazyValueInfo(&AC, &
F.getParent()->getDataLayout(), &TLI);
1585 if (isa<AllocaInst>(V))
1597 getImpl(PImpl, AC,
BB->getModule()).getValueInBlock(V,
BB, CxtI);
1599 if (Result.isConstant())
1600 return Result.getConstant();
1601 if (Result.isConstantRange()) {
1610 bool UndefAllowed) {
1615 getImpl(PImpl, AC,
BB->getModule()).getValueInBlock(V,
BB, CxtI);
1616 if (Result.isUnknown())
1617 return ConstantRange::getEmpty(
Width);
1618 if (Result.isConstantRange(UndefAllowed))
1619 return Result.getConstantRange(UndefAllowed);
1622 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1623 "ConstantInt value must be represented as constantrange");
1624 return ConstantRange::getFull(
Width);
1634 getImpl(PImpl, AC,
M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1636 if (Result.isConstant())
1637 return Result.getConstant();
1638 if (Result.isConstantRange()) {
1653 getImpl(PImpl, AC,
M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1655 if (Result.isUnknown())
1656 return ConstantRange::getEmpty(
Width);
1657 if (Result.isConstantRange())
1658 return Result.getConstantRange();
1661 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1662 "ConstantInt value must be represented as constantrange");
1663 return ConstantRange::getFull(
Width);
1673 if (
ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1739 getImpl(PImpl, AC,
M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1763 :
getImpl(PImpl, AC,
M).getValueAt(V, CxtI);
1802 if (
auto *PHI = dyn_cast<PHINode>(V))
1803 if (PHI->getParent() ==
BB) {
1805 for (
unsigned i = 0,
e = PHI->getNumIncomingValues();
i <
e;
i++) {
1806 Value *Incoming = PHI->getIncomingValue(
i);
1814 Baseline = (
i == 0) ? Result
1815 : (Baseline == Result ? Baseline
1827 if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() !=
BB) {
1834 while (++PI != PE) {
1836 if (
Ret != Baseline)
1852 bool UseBlockValue) {
1855 if (
auto *
C = dyn_cast<Constant>(
RHS))
1857 if (
auto *
C = dyn_cast<Constant>(
LHS))
1871 .threadEdge(PredBB, OldSucc, NewSucc);
1877 getImpl(PImpl, AC,
BB->getModule()).eraseBlock(
BB);
1889 getImpl(PImpl, AC,
F.getParent()).printLVI(
F, DTree, OS);
1894 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1897 auto *
F =
BB->getParent();
1898 for (
auto &
Arg :
F->args()) {
1901 if (Result.isUnknown())
1903 OS <<
"; LatticeVal for: '" <<
Arg <<
"' is: " << Result <<
"\n";
1911 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1914 auto *ParentBB =
I->getParent();
1922 if (!BlocksContainingLVI.
insert(
BB).second)
1926 OS <<
"; LatticeVal for: '" << *
I <<
"' in BB: '";
1927 BB->printAsOperand(OS,
false);
1928 OS <<
"' is: " <<
Result <<
"\n";
1931 printResult(ParentBB);
1935 if (DT.dominates(ParentBB, BBSucc))
1936 printResult(BBSucc);
1939 for (
auto *U :
I->users())
1940 if (
auto *UseI = dyn_cast<Instruction>(U))
1941 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1942 printResult(UseI->getParent());
1964 dbgs() <<
"LVI for function '" <<
F.getName() <<
"':\n";
1965 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1966 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1967 LVI.printLVI(
F, DTree,
dbgs());
1975 "Lazy Value Info Printer Pass",
false,
false)
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.
static ValueLatticeElement getNot(Constant *C)
A set of analyses that are preserved following a run of a transformation pass.
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
This class represents an incoming formal argument to a Function.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldCompareInstOperands - Attempt to constant fold a compare instruction (icmp/fcmp) with the...
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
@ SPF_SMAX
Unsigned minimum.
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest=true)
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
This is an optimization pass for GlobalISel generic memory operations.
static IntegerType * getInt1Ty(LLVMContext &C)
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
A parsed version of the target data layout string in and methods for querying it.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static bool isOperationFoldable(User *Usr)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
bool isPointerTy() const
True if this is an instance of PointerType.
static bool isKnownNonConstant(Value *V)
Returns true if we can statically tell that this value will never be a "useful" constant.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
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 ...
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest)
This class wraps the llvm.memcpy/memmove intrinsics.
Constant * getConstant() const
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) INITIALIZE_PASS_END(LazyValueInfoWrapperPass
Optional< APInt > asConstantInteger() const
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
SelectPatternFlavor Flavor
const APInt & getValue() const
Return the constant as an APInt value reference.
Analysis to compute lazy value information.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const Module *M)
This lazily constructs the LazyValueInfoImpl.
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...
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Constant * getNotConstant() const
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static bool hasSingleValue(const ValueLatticeElement &Val)
Returns true if this lattice value represents at most one possible value.
Implements a dense probed hash-table based set with some number of buckets stored inline.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
static Optional< ValueLatticeElement > getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, bool isRevisit, SmallDenseMap< Value *, ValueLatticeElement > &Visited, SmallVectorImpl< Value * > &Worklist)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionAnalysisManager FAM
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.
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
static void AddNonNullPointersByInstruction(Instruction *I, NonNullPointerSet &PtrSet)
The instances of the Type class are immutable: once they are created, they are never changed.
static ValueLatticeElement getOverdefined()
@ SPF_UMAX
Signed maximum.
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)
This is the common base class for memset/memcpy/memmove.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
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...
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.
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
std::pair< iterator, bool > insert(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.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
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...
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
Type * getDestTy() const
Return the destination type, as a convenience.
Result run(Function &F, FunctionAnalysisManager &FAM)
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...
LLVM Basic Block Representation.
constexpr bool hasValue() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static void clear(coro::Shape &Shape)
Value * SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
@ SPF_NABS
Absolute value.
static bool usesOperand(User *Usr, Value *Op)
print alias Alias Set Printer
This is the shared class of boolean and integer constants.
static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val, Type *Ty, const DataLayout &DL)
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
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,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
(vector float) vec_cmpeq(*A, *B) C
@ ICMP_ULE
unsigned less or equal
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
bool isSingleElement() const
Return true if this set contains exactly one member.
Represent the analysis usage information of a pass.
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL, TargetLibraryInfo *TLI)
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
BinaryOps getOpcode() const
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
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.
Legacy analysis pass which computes a DominatorTree.
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Print the \LazyValueInfo Analysis.
auto predecessors(MachineBasicBlock *BB)
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
This class implements an extremely fast bulk output stream that can only output to a stream.
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 Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Analysis containing CSE Info
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
API to communicate dependencies between analyses during invalidation.
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned getIntegerBitWidth() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
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 isIntegerTy() const
True if this is an instance of IntegerType.
An efficient, type-erasing, non-owning reference to a callable.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
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...
Implements a dense probed hash-table based set.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
static bool InBlock(const Value *V, const BasicBlock *BB)
An instruction for storing to memory.
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
This instruction compares its operands according to the predicate given to the constructor.
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
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...
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
A function analysis which provides an AssumptionCache.
Wrapper around LazyValueInfo.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
static ValueLatticeElement getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS, const APInt &Offset)
Get value range for a "(Val + Offset) Pred RHS" condition.
static const unsigned MaxProcessedPerValue
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
A special type used by analysis passes to provide an address that identifies that particular analysis...
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Class to represent pointers.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr const T & getValue() const &
@ SPF_ABS
Floating point maxnum.
StandardInstrumentations SI(Debug, VerifyEach)
@ ICMP_UGE
unsigned greater or equal
This class represents the LLVM 'select' instruction.
print Print MemDeps of function
This pass computes, caches, and vends lazy value constraint information.
A Module instance is used to store all the information related to an LLVM module.
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)
An immutable pass that tracks lazily created AssumptionCache objects.
SmallVector< MachineOperand, 4 > Cond
APInt zextOrSelf(unsigned width) const
Zero-extend this APInt if necessary to ensure that its bit width is >= width.
A cache of @llvm.assume calls within a function.
@ ICMP_ULT
unsigned less than
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * SimplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
Type * getType() const
All values are typed, get the type of this value.
LazyValueInfoWrapperPass()
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
This class represents lattice values for constants.
This is the base class for all instructions that perform data casts.
Represents an op.with.overflow intrinsic.
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool isOverdefined() const
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Solution solve(PBQPRAGraph &G)
static bool runOnFunction(Function &F, bool PostInlining)
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
void initializeLazyValueInfoWrapperPassPass(PassRegistry &)
void setPreservesAll()
Set by analyses that do not transform their input at all.
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Interval::pred_iterator pred_end(Interval *I)
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive,...
constexpr unsigned BitWidth
void clear(const Module *M)
Complete flush all previously computed values.
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
Provides information about what library functions are available for the current target.
bool isNotConstant() const
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Value handle with callbacks on RAUW and destruction.
This class represents a range of values.
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
A wrapper class for inspecting calls to intrinsic functions.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
FunctionPass * createLazyValueInfoPass()
createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.
void initializeLazyValueInfoPrinterPass(PassRegistry &)
const Instruction & back() const
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...
Pass interface - Implemented by all 'passes'.
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...
static ValueLatticeElement get(Constant *C)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
Tristate
This is used to return true/false/dunno results.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
@ ICMP_UGT
unsigned greater than
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
@ SPF_UMIN
Signed minimum.
const BasicBlock * getParent() const
Predicate getPredicate() const
Return the predicate for this instruction.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool erase(const ValueT &V)
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...
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
A container for analyses that lazily runs them and caches their results.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
Value * getOperand(unsigned i) const
bool isEmptySet() const
Return true if this set contains no members.
Conditional or Unconditional Branch instruction.
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
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 ...
static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet)
LLVM Value Representation.
static Optional< ValueLatticeElement > getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo)
Compute the value of Val on the edge BBFrom -> BBTo.
Analysis pass providing the TargetLibraryInfo.
static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
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...
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
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.
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.