1 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the interface for lazy computation of value constraint
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Analysis/LazyValueInfo.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/Analysis/AssumptionCache.h"
19 #include "llvm/Analysis/ConstantFolding.h"
20 #include "llvm/Analysis/TargetLibraryInfo.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/ConstantRange.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/Intrinsics.h"
30 #include "llvm/IR/LLVMContext.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/IR/ValueHandle.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/raw_ostream.h"
38 using namespace PatternMatch;
40 #define DEBUG_TYPE "lazy-value-info"
42 char LazyValueInfoWrapperPass::ID = 0;
43 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
44 "Lazy Value Information Analysis", false, true)
45 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
46 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
47 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
48 "Lazy Value Information Analysis", false, true)
51 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
54 AnalysisKey LazyValueAnalysis::Key;
56 //===----------------------------------------------------------------------===//
58 //===----------------------------------------------------------------------===//
60 /// This is the information tracked by LazyValueInfo for each value.
62 /// FIXME: This is basically just for bringup, this can be made a lot more rich
68 /// This Value has no known value yet. As a result, this implies the
69 /// producing instruction is dead. Caution: We use this as the starting
70 /// state in our local meet rules. In this usage, it's taken to mean
71 /// "nothing known yet".
74 /// This Value has a specific constant value. (For constant integers,
75 /// constantrange is used instead. Integer typed constantexprs can appear
79 /// This Value is known to not have the specified value. (For constant
80 /// integers, constantrange is used instead. As above, integer typed
81 /// constantexprs can appear here.)
84 /// The Value falls within this range. (Used only for integer typed values.)
87 /// We can not precisely model the dynamic values this value might take.
91 /// Val: This stores the current lattice value along with the Constant* for
92 /// the constant if this is a 'constant' or 'notconstant' value.
98 LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
100 static LVILatticeVal get(Constant *C) {
102 if (!isa<UndefValue>(C))
106 static LVILatticeVal getNot(Constant *C) {
108 if (!isa<UndefValue>(C))
109 Res.markNotConstant(C);
112 static LVILatticeVal getRange(ConstantRange CR) {
114 Res.markConstantRange(std::move(CR));
117 static LVILatticeVal getOverdefined() {
119 Res.markOverdefined();
123 bool isUndefined() const { return Tag == undefined; }
124 bool isConstant() const { return Tag == constant; }
125 bool isNotConstant() const { return Tag == notconstant; }
126 bool isConstantRange() const { return Tag == constantrange; }
127 bool isOverdefined() const { return Tag == overdefined; }
129 Constant *getConstant() const {
130 assert(isConstant() && "Cannot get the constant of a non-constant!");
134 Constant *getNotConstant() const {
135 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
139 ConstantRange getConstantRange() const {
140 assert(isConstantRange() &&
141 "Cannot get the constant-range of a non-constant-range!");
146 void markOverdefined() {
152 void markConstant(Constant *V) {
153 assert(V && "Marking constant with NULL");
154 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
155 markConstantRange(ConstantRange(CI->getValue()));
158 if (isa<UndefValue>(V))
161 assert((!isConstant() || getConstant() == V) &&
162 "Marking constant with different value");
163 assert(isUndefined());
168 void markNotConstant(Constant *V) {
169 assert(V && "Marking constant with NULL");
170 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
171 markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
174 if (isa<UndefValue>(V))
177 assert((!isConstant() || getConstant() != V) &&
178 "Marking constant !constant with same value");
179 assert((!isNotConstant() || getNotConstant() == V) &&
180 "Marking !constant with different value");
181 assert(isUndefined() || isConstant());
186 void markConstantRange(ConstantRange NewR) {
187 if (isConstantRange()) {
188 if (NewR.isEmptySet())
191 Range = std::move(NewR);
196 assert(isUndefined());
197 if (NewR.isEmptySet())
201 Range = std::move(NewR);
207 /// Merge the specified lattice value into this one, updating this
208 /// one and returning true if anything changed.
209 void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
210 if (RHS.isUndefined() || isOverdefined())
212 if (RHS.isOverdefined()) {
223 if (RHS.isConstant() && Val == RHS.Val)
229 if (isNotConstant()) {
230 if (RHS.isNotConstant() && Val == RHS.Val)
236 assert(isConstantRange() && "New LVILattice type?");
237 if (!RHS.isConstantRange()) {
238 // We can get here if we've encountered a constantexpr of integer type
239 // and merge it with a constantrange.
243 ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
244 if (NewR.isFullSet())
247 markConstantRange(NewR);
251 } // end anonymous namespace.
254 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
256 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
257 if (Val.isUndefined())
258 return OS << "undefined";
259 if (Val.isOverdefined())
260 return OS << "overdefined";
262 if (Val.isNotConstant())
263 return OS << "notconstant<" << *Val.getNotConstant() << '>';
264 if (Val.isConstantRange())
265 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
266 << Val.getConstantRange().getUpper() << '>';
267 return OS << "constant<" << *Val.getConstant() << '>';
271 /// Returns true if this lattice value represents at most one possible value.
272 /// This is as precise as any lattice value can get while still representing
274 static bool hasSingleValue(const LVILatticeVal &Val) {
275 if (Val.isConstantRange() &&
276 Val.getConstantRange().isSingleElement())
277 // Integer constants are single element ranges
279 if (Val.isConstant())
280 // Non integer constants
285 /// Combine two sets of facts about the same value into a single set of
286 /// facts. Note that this method is not suitable for merging facts along
287 /// different paths in a CFG; that's what the mergeIn function is for. This
288 /// is for merging facts gathered about the same value at the same location
289 /// through two independent means.
291 /// * This method does not promise to return the most precise possible lattice
292 /// value implied by A and B. It is allowed to return any lattice element
293 /// which is at least as strong as *either* A or B (unless our facts
294 /// conflict, see below).
295 /// * Due to unreachable code, the intersection of two lattice values could be
296 /// contradictory. If this happens, we return some valid lattice value so as
297 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
298 /// we do not make this guarantee. TODO: This would be a useful enhancement.
299 static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
300 // Undefined is the strongest state. It means the value is known to be along
301 // an unreachable path.
307 // If we gave up for one, but got a useable fact from the other, use it.
308 if (A.isOverdefined())
310 if (B.isOverdefined())
313 // Can't get any more precise than constants.
314 if (hasSingleValue(A))
316 if (hasSingleValue(B))
319 // Could be either constant range or not constant here.
320 if (!A.isConstantRange() || !B.isConstantRange()) {
321 // TODO: Arbitrary choice, could be improved
325 // Intersect two constant ranges
326 ConstantRange Range =
327 A.getConstantRange().intersectWith(B.getConstantRange());
328 // Note: An empty range is implicitly converted to overdefined internally.
329 // TODO: We could instead use Undefined here since we've proven a conflict
330 // and thus know this path must be unreachable.
331 return LVILatticeVal::getRange(std::move(Range));
334 //===----------------------------------------------------------------------===//
335 // LazyValueInfoCache Decl
336 //===----------------------------------------------------------------------===//
339 /// A callback value handle updates the cache when values are erased.
340 class LazyValueInfoCache;
341 struct LVIValueHandle final : public CallbackVH {
342 // Needs to access getValPtr(), which is protected.
343 friend struct DenseMapInfo<LVIValueHandle>;
345 LazyValueInfoCache *Parent;
347 LVIValueHandle(Value *V, LazyValueInfoCache *P)
348 : CallbackVH(V), Parent(P) { }
350 void deleted() override;
351 void allUsesReplacedWith(Value *V) override {
355 } // end anonymous namespace
358 /// This is the cache kept by LazyValueInfo which
359 /// maintains information about queries across the clients' queries.
360 class LazyValueInfoCache {
361 /// This is all of the cached block information for exactly one Value*.
362 /// The entries are sorted by the BasicBlock* of the
363 /// entries, allowing us to do a lookup with a binary search.
364 /// Over-defined lattice values are recorded in OverDefinedCache to reduce
366 struct ValueCacheEntryTy {
367 ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
368 LVIValueHandle Handle;
369 SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
372 /// This is all of the cached information for all values,
373 /// mapped from Value* to key information.
374 DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
376 /// This tracks, on a per-block basis, the set of values that are
377 /// over-defined at the end of that block.
378 typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
380 OverDefinedCacheTy OverDefinedCache;
382 /// Keep track of all blocks that we have ever seen, so we
383 /// don't spend time removing unused blocks from our caches.
384 DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
387 void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
388 SeenBlocks.insert(BB);
390 // Insert over-defined values into their own cache to reduce memory
392 if (Result.isOverdefined())
393 OverDefinedCache[BB].insert(Val);
395 auto It = ValueCache.find_as(Val);
396 if (It == ValueCache.end()) {
397 ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
398 It = ValueCache.find_as(Val);
399 assert(It != ValueCache.end() && "Val was just added to the map!");
401 It->second->BlockVals[BB] = Result;
405 bool isOverdefined(Value *V, BasicBlock *BB) const {
406 auto ODI = OverDefinedCache.find(BB);
408 if (ODI == OverDefinedCache.end())
411 return ODI->second.count(V);
414 bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
415 if (isOverdefined(V, BB))
418 auto I = ValueCache.find_as(V);
419 if (I == ValueCache.end())
422 return I->second->BlockVals.count(BB);
425 LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const {
426 if (isOverdefined(V, BB))
427 return LVILatticeVal::getOverdefined();
429 auto I = ValueCache.find_as(V);
430 if (I == ValueCache.end())
431 return LVILatticeVal();
432 auto BBI = I->second->BlockVals.find(BB);
433 if (BBI == I->second->BlockVals.end())
434 return LVILatticeVal();
438 /// clear - Empty the cache.
442 OverDefinedCache.clear();
445 /// Inform the cache that a given value has been deleted.
446 void eraseValue(Value *V);
448 /// This is part of the update interface to inform the cache
449 /// that a block has been deleted.
450 void eraseBlock(BasicBlock *BB);
452 /// Updates the cache to remove any influence an overdefined value in
453 /// OldSucc might have (unless also overdefined in NewSucc). This just
454 /// flushes elements from the cache and does not add any.
455 void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
457 friend struct LVIValueHandle;
461 void LazyValueInfoCache::eraseValue(Value *V) {
462 SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
463 for (auto &I : OverDefinedCache) {
464 SmallPtrSetImpl<Value *> &ValueSet = I.second;
466 if (ValueSet.empty())
467 ToErase.push_back(I.first);
469 for (auto &BB : ToErase)
470 OverDefinedCache.erase(BB);
475 void LVIValueHandle::deleted() {
476 // This erasure deallocates *this, so it MUST happen after we're done
477 // using any and all members of *this.
478 Parent->eraseValue(*this);
481 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
482 // Shortcut if we have never seen this block.
483 DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
484 if (I == SeenBlocks.end())
488 auto ODI = OverDefinedCache.find(BB);
489 if (ODI != OverDefinedCache.end())
490 OverDefinedCache.erase(ODI);
492 for (auto &I : ValueCache)
493 I.second->BlockVals.erase(BB);
496 void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
497 BasicBlock *NewSucc) {
498 // When an edge in the graph has been threaded, values that we could not
499 // determine a value for before (i.e. were marked overdefined) may be
500 // possible to solve now. We do NOT try to proactively update these values.
501 // Instead, we clear their entries from the cache, and allow lazy updating to
502 // recompute them when needed.
504 // The updating process is fairly simple: we need to drop cached info
505 // for all values that were marked overdefined in OldSucc, and for those same
506 // values in any successor of OldSucc (except NewSucc) in which they were
507 // also marked overdefined.
508 std::vector<BasicBlock*> worklist;
509 worklist.push_back(OldSucc);
511 auto I = OverDefinedCache.find(OldSucc);
512 if (I == OverDefinedCache.end())
513 return; // Nothing to process here.
514 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
516 // Use a worklist to perform a depth-first search of OldSucc's successors.
517 // NOTE: We do not need a visited list since any blocks we have already
518 // visited will have had their overdefined markers cleared already, and we
519 // thus won't loop to their successors.
520 while (!worklist.empty()) {
521 BasicBlock *ToUpdate = worklist.back();
524 // Skip blocks only accessible through NewSucc.
525 if (ToUpdate == NewSucc) continue;
527 // If a value was marked overdefined in OldSucc, and is here too...
528 auto OI = OverDefinedCache.find(ToUpdate);
529 if (OI == OverDefinedCache.end())
531 SmallPtrSetImpl<Value *> &ValueSet = OI->second;
533 bool changed = false;
534 for (Value *V : ValsToClear) {
535 if (!ValueSet.erase(V))
538 // If we removed anything, then we potentially need to update
539 // blocks successors too.
542 if (ValueSet.empty()) {
543 OverDefinedCache.erase(OI);
548 if (!changed) continue;
550 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
555 // The actual implementation of the lazy analysis and update. Note that the
556 // inheritance from LazyValueInfoCache is intended to be temporary while
557 // splitting the code and then transitioning to a has-a relationship.
558 class LazyValueInfoImpl {
560 /// Cached results from previous queries
561 LazyValueInfoCache TheCache;
563 /// This stack holds the state of the value solver during a query.
564 /// It basically emulates the callstack of the naive
565 /// recursive value lookup process.
566 std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
568 /// Keeps track of which block-value pairs are in BlockValueStack.
569 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
571 /// Push BV onto BlockValueStack unless it's already in there.
572 /// Returns true on success.
573 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
574 if (!BlockValueSet.insert(BV).second)
575 return false; // It's already in the stack.
577 DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
579 BlockValueStack.push(BV);
583 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
584 const DataLayout &DL; ///< A mandatory DataLayout
585 DominatorTree *DT; ///< An optional DT pointer.
587 LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
588 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
589 LVILatticeVal &Result, Instruction *CxtI = nullptr);
590 bool hasBlockValue(Value *Val, BasicBlock *BB);
592 // These methods process one work item and may add more. A false value
593 // returned means that the work item was not completely processed and must
594 // be revisited after going through the new items.
595 bool solveBlockValue(Value *Val, BasicBlock *BB);
596 bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB);
597 bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
598 bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
599 bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
601 bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI,
603 bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI,
605 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
612 /// This is the query interface to determine the lattice
613 /// value for the specified Value* at the end of the specified block.
614 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
615 Instruction *CxtI = nullptr);
617 /// This is the query interface to determine the lattice
618 /// value for the specified Value* at the specified instruction (generally
619 /// from an assume intrinsic).
620 LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
622 /// This is the query interface to determine the lattice
623 /// value for the specified Value* that is true on the specified edge.
624 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
625 Instruction *CxtI = nullptr);
627 /// Complete flush all previously computed values
632 /// This is part of the update interface to inform the cache
633 /// that a block has been deleted.
634 void eraseBlock(BasicBlock *BB) {
635 TheCache.eraseBlock(BB);
638 /// This is the update interface to inform the cache that an edge from
639 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
640 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
642 LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
643 DominatorTree *DT = nullptr)
644 : AC(AC), DL(DL), DT(DT) {}
646 } // end anonymous namespace
648 void LazyValueInfoImpl::solve() {
649 while (!BlockValueStack.empty()) {
650 std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
651 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
653 if (solveBlockValue(e.second, e.first)) {
654 // The work item was completely processed.
655 assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
656 assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
657 "Result should be in cache!");
659 DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
660 << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
662 BlockValueStack.pop();
663 BlockValueSet.erase(e);
665 // More work needs to be done before revisiting.
666 assert(BlockValueStack.top() != e && "Stack should have been pushed!");
671 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
672 // If already a constant, there is nothing to compute.
673 if (isa<Constant>(Val))
676 return TheCache.hasCachedValueInfo(Val, BB);
679 LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) {
680 // If already a constant, there is nothing to compute.
681 if (Constant *VC = dyn_cast<Constant>(Val))
682 return LVILatticeVal::get(VC);
684 return TheCache.getCachedValueInfo(Val, BB);
687 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
688 switch (BBI->getOpcode()) {
690 case Instruction::Load:
691 case Instruction::Call:
692 case Instruction::Invoke:
693 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
694 if (isa<IntegerType>(BBI->getType())) {
695 return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
699 // Nothing known - will be intersected with other facts
700 return LVILatticeVal::getOverdefined();
703 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
704 if (isa<Constant>(Val))
707 if (TheCache.hasCachedValueInfo(Val, BB)) {
708 // If we have a cached value, use that.
709 DEBUG(dbgs() << " reuse BB '" << BB->getName()
710 << "' val=" << TheCache.getCachedValueInfo(Val, BB) << '\n');
712 // Since we're reusing a cached value, we don't need to update the
713 // OverDefinedCache. The cache will have been properly updated whenever the
714 // cached value was inserted.
718 // Hold off inserting this value into the Cache in case we have to return
719 // false and come back later.
721 if (!solveBlockValueImpl(Res, Val, BB))
722 // Work pushed, will revisit
725 TheCache.insertResult(Val, BB, Res);
729 bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res,
730 Value *Val, BasicBlock *BB) {
732 Instruction *BBI = dyn_cast<Instruction>(Val);
733 if (!BBI || BBI->getParent() != BB)
734 return solveBlockValueNonLocal(Res, Val, BB);
736 if (PHINode *PN = dyn_cast<PHINode>(BBI))
737 return solveBlockValuePHINode(Res, PN, BB);
739 if (auto *SI = dyn_cast<SelectInst>(BBI))
740 return solveBlockValueSelect(Res, SI, BB);
742 // If this value is a nonnull pointer, record it's range and bailout. Note
743 // that for all other pointer typed values, we terminate the search at the
744 // definition. We could easily extend this to look through geps, bitcasts,
745 // and the like to prove non-nullness, but it's not clear that's worth it
746 // compile time wise. The context-insensative value walk done inside
747 // isKnownNonNull gets most of the profitable cases at much less expense.
748 // This does mean that we have a sensativity to where the defining
749 // instruction is placed, even if it could legally be hoisted much higher.
750 // That is unfortunate.
751 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
752 if (PT && isKnownNonNull(BBI)) {
753 Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
756 if (BBI->getType()->isIntegerTy()) {
757 if (isa<CastInst>(BBI))
758 return solveBlockValueCast(Res, BBI, BB);
760 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
761 if (BO && isa<ConstantInt>(BO->getOperand(1)))
762 return solveBlockValueBinaryOp(Res, BBI, BB);
765 DEBUG(dbgs() << " compute BB '" << BB->getName()
766 << "' - unknown inst def found.\n");
767 Res = getFromRangeMetadata(BBI);
771 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
772 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
773 return L->getPointerAddressSpace() == 0 &&
774 GetUnderlyingObject(L->getPointerOperand(),
775 L->getModule()->getDataLayout()) == Ptr;
777 if (StoreInst *S = dyn_cast<StoreInst>(I)) {
778 return S->getPointerAddressSpace() == 0 &&
779 GetUnderlyingObject(S->getPointerOperand(),
780 S->getModule()->getDataLayout()) == Ptr;
782 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
783 if (MI->isVolatile()) return false;
785 // FIXME: check whether it has a valuerange that excludes zero?
786 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
787 if (!Len || Len->isZero()) return false;
789 if (MI->getDestAddressSpace() == 0)
790 if (GetUnderlyingObject(MI->getRawDest(),
791 MI->getModule()->getDataLayout()) == Ptr)
793 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
794 if (MTI->getSourceAddressSpace() == 0)
795 if (GetUnderlyingObject(MTI->getRawSource(),
796 MTI->getModule()->getDataLayout()) == Ptr)
802 /// Return true if the allocation associated with Val is ever dereferenced
803 /// within the given basic block. This establishes the fact Val is not null,
804 /// but does not imply that the memory at Val is dereferenceable. (Val may
805 /// point off the end of the dereferenceable part of the object.)
806 static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
807 assert(Val->getType()->isPointerTy());
809 const DataLayout &DL = BB->getModule()->getDataLayout();
810 Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
811 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
812 // inside InstructionDereferencesPointer either.
813 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
814 for (Instruction &I : *BB)
815 if (InstructionDereferencesPointer(&I, UnderlyingVal))
820 bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
821 Value *Val, BasicBlock *BB) {
822 LVILatticeVal Result; // Start Undefined.
824 // If this is the entry block, we must be asking about an argument. The
825 // value is overdefined.
826 if (BB == &BB->getParent()->getEntryBlock()) {
827 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
828 // Bofore giving up, see if we can prove the pointer non-null local to
829 // this particular block.
830 if (Val->getType()->isPointerTy() &&
831 (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) {
832 PointerType *PTy = cast<PointerType>(Val->getType());
833 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
835 Result = LVILatticeVal::getOverdefined();
841 // Loop over all of our predecessors, merging what we know from them into
843 bool EdgesMissing = false;
844 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
845 LVILatticeVal EdgeResult;
846 EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
850 Result.mergeIn(EdgeResult, DL);
852 // If we hit overdefined, exit early. The BlockVals entry is already set
854 if (Result.isOverdefined()) {
855 DEBUG(dbgs() << " compute BB '" << BB->getName()
856 << "' - overdefined because of pred (non local).\n");
857 // Before giving up, see if we can prove the pointer non-null local to
858 // this particular block.
859 if (Val->getType()->isPointerTy() &&
860 isObjectDereferencedInBlock(Val, BB)) {
861 PointerType *PTy = cast<PointerType>(Val->getType());
862 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
872 // Return the merged value, which is more precise than 'overdefined'.
873 assert(!Result.isOverdefined());
878 bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
879 PHINode *PN, BasicBlock *BB) {
880 LVILatticeVal Result; // Start Undefined.
882 // Loop over all of our predecessors, merging what we know from them into
884 bool EdgesMissing = false;
885 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
886 BasicBlock *PhiBB = PN->getIncomingBlock(i);
887 Value *PhiVal = PN->getIncomingValue(i);
888 LVILatticeVal EdgeResult;
889 // Note that we can provide PN as the context value to getEdgeValue, even
890 // though the results will be cached, because PN is the value being used as
891 // the cache key in the caller.
892 EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
896 Result.mergeIn(EdgeResult, DL);
898 // If we hit overdefined, exit early. The BlockVals entry is already set
900 if (Result.isOverdefined()) {
901 DEBUG(dbgs() << " compute BB '" << BB->getName()
902 << "' - overdefined because of pred (local).\n");
911 // Return the merged value, which is more precise than 'overdefined'.
912 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
917 static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
918 bool isTrueDest = true);
920 // If we can determine a constraint on the value given conditions assumed by
921 // the program, intersect those constraints with BBLV
922 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
923 Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
924 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
928 for (auto &AssumeVH : AC->assumptions()) {
931 auto *I = cast<CallInst>(AssumeVH);
932 if (!isValidAssumeForContext(I, BBI, DT))
935 BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
938 // If guards are not used in the module, don't spend time looking for them
939 auto *GuardDecl = BBI->getModule()->getFunction(
940 Intrinsic::getName(Intrinsic::experimental_guard));
941 if (!GuardDecl || GuardDecl->use_empty())
944 for (Instruction &I : make_range(BBI->getIterator().getReverse(),
945 BBI->getParent()->rend())) {
946 Value *Cond = nullptr;
947 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
948 BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
952 bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV,
953 SelectInst *SI, BasicBlock *BB) {
955 // Recurse on our inputs if needed
956 if (!hasBlockValue(SI->getTrueValue(), BB)) {
957 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
959 BBLV = LVILatticeVal::getOverdefined();
962 LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
963 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
964 // extra slots in the table if we can.
965 if (TrueVal.isOverdefined()) {
966 BBLV = LVILatticeVal::getOverdefined();
970 if (!hasBlockValue(SI->getFalseValue(), BB)) {
971 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
973 BBLV = LVILatticeVal::getOverdefined();
976 LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
977 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
978 // extra slots in the table if we can.
979 if (FalseVal.isOverdefined()) {
980 BBLV = LVILatticeVal::getOverdefined();
984 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
985 ConstantRange TrueCR = TrueVal.getConstantRange();
986 ConstantRange FalseCR = FalseVal.getConstantRange();
987 Value *LHS = nullptr;
988 Value *RHS = nullptr;
989 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
990 // Is this a min specifically of our two inputs? (Avoid the risk of
991 // ValueTracking getting smarter looking back past our immediate inputs.)
992 if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
993 LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
994 ConstantRange ResultCR = [&]() {
995 switch (SPR.Flavor) {
997 llvm_unreachable("unexpected minmax type!");
998 case SPF_SMIN: /// Signed minimum
999 return TrueCR.smin(FalseCR);
1000 case SPF_UMIN: /// Unsigned minimum
1001 return TrueCR.umin(FalseCR);
1002 case SPF_SMAX: /// Signed maximum
1003 return TrueCR.smax(FalseCR);
1004 case SPF_UMAX: /// Unsigned maximum
1005 return TrueCR.umax(FalseCR);
1008 BBLV = LVILatticeVal::getRange(ResultCR);
1012 // TODO: ABS, NABS from the SelectPatternResult
1015 // Can we constrain the facts about the true and false values by using the
1016 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
1017 // TODO: We could potentially refine an overdefined true value above.
1018 Value *Cond = SI->getCondition();
1019 TrueVal = intersect(TrueVal,
1020 getValueFromCondition(SI->getTrueValue(), Cond, true));
1021 FalseVal = intersect(FalseVal,
1022 getValueFromCondition(SI->getFalseValue(), Cond, false));
1024 // Handle clamp idioms such as:
1025 // %24 = constantrange<0, 17>
1026 // %39 = icmp eq i32 %24, 0
1027 // %40 = add i32 %24, -1
1028 // %siv.next = select i1 %39, i32 16, i32 %40
1029 // %siv.next = constantrange<0, 17> not <-1, 17>
1030 // In general, this can handle any clamp idiom which tests the edge
1031 // condition via an equality or inequality.
1032 if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
1033 ICmpInst::Predicate Pred = ICI->getPredicate();
1034 Value *A = ICI->getOperand(0);
1035 if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
1036 auto addConstants = [](ConstantInt *A, ConstantInt *B) {
1037 assert(A->getType() == B->getType());
1038 return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
1040 // See if either input is A + C2, subject to the constraint from the
1041 // condition that A != C when that input is used. We can assume that
1042 // that input doesn't include C + C2.
1043 ConstantInt *CIAdded;
1046 case ICmpInst::ICMP_EQ:
1047 if (match(SI->getFalseValue(), m_Add(m_Specific(A),
1048 m_ConstantInt(CIAdded)))) {
1049 auto ResNot = addConstants(CIBase, CIAdded);
1050 FalseVal = intersect(FalseVal,
1051 LVILatticeVal::getNot(ResNot));
1054 case ICmpInst::ICMP_NE:
1055 if (match(SI->getTrueValue(), m_Add(m_Specific(A),
1056 m_ConstantInt(CIAdded)))) {
1057 auto ResNot = addConstants(CIBase, CIAdded);
1058 TrueVal = intersect(TrueVal,
1059 LVILatticeVal::getNot(ResNot));
1066 LVILatticeVal Result; // Start Undefined.
1067 Result.mergeIn(TrueVal, DL);
1068 Result.mergeIn(FalseVal, DL);
1073 bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV,
1076 if (!BBI->getOperand(0)->getType()->isSized()) {
1077 // Without knowing how wide the input is, we can't analyze it in any useful
1079 BBLV = LVILatticeVal::getOverdefined();
1083 // Filter out casts we don't know how to reason about before attempting to
1084 // recurse on our operand. This can cut a long search short if we know we're
1085 // not going to be able to get any useful information anways.
1086 switch (BBI->getOpcode()) {
1087 case Instruction::Trunc:
1088 case Instruction::SExt:
1089 case Instruction::ZExt:
1090 case Instruction::BitCast:
1093 // Unhandled instructions are overdefined.
1094 DEBUG(dbgs() << " compute BB '" << BB->getName()
1095 << "' - overdefined (unknown cast).\n");
1096 BBLV = LVILatticeVal::getOverdefined();
1100 // Figure out the range of the LHS. If that fails, we still apply the
1101 // transfer rule on the full set since we may be able to locally infer
1102 // interesting facts.
1103 if (!hasBlockValue(BBI->getOperand(0), BB))
1104 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
1105 // More work to do before applying this transfer rule.
1108 const unsigned OperandBitWidth =
1109 DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
1110 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1111 if (hasBlockValue(BBI->getOperand(0), BB)) {
1112 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1113 intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal,
1115 if (LHSVal.isConstantRange())
1116 LHSRange = LHSVal.getConstantRange();
1119 const unsigned ResultBitWidth =
1120 cast<IntegerType>(BBI->getType())->getBitWidth();
1122 // NOTE: We're currently limited by the set of operations that ConstantRange
1123 // can evaluate symbolically. Enhancing that set will allows us to analyze
1124 // more definitions.
1125 auto CastOp = (Instruction::CastOps) BBI->getOpcode();
1126 BBLV = LVILatticeVal::getRange(LHSRange.castOp(CastOp, ResultBitWidth));
1130 bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
1134 assert(BBI->getOperand(0)->getType()->isSized() &&
1135 "all operands to binary operators are sized");
1137 // Filter out operators we don't know how to reason about before attempting to
1138 // recurse on our operand(s). This can cut a long search short if we know
1139 // we're not going to be able to get any useful information anways.
1140 switch (BBI->getOpcode()) {
1141 case Instruction::Add:
1142 case Instruction::Sub:
1143 case Instruction::Mul:
1144 case Instruction::UDiv:
1145 case Instruction::Shl:
1146 case Instruction::LShr:
1147 case Instruction::And:
1148 case Instruction::Or:
1149 // continue into the code below
1152 // Unhandled instructions are overdefined.
1153 DEBUG(dbgs() << " compute BB '" << BB->getName()
1154 << "' - overdefined (unknown binary operator).\n");
1155 BBLV = LVILatticeVal::getOverdefined();
1159 // Figure out the range of the LHS. If that fails, use a conservative range,
1160 // but apply the transfer rule anyways. This lets us pick up facts from
1161 // expressions like "and i32 (call i32 @foo()), 32"
1162 if (!hasBlockValue(BBI->getOperand(0), BB))
1163 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
1164 // More work to do before applying this transfer rule.
1167 const unsigned OperandBitWidth =
1168 DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
1169 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1170 if (hasBlockValue(BBI->getOperand(0), BB)) {
1171 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1172 intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal,
1174 if (LHSVal.isConstantRange())
1175 LHSRange = LHSVal.getConstantRange();
1178 ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
1179 ConstantRange RHSRange = ConstantRange(RHS->getValue());
1181 // NOTE: We're currently limited by the set of operations that ConstantRange
1182 // can evaluate symbolically. Enhancing that set will allows us to analyze
1183 // more definitions.
1184 auto BinOp = (Instruction::BinaryOps) BBI->getOpcode();
1185 BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1189 static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1191 Value *LHS = ICI->getOperand(0);
1192 Value *RHS = ICI->getOperand(1);
1193 CmpInst::Predicate Predicate = ICI->getPredicate();
1195 if (isa<Constant>(RHS)) {
1196 if (ICI->isEquality() && LHS == Val) {
1197 // We know that V has the RHS constant if this is a true SETEQ or
1199 if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1200 return LVILatticeVal::get(cast<Constant>(RHS));
1202 return LVILatticeVal::getNot(cast<Constant>(RHS));
1206 if (!Val->getType()->isIntegerTy())
1207 return LVILatticeVal::getOverdefined();
1209 // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1210 // range of Val guaranteed by the condition. Recognize comparisons in the from
1212 // icmp <pred> Val, ...
1213 // icmp <pred> (add Val, Offset), ...
1214 // The latter is the range checking idiom that InstCombine produces. Subtract
1215 // the offset from the allowed range for RHS in this case.
1217 // Val or (add Val, Offset) can be on either hand of the comparison
1218 if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1219 std::swap(LHS, RHS);
1220 Predicate = CmpInst::getSwappedPredicate(Predicate);
1223 ConstantInt *Offset = nullptr;
1225 match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1227 if (LHS == Val || Offset) {
1228 // Calculate the range of values that are allowed by the comparison
1229 ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1230 /*isFullSet=*/true);
1231 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1232 RHSRange = ConstantRange(CI->getValue());
1233 else if (Instruction *I = dyn_cast<Instruction>(RHS))
1234 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1235 RHSRange = getConstantRangeFromMetadata(*Ranges);
1237 // If we're interested in the false dest, invert the condition
1238 CmpInst::Predicate Pred =
1239 isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1240 ConstantRange TrueValues =
1241 ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1243 if (Offset) // Apply the offset from above.
1244 TrueValues = TrueValues.subtract(Offset->getValue());
1246 return LVILatticeVal::getRange(std::move(TrueValues));
1249 return LVILatticeVal::getOverdefined();
1252 static LVILatticeVal
1253 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1254 DenseMap<Value*, LVILatticeVal> &Visited);
1256 static LVILatticeVal
1257 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1258 DenseMap<Value*, LVILatticeVal> &Visited) {
1259 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1260 return getValueFromICmpCondition(Val, ICI, isTrueDest);
1262 // Handle conditions in the form of (cond1 && cond2), we know that on the
1263 // true dest path both of the conditions hold.
1265 return LVILatticeVal::getOverdefined();
1267 BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1268 if (!BO || BO->getOpcode() != BinaryOperator::And)
1269 return LVILatticeVal::getOverdefined();
1271 auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
1272 auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
1273 return intersect(RHS, LHS);
1276 static LVILatticeVal
1277 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1278 DenseMap<Value*, LVILatticeVal> &Visited) {
1279 auto I = Visited.find(Cond);
1280 if (I != Visited.end())
1283 auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1284 Visited[Cond] = Result;
1288 LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
1289 assert(Cond && "precondition");
1290 DenseMap<Value*, LVILatticeVal> Visited;
1291 return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1294 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1295 /// Val is not constrained on the edge. Result is unspecified if return value
1297 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1298 BasicBlock *BBTo, LVILatticeVal &Result) {
1299 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1300 // know that v != 0.
1301 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1302 // If this is a conditional branch and only one successor goes to BBTo, then
1303 // we may be able to infer something from the condition.
1304 if (BI->isConditional() &&
1305 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1306 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1307 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1308 "BBTo isn't a successor of BBFrom");
1310 // If V is the condition of the branch itself, then we know exactly what
1312 if (BI->getCondition() == Val) {
1313 Result = LVILatticeVal::get(ConstantInt::get(
1314 Type::getInt1Ty(Val->getContext()), isTrueDest));
1318 // If the condition of the branch is an equality comparison, we may be
1319 // able to infer the value.
1320 Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest);
1321 if (!Result.isOverdefined())
1326 // If the edge was formed by a switch on the value, then we may know exactly
1328 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1329 if (SI->getCondition() != Val)
1332 bool DefaultCase = SI->getDefaultDest() == BBTo;
1333 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1334 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1336 for (SwitchInst::CaseIt i : SI->cases()) {
1337 ConstantRange EdgeVal(i.getCaseValue()->getValue());
1339 // It is possible that the default destination is the destination of
1340 // some cases. There is no need to perform difference for those cases.
1341 if (i.getCaseSuccessor() != BBTo)
1342 EdgesVals = EdgesVals.difference(EdgeVal);
1343 } else if (i.getCaseSuccessor() == BBTo)
1344 EdgesVals = EdgesVals.unionWith(EdgeVal);
1346 Result = LVILatticeVal::getRange(std::move(EdgesVals));
1352 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1353 /// the basic block if the edge does not constrain Val.
1354 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1355 BasicBlock *BBTo, LVILatticeVal &Result,
1356 Instruction *CxtI) {
1357 // If already a constant, there is nothing to compute.
1358 if (Constant *VC = dyn_cast<Constant>(Val)) {
1359 Result = LVILatticeVal::get(VC);
1363 LVILatticeVal LocalResult;
1364 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1365 // If we couldn't constrain the value on the edge, LocalResult doesn't
1366 // provide any information.
1367 LocalResult = LVILatticeVal::getOverdefined();
1369 if (hasSingleValue(LocalResult)) {
1370 // Can't get any more precise here
1371 Result = LocalResult;
1375 if (!hasBlockValue(Val, BBFrom)) {
1376 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1378 // No new information.
1379 Result = LocalResult;
1383 // Try to intersect ranges of the BB and the constraint on the edge.
1384 LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
1385 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1386 BBFrom->getTerminator());
1387 // We can use the context instruction (generically the ultimate instruction
1388 // the calling pass is trying to simplify) here, even though the result of
1389 // this function is generally cached when called from the solve* functions
1390 // (and that cached result might be used with queries using a different
1391 // context instruction), because when this function is called from the solve*
1392 // functions, the context instruction is not provided. When called from
1393 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1394 // but then the result is not cached.
1395 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1397 Result = intersect(LocalResult, InBlock);
1401 LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1402 Instruction *CxtI) {
1403 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1404 << BB->getName() << "'\n");
1406 assert(BlockValueStack.empty() && BlockValueSet.empty());
1407 if (!hasBlockValue(V, BB)) {
1408 pushBlockValue(std::make_pair(BB, V));
1411 LVILatticeVal Result = getBlockValue(V, BB);
1412 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1414 DEBUG(dbgs() << " Result = " << Result << "\n");
1418 LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1419 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1420 << CxtI->getName() << "'\n");
1422 if (auto *C = dyn_cast<Constant>(V))
1423 return LVILatticeVal::get(C);
1425 LVILatticeVal Result = LVILatticeVal::getOverdefined();
1426 if (auto *I = dyn_cast<Instruction>(V))
1427 Result = getFromRangeMetadata(I);
1428 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1430 DEBUG(dbgs() << " Result = " << Result << "\n");
1434 LVILatticeVal LazyValueInfoImpl::
1435 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1436 Instruction *CxtI) {
1437 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1438 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1440 LVILatticeVal Result;
1441 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1443 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1445 assert(WasFastQuery && "More work to do after problem solved?");
1448 DEBUG(dbgs() << " Result = " << Result << "\n");
1452 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1453 BasicBlock *NewSucc) {
1454 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1457 //===----------------------------------------------------------------------===//
1458 // LazyValueInfo Impl
1459 //===----------------------------------------------------------------------===//
1461 /// This lazily constructs the LazyValueInfoImpl.
1462 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1463 const DataLayout *DL,
1464 DominatorTree *DT = nullptr) {
1466 assert(DL && "getCache() called with a null DataLayout");
1467 PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1469 return *static_cast<LazyValueInfoImpl*>(PImpl);
1472 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1473 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1474 const DataLayout &DL = F.getParent()->getDataLayout();
1476 DominatorTreeWrapperPass *DTWP =
1477 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1478 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1479 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1482 getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1488 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1489 AU.setPreservesAll();
1490 AU.addRequired<AssumptionCacheTracker>();
1491 AU.addRequired<TargetLibraryInfoWrapperPass>();
1494 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1496 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1498 void LazyValueInfo::releaseMemory() {
1499 // If the cache was allocated, free it.
1501 delete &getImpl(PImpl, AC, nullptr);
1506 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1508 LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
1509 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1510 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1511 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1513 return LazyValueInfo(&AC, &TLI, DT);
1516 /// Returns true if we can statically tell that this value will never be a
1517 /// "useful" constant. In practice, this means we've got something like an
1518 /// alloca or a malloc call for which a comparison against a constant can
1519 /// only be guarding dead code. Note that we are potentially giving up some
1520 /// precision in dead code (a constant result) in favour of avoiding a
1521 /// expensive search for a easily answered common query.
1522 static bool isKnownNonConstant(Value *V) {
1523 V = V->stripPointerCasts();
1524 // The return val of alloc cannot be a Constant.
1525 if (isa<AllocaInst>(V))
1530 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1531 Instruction *CxtI) {
1532 // Bail out early if V is known not to be a Constant.
1533 if (isKnownNonConstant(V))
1536 const DataLayout &DL = BB->getModule()->getDataLayout();
1537 LVILatticeVal Result =
1538 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1540 if (Result.isConstant())
1541 return Result.getConstant();
1542 if (Result.isConstantRange()) {
1543 ConstantRange CR = Result.getConstantRange();
1544 if (const APInt *SingleVal = CR.getSingleElement())
1545 return ConstantInt::get(V->getContext(), *SingleVal);
1550 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1551 Instruction *CxtI) {
1552 assert(V->getType()->isIntegerTy());
1553 unsigned Width = V->getType()->getIntegerBitWidth();
1554 const DataLayout &DL = BB->getModule()->getDataLayout();
1555 LVILatticeVal Result =
1556 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1557 if (Result.isUndefined())
1558 return ConstantRange(Width, /*isFullSet=*/false);
1559 if (Result.isConstantRange())
1560 return Result.getConstantRange();
1561 // We represent ConstantInt constants as constant ranges but other kinds
1562 // of integer constants, i.e. ConstantExpr will be tagged as constants
1563 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1564 "ConstantInt value must be represented as constantrange");
1565 return ConstantRange(Width, /*isFullSet=*/true);
1568 /// Determine whether the specified value is known to be a
1569 /// constant on the specified edge. Return null if not.
1570 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1572 Instruction *CxtI) {
1573 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1574 LVILatticeVal Result =
1575 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1577 if (Result.isConstant())
1578 return Result.getConstant();
1579 if (Result.isConstantRange()) {
1580 ConstantRange CR = Result.getConstantRange();
1581 if (const APInt *SingleVal = CR.getSingleElement())
1582 return ConstantInt::get(V->getContext(), *SingleVal);
1587 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1588 LVILatticeVal &Result,
1589 const DataLayout &DL,
1590 TargetLibraryInfo *TLI) {
1592 // If we know the value is a constant, evaluate the conditional.
1593 Constant *Res = nullptr;
1594 if (Result.isConstant()) {
1595 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
1597 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1598 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1599 return LazyValueInfo::Unknown;
1602 if (Result.isConstantRange()) {
1603 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1604 if (!CI) return LazyValueInfo::Unknown;
1606 ConstantRange CR = Result.getConstantRange();
1607 if (Pred == ICmpInst::ICMP_EQ) {
1608 if (!CR.contains(CI->getValue()))
1609 return LazyValueInfo::False;
1611 if (CR.isSingleElement() && CR.contains(CI->getValue()))
1612 return LazyValueInfo::True;
1613 } else if (Pred == ICmpInst::ICMP_NE) {
1614 if (!CR.contains(CI->getValue()))
1615 return LazyValueInfo::True;
1617 if (CR.isSingleElement() && CR.contains(CI->getValue()))
1618 return LazyValueInfo::False;
1621 // Handle more complex predicates.
1622 ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1623 (ICmpInst::Predicate)Pred, CI->getValue());
1624 if (TrueValues.contains(CR))
1625 return LazyValueInfo::True;
1626 if (TrueValues.inverse().contains(CR))
1627 return LazyValueInfo::False;
1628 return LazyValueInfo::Unknown;
1631 if (Result.isNotConstant()) {
1632 // If this is an equality comparison, we can try to fold it knowing that
1634 if (Pred == ICmpInst::ICMP_EQ) {
1635 // !C1 == C -> false iff C1 == C.
1636 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1637 Result.getNotConstant(), C, DL,
1639 if (Res->isNullValue())
1640 return LazyValueInfo::False;
1641 } else if (Pred == ICmpInst::ICMP_NE) {
1642 // !C1 != C -> true iff C1 == C.
1643 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1644 Result.getNotConstant(), C, DL,
1646 if (Res->isNullValue())
1647 return LazyValueInfo::True;
1649 return LazyValueInfo::Unknown;
1652 return LazyValueInfo::Unknown;
1655 /// Determine whether the specified value comparison with a constant is known to
1656 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1657 LazyValueInfo::Tristate
1658 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1659 BasicBlock *FromBB, BasicBlock *ToBB,
1660 Instruction *CxtI) {
1661 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1662 LVILatticeVal Result =
1663 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1665 return getPredicateResult(Pred, C, Result, DL, TLI);
1668 LazyValueInfo::Tristate
1669 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1670 Instruction *CxtI) {
1671 // Is or is not NonNull are common predicates being queried. If
1672 // isKnownNonNull can tell us the result of the predicate, we can
1673 // return it quickly. But this is only a fastpath, and falling
1674 // through would still be correct.
1675 if (V->getType()->isPointerTy() && C->isNullValue() &&
1676 isKnownNonNull(V->stripPointerCasts())) {
1677 if (Pred == ICmpInst::ICMP_EQ)
1678 return LazyValueInfo::False;
1679 else if (Pred == ICmpInst::ICMP_NE)
1680 return LazyValueInfo::True;
1682 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1683 LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1684 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1688 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1689 // LVI as a whole tries to compute a lattice value which is conservatively
1690 // correct at a given location. In this case, we have a predicate which we
1691 // weren't able to prove about the merged result, and we're pushing that
1692 // predicate back along each incoming edge to see if we can prove it
1693 // separately for each input. As a motivating example, consider:
1695 // %v1 = ... ; constantrange<1, 5>
1698 // %v2 = ... ; constantrange<10, 20>
1701 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1702 // %pred = icmp eq i32 %phi, 8
1703 // We can't tell from the lattice value for '%phi' that '%pred' is false
1704 // along each path, but by checking the predicate over each input separately,
1706 // We limit the search to one step backwards from the current BB and value.
1707 // We could consider extending this to search further backwards through the
1708 // CFG and/or value graph, but there are non-obvious compile time vs quality
1711 BasicBlock *BB = CxtI->getParent();
1713 // Function entry or an unreachable block. Bail to avoid confusing
1715 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1719 // If V is a PHI node in the same block as the context, we need to ask
1720 // questions about the predicate as applied to the incoming value along
1721 // each edge. This is useful for eliminating cases where the predicate is
1722 // known along all incoming edges.
1723 if (auto *PHI = dyn_cast<PHINode>(V))
1724 if (PHI->getParent() == BB) {
1725 Tristate Baseline = Unknown;
1726 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1727 Value *Incoming = PHI->getIncomingValue(i);
1728 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1729 // Note that PredBB may be BB itself.
1730 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1733 // Keep going as long as we've seen a consistent known result for
1735 Baseline = (i == 0) ? Result /* First iteration */
1736 : (Baseline == Result ? Baseline : Unknown); /* All others */
1737 if (Baseline == Unknown)
1740 if (Baseline != Unknown)
1744 // For a comparison where the V is outside this block, it's possible
1745 // that we've branched on it before. Look to see if the value is known
1746 // on all incoming edges.
1747 if (!isa<Instruction>(V) ||
1748 cast<Instruction>(V)->getParent() != BB) {
1749 // For predecessor edge, determine if the comparison is true or false
1750 // on that edge. If they're all true or all false, we can conclude
1751 // the value of the comparison in this block.
1752 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1753 if (Baseline != Unknown) {
1754 // Check that all remaining incoming values match the first one.
1755 while (++PI != PE) {
1756 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1757 if (Ret != Baseline) break;
1759 // If we terminated early, then one of the values didn't match.
1769 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1770 BasicBlock *NewSucc) {
1772 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1773 getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1777 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1779 const DataLayout &DL = BB->getModule()->getDataLayout();
1780 getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);