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/AssemblyAnnotationWriter.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/ConstantRange.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DataLayout.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/IR/Intrinsics.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/IR/ValueHandle.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/FormattedStream.h"
36 #include "llvm/Support/raw_ostream.h"
40 using namespace PatternMatch;
42 #define DEBUG_TYPE "lazy-value-info"
44 // This is the number of worklist items we will process to try to discover an
45 // answer for a given value.
46 static const unsigned MaxProcessedPerValue = 500;
48 char LazyValueInfoWrapperPass::ID = 0;
49 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
50 "Lazy Value Information Analysis", false, true)
51 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
52 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
53 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
54 "Lazy Value Information Analysis", false, true)
57 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
60 AnalysisKey LazyValueAnalysis::Key;
62 //===----------------------------------------------------------------------===//
64 //===----------------------------------------------------------------------===//
66 /// This is the information tracked by LazyValueInfo for each value.
68 /// FIXME: This is basically just for bringup, this can be made a lot more rich
74 /// This Value has no known value yet. As a result, this implies the
75 /// producing instruction is dead. Caution: We use this as the starting
76 /// state in our local meet rules. In this usage, it's taken to mean
77 /// "nothing known yet".
80 /// This Value has a specific constant value. (For constant integers,
81 /// constantrange is used instead. Integer typed constantexprs can appear
85 /// This Value is known to not have the specified value. (For constant
86 /// integers, constantrange is used instead. As above, integer typed
87 /// constantexprs can appear here.)
90 /// The Value falls within this range. (Used only for integer typed values.)
93 /// We can not precisely model the dynamic values this value might take.
97 /// Val: This stores the current lattice value along with the Constant* for
98 /// the constant if this is a 'constant' or 'notconstant' value.
104 LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
106 static LVILatticeVal get(Constant *C) {
108 if (!isa<UndefValue>(C))
112 static LVILatticeVal getNot(Constant *C) {
114 if (!isa<UndefValue>(C))
115 Res.markNotConstant(C);
118 static LVILatticeVal getRange(ConstantRange CR) {
120 Res.markConstantRange(std::move(CR));
123 static LVILatticeVal getOverdefined() {
125 Res.markOverdefined();
129 bool isUndefined() const { return Tag == undefined; }
130 bool isConstant() const { return Tag == constant; }
131 bool isNotConstant() const { return Tag == notconstant; }
132 bool isConstantRange() const { return Tag == constantrange; }
133 bool isOverdefined() const { return Tag == overdefined; }
135 Constant *getConstant() const {
136 assert(isConstant() && "Cannot get the constant of a non-constant!");
140 Constant *getNotConstant() const {
141 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
145 const ConstantRange &getConstantRange() const {
146 assert(isConstantRange() &&
147 "Cannot get the constant-range of a non-constant-range!");
152 void markOverdefined() {
158 void markConstant(Constant *V) {
159 assert(V && "Marking constant with NULL");
160 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
161 markConstantRange(ConstantRange(CI->getValue()));
164 if (isa<UndefValue>(V))
167 assert((!isConstant() || getConstant() == V) &&
168 "Marking constant with different value");
169 assert(isUndefined());
174 void markNotConstant(Constant *V) {
175 assert(V && "Marking constant with NULL");
176 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
177 markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
180 if (isa<UndefValue>(V))
183 assert((!isConstant() || getConstant() != V) &&
184 "Marking constant !constant with same value");
185 assert((!isNotConstant() || getNotConstant() == V) &&
186 "Marking !constant with different value");
187 assert(isUndefined() || isConstant());
192 void markConstantRange(ConstantRange NewR) {
193 if (isConstantRange()) {
194 if (NewR.isEmptySet())
197 Range = std::move(NewR);
202 assert(isUndefined());
203 if (NewR.isEmptySet())
207 Range = std::move(NewR);
213 /// Merge the specified lattice value into this one, updating this
214 /// one and returning true if anything changed.
215 void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
216 if (RHS.isUndefined() || isOverdefined())
218 if (RHS.isOverdefined()) {
229 if (RHS.isConstant() && Val == RHS.Val)
235 if (isNotConstant()) {
236 if (RHS.isNotConstant() && Val == RHS.Val)
242 assert(isConstantRange() && "New LVILattice type?");
243 if (!RHS.isConstantRange()) {
244 // We can get here if we've encountered a constantexpr of integer type
245 // and merge it with a constantrange.
249 ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
250 if (NewR.isFullSet())
253 markConstantRange(std::move(NewR));
257 } // end anonymous namespace.
260 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
262 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
263 if (Val.isUndefined())
264 return OS << "undefined";
265 if (Val.isOverdefined())
266 return OS << "overdefined";
268 if (Val.isNotConstant())
269 return OS << "notconstant<" << *Val.getNotConstant() << '>';
270 if (Val.isConstantRange())
271 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
272 << Val.getConstantRange().getUpper() << '>';
273 return OS << "constant<" << *Val.getConstant() << '>';
277 /// Returns true if this lattice value represents at most one possible value.
278 /// This is as precise as any lattice value can get while still representing
280 static bool hasSingleValue(const LVILatticeVal &Val) {
281 if (Val.isConstantRange() &&
282 Val.getConstantRange().isSingleElement())
283 // Integer constants are single element ranges
285 if (Val.isConstant())
286 // Non integer constants
291 /// Combine two sets of facts about the same value into a single set of
292 /// facts. Note that this method is not suitable for merging facts along
293 /// different paths in a CFG; that's what the mergeIn function is for. This
294 /// is for merging facts gathered about the same value at the same location
295 /// through two independent means.
297 /// * This method does not promise to return the most precise possible lattice
298 /// value implied by A and B. It is allowed to return any lattice element
299 /// which is at least as strong as *either* A or B (unless our facts
300 /// conflict, see below).
301 /// * Due to unreachable code, the intersection of two lattice values could be
302 /// contradictory. If this happens, we return some valid lattice value so as
303 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
304 /// we do not make this guarantee. TODO: This would be a useful enhancement.
305 static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
306 // Undefined is the strongest state. It means the value is known to be along
307 // an unreachable path.
313 // If we gave up for one, but got a useable fact from the other, use it.
314 if (A.isOverdefined())
316 if (B.isOverdefined())
319 // Can't get any more precise than constants.
320 if (hasSingleValue(A))
322 if (hasSingleValue(B))
325 // Could be either constant range or not constant here.
326 if (!A.isConstantRange() || !B.isConstantRange()) {
327 // TODO: Arbitrary choice, could be improved
331 // Intersect two constant ranges
332 ConstantRange Range =
333 A.getConstantRange().intersectWith(B.getConstantRange());
334 // Note: An empty range is implicitly converted to overdefined internally.
335 // TODO: We could instead use Undefined here since we've proven a conflict
336 // and thus know this path must be unreachable.
337 return LVILatticeVal::getRange(std::move(Range));
340 //===----------------------------------------------------------------------===//
341 // LazyValueInfoCache Decl
342 //===----------------------------------------------------------------------===//
345 /// A callback value handle updates the cache when values are erased.
346 class LazyValueInfoCache;
347 struct LVIValueHandle final : public CallbackVH {
348 // Needs to access getValPtr(), which is protected.
349 friend struct DenseMapInfo<LVIValueHandle>;
351 LazyValueInfoCache *Parent;
353 LVIValueHandle(Value *V, LazyValueInfoCache *P)
354 : CallbackVH(V), Parent(P) { }
356 void deleted() override;
357 void allUsesReplacedWith(Value *V) override {
361 } // end anonymous namespace
364 /// This is the cache kept by LazyValueInfo which
365 /// maintains information about queries across the clients' queries.
366 class LazyValueInfoCache {
367 friend class LazyValueInfoAnnotatedWriter;
368 /// This is all of the cached block information for exactly one Value*.
369 /// The entries are sorted by the BasicBlock* of the
370 /// entries, allowing us to do a lookup with a binary search.
371 /// Over-defined lattice values are recorded in OverDefinedCache to reduce
373 struct ValueCacheEntryTy {
374 ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
375 LVIValueHandle Handle;
376 SmallDenseMap<PoisoningVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
379 /// This tracks, on a per-block basis, the set of values that are
380 /// over-defined at the end of that block.
381 typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
383 /// Keep track of all blocks that we have ever seen, so we
384 /// don't spend time removing unused blocks from our caches.
385 DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
388 /// This is all of the cached information for all values,
389 /// mapped from Value* to key information.
390 DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
391 OverDefinedCacheTy OverDefinedCache;
395 void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
396 SeenBlocks.insert(BB);
398 // Insert over-defined values into their own cache to reduce memory
400 if (Result.isOverdefined())
401 OverDefinedCache[BB].insert(Val);
403 auto It = ValueCache.find_as(Val);
404 if (It == ValueCache.end()) {
405 ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
406 It = ValueCache.find_as(Val);
407 assert(It != ValueCache.end() && "Val was just added to the map!");
409 It->second->BlockVals[BB] = Result;
413 bool isOverdefined(Value *V, BasicBlock *BB) const {
414 auto ODI = OverDefinedCache.find(BB);
416 if (ODI == OverDefinedCache.end())
419 return ODI->second.count(V);
422 bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
423 if (isOverdefined(V, BB))
426 auto I = ValueCache.find_as(V);
427 if (I == ValueCache.end())
430 return I->second->BlockVals.count(BB);
433 LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const {
434 if (isOverdefined(V, BB))
435 return LVILatticeVal::getOverdefined();
437 auto I = ValueCache.find_as(V);
438 if (I == ValueCache.end())
439 return LVILatticeVal();
440 auto BBI = I->second->BlockVals.find(BB);
441 if (BBI == I->second->BlockVals.end())
442 return LVILatticeVal();
446 void printCache(Function &F, raw_ostream &OS);
447 /// clear - Empty the cache.
451 OverDefinedCache.clear();
454 /// Inform the cache that a given value has been deleted.
455 void eraseValue(Value *V);
457 /// This is part of the update interface to inform the cache
458 /// that a block has been deleted.
459 void eraseBlock(BasicBlock *BB);
461 /// Updates the cache to remove any influence an overdefined value in
462 /// OldSucc might have (unless also overdefined in NewSucc). This just
463 /// flushes elements from the cache and does not add any.
464 void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
466 friend struct LVIValueHandle;
473 /// An assembly annotator class to print LazyValueCache information in
475 class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
476 const LazyValueInfoCache* LVICache;
479 LazyValueInfoAnnotatedWriter(const LazyValueInfoCache *L) : LVICache(L) {}
481 virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
482 formatted_raw_ostream &OS) {
483 auto ODI = LVICache->OverDefinedCache.find(const_cast<BasicBlock*>(BB));
484 if (ODI == LVICache->OverDefinedCache.end())
486 OS << "; OverDefined values for block are: \n";
487 for (auto *V : ODI->second)
488 OS << ";" << *V << "\n";
490 // Find if there are latticevalues defined for arguments of the function.
491 auto *F = const_cast<Function *>(BB->getParent());
492 for (auto &Arg : F->args()) {
493 auto VI = LVICache->ValueCache.find_as(&Arg);
494 if (VI == LVICache->ValueCache.end())
496 auto BBI = VI->second->BlockVals.find(const_cast<BasicBlock *>(BB));
497 if (BBI != VI->second->BlockVals.end())
498 OS << "; CachedLatticeValue for: '" << *VI->first << "' is: '"
499 << BBI->second << "'\n";
503 virtual void emitInstructionAnnot(const Instruction *I,
504 formatted_raw_ostream &OS) {
506 auto VI = LVICache->ValueCache.find_as(const_cast<Instruction *>(I));
507 if (VI == LVICache->ValueCache.end())
509 OS << "; CachedLatticeValues for: '" << *VI->first << "'\n";
510 for (auto &BV : VI->second->BlockVals) {
511 OS << "; at beginning of BasicBlock: '";
512 BV.first->printAsOperand(OS, false);
513 OS << "' LatticeVal: '" << BV.second << "' \n";
519 void LazyValueInfoCache::printCache(Function &F, raw_ostream &OS) {
520 LazyValueInfoAnnotatedWriter Writer(this);
521 F.print(OS, &Writer);
525 void LazyValueInfoCache::eraseValue(Value *V) {
526 for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
527 // Copy and increment the iterator immediately so we can erase behind
530 SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
532 if (ValueSet.empty())
533 OverDefinedCache.erase(Iter);
539 void LVIValueHandle::deleted() {
540 // This erasure deallocates *this, so it MUST happen after we're done
541 // using any and all members of *this.
542 Parent->eraseValue(*this);
545 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
546 // Shortcut if we have never seen this block.
547 DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
548 if (I == SeenBlocks.end())
552 auto ODI = OverDefinedCache.find(BB);
553 if (ODI != OverDefinedCache.end())
554 OverDefinedCache.erase(ODI);
556 for (auto &I : ValueCache)
557 I.second->BlockVals.erase(BB);
560 void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
561 BasicBlock *NewSucc) {
562 // When an edge in the graph has been threaded, values that we could not
563 // determine a value for before (i.e. were marked overdefined) may be
564 // possible to solve now. We do NOT try to proactively update these values.
565 // Instead, we clear their entries from the cache, and allow lazy updating to
566 // recompute them when needed.
568 // The updating process is fairly simple: we need to drop cached info
569 // for all values that were marked overdefined in OldSucc, and for those same
570 // values in any successor of OldSucc (except NewSucc) in which they were
571 // also marked overdefined.
572 std::vector<BasicBlock*> worklist;
573 worklist.push_back(OldSucc);
575 auto I = OverDefinedCache.find(OldSucc);
576 if (I == OverDefinedCache.end())
577 return; // Nothing to process here.
578 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
580 // Use a worklist to perform a depth-first search of OldSucc's successors.
581 // NOTE: We do not need a visited list since any blocks we have already
582 // visited will have had their overdefined markers cleared already, and we
583 // thus won't loop to their successors.
584 while (!worklist.empty()) {
585 BasicBlock *ToUpdate = worklist.back();
588 // Skip blocks only accessible through NewSucc.
589 if (ToUpdate == NewSucc) continue;
591 // If a value was marked overdefined in OldSucc, and is here too...
592 auto OI = OverDefinedCache.find(ToUpdate);
593 if (OI == OverDefinedCache.end())
595 SmallPtrSetImpl<Value *> &ValueSet = OI->second;
597 bool changed = false;
598 for (Value *V : ValsToClear) {
599 if (!ValueSet.erase(V))
602 // If we removed anything, then we potentially need to update
603 // blocks successors too.
606 if (ValueSet.empty()) {
607 OverDefinedCache.erase(OI);
612 if (!changed) continue;
614 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
619 // The actual implementation of the lazy analysis and update. Note that the
620 // inheritance from LazyValueInfoCache is intended to be temporary while
621 // splitting the code and then transitioning to a has-a relationship.
622 class LazyValueInfoImpl {
624 /// Cached results from previous queries
625 LazyValueInfoCache TheCache;
627 /// This stack holds the state of the value solver during a query.
628 /// It basically emulates the callstack of the naive
629 /// recursive value lookup process.
630 SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
632 /// Keeps track of which block-value pairs are in BlockValueStack.
633 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
635 /// Push BV onto BlockValueStack unless it's already in there.
636 /// Returns true on success.
637 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
638 if (!BlockValueSet.insert(BV).second)
639 return false; // It's already in the stack.
641 DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
643 BlockValueStack.push_back(BV);
647 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
648 const DataLayout &DL; ///< A mandatory DataLayout
649 DominatorTree *DT; ///< An optional DT pointer.
651 LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
652 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
653 LVILatticeVal &Result, Instruction *CxtI = nullptr);
654 bool hasBlockValue(Value *Val, BasicBlock *BB);
656 // These methods process one work item and may add more. A false value
657 // returned means that the work item was not completely processed and must
658 // be revisited after going through the new items.
659 bool solveBlockValue(Value *Val, BasicBlock *BB);
660 bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB);
661 bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
662 bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
663 bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
665 bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, BinaryOperator *BBI,
667 bool solveBlockValueCast(LVILatticeVal &BBLV, CastInst *CI,
669 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
676 /// This is the query interface to determine the lattice
677 /// value for the specified Value* at the end of the specified block.
678 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
679 Instruction *CxtI = nullptr);
681 /// This is the query interface to determine the lattice
682 /// value for the specified Value* at the specified instruction (generally
683 /// from an assume intrinsic).
684 LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
686 /// This is the query interface to determine the lattice
687 /// value for the specified Value* that is true on the specified edge.
688 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
689 Instruction *CxtI = nullptr);
691 /// Complete flush all previously computed values
696 /// Printing the LazyValueInfoCache.
697 void printCache(Function &F, raw_ostream &OS) {
698 TheCache.printCache(F, OS);
701 /// This is part of the update interface to inform the cache
702 /// that a block has been deleted.
703 void eraseBlock(BasicBlock *BB) {
704 TheCache.eraseBlock(BB);
707 /// This is the update interface to inform the cache that an edge from
708 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
709 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
711 LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
712 DominatorTree *DT = nullptr)
713 : AC(AC), DL(DL), DT(DT) {}
715 } // end anonymous namespace
717 void LazyValueInfoImpl::solve() {
718 SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
719 BlockValueStack.begin(), BlockValueStack.end());
721 unsigned processedCount = 0;
722 while (!BlockValueStack.empty()) {
724 // Abort if we have to process too many values to get a result for this one.
725 // Because of the design of the overdefined cache currently being per-block
726 // to avoid naming-related issues (IE it wants to try to give different
727 // results for the same name in different blocks), overdefined results don't
728 // get cached globally, which in turn means we will often try to rediscover
729 // the same overdefined result again and again. Once something like
730 // PredicateInfo is used in LVI or CVP, we should be able to make the
731 // overdefined cache global, and remove this throttle.
732 if (processedCount > MaxProcessedPerValue) {
733 DEBUG(dbgs() << "Giving up on stack because we are getting too deep\n");
734 // Fill in the original values
735 while (!StartingStack.empty()) {
736 std::pair<BasicBlock *, Value *> &e = StartingStack.back();
737 TheCache.insertResult(e.second, e.first,
738 LVILatticeVal::getOverdefined());
739 StartingStack.pop_back();
741 BlockValueSet.clear();
742 BlockValueStack.clear();
745 std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
746 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
748 if (solveBlockValue(e.second, e.first)) {
749 // The work item was completely processed.
750 assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
751 assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
752 "Result should be in cache!");
754 DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
755 << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
757 BlockValueStack.pop_back();
758 BlockValueSet.erase(e);
760 // More work needs to be done before revisiting.
761 assert(BlockValueStack.back() != e && "Stack should have been pushed!");
766 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
767 // If already a constant, there is nothing to compute.
768 if (isa<Constant>(Val))
771 return TheCache.hasCachedValueInfo(Val, BB);
774 LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) {
775 // If already a constant, there is nothing to compute.
776 if (Constant *VC = dyn_cast<Constant>(Val))
777 return LVILatticeVal::get(VC);
779 return TheCache.getCachedValueInfo(Val, BB);
782 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
783 switch (BBI->getOpcode()) {
785 case Instruction::Load:
786 case Instruction::Call:
787 case Instruction::Invoke:
788 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
789 if (isa<IntegerType>(BBI->getType())) {
790 return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
794 // Nothing known - will be intersected with other facts
795 return LVILatticeVal::getOverdefined();
798 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
799 if (isa<Constant>(Val))
802 if (TheCache.hasCachedValueInfo(Val, BB)) {
803 // If we have a cached value, use that.
804 DEBUG(dbgs() << " reuse BB '" << BB->getName()
805 << "' val=" << TheCache.getCachedValueInfo(Val, BB) << '\n');
807 // Since we're reusing a cached value, we don't need to update the
808 // OverDefinedCache. The cache will have been properly updated whenever the
809 // cached value was inserted.
813 // Hold off inserting this value into the Cache in case we have to return
814 // false and come back later.
816 if (!solveBlockValueImpl(Res, Val, BB))
817 // Work pushed, will revisit
820 TheCache.insertResult(Val, BB, Res);
824 bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res,
825 Value *Val, BasicBlock *BB) {
827 Instruction *BBI = dyn_cast<Instruction>(Val);
828 if (!BBI || BBI->getParent() != BB)
829 return solveBlockValueNonLocal(Res, Val, BB);
831 if (PHINode *PN = dyn_cast<PHINode>(BBI))
832 return solveBlockValuePHINode(Res, PN, BB);
834 if (auto *SI = dyn_cast<SelectInst>(BBI))
835 return solveBlockValueSelect(Res, SI, BB);
837 // If this value is a nonnull pointer, record it's range and bailout. Note
838 // that for all other pointer typed values, we terminate the search at the
839 // definition. We could easily extend this to look through geps, bitcasts,
840 // and the like to prove non-nullness, but it's not clear that's worth it
841 // compile time wise. The context-insensative value walk done inside
842 // isKnownNonNull gets most of the profitable cases at much less expense.
843 // This does mean that we have a sensativity to where the defining
844 // instruction is placed, even if it could legally be hoisted much higher.
845 // That is unfortunate.
846 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
847 if (PT && isKnownNonNull(BBI)) {
848 Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
851 if (BBI->getType()->isIntegerTy()) {
852 if (auto *CI = dyn_cast<CastInst>(BBI))
853 return solveBlockValueCast(Res, CI, BB);
855 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
856 if (BO && isa<ConstantInt>(BO->getOperand(1)))
857 return solveBlockValueBinaryOp(Res, BO, BB);
860 DEBUG(dbgs() << " compute BB '" << BB->getName()
861 << "' - unknown inst def found.\n");
862 Res = getFromRangeMetadata(BBI);
866 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
867 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
868 return L->getPointerAddressSpace() == 0 &&
869 GetUnderlyingObject(L->getPointerOperand(),
870 L->getModule()->getDataLayout()) == Ptr;
872 if (StoreInst *S = dyn_cast<StoreInst>(I)) {
873 return S->getPointerAddressSpace() == 0 &&
874 GetUnderlyingObject(S->getPointerOperand(),
875 S->getModule()->getDataLayout()) == Ptr;
877 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
878 if (MI->isVolatile()) return false;
880 // FIXME: check whether it has a valuerange that excludes zero?
881 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
882 if (!Len || Len->isZero()) return false;
884 if (MI->getDestAddressSpace() == 0)
885 if (GetUnderlyingObject(MI->getRawDest(),
886 MI->getModule()->getDataLayout()) == Ptr)
888 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
889 if (MTI->getSourceAddressSpace() == 0)
890 if (GetUnderlyingObject(MTI->getRawSource(),
891 MTI->getModule()->getDataLayout()) == Ptr)
897 /// Return true if the allocation associated with Val is ever dereferenced
898 /// within the given basic block. This establishes the fact Val is not null,
899 /// but does not imply that the memory at Val is dereferenceable. (Val may
900 /// point off the end of the dereferenceable part of the object.)
901 static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
902 assert(Val->getType()->isPointerTy());
904 const DataLayout &DL = BB->getModule()->getDataLayout();
905 Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
906 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
907 // inside InstructionDereferencesPointer either.
908 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
909 for (Instruction &I : *BB)
910 if (InstructionDereferencesPointer(&I, UnderlyingVal))
915 bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
916 Value *Val, BasicBlock *BB) {
917 LVILatticeVal Result; // Start Undefined.
919 // If this is the entry block, we must be asking about an argument. The
920 // value is overdefined.
921 if (BB == &BB->getParent()->getEntryBlock()) {
922 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
923 // Before giving up, see if we can prove the pointer non-null local to
924 // this particular block.
925 if (Val->getType()->isPointerTy() &&
926 (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) {
927 PointerType *PTy = cast<PointerType>(Val->getType());
928 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
930 Result = LVILatticeVal::getOverdefined();
936 // Loop over all of our predecessors, merging what we know from them into
937 // result. If we encounter an unexplored predecessor, we eagerly explore it
938 // in a depth first manner. In practice, this has the effect of discovering
939 // paths we can't analyze eagerly without spending compile times analyzing
940 // other paths. This heuristic benefits from the fact that predecessors are
941 // frequently arranged such that dominating ones come first and we quickly
942 // find a path to function entry. TODO: We should consider explicitly
943 // canonicalizing to make this true rather than relying on this happy
945 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
946 LVILatticeVal EdgeResult;
947 if (!getEdgeValue(Val, *PI, BB, EdgeResult))
948 // Explore that input, then return here
951 Result.mergeIn(EdgeResult, DL);
953 // If we hit overdefined, exit early. The BlockVals entry is already set
955 if (Result.isOverdefined()) {
956 DEBUG(dbgs() << " compute BB '" << BB->getName()
957 << "' - overdefined because of pred (non local).\n");
958 // Before giving up, see if we can prove the pointer non-null local to
959 // this particular block.
960 if (Val->getType()->isPointerTy() &&
961 isObjectDereferencedInBlock(Val, BB)) {
962 PointerType *PTy = cast<PointerType>(Val->getType());
963 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
971 // Return the merged value, which is more precise than 'overdefined'.
972 assert(!Result.isOverdefined());
977 bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
978 PHINode *PN, BasicBlock *BB) {
979 LVILatticeVal Result; // Start Undefined.
981 // Loop over all of our predecessors, merging what we know from them into
982 // result. See the comment about the chosen traversal order in
983 // solveBlockValueNonLocal; the same reasoning applies here.
984 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
985 BasicBlock *PhiBB = PN->getIncomingBlock(i);
986 Value *PhiVal = PN->getIncomingValue(i);
987 LVILatticeVal EdgeResult;
988 // Note that we can provide PN as the context value to getEdgeValue, even
989 // though the results will be cached, because PN is the value being used as
990 // the cache key in the caller.
991 if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
992 // Explore that input, then return here
995 Result.mergeIn(EdgeResult, DL);
997 // If we hit overdefined, exit early. The BlockVals entry is already set
999 if (Result.isOverdefined()) {
1000 DEBUG(dbgs() << " compute BB '" << BB->getName()
1001 << "' - overdefined because of pred (local).\n");
1008 // Return the merged value, which is more precise than 'overdefined'.
1009 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
1014 static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
1015 bool isTrueDest = true);
1017 // If we can determine a constraint on the value given conditions assumed by
1018 // the program, intersect those constraints with BBLV
1019 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
1020 Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
1021 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
1025 for (auto &AssumeVH : AC->assumptionsFor(Val)) {
1028 auto *I = cast<CallInst>(AssumeVH);
1029 if (!isValidAssumeForContext(I, BBI, DT))
1032 BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
1035 // If guards are not used in the module, don't spend time looking for them
1036 auto *GuardDecl = BBI->getModule()->getFunction(
1037 Intrinsic::getName(Intrinsic::experimental_guard));
1038 if (!GuardDecl || GuardDecl->use_empty())
1041 for (Instruction &I : make_range(BBI->getIterator().getReverse(),
1042 BBI->getParent()->rend())) {
1043 Value *Cond = nullptr;
1044 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
1045 BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
1049 bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV,
1050 SelectInst *SI, BasicBlock *BB) {
1052 // Recurse on our inputs if needed
1053 if (!hasBlockValue(SI->getTrueValue(), BB)) {
1054 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
1056 BBLV = LVILatticeVal::getOverdefined();
1059 LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
1060 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
1061 // extra slots in the table if we can.
1062 if (TrueVal.isOverdefined()) {
1063 BBLV = LVILatticeVal::getOverdefined();
1067 if (!hasBlockValue(SI->getFalseValue(), BB)) {
1068 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
1070 BBLV = LVILatticeVal::getOverdefined();
1073 LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
1074 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
1075 // extra slots in the table if we can.
1076 if (FalseVal.isOverdefined()) {
1077 BBLV = LVILatticeVal::getOverdefined();
1081 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
1082 const ConstantRange &TrueCR = TrueVal.getConstantRange();
1083 const ConstantRange &FalseCR = FalseVal.getConstantRange();
1084 Value *LHS = nullptr;
1085 Value *RHS = nullptr;
1086 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
1087 // Is this a min specifically of our two inputs? (Avoid the risk of
1088 // ValueTracking getting smarter looking back past our immediate inputs.)
1089 if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
1090 LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
1091 ConstantRange ResultCR = [&]() {
1092 switch (SPR.Flavor) {
1094 llvm_unreachable("unexpected minmax type!");
1095 case SPF_SMIN: /// Signed minimum
1096 return TrueCR.smin(FalseCR);
1097 case SPF_UMIN: /// Unsigned minimum
1098 return TrueCR.umin(FalseCR);
1099 case SPF_SMAX: /// Signed maximum
1100 return TrueCR.smax(FalseCR);
1101 case SPF_UMAX: /// Unsigned maximum
1102 return TrueCR.umax(FalseCR);
1105 BBLV = LVILatticeVal::getRange(ResultCR);
1109 // TODO: ABS, NABS from the SelectPatternResult
1112 // Can we constrain the facts about the true and false values by using the
1113 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
1114 // TODO: We could potentially refine an overdefined true value above.
1115 Value *Cond = SI->getCondition();
1116 TrueVal = intersect(TrueVal,
1117 getValueFromCondition(SI->getTrueValue(), Cond, true));
1118 FalseVal = intersect(FalseVal,
1119 getValueFromCondition(SI->getFalseValue(), Cond, false));
1121 // Handle clamp idioms such as:
1122 // %24 = constantrange<0, 17>
1123 // %39 = icmp eq i32 %24, 0
1124 // %40 = add i32 %24, -1
1125 // %siv.next = select i1 %39, i32 16, i32 %40
1126 // %siv.next = constantrange<0, 17> not <-1, 17>
1127 // In general, this can handle any clamp idiom which tests the edge
1128 // condition via an equality or inequality.
1129 if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
1130 ICmpInst::Predicate Pred = ICI->getPredicate();
1131 Value *A = ICI->getOperand(0);
1132 if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
1133 auto addConstants = [](ConstantInt *A, ConstantInt *B) {
1134 assert(A->getType() == B->getType());
1135 return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
1137 // See if either input is A + C2, subject to the constraint from the
1138 // condition that A != C when that input is used. We can assume that
1139 // that input doesn't include C + C2.
1140 ConstantInt *CIAdded;
1143 case ICmpInst::ICMP_EQ:
1144 if (match(SI->getFalseValue(), m_Add(m_Specific(A),
1145 m_ConstantInt(CIAdded)))) {
1146 auto ResNot = addConstants(CIBase, CIAdded);
1147 FalseVal = intersect(FalseVal,
1148 LVILatticeVal::getNot(ResNot));
1151 case ICmpInst::ICMP_NE:
1152 if (match(SI->getTrueValue(), m_Add(m_Specific(A),
1153 m_ConstantInt(CIAdded)))) {
1154 auto ResNot = addConstants(CIBase, CIAdded);
1155 TrueVal = intersect(TrueVal,
1156 LVILatticeVal::getNot(ResNot));
1163 LVILatticeVal Result; // Start Undefined.
1164 Result.mergeIn(TrueVal, DL);
1165 Result.mergeIn(FalseVal, DL);
1170 bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV,
1173 if (!CI->getOperand(0)->getType()->isSized()) {
1174 // Without knowing how wide the input is, we can't analyze it in any useful
1176 BBLV = LVILatticeVal::getOverdefined();
1180 // Filter out casts we don't know how to reason about before attempting to
1181 // recurse on our operand. This can cut a long search short if we know we're
1182 // not going to be able to get any useful information anways.
1183 switch (CI->getOpcode()) {
1184 case Instruction::Trunc:
1185 case Instruction::SExt:
1186 case Instruction::ZExt:
1187 case Instruction::BitCast:
1190 // Unhandled instructions are overdefined.
1191 DEBUG(dbgs() << " compute BB '" << BB->getName()
1192 << "' - overdefined (unknown cast).\n");
1193 BBLV = LVILatticeVal::getOverdefined();
1197 // Figure out the range of the LHS. If that fails, we still apply the
1198 // transfer rule on the full set since we may be able to locally infer
1199 // interesting facts.
1200 if (!hasBlockValue(CI->getOperand(0), BB))
1201 if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
1202 // More work to do before applying this transfer rule.
1205 const unsigned OperandBitWidth =
1206 DL.getTypeSizeInBits(CI->getOperand(0)->getType());
1207 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1208 if (hasBlockValue(CI->getOperand(0), BB)) {
1209 LVILatticeVal LHSVal = getBlockValue(CI->getOperand(0), BB);
1210 intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
1212 if (LHSVal.isConstantRange())
1213 LHSRange = LHSVal.getConstantRange();
1216 const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
1218 // NOTE: We're currently limited by the set of operations that ConstantRange
1219 // can evaluate symbolically. Enhancing that set will allows us to analyze
1220 // more definitions.
1221 BBLV = LVILatticeVal::getRange(LHSRange.castOp(CI->getOpcode(),
1226 bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
1230 assert(BO->getOperand(0)->getType()->isSized() &&
1231 "all operands to binary operators are sized");
1233 // Filter out operators we don't know how to reason about before attempting to
1234 // recurse on our operand(s). This can cut a long search short if we know
1235 // we're not going to be able to get any useful information anyways.
1236 switch (BO->getOpcode()) {
1237 case Instruction::Add:
1238 case Instruction::Sub:
1239 case Instruction::Mul:
1240 case Instruction::UDiv:
1241 case Instruction::Shl:
1242 case Instruction::LShr:
1243 case Instruction::And:
1244 case Instruction::Or:
1245 // continue into the code below
1248 // Unhandled instructions are overdefined.
1249 DEBUG(dbgs() << " compute BB '" << BB->getName()
1250 << "' - overdefined (unknown binary operator).\n");
1251 BBLV = LVILatticeVal::getOverdefined();
1255 // Figure out the range of the LHS. If that fails, use a conservative range,
1256 // but apply the transfer rule anyways. This lets us pick up facts from
1257 // expressions like "and i32 (call i32 @foo()), 32"
1258 if (!hasBlockValue(BO->getOperand(0), BB))
1259 if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
1260 // More work to do before applying this transfer rule.
1263 const unsigned OperandBitWidth =
1264 DL.getTypeSizeInBits(BO->getOperand(0)->getType());
1265 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1266 if (hasBlockValue(BO->getOperand(0), BB)) {
1267 LVILatticeVal LHSVal = getBlockValue(BO->getOperand(0), BB);
1268 intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
1270 if (LHSVal.isConstantRange())
1271 LHSRange = LHSVal.getConstantRange();
1274 ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
1275 ConstantRange RHSRange = ConstantRange(RHS->getValue());
1277 // NOTE: We're currently limited by the set of operations that ConstantRange
1278 // can evaluate symbolically. Enhancing that set will allows us to analyze
1279 // more definitions.
1280 Instruction::BinaryOps BinOp = BO->getOpcode();
1281 BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1285 static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1287 Value *LHS = ICI->getOperand(0);
1288 Value *RHS = ICI->getOperand(1);
1289 CmpInst::Predicate Predicate = ICI->getPredicate();
1291 if (isa<Constant>(RHS)) {
1292 if (ICI->isEquality() && LHS == Val) {
1293 // We know that V has the RHS constant if this is a true SETEQ or
1295 if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1296 return LVILatticeVal::get(cast<Constant>(RHS));
1298 return LVILatticeVal::getNot(cast<Constant>(RHS));
1302 if (!Val->getType()->isIntegerTy())
1303 return LVILatticeVal::getOverdefined();
1305 // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1306 // range of Val guaranteed by the condition. Recognize comparisons in the from
1308 // icmp <pred> Val, ...
1309 // icmp <pred> (add Val, Offset), ...
1310 // The latter is the range checking idiom that InstCombine produces. Subtract
1311 // the offset from the allowed range for RHS in this case.
1313 // Val or (add Val, Offset) can be on either hand of the comparison
1314 if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1315 std::swap(LHS, RHS);
1316 Predicate = CmpInst::getSwappedPredicate(Predicate);
1319 ConstantInt *Offset = nullptr;
1321 match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1323 if (LHS == Val || Offset) {
1324 // Calculate the range of values that are allowed by the comparison
1325 ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1326 /*isFullSet=*/true);
1327 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1328 RHSRange = ConstantRange(CI->getValue());
1329 else if (Instruction *I = dyn_cast<Instruction>(RHS))
1330 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1331 RHSRange = getConstantRangeFromMetadata(*Ranges);
1333 // If we're interested in the false dest, invert the condition
1334 CmpInst::Predicate Pred =
1335 isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1336 ConstantRange TrueValues =
1337 ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1339 if (Offset) // Apply the offset from above.
1340 TrueValues = TrueValues.subtract(Offset->getValue());
1342 return LVILatticeVal::getRange(std::move(TrueValues));
1345 return LVILatticeVal::getOverdefined();
1348 static LVILatticeVal
1349 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1350 DenseMap<Value*, LVILatticeVal> &Visited);
1352 static LVILatticeVal
1353 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1354 DenseMap<Value*, LVILatticeVal> &Visited) {
1355 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1356 return getValueFromICmpCondition(Val, ICI, isTrueDest);
1358 // Handle conditions in the form of (cond1 && cond2), we know that on the
1359 // true dest path both of the conditions hold.
1361 return LVILatticeVal::getOverdefined();
1363 BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1364 if (!BO || BO->getOpcode() != BinaryOperator::And)
1365 return LVILatticeVal::getOverdefined();
1367 auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
1368 auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
1369 return intersect(RHS, LHS);
1372 static LVILatticeVal
1373 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1374 DenseMap<Value*, LVILatticeVal> &Visited) {
1375 auto I = Visited.find(Cond);
1376 if (I != Visited.end())
1379 auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1380 Visited[Cond] = Result;
1384 LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
1385 assert(Cond && "precondition");
1386 DenseMap<Value*, LVILatticeVal> Visited;
1387 return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1390 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1391 /// Val is not constrained on the edge. Result is unspecified if return value
1393 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1394 BasicBlock *BBTo, LVILatticeVal &Result) {
1395 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1396 // know that v != 0.
1397 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1398 // If this is a conditional branch and only one successor goes to BBTo, then
1399 // we may be able to infer something from the condition.
1400 if (BI->isConditional() &&
1401 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1402 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1403 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1404 "BBTo isn't a successor of BBFrom");
1406 // If V is the condition of the branch itself, then we know exactly what
1408 if (BI->getCondition() == Val) {
1409 Result = LVILatticeVal::get(ConstantInt::get(
1410 Type::getInt1Ty(Val->getContext()), isTrueDest));
1414 // If the condition of the branch is an equality comparison, we may be
1415 // able to infer the value.
1416 Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest);
1417 if (!Result.isOverdefined())
1422 // If the edge was formed by a switch on the value, then we may know exactly
1424 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1425 if (SI->getCondition() != Val)
1428 bool DefaultCase = SI->getDefaultDest() == BBTo;
1429 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1430 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1432 for (auto Case : SI->cases()) {
1433 ConstantRange EdgeVal(Case.getCaseValue()->getValue());
1435 // It is possible that the default destination is the destination of
1436 // some cases. There is no need to perform difference for those cases.
1437 if (Case.getCaseSuccessor() != BBTo)
1438 EdgesVals = EdgesVals.difference(EdgeVal);
1439 } else if (Case.getCaseSuccessor() == BBTo)
1440 EdgesVals = EdgesVals.unionWith(EdgeVal);
1442 Result = LVILatticeVal::getRange(std::move(EdgesVals));
1448 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1449 /// the basic block if the edge does not constrain Val.
1450 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1451 BasicBlock *BBTo, LVILatticeVal &Result,
1452 Instruction *CxtI) {
1453 // If already a constant, there is nothing to compute.
1454 if (Constant *VC = dyn_cast<Constant>(Val)) {
1455 Result = LVILatticeVal::get(VC);
1459 LVILatticeVal LocalResult;
1460 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1461 // If we couldn't constrain the value on the edge, LocalResult doesn't
1462 // provide any information.
1463 LocalResult = LVILatticeVal::getOverdefined();
1465 if (hasSingleValue(LocalResult)) {
1466 // Can't get any more precise here
1467 Result = LocalResult;
1471 if (!hasBlockValue(Val, BBFrom)) {
1472 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1474 // No new information.
1475 Result = LocalResult;
1479 // Try to intersect ranges of the BB and the constraint on the edge.
1480 LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
1481 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1482 BBFrom->getTerminator());
1483 // We can use the context instruction (generically the ultimate instruction
1484 // the calling pass is trying to simplify) here, even though the result of
1485 // this function is generally cached when called from the solve* functions
1486 // (and that cached result might be used with queries using a different
1487 // context instruction), because when this function is called from the solve*
1488 // functions, the context instruction is not provided. When called from
1489 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1490 // but then the result is not cached.
1491 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1493 Result = intersect(LocalResult, InBlock);
1497 LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1498 Instruction *CxtI) {
1499 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1500 << BB->getName() << "'\n");
1502 assert(BlockValueStack.empty() && BlockValueSet.empty());
1503 if (!hasBlockValue(V, BB)) {
1504 pushBlockValue(std::make_pair(BB, V));
1507 LVILatticeVal Result = getBlockValue(V, BB);
1508 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1510 DEBUG(dbgs() << " Result = " << Result << "\n");
1514 LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1515 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1516 << CxtI->getName() << "'\n");
1518 if (auto *C = dyn_cast<Constant>(V))
1519 return LVILatticeVal::get(C);
1521 LVILatticeVal Result = LVILatticeVal::getOverdefined();
1522 if (auto *I = dyn_cast<Instruction>(V))
1523 Result = getFromRangeMetadata(I);
1524 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1526 DEBUG(dbgs() << " Result = " << Result << "\n");
1530 LVILatticeVal LazyValueInfoImpl::
1531 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1532 Instruction *CxtI) {
1533 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1534 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1536 LVILatticeVal Result;
1537 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1539 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1541 assert(WasFastQuery && "More work to do after problem solved?");
1544 DEBUG(dbgs() << " Result = " << Result << "\n");
1548 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1549 BasicBlock *NewSucc) {
1550 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1553 //===----------------------------------------------------------------------===//
1554 // LazyValueInfo Impl
1555 //===----------------------------------------------------------------------===//
1557 /// This lazily constructs the LazyValueInfoImpl.
1558 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1559 const DataLayout *DL,
1560 DominatorTree *DT = nullptr) {
1562 assert(DL && "getCache() called with a null DataLayout");
1563 PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1565 return *static_cast<LazyValueInfoImpl*>(PImpl);
1568 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1569 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1570 const DataLayout &DL = F.getParent()->getDataLayout();
1572 DominatorTreeWrapperPass *DTWP =
1573 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1574 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1575 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1578 getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1584 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1585 AU.setPreservesAll();
1586 AU.addRequired<AssumptionCacheTracker>();
1587 AU.addRequired<TargetLibraryInfoWrapperPass>();
1590 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1592 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1594 void LazyValueInfo::releaseMemory() {
1595 // If the cache was allocated, free it.
1597 delete &getImpl(PImpl, AC, nullptr);
1602 bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1603 FunctionAnalysisManager::Invalidator &Inv) {
1604 // We need to invalidate if we have either failed to preserve this analyses
1605 // result directly or if any of its dependencies have been invalidated.
1606 auto PAC = PA.getChecker<LazyValueAnalysis>();
1607 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1608 (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1614 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1616 LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
1617 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1618 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1619 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1621 return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1624 /// Returns true if we can statically tell that this value will never be a
1625 /// "useful" constant. In practice, this means we've got something like an
1626 /// alloca or a malloc call for which a comparison against a constant can
1627 /// only be guarding dead code. Note that we are potentially giving up some
1628 /// precision in dead code (a constant result) in favour of avoiding a
1629 /// expensive search for a easily answered common query.
1630 static bool isKnownNonConstant(Value *V) {
1631 V = V->stripPointerCasts();
1632 // The return val of alloc cannot be a Constant.
1633 if (isa<AllocaInst>(V))
1638 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1639 Instruction *CxtI) {
1640 // Bail out early if V is known not to be a Constant.
1641 if (isKnownNonConstant(V))
1644 const DataLayout &DL = BB->getModule()->getDataLayout();
1645 LVILatticeVal Result =
1646 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1648 if (Result.isConstant())
1649 return Result.getConstant();
1650 if (Result.isConstantRange()) {
1651 const ConstantRange &CR = Result.getConstantRange();
1652 if (const APInt *SingleVal = CR.getSingleElement())
1653 return ConstantInt::get(V->getContext(), *SingleVal);
1658 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1659 Instruction *CxtI) {
1660 assert(V->getType()->isIntegerTy());
1661 unsigned Width = V->getType()->getIntegerBitWidth();
1662 const DataLayout &DL = BB->getModule()->getDataLayout();
1663 LVILatticeVal Result =
1664 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1665 if (Result.isUndefined())
1666 return ConstantRange(Width, /*isFullSet=*/false);
1667 if (Result.isConstantRange())
1668 return Result.getConstantRange();
1669 // We represent ConstantInt constants as constant ranges but other kinds
1670 // of integer constants, i.e. ConstantExpr will be tagged as constants
1671 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1672 "ConstantInt value must be represented as constantrange");
1673 return ConstantRange(Width, /*isFullSet=*/true);
1676 /// Determine whether the specified value is known to be a
1677 /// constant on the specified edge. Return null if not.
1678 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1680 Instruction *CxtI) {
1681 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1682 LVILatticeVal Result =
1683 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1685 if (Result.isConstant())
1686 return Result.getConstant();
1687 if (Result.isConstantRange()) {
1688 const ConstantRange &CR = Result.getConstantRange();
1689 if (const APInt *SingleVal = CR.getSingleElement())
1690 return ConstantInt::get(V->getContext(), *SingleVal);
1695 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1696 LVILatticeVal &Result,
1697 const DataLayout &DL,
1698 TargetLibraryInfo *TLI) {
1700 // If we know the value is a constant, evaluate the conditional.
1701 Constant *Res = nullptr;
1702 if (Result.isConstant()) {
1703 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
1705 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1706 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1707 return LazyValueInfo::Unknown;
1710 if (Result.isConstantRange()) {
1711 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1712 if (!CI) return LazyValueInfo::Unknown;
1714 const ConstantRange &CR = Result.getConstantRange();
1715 if (Pred == ICmpInst::ICMP_EQ) {
1716 if (!CR.contains(CI->getValue()))
1717 return LazyValueInfo::False;
1719 if (CR.isSingleElement() && CR.contains(CI->getValue()))
1720 return LazyValueInfo::True;
1721 } else if (Pred == ICmpInst::ICMP_NE) {
1722 if (!CR.contains(CI->getValue()))
1723 return LazyValueInfo::True;
1725 if (CR.isSingleElement() && CR.contains(CI->getValue()))
1726 return LazyValueInfo::False;
1729 // Handle more complex predicates.
1730 ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1731 (ICmpInst::Predicate)Pred, CI->getValue());
1732 if (TrueValues.contains(CR))
1733 return LazyValueInfo::True;
1734 if (TrueValues.inverse().contains(CR))
1735 return LazyValueInfo::False;
1736 return LazyValueInfo::Unknown;
1739 if (Result.isNotConstant()) {
1740 // If this is an equality comparison, we can try to fold it knowing that
1742 if (Pred == ICmpInst::ICMP_EQ) {
1743 // !C1 == C -> false iff C1 == C.
1744 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1745 Result.getNotConstant(), C, DL,
1747 if (Res->isNullValue())
1748 return LazyValueInfo::False;
1749 } else if (Pred == ICmpInst::ICMP_NE) {
1750 // !C1 != C -> true iff C1 == C.
1751 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1752 Result.getNotConstant(), C, DL,
1754 if (Res->isNullValue())
1755 return LazyValueInfo::True;
1757 return LazyValueInfo::Unknown;
1760 return LazyValueInfo::Unknown;
1763 /// Determine whether the specified value comparison with a constant is known to
1764 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1765 LazyValueInfo::Tristate
1766 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1767 BasicBlock *FromBB, BasicBlock *ToBB,
1768 Instruction *CxtI) {
1769 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1770 LVILatticeVal Result =
1771 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1773 return getPredicateResult(Pred, C, Result, DL, TLI);
1776 LazyValueInfo::Tristate
1777 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1778 Instruction *CxtI) {
1779 // Is or is not NonNull are common predicates being queried. If
1780 // isKnownNonNull can tell us the result of the predicate, we can
1781 // return it quickly. But this is only a fastpath, and falling
1782 // through would still be correct.
1783 if (V->getType()->isPointerTy() && C->isNullValue() &&
1784 isKnownNonNull(V->stripPointerCasts())) {
1785 if (Pred == ICmpInst::ICMP_EQ)
1786 return LazyValueInfo::False;
1787 else if (Pred == ICmpInst::ICMP_NE)
1788 return LazyValueInfo::True;
1790 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1791 LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1792 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1796 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1797 // LVI as a whole tries to compute a lattice value which is conservatively
1798 // correct at a given location. In this case, we have a predicate which we
1799 // weren't able to prove about the merged result, and we're pushing that
1800 // predicate back along each incoming edge to see if we can prove it
1801 // separately for each input. As a motivating example, consider:
1803 // %v1 = ... ; constantrange<1, 5>
1806 // %v2 = ... ; constantrange<10, 20>
1809 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1810 // %pred = icmp eq i32 %phi, 8
1811 // We can't tell from the lattice value for '%phi' that '%pred' is false
1812 // along each path, but by checking the predicate over each input separately,
1814 // We limit the search to one step backwards from the current BB and value.
1815 // We could consider extending this to search further backwards through the
1816 // CFG and/or value graph, but there are non-obvious compile time vs quality
1819 BasicBlock *BB = CxtI->getParent();
1821 // Function entry or an unreachable block. Bail to avoid confusing
1823 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1827 // If V is a PHI node in the same block as the context, we need to ask
1828 // questions about the predicate as applied to the incoming value along
1829 // each edge. This is useful for eliminating cases where the predicate is
1830 // known along all incoming edges.
1831 if (auto *PHI = dyn_cast<PHINode>(V))
1832 if (PHI->getParent() == BB) {
1833 Tristate Baseline = Unknown;
1834 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1835 Value *Incoming = PHI->getIncomingValue(i);
1836 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1837 // Note that PredBB may be BB itself.
1838 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1841 // Keep going as long as we've seen a consistent known result for
1843 Baseline = (i == 0) ? Result /* First iteration */
1844 : (Baseline == Result ? Baseline : Unknown); /* All others */
1845 if (Baseline == Unknown)
1848 if (Baseline != Unknown)
1852 // For a comparison where the V is outside this block, it's possible
1853 // that we've branched on it before. Look to see if the value is known
1854 // on all incoming edges.
1855 if (!isa<Instruction>(V) ||
1856 cast<Instruction>(V)->getParent() != BB) {
1857 // For predecessor edge, determine if the comparison is true or false
1858 // on that edge. If they're all true or all false, we can conclude
1859 // the value of the comparison in this block.
1860 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1861 if (Baseline != Unknown) {
1862 // Check that all remaining incoming values match the first one.
1863 while (++PI != PE) {
1864 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1865 if (Ret != Baseline) break;
1867 // If we terminated early, then one of the values didn't match.
1877 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1878 BasicBlock *NewSucc) {
1880 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1881 getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1885 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1887 const DataLayout &DL = BB->getModule()->getDataLayout();
1888 getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1893 void LazyValueInfo::printCache(Function &F, raw_ostream &OS) {
1895 getImpl(PImpl, AC, DL, DT).printCache(F, OS);
1900 // Printer class for LazyValueInfo results.
1901 class LazyValueInfoPrinter : public FunctionPass {
1903 static char ID; // Pass identification, replacement for typeid
1904 LazyValueInfoPrinter() : FunctionPass(ID) {
1905 initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
1908 void getAnalysisUsage(AnalysisUsage &AU) const override {
1909 AU.setPreservesAll();
1910 AU.addRequired<LazyValueInfoWrapperPass>();
1913 bool runOnFunction(Function &F) override {
1914 dbgs() << "LVI for function '" << F.getName() << "':\n";
1915 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1916 LVI.printCache(F, dbgs());
1922 char LazyValueInfoPrinter::ID = 0;
1923 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1924 "Lazy Value Info Printer Pass", false, false)
1925 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
1926 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1927 "Lazy Value Info Printer Pass", false, false)