LCOV - code coverage report
Current view: top level - lib/Analysis - LazyValueInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 522 568 91.9 %
Date: 2018-10-20 13:21:21 Functions: 63 69 91.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the interface for lazy computation of value constraint
      11             : // information.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      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/InstructionSimplify.h"
      21             : #include "llvm/Analysis/TargetLibraryInfo.h"
      22             : #include "llvm/Analysis/ValueTracking.h"
      23             : #include "llvm/Analysis/ValueLattice.h"
      24             : #include "llvm/IR/AssemblyAnnotationWriter.h"
      25             : #include "llvm/IR/CFG.h"
      26             : #include "llvm/IR/ConstantRange.h"
      27             : #include "llvm/IR/Constants.h"
      28             : #include "llvm/IR/DataLayout.h"
      29             : #include "llvm/IR/Dominators.h"
      30             : #include "llvm/IR/Instructions.h"
      31             : #include "llvm/IR/IntrinsicInst.h"
      32             : #include "llvm/IR/Intrinsics.h"
      33             : #include "llvm/IR/LLVMContext.h"
      34             : #include "llvm/IR/PatternMatch.h"
      35             : #include "llvm/IR/ValueHandle.h"
      36             : #include "llvm/Support/Debug.h"
      37             : #include "llvm/Support/FormattedStream.h"
      38             : #include "llvm/Support/raw_ostream.h"
      39             : #include <map>
      40             : using namespace llvm;
      41             : using namespace PatternMatch;
      42             : 
      43             : #define DEBUG_TYPE "lazy-value-info"
      44             : 
      45             : // This is the number of worklist items we will process to try to discover an
      46             : // answer for a given value.
      47             : static const unsigned MaxProcessedPerValue = 500;
      48             : 
      49             : char LazyValueInfoWrapperPass::ID = 0;
      50       33336 : INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
      51             :                 "Lazy Value Information Analysis", false, true)
      52       33336 : INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
      53       33336 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
      54      124663 : INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
      55             :                 "Lazy Value Information Analysis", false, true)
      56             : 
      57             : namespace llvm {
      58           0 :   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
      59             : }
      60             : 
      61             : AnalysisKey LazyValueAnalysis::Key;
      62             : 
      63             : /// Returns true if this lattice value represents at most one possible value.
      64             : /// This is as precise as any lattice value can get while still representing
      65             : /// reachable code.
      66             : static bool hasSingleValue(const ValueLatticeElement &Val) {
      67     1820281 :   if (Val.isConstantRange() &&
      68             :       Val.getConstantRange().isSingleElement())
      69             :     // Integer constants are single element ranges
      70             :     return true;
      71     1726287 :   if (Val.isConstant())
      72             :     // Non integer constants
      73             :     return true;
      74             :   return false;
      75             : }
      76             : 
      77             : /// Combine two sets of facts about the same value into a single set of
      78             : /// facts.  Note that this method is not suitable for merging facts along
      79             : /// different paths in a CFG; that's what the mergeIn function is for.  This
      80             : /// is for merging facts gathered about the same value at the same location
      81             : /// through two independent means.
      82             : /// Notes:
      83             : /// * This method does not promise to return the most precise possible lattice
      84             : ///   value implied by A and B.  It is allowed to return any lattice element
      85             : ///   which is at least as strong as *either* A or B (unless our facts
      86             : ///   conflict, see below).
      87             : /// * Due to unreachable code, the intersection of two lattice values could be
      88             : ///   contradictory.  If this happens, we return some valid lattice value so as
      89             : ///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
      90             : ///   we do not make this guarantee.  TODO: This would be a useful enhancement.
      91     1014869 : static ValueLatticeElement intersect(const ValueLatticeElement &A,
      92             :                                      const ValueLatticeElement &B) {
      93             :   // Undefined is the strongest state.  It means the value is known to be along
      94             :   // an unreachable path.
      95     1014869 :   if (A.isUndefined())
      96             :     return A;
      97     1014869 :   if (B.isUndefined())
      98             :     return B;
      99             : 
     100             :   // If we gave up for one, but got a useable fact from the other, use it.
     101     1014367 :   if (A.isOverdefined())
     102             :     return B;
     103       43993 :   if (B.isOverdefined())
     104             :     return A;
     105             : 
     106             :   // Can't get any more precise than constants.
     107             :   if (hasSingleValue(A))
     108             :     return A;
     109             :   if (hasSingleValue(B))
     110             :     return B;
     111             : 
     112             :   // Could be either constant range or not constant here.
     113       15008 :   if (!A.isConstantRange() || !B.isConstantRange()) {
     114             :     // TODO: Arbitrary choice, could be improved
     115             :     return A;
     116             :   }
     117             : 
     118             :   // Intersect two constant ranges
     119             :   ConstantRange Range =
     120       14964 :     A.getConstantRange().intersectWith(B.getConstantRange());
     121             :   // Note: An empty range is implicitly converted to overdefined internally.
     122             :   // TODO: We could instead use Undefined here since we've proven a conflict
     123             :   // and thus know this path must be unreachable.
     124       14964 :   return ValueLatticeElement::getRange(std::move(Range));
     125             : }
     126             : 
     127             : //===----------------------------------------------------------------------===//
     128             : //                          LazyValueInfoCache Decl
     129             : //===----------------------------------------------------------------------===//
     130             : 
     131             : namespace {
     132             :   /// A callback value handle updates the cache when values are erased.
     133             :   class LazyValueInfoCache;
     134             :   struct LVIValueHandle final : public CallbackVH {
     135             :     // Needs to access getValPtr(), which is protected.
     136             :     friend struct DenseMapInfo<LVIValueHandle>;
     137             : 
     138             :     LazyValueInfoCache *Parent;
     139             : 
     140             :     LVIValueHandle(Value *V, LazyValueInfoCache *P)
     141      371940 :       : CallbackVH(V), Parent(P) { }
     142             : 
     143             :     void deleted() override;
     144         282 :     void allUsesReplacedWith(Value *V) override {
     145             :       deleted();
     146         282 :     }
     147             :   };
     148             : } // end anonymous namespace
     149             : 
     150             : namespace {
     151             :   /// This is the cache kept by LazyValueInfo which
     152             :   /// maintains information about queries across the clients' queries.
     153             :   class LazyValueInfoCache {
     154             :     /// This is all of the cached block information for exactly one Value*.
     155             :     /// The entries are sorted by the BasicBlock* of the
     156             :     /// entries, allowing us to do a lookup with a binary search.
     157             :     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     158             :     /// memory overhead.
     159             :     struct ValueCacheEntryTy {
     160      371940 :       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
     161             :       LVIValueHandle Handle;
     162             :       SmallDenseMap<PoisoningVH<BasicBlock>, ValueLatticeElement, 4> BlockVals;
     163             :     };
     164             : 
     165             :     /// This tracks, on a per-block basis, the set of values that are
     166             :     /// over-defined at the end of that block.
     167             :     typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
     168             :         OverDefinedCacheTy;
     169             :     /// Keep track of all blocks that we have ever seen, so we
     170             :     /// don't spend time removing unused blocks from our caches.
     171             :     DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
     172             : 
     173             :     /// This is all of the cached information for all values,
     174             :     /// mapped from Value* to key information.
     175             :     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
     176             :     OverDefinedCacheTy OverDefinedCache;
     177             : 
     178             : 
     179             :   public:
     180     1146822 :     void insertResult(Value *Val, BasicBlock *BB,
     181             :                       const ValueLatticeElement &Result) {
     182     1146821 :       SeenBlocks.insert(BB);
     183             : 
     184             :       // Insert over-defined values into their own cache to reduce memory
     185             :       // overhead.
     186     1146821 :       if (Result.isOverdefined())
     187      720941 :         OverDefinedCache[BB].insert(Val);
     188             :       else {
     189      425880 :         auto It = ValueCache.find_as(Val);
     190      425880 :         if (It == ValueCache.end()) {
     191      371940 :           ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
     192      185970 :           It = ValueCache.find_as(Val);
     193             :           assert(It != ValueCache.end() && "Val was just added to the map!");
     194             :         }
     195      425880 :         It->second->BlockVals[BB] = Result;
     196             :       }
     197     1146822 :     }
     198             : 
     199     5664909 :     bool isOverdefined(Value *V, BasicBlock *BB) const {
     200    11329818 :       auto ODI = OverDefinedCache.find(BB);
     201             : 
     202     5664909 :       if (ODI == OverDefinedCache.end())
     203             :         return false;
     204             : 
     205     3958910 :       return ODI->second.count(V);
     206             :     }
     207             : 
     208     4013823 :     bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
     209     4013823 :       if (isOverdefined(V, BB))
     210             :         return true;
     211             : 
     212     3272186 :       auto I = ValueCache.find_as(V);
     213     3272186 :       if (I == ValueCache.end())
     214             :         return false;
     215             : 
     216     2435068 :       return I->second->BlockVals.count(BB);
     217             :     }
     218             : 
     219     1651086 :     ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const {
     220     1651086 :       if (isOverdefined(V, BB))
     221             :         return ValueLatticeElement::getOverdefined();
     222             : 
     223      632250 :       auto I = ValueCache.find_as(V);
     224      632250 :       if (I == ValueCache.end())
     225             :         return ValueLatticeElement();
     226     1264500 :       auto BBI = I->second->BlockVals.find(BB);
     227      632250 :       if (BBI == I->second->BlockVals.end())
     228             :         return ValueLatticeElement();
     229      632250 :       return BBI->second;
     230             :     }
     231             : 
     232             :     /// clear - Empty the cache.
     233           0 :     void clear() {
     234             :       SeenBlocks.clear();
     235           0 :       ValueCache.clear();
     236           0 :       OverDefinedCache.clear();
     237           0 :     }
     238             : 
     239             :     /// Inform the cache that a given value has been deleted.
     240             :     void eraseValue(Value *V);
     241             : 
     242             :     /// This is part of the update interface to inform the cache
     243             :     /// that a block has been deleted.
     244             :     void eraseBlock(BasicBlock *BB);
     245             : 
     246             :     /// Updates the cache to remove any influence an overdefined value in
     247             :     /// OldSucc might have (unless also overdefined in NewSucc).  This just
     248             :     /// flushes elements from the cache and does not add any.
     249             :     void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
     250             : 
     251             :     friend struct LVIValueHandle;
     252             :   };
     253             : }
     254             : 
     255         363 : void LazyValueInfoCache::eraseValue(Value *V) {
     256       16924 :   for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
     257             :     // Copy and increment the iterator immediately so we can erase behind
     258             :     // ourselves.
     259             :     auto Iter = I++;
     260             :     SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
     261       16561 :     ValueSet.erase(V);
     262       16561 :     if (ValueSet.empty())
     263             :       OverDefinedCache.erase(Iter);
     264             :   }
     265             : 
     266         363 :   ValueCache.erase(V);
     267         363 : }
     268             : 
     269          81 : void LVIValueHandle::deleted() {
     270             :   // This erasure deallocates *this, so it MUST happen after we're done
     271             :   // using any and all members of *this.
     272         726 :   Parent->eraseValue(*this);
     273          81 : }
     274             : 
     275       30650 : void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
     276             :   // Shortcut if we have never seen this block.
     277       30650 :   DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
     278       30650 :   if (I == SeenBlocks.end())
     279       26289 :     return;
     280             :   SeenBlocks.erase(I);
     281             : 
     282        8722 :   auto ODI = OverDefinedCache.find(BB);
     283        4361 :   if (ODI != OverDefinedCache.end())
     284             :     OverDefinedCache.erase(ODI);
     285             : 
     286       24468 :   for (auto &I : ValueCache)
     287       40214 :     I.second->BlockVals.erase(BB);
     288             : }
     289             : 
     290        2525 : void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
     291             :                                         BasicBlock *NewSucc) {
     292             :   // When an edge in the graph has been threaded, values that we could not
     293             :   // determine a value for before (i.e. were marked overdefined) may be
     294             :   // possible to solve now. We do NOT try to proactively update these values.
     295             :   // Instead, we clear their entries from the cache, and allow lazy updating to
     296             :   // recompute them when needed.
     297             : 
     298             :   // The updating process is fairly simple: we need to drop cached info
     299             :   // for all values that were marked overdefined in OldSucc, and for those same
     300             :   // values in any successor of OldSucc (except NewSucc) in which they were
     301             :   // also marked overdefined.
     302             :   std::vector<BasicBlock*> worklist;
     303        2525 :   worklist.push_back(OldSucc);
     304             : 
     305        5050 :   auto I = OverDefinedCache.find(OldSucc);
     306        2525 :   if (I == OverDefinedCache.end())
     307             :     return; // Nothing to process here.
     308         316 :   SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
     309             : 
     310             :   // Use a worklist to perform a depth-first search of OldSucc's successors.
     311             :   // NOTE: We do not need a visited list since any blocks we have already
     312             :   // visited will have had their overdefined markers cleared already, and we
     313             :   // thus won't loop to their successors.
     314        2054 :   while (!worklist.empty()) {
     315        1896 :     BasicBlock *ToUpdate = worklist.back();
     316             :     worklist.pop_back();
     317             : 
     318             :     // Skip blocks only accessible through NewSucc.
     319        2646 :     if (ToUpdate == NewSucc) continue;
     320             : 
     321             :     // If a value was marked overdefined in OldSucc, and is here too...
     322        1703 :     auto OI = OverDefinedCache.find(ToUpdate);
     323        1703 :     if (OI == OverDefinedCache.end())
     324             :       continue;
     325             :     SmallPtrSetImpl<Value *> &ValueSet = OI->second;
     326             : 
     327             :     bool changed = false;
     328        2369 :     for (Value *V : ValsToClear) {
     329        1844 :       if (!ValueSet.erase(V))
     330             :         continue;
     331             : 
     332             :       // If we removed anything, then we potentially need to update
     333             :       // blocks successors too.
     334             :       changed = true;
     335             : 
     336        1314 :       if (ValueSet.empty()) {
     337             :         OverDefinedCache.erase(OI);
     338             :         break;
     339             :       }
     340             :     }
     341             : 
     342         525 :     if (!changed) continue;
     343             : 
     344         953 :     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
     345             :   }
     346             : }
     347             : 
     348             : 
     349             : namespace {
     350             : /// An assembly annotator class to print LazyValueCache information in
     351             : /// comments.
     352             : class LazyValueInfoImpl;
     353           4 : class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
     354             :   LazyValueInfoImpl *LVIImpl;
     355             :   // While analyzing which blocks we can solve values for, we need the dominator
     356             :   // information. Since this is an optional parameter in LVI, we require this
     357             :   // DomTreeAnalysis pass in the printer pass, and pass the dominator
     358             :   // tree to the LazyValueInfoAnnotatedWriter.
     359             :   DominatorTree &DT;
     360             : 
     361             : public:
     362             :   LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
     363           4 :       : LVIImpl(L), DT(DTree) {}
     364             : 
     365             :   virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
     366             :                                         formatted_raw_ostream &OS);
     367             : 
     368             :   virtual void emitInstructionAnnot(const Instruction *I,
     369             :                                     formatted_raw_ostream &OS);
     370             : };
     371             : }
     372             : namespace {
     373             :   // The actual implementation of the lazy analysis and update.  Note that the
     374             :   // inheritance from LazyValueInfoCache is intended to be temporary while
     375             :   // splitting the code and then transitioning to a has-a relationship.
     376             :   class LazyValueInfoImpl {
     377             : 
     378             :     /// Cached results from previous queries
     379             :     LazyValueInfoCache TheCache;
     380             : 
     381             :     /// This stack holds the state of the value solver during a query.
     382             :     /// It basically emulates the callstack of the naive
     383             :     /// recursive value lookup process.
     384             :     SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
     385             : 
     386             :     /// Keeps track of which block-value pairs are in BlockValueStack.
     387             :     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
     388             : 
     389             :     /// Push BV onto BlockValueStack unless it's already in there.
     390             :     /// Returns true on success.
     391     1167215 :     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
     392     1167215 :       if (!BlockValueSet.insert(BV).second)
     393             :         return false;  // It's already in the stack.
     394             : 
     395             :       LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
     396             :                         << BV.first->getName() << "\n");
     397     1147458 :       BlockValueStack.push_back(BV);
     398     1147458 :       return true;
     399             :     }
     400             : 
     401             :     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     402             :     const DataLayout &DL; ///< A mandatory DataLayout
     403             :     DominatorTree *DT;    ///< An optional DT pointer.
     404             :     DominatorTree *DisabledDT; ///< Stores DT if it's disabled.
     405             : 
     406             :   ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
     407             :   bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
     408             :                     ValueLatticeElement &Result, Instruction *CxtI = nullptr);
     409             :   bool hasBlockValue(Value *Val, BasicBlock *BB);
     410             : 
     411             :   // These methods process one work item and may add more. A false value
     412             :   // returned means that the work item was not completely processed and must
     413             :   // be revisited after going through the new items.
     414             :   bool solveBlockValue(Value *Val, BasicBlock *BB);
     415             :   bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
     416             :                            BasicBlock *BB);
     417             :   bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
     418             :                                BasicBlock *BB);
     419             :   bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
     420             :                               BasicBlock *BB);
     421             :   bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
     422             :                              BasicBlock *BB);
     423             :   bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
     424             :                                BasicBlock *BB);
     425             :   bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
     426             :                            BasicBlock *BB);
     427             :   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
     428             :                                                      ValueLatticeElement &BBLV,
     429             :                                                      Instruction *BBI);
     430             : 
     431             :   void solve();
     432             : 
     433             :   public:
     434             :     /// This is the query interface to determine the lattice
     435             :     /// value for the specified Value* at the end of the specified block.
     436             :     ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
     437             :                                         Instruction *CxtI = nullptr);
     438             : 
     439             :     /// This is the query interface to determine the lattice
     440             :     /// value for the specified Value* at the specified instruction (generally
     441             :     /// from an assume intrinsic).
     442             :     ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
     443             : 
     444             :     /// This is the query interface to determine the lattice
     445             :     /// value for the specified Value* that is true on the specified edge.
     446             :     ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
     447             :                                        BasicBlock *ToBB,
     448             :                                    Instruction *CxtI = nullptr);
     449             : 
     450             :     /// Complete flush all previously computed values
     451             :     void clear() {
     452           0 :       TheCache.clear();
     453             :     }
     454             : 
     455             :     /// Printing the LazyValueInfo Analysis.
     456           4 :     void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
     457             :         LazyValueInfoAnnotatedWriter Writer(this, DTree);
     458           4 :         F.print(OS, &Writer);
     459           4 :     }
     460             : 
     461             :     /// This is part of the update interface to inform the cache
     462             :     /// that a block has been deleted.
     463             :     void eraseBlock(BasicBlock *BB) {
     464       30650 :       TheCache.eraseBlock(BB);
     465             :     }
     466             : 
     467             :     /// Disables use of the DominatorTree within LVI.
     468             :     void disableDT() {
     469      203820 :       if (DT) {
     470             :         assert(!DisabledDT && "Both DT and DisabledDT are not nullptr!");
     471             :         std::swap(DT, DisabledDT);
     472             :       }
     473             :     }
     474             : 
     475             :     /// Enables use of the DominatorTree within LVI. Does nothing if the class
     476             :     /// instance was initialized without a DT pointer.
     477             :     void enableDT() {
     478      131292 :       if (DisabledDT) {
     479             :         assert(!DT && "Both DT and DisabledDT are not nullptr!");
     480             :         std::swap(DT, DisabledDT);
     481             :       }
     482             :     }
     483             : 
     484             :     /// This is the update interface to inform the cache that an edge from
     485             :     /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
     486             :     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
     487             : 
     488             :     LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
     489             :                        DominatorTree *DT = nullptr)
     490       75817 :         : AC(AC), DL(DL), DT(DT), DisabledDT(nullptr) {}
     491             :   };
     492             : } // end anonymous namespace
     493             : 
     494             : 
     495      670538 : void LazyValueInfoImpl::solve() {
     496             :   SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
     497             :       BlockValueStack.begin(), BlockValueStack.end());
     498             : 
     499             :   unsigned processedCount = 0;
     500     2294262 :   while (!BlockValueStack.empty()) {
     501     1623742 :     processedCount++;
     502             :     // Abort if we have to process too many values to get a result for this one.
     503             :     // Because of the design of the overdefined cache currently being per-block
     504             :     // to avoid naming-related issues (IE it wants to try to give different
     505             :     // results for the same name in different blocks), overdefined results don't
     506             :     // get cached globally, which in turn means we will often try to rediscover
     507             :     // the same overdefined result again and again.  Once something like
     508             :     // PredicateInfo is used in LVI or CVP, we should be able to make the
     509             :     // overdefined cache global, and remove this throttle.
     510     1623742 :     if (processedCount > MaxProcessedPerValue) {
     511             :       LLVM_DEBUG(
     512             :           dbgs() << "Giving up on stack because we are getting too deep\n");
     513             :       // Fill in the original values
     514          36 :       while (!StartingStack.empty()) {
     515             :         std::pair<BasicBlock *, Value *> &e = StartingStack.back();
     516          18 :         TheCache.insertResult(e.second, e.first,
     517          18 :                               ValueLatticeElement::getOverdefined());
     518             :         StartingStack.pop_back();
     519             :       }
     520             :       BlockValueSet.clear();
     521             :       BlockValueStack.clear();
     522          18 :       return;
     523             :     }
     524     1623724 :     std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
     525             :     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
     526             : 
     527     1623724 :     if (solveBlockValue(e.second, e.first)) {
     528             :       // The work item was completely processed.
     529             :       assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
     530             :       assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
     531             :              "Result should be in cache!");
     532             : 
     533             :       LLVM_DEBUG(
     534             :           dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
     535             :                  << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
     536             : 
     537             :       BlockValueStack.pop_back();
     538             :       BlockValueSet.erase(e);
     539             :     } else {
     540             :       // More work needs to be done before revisiting.
     541             :       assert(BlockValueStack.back() != e && "Stack should have been pushed!");
     542             :     }
     543             :   }
     544             : }
     545             : 
     546             : bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
     547             :   // If already a constant, there is nothing to compute.
     548     2392774 :   if (isa<Constant>(Val))
     549             :     return true;
     550             : 
     551     2390099 :   return TheCache.hasCachedValueInfo(Val, BB);
     552             : }
     553             : 
     554     1653741 : ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
     555             :                                                      BasicBlock *BB) {
     556             :   // If already a constant, there is nothing to compute.
     557             :   if (Constant *VC = dyn_cast<Constant>(Val))
     558             :     return ValueLatticeElement::get(VC);
     559             : 
     560     1651086 :   return TheCache.getCachedValueInfo(Val, BB);
     561             : }
     562             : 
     563      579860 : static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
     564             :   switch (BBI->getOpcode()) {
     565             :   default: break;
     566             :   case Instruction::Load:
     567             :   case Instruction::Call:
     568             :   case Instruction::Invoke:
     569      234681 :     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
     570       25182 :       if (isa<IntegerType>(BBI->getType())) {
     571             :         return ValueLatticeElement::getRange(
     572       12591 :             getConstantRangeFromMetadata(*Ranges));
     573             :       }
     574             :     break;
     575             :   };
     576             :   // Nothing known - will be intersected with other facts
     577             :   return ValueLatticeElement::getOverdefined();
     578             : }
     579             : 
     580     1623724 : bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
     581     1623724 :   if (isa<Constant>(Val))
     582             :     return true;
     583             : 
     584     1623724 :   if (TheCache.hasCachedValueInfo(Val, BB)) {
     585             :     // If we have a cached value, use that.
     586             :     LLVM_DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val="
     587             :                       << TheCache.getCachedValueInfo(Val, BB) << '\n');
     588             : 
     589             :     // Since we're reusing a cached value, we don't need to update the
     590             :     // OverDefinedCache. The cache will have been properly updated whenever the
     591             :     // cached value was inserted.
     592             :     return true;
     593             :   }
     594             : 
     595             :   // Hold off inserting this value into the Cache in case we have to return
     596             :   // false and come back later.
     597             :   ValueLatticeElement Res;
     598     1623724 :   if (!solveBlockValueImpl(Res, Val, BB))
     599             :     // Work pushed, will revisit
     600             :     return false;
     601             : 
     602     1146804 :   TheCache.insertResult(Val, BB, Res);
     603     1146804 :   return true;
     604             : }
     605             : 
     606     1623724 : bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
     607             :                                             Value *Val, BasicBlock *BB) {
     608             : 
     609             :   Instruction *BBI = dyn_cast<Instruction>(Val);
     610     1477717 :   if (!BBI || BBI->getParent() != BB)
     611      915998 :     return solveBlockValueNonLocal(Res, Val, BB);
     612             : 
     613             :   if (PHINode *PN = dyn_cast<PHINode>(BBI))
     614      196664 :     return solveBlockValuePHINode(Res, PN, BB);
     615             : 
     616             :   if (auto *SI = dyn_cast<SelectInst>(BBI))
     617        4562 :     return solveBlockValueSelect(Res, SI, BB);
     618             : 
     619             :   // If this value is a nonnull pointer, record it's range and bailout.  Note
     620             :   // that for all other pointer typed values, we terminate the search at the
     621             :   // definition.  We could easily extend this to look through geps, bitcasts,
     622             :   // and the like to prove non-nullness, but it's not clear that's worth it
     623             :   // compile time wise.  The context-insensitive value walk done inside
     624             :   // isKnownNonZero gets most of the profitable cases at much less expense.
     625             :   // This does mean that we have a sensativity to where the defining
     626             :   // instruction is placed, even if it could legally be hoisted much higher.
     627             :   // That is unfortunate.
     628      506500 :   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
     629      309246 :   if (PT && isKnownNonZero(BBI, DL)) {
     630      214396 :     Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
     631      107198 :     return true;
     632             :   }
     633      798604 :   if (BBI->getType()->isIntegerTy()) {
     634             :     if (auto *CI = dyn_cast<CastInst>(BBI))
     635        8833 :       return solveBlockValueCast(Res, CI, BB);
     636             : 
     637             :     BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
     638       50099 :     if (BO && isa<ConstantInt>(BO->getOperand(1)))
     639       42500 :       return solveBlockValueBinaryOp(Res, BO, BB);
     640             :   }
     641             : 
     642             :   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
     643             :                     << "' - unknown inst def found.\n");
     644      347969 :   Res = getFromRangeMetadata(BBI);
     645      347969 :   return true;
     646             : }
     647             : 
     648     2089447 : static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
     649             :   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
     650      909794 :     return L->getPointerAddressSpace() == 0 &&
     651      909416 :            GetUnderlyingObject(L->getPointerOperand(),
     652             :                                L->getModule()->getDataLayout()) == Ptr;
     653             :   }
     654             :   if (StoreInst *S = dyn_cast<StoreInst>(I)) {
     655      852001 :     return S->getPointerAddressSpace() == 0 &&
     656      851244 :            GetUnderlyingObject(S->getPointerOperand(),
     657             :                                S->getModule()->getDataLayout()) == Ptr;
     658             :   }
     659             :   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
     660        2168 :     if (MI->isVolatile()) return false;
     661             : 
     662             :     // FIXME: check whether it has a valuerange that excludes zero?
     663             :     ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
     664        1615 :     if (!Len || Len->isZero()) return false;
     665             : 
     666        1615 :     if (MI->getDestAddressSpace() == 0)
     667        3226 :       if (GetUnderlyingObject(MI->getRawDest(),
     668             :                               MI->getModule()->getDataLayout()) == Ptr)
     669             :         return true;
     670             :     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
     671         580 :       if (MTI->getSourceAddressSpace() == 0)
     672        1156 :         if (GetUnderlyingObject(MTI->getRawSource(),
     673             :                                 MTI->getModule()->getDataLayout()) == Ptr)
     674          64 :           return true;
     675             :   }
     676             :   return false;
     677             : }
     678             : 
     679             : /// Return true if the allocation associated with Val is ever dereferenced
     680             : /// within the given basic block.  This establishes the fact Val is not null,
     681             : /// but does not imply that the memory at Val is dereferenceable.  (Val may
     682             : /// point off the end of the dereferenceable part of the object.)
     683      179546 : static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
     684             :   assert(Val->getType()->isPointerTy());
     685             : 
     686      179546 :   const DataLayout &DL = BB->getModule()->getDataLayout();
     687      179546 :   Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
     688             :   // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
     689             :   // inside InstructionDereferencesPointer either.
     690      179546 :   if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
     691     2239416 :     for (Instruction &I : *BB)
     692     2089447 :       if (InstructionDereferencesPointer(&I, UnderlyingVal))
     693             :         return true;
     694             :   return false;
     695             : }
     696             : 
     697      915998 : bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
     698             :                                                  Value *Val, BasicBlock *BB) {
     699             :   ValueLatticeElement Result;  // Start Undefined.
     700             : 
     701             :   // If this is the entry block, we must be asking about an argument.  The
     702             :   // value is overdefined.
     703     1831996 :   if (BB == &BB->getParent()->getEntryBlock()) {
     704             :     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
     705             :     // Before giving up, see if we can prove the pointer non-null local to
     706             :     // this particular block.
     707       33922 :     PointerType *PTy = dyn_cast<PointerType>(Val->getType());
     708       30555 :     if (PTy &&
     709       48922 :         (isKnownNonZero(Val, DL) ||
     710       21757 :           (isObjectDereferencedInBlock(Val, BB) &&
     711        3390 :            !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) {
     712       46707 :       Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
     713             :     } else {
     714       36706 :       Result = ValueLatticeElement::getOverdefined();
     715             :     }
     716       33922 :     BBLV = Result;
     717       33922 :     return true;
     718             :   }
     719             : 
     720             :   // Loop over all of our predecessors, merging what we know from them into
     721             :   // result.  If we encounter an unexplored predecessor, we eagerly explore it
     722             :   // in a depth first manner.  In practice, this has the effect of discovering
     723             :   // paths we can't analyze eagerly without spending compile times analyzing
     724             :   // other paths.  This heuristic benefits from the fact that predecessors are
     725             :   // frequently arranged such that dominating ones come first and we quickly
     726             :   // find a path to function entry.  TODO: We should consider explicitly
     727             :   // canonicalizing to make this true rather than relying on this happy
     728             :   // accident.
     729     1257593 :   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     730             :     ValueLatticeElement EdgeResult;
     731     1018342 :     if (!getEdgeValue(Val, *PI, BB, EdgeResult))
     732             :       // Explore that input, then return here
     733             :       return false;
     734             : 
     735      607617 :     Result.mergeIn(EdgeResult, DL);
     736             : 
     737             :     // If we hit overdefined, exit early.  The BlockVals entry is already set
     738             :     // to overdefined.
     739      607617 :     if (Result.isOverdefined()) {
     740             :       LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
     741             :                         << "' - overdefined because of pred (non local).\n");
     742             :       // Before giving up, see if we can prove the pointer non-null local to
     743             :       // this particular block.
     744      232100 :       PointerType *PTy = dyn_cast<PointerType>(Val->getType());
     745      187366 :       if (PTy && isObjectDereferencedInBlock(Val, BB) &&
     746       26187 :           !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) {
     747       78561 :         Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
     748             :       }
     749             : 
     750      232100 :       BBLV = Result;
     751      232100 :       return true;
     752             :     }
     753             :   }
     754             : 
     755             :   // Return the merged value, which is more precise than 'overdefined'.
     756             :   assert(!Result.isOverdefined());
     757      239251 :   BBLV = Result;
     758      239251 :   return true;
     759             : }
     760             : 
     761      196664 : bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV,
     762             :                                                PHINode *PN, BasicBlock *BB) {
     763             :   ValueLatticeElement Result;  // Start Undefined.
     764             : 
     765             :   // Loop over all of our predecessors, merging what we know from them into
     766             :   // result.  See the comment about the chosen traversal order in
     767             :   // solveBlockValueNonLocal; the same reasoning applies here.
     768      308710 :   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     769             :     BasicBlock *PhiBB = PN->getIncomingBlock(i);
     770             :     Value *PhiVal = PN->getIncomingValue(i);
     771             :     ValueLatticeElement EdgeResult;
     772             :     // Note that we can provide PN as the context value to getEdgeValue, even
     773             :     // though the results will be cached, because PN is the value being used as
     774             :     // the cache key in the caller.
     775      302287 :     if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
     776             :       // Explore that input, then return here
     777             :       return false;
     778             : 
     779      261952 :     Result.mergeIn(EdgeResult, DL);
     780             : 
     781             :     // If we hit overdefined, exit early.  The BlockVals entry is already set
     782             :     // to overdefined.
     783      261952 :     if (Result.isOverdefined()) {
     784             :       LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
     785             :                         << "' - overdefined because of pred (local).\n");
     786             : 
     787      149906 :       BBLV = Result;
     788      149906 :       return true;
     789             :     }
     790             :   }
     791             : 
     792             :   // Return the merged value, which is more precise than 'overdefined'.
     793             :   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
     794        6423 :   BBLV = Result;
     795        6423 :   return true;
     796             : }
     797             : 
     798             : static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
     799             :                                                  bool isTrueDest = true);
     800             : 
     801             : // If we can determine a constraint on the value given conditions assumed by
     802             : // the program, intersect those constraints with BBLV
     803           0 : void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
     804             :         Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
     805           0 :   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
     806           0 :   if (!BBI)
     807           0 :     return;
     808             : 
     809           0 :   for (auto &AssumeVH : AC->assumptionsFor(Val)) {
     810           0 :     if (!AssumeVH)
     811           0 :       continue;
     812             :     auto *I = cast<CallInst>(AssumeVH);
     813           0 :     if (!isValidAssumeForContext(I, BBI, DT))
     814           0 :       continue;
     815             : 
     816           0 :     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
     817             :   }
     818             : 
     819             :   // If guards are not used in the module, don't spend time looking for them
     820           0 :   auto *GuardDecl = BBI->getModule()->getFunction(
     821             :           Intrinsic::getName(Intrinsic::experimental_guard));
     822           0 :   if (!GuardDecl || GuardDecl->use_empty())
     823           0 :     return;
     824             : 
     825           0 :   for (Instruction &I : make_range(BBI->getIterator().getReverse(),
     826           0 :                                    BBI->getParent()->rend())) {
     827           0 :     Value *Cond = nullptr;
     828           0 :     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
     829           0 :       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
     830             :   }
     831             : }
     832             : 
     833        4562 : bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
     834             :                                               SelectInst *SI, BasicBlock *BB) {
     835             : 
     836             :   // Recurse on our inputs if needed
     837        3228 :   if (!hasBlockValue(SI->getTrueValue(), BB)) {
     838        1251 :     if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
     839             :       return false;
     840           1 :     BBLV = ValueLatticeElement::getOverdefined();
     841           1 :     return true;
     842             :   }
     843        3311 :   ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
     844             :   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
     845             :   // extra slots in the table if we can.
     846        3311 :   if (TrueVal.isOverdefined()) {
     847         551 :     BBLV = ValueLatticeElement::getOverdefined();
     848         551 :     return true;
     849             :   }
     850             : 
     851        2395 :   if (!hasBlockValue(SI->getFalseValue(), BB)) {
     852        1128 :     if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
     853             :       return false;
     854           0 :     BBLV = ValueLatticeElement::getOverdefined();
     855           0 :     return true;
     856             :   }
     857        1632 :   ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
     858             :   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
     859             :   // extra slots in the table if we can.
     860        1632 :   if (FalseVal.isOverdefined()) {
     861         704 :     BBLV = ValueLatticeElement::getOverdefined();
     862         704 :     return true;
     863             :   }
     864             : 
     865         928 :   if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
     866             :     const ConstantRange &TrueCR = TrueVal.getConstantRange();
     867             :     const ConstantRange &FalseCR = FalseVal.getConstantRange();
     868         657 :     Value *LHS = nullptr;
     869         657 :     Value *RHS = nullptr;
     870         657 :     SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
     871             :     // Is this a min specifically of our two inputs?  (Avoid the risk of
     872             :     // ValueTracking getting smarter looking back past our immediate inputs.)
     873         657 :     if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
     874         157 :         LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
     875             :       ConstantRange ResultCR = [&]() {
     876             :         switch (SPR.Flavor) {
     877             :         default:
     878             :           llvm_unreachable("unexpected minmax type!");
     879             :         case SPF_SMIN:                   /// Signed minimum
     880             :           return TrueCR.smin(FalseCR);
     881             :         case SPF_UMIN:                   /// Unsigned minimum
     882             :           return TrueCR.umin(FalseCR);
     883             :         case SPF_SMAX:                   /// Signed maximum
     884             :           return TrueCR.smax(FalseCR);
     885             :         case SPF_UMAX:                   /// Unsigned maximum
     886             :           return TrueCR.umax(FalseCR);
     887             :         };
     888         102 :       }();
     889         204 :       BBLV = ValueLatticeElement::getRange(ResultCR);
     890             :       return true;
     891             :     }
     892             : 
     893             :     // TODO: ABS, NABS from the SelectPatternResult
     894             :   }
     895             : 
     896             :   // Can we constrain the facts about the true and false values by using the
     897             :   // condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
     898             :   // TODO: We could potentially refine an overdefined true value above.
     899             :   Value *Cond = SI->getCondition();
     900        1652 :   TrueVal = intersect(TrueVal,
     901        2478 :                       getValueFromCondition(SI->getTrueValue(), Cond, true));
     902        1652 :   FalseVal = intersect(FalseVal,
     903        2478 :                        getValueFromCondition(SI->getFalseValue(), Cond, false));
     904             : 
     905             :   // Handle clamp idioms such as:
     906             :   //   %24 = constantrange<0, 17>
     907             :   //   %39 = icmp eq i32 %24, 0
     908             :   //   %40 = add i32 %24, -1
     909             :   //   %siv.next = select i1 %39, i32 16, i32 %40
     910             :   //   %siv.next = constantrange<0, 17> not <-1, 17>
     911             :   // In general, this can handle any clamp idiom which tests the edge
     912             :   // condition via an equality or inequality.
     913             :   if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
     914             :     ICmpInst::Predicate Pred = ICI->getPredicate();
     915             :     Value *A = ICI->getOperand(0);
     916             :     if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
     917             :       auto addConstants = [](ConstantInt *A, ConstantInt *B) {
     918             :         assert(A->getType() == B->getType());
     919             :         return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
     920             :       };
     921             :       // See if either input is A + C2, subject to the constraint from the
     922             :       // condition that A != C when that input is used.  We can assume that
     923             :       // that input doesn't include C + C2.
     924             :       ConstantInt *CIAdded;
     925         423 :       switch (Pred) {
     926             :       default: break;
     927             :       case ICmpInst::ICMP_EQ:
     928         367 :         if (match(SI->getFalseValue(), m_Add(m_Specific(A),
     929         367 :                                              m_ConstantInt(CIAdded)))) {
     930           9 :           auto ResNot = addConstants(CIBase, CIAdded);
     931          18 :           FalseVal = intersect(FalseVal,
     932          18 :                                ValueLatticeElement::getNot(ResNot));
     933             :         }
     934             :         break;
     935             :       case ICmpInst::ICMP_NE:
     936           6 :         if (match(SI->getTrueValue(), m_Add(m_Specific(A),
     937           6 :                                             m_ConstantInt(CIAdded)))) {
     938           0 :           auto ResNot = addConstants(CIBase, CIAdded);
     939           0 :           TrueVal = intersect(TrueVal,
     940           0 :                               ValueLatticeElement::getNot(ResNot));
     941             :         }
     942             :         break;
     943             :       };
     944             :     }
     945             :   }
     946             : 
     947             :   ValueLatticeElement Result;  // Start Undefined.
     948         826 :   Result.mergeIn(TrueVal, DL);
     949         826 :   Result.mergeIn(FalseVal, DL);
     950         826 :   BBLV = Result;
     951             :   return true;
     952             : }
     953             : 
     954        8833 : bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
     955             :                                             CastInst *CI,
     956             :                                             BasicBlock *BB) {
     957        8833 :   if (!CI->getOperand(0)->getType()->isSized()) {
     958             :     // Without knowing how wide the input is, we can't analyze it in any useful
     959             :     // way.
     960           0 :     BBLV = ValueLatticeElement::getOverdefined();
     961           0 :     return true;
     962             :   }
     963             : 
     964             :   // Filter out casts we don't know how to reason about before attempting to
     965             :   // recurse on our operand.  This can cut a long search short if we know we're
     966             :   // not going to be able to get any useful information anways.
     967             :   switch (CI->getOpcode()) {
     968             :   case Instruction::Trunc:
     969             :   case Instruction::SExt:
     970             :   case Instruction::ZExt:
     971             :   case Instruction::BitCast:
     972             :     break;
     973             :   default:
     974             :     // Unhandled instructions are overdefined.
     975             :     LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
     976             :                       << "' - overdefined (unknown cast).\n");
     977        1572 :     BBLV = ValueLatticeElement::getOverdefined();
     978        1572 :     return true;
     979             :   }
     980             : 
     981             :   // Figure out the range of the LHS.  If that fails, we still apply the
     982             :   // transfer rule on the full set since we may be able to locally infer
     983             :   // interesting facts.
     984        7260 :   if (!hasBlockValue(CI->getOperand(0), BB))
     985        3582 :     if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
     986             :       // More work to do before applying this transfer rule.
     987             :       return false;
     988             : 
     989             :   const unsigned OperandBitWidth =
     990        3679 :     DL.getTypeSizeInBits(CI->getOperand(0)->getType());
     991        3679 :   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
     992        3678 :   if (hasBlockValue(CI->getOperand(0), BB)) {
     993        3679 :     ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB);
     994        3679 :     intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
     995             :                                                   CI);
     996        3679 :     if (LHSVal.isConstantRange())
     997             :       LHSRange = LHSVal.getConstantRange();
     998             :   }
     999             : 
    1000        3679 :   const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
    1001             : 
    1002             :   // NOTE: We're currently limited by the set of operations that ConstantRange
    1003             :   // can evaluate symbolically.  Enhancing that set will allows us to analyze
    1004             :   // more definitions.
    1005        7358 :   BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
    1006        3679 :                                                        ResultBitWidth));
    1007             :   return true;
    1008             : }
    1009             : 
    1010       42500 : bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
    1011             :                                                 BinaryOperator *BO,
    1012             :                                                 BasicBlock *BB) {
    1013             : 
    1014             :   assert(BO->getOperand(0)->getType()->isSized() &&
    1015             :          "all operands to binary operators are sized");
    1016             : 
    1017             :   // Filter out operators we don't know how to reason about before attempting to
    1018             :   // recurse on our operand(s).  This can cut a long search short if we know
    1019             :   // we're not going to be able to get any useful information anyways.
    1020             :   switch (BO->getOpcode()) {
    1021             :   case Instruction::Add:
    1022             :   case Instruction::Sub:
    1023             :   case Instruction::Mul:
    1024             :   case Instruction::UDiv:
    1025             :   case Instruction::Shl:
    1026             :   case Instruction::LShr:
    1027             :   case Instruction::AShr:
    1028             :   case Instruction::And:
    1029             :   case Instruction::Or:
    1030             :     // continue into the code below
    1031             :     break;
    1032             :   default:
    1033             :     // Unhandled instructions are overdefined.
    1034             :     LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
    1035             :                       << "' - overdefined (unknown binary operator).\n");
    1036         653 :     BBLV = ValueLatticeElement::getOverdefined();
    1037         653 :     return true;
    1038             :   };
    1039             : 
    1040             :   // Figure out the range of the LHS.  If that fails, use a conservative range,
    1041             :   // but apply the transfer rule anyways.  This lets us pick up facts from
    1042             :   // expressions like "and i32 (call i32 @foo()), 32"
    1043       41828 :   if (!hasBlockValue(BO->getOperand(0), BB))
    1044       19915 :     if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
    1045             :       // More work to do before applying this transfer rule.
    1046             :       return false;
    1047             : 
    1048             :   const unsigned OperandBitWidth =
    1049       21947 :     DL.getTypeSizeInBits(BO->getOperand(0)->getType());
    1050       43894 :   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
    1051       21928 :   if (hasBlockValue(BO->getOperand(0), BB)) {
    1052       21932 :     ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
    1053       21932 :     intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
    1054             :                                                   BO);
    1055       21932 :     if (LHSVal.isConstantRange())
    1056             :       LHSRange = LHSVal.getConstantRange();
    1057             :   }
    1058             : 
    1059             :   ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
    1060       43894 :   ConstantRange RHSRange = ConstantRange(RHS->getValue());
    1061             : 
    1062             :   // NOTE: We're currently limited by the set of operations that ConstantRange
    1063             :   // can evaluate symbolically.  Enhancing that set will allows us to analyze
    1064             :   // more definitions.
    1065             :   Instruction::BinaryOps BinOp = BO->getOpcode();
    1066       43894 :   BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
    1067             :   return true;
    1068             : }
    1069             : 
    1070      712880 : static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
    1071             :                                                      bool isTrueDest) {
    1072             :   Value *LHS = ICI->getOperand(0);
    1073             :   Value *RHS = ICI->getOperand(1);
    1074             :   CmpInst::Predicate Predicate = ICI->getPredicate();
    1075             : 
    1076      712880 :   if (isa<Constant>(RHS)) {
    1077      456339 :     if (ICI->isEquality() && LHS == Val) {
    1078             :       // We know that V has the RHS constant if this is a true SETEQ or
    1079             :       // false SETNE.
    1080       26652 :       if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
    1081             :         return ValueLatticeElement::get(cast<Constant>(RHS));
    1082             :       else
    1083             :         return ValueLatticeElement::getNot(cast<Constant>(RHS));
    1084             :     }
    1085             :   }
    1086             : 
    1087     1372456 :   if (!Val->getType()->isIntegerTy())
    1088             :     return ValueLatticeElement::getOverdefined();
    1089             : 
    1090             :   // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
    1091             :   // range of Val guaranteed by the condition. Recognize comparisons in the from
    1092             :   // of:
    1093             :   //  icmp <pred> Val, ...
    1094             :   //  icmp <pred> (add Val, Offset), ...
    1095             :   // The latter is the range checking idiom that InstCombine produces. Subtract
    1096             :   // the offset from the allowed range for RHS in this case.
    1097             : 
    1098             :   // Val or (add Val, Offset) can be on either hand of the comparison
    1099      257284 :   if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
    1100             :     std::swap(LHS, RHS);
    1101      226249 :     Predicate = CmpInst::getSwappedPredicate(Predicate);
    1102             :   }
    1103             : 
    1104      257284 :   ConstantInt *Offset = nullptr;
    1105      257284 :   if (LHS != Val)
    1106      222697 :     match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
    1107             : 
    1108      257284 :   if (LHS == Val || Offset) {
    1109             :     // Calculate the range of values that are allowed by the comparison
    1110             :     ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
    1111      113316 :                            /*isFullSet=*/true);
    1112             :     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
    1113       21601 :       RHSRange = ConstantRange(CI->getValue());
    1114             :     else if (Instruction *I = dyn_cast<Instruction>(RHS))
    1115       12471 :       if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
    1116           4 :         RHSRange = getConstantRangeFromMetadata(*Ranges);
    1117             : 
    1118             :     // If we're interested in the false dest, invert the condition
    1119             :     CmpInst::Predicate Pred =
    1120       37772 :             isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
    1121             :     ConstantRange TrueValues =
    1122       37772 :             ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
    1123             : 
    1124       37772 :     if (Offset) // Apply the offset from above.
    1125        3185 :       TrueValues = TrueValues.subtract(Offset->getValue());
    1126             : 
    1127       37772 :     return ValueLatticeElement::getRange(std::move(TrueValues));
    1128             :   }
    1129             : 
    1130             :   return ValueLatticeElement::getOverdefined();
    1131             : }
    1132             : 
    1133             : static ValueLatticeElement
    1134             : getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
    1135             :                       DenseMap<Value*, ValueLatticeElement> &Visited);
    1136             : 
    1137             : static ValueLatticeElement
    1138      773134 : getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
    1139             :                           DenseMap<Value*, ValueLatticeElement> &Visited) {
    1140             :   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
    1141      712880 :     return getValueFromICmpCondition(Val, ICI, isTrueDest);
    1142             : 
    1143             :   // Handle conditions in the form of (cond1 && cond2), we know that on the
    1144             :   // true dest path both of the conditions hold. Similarly for conditions of
    1145             :   // the form (cond1 || cond2), we know that on the false dest path neither
    1146             :   // condition holds.
    1147             :   BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
    1148       17668 :   if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
    1149        7347 :              (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
    1150             :     return ValueLatticeElement::getOverdefined();
    1151             : 
    1152             :   // Prevent infinite recursion if Cond references itself as in this example:
    1153             :   //  Cond: "%tmp4 = and i1 %tmp4, undef"
    1154             :   //    BL: "%tmp4 = and i1 %tmp4, undef"
    1155             :   //    BR: "i1 undef"
    1156             :   Value *BL = BO->getOperand(0);
    1157             :   Value *BR = BO->getOperand(1);
    1158        5414 :   if (BL == Cond || BR == Cond)
    1159             :     return ValueLatticeElement::getOverdefined();
    1160             : 
    1161       10824 :   return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
    1162       16236 :                    getValueFromCondition(Val, BR, isTrueDest, Visited));
    1163             : }
    1164             : 
    1165             : static ValueLatticeElement
    1166      773396 : getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
    1167             :                       DenseMap<Value*, ValueLatticeElement> &Visited) {
    1168      773396 :   auto I = Visited.find(Cond);
    1169      773396 :   if (I != Visited.end())
    1170         262 :     return I->second;
    1171             : 
    1172      773134 :   auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
    1173      773134 :   Visited[Cond] = Result;
    1174             :   return Result;
    1175             : }
    1176             : 
    1177      762572 : ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
    1178             :                                           bool isTrueDest) {
    1179             :   assert(Cond && "precondition");
    1180             :   DenseMap<Value*, ValueLatticeElement> Visited;
    1181      762572 :   return getValueFromCondition(Val, Cond, isTrueDest, Visited);
    1182             : }
    1183             : 
    1184             : // Return true if Usr has Op as an operand, otherwise false.
    1185       37768 : static bool usesOperand(User *Usr, Value *Op) {
    1186       37768 :   return find(Usr->operands(), Op) != Usr->op_end();
    1187             : }
    1188             : 
    1189             : // Return true if the instruction type of Val is supported by
    1190             : // constantFoldUser(). Currently CastInst and BinaryOperator only.  Call this
    1191             : // before calling constantFoldUser() to find out if it's even worth attempting
    1192             : // to call it.
    1193             : static bool isOperationFoldable(User *Usr) {
    1194             :   return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
    1195             : }
    1196             : 
    1197             : // Check if Usr can be simplified to an integer constant when the value of one
    1198             : // of its operands Op is an integer constant OpConstVal. If so, return it as an
    1199             : // lattice value range with a single element or otherwise return an overdefined
    1200             : // lattice value.
    1201         294 : static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
    1202             :                                             const APInt &OpConstVal,
    1203             :                                             const DataLayout &DL) {
    1204             :   assert(isOperationFoldable(Usr) && "Precondition");
    1205         294 :   Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
    1206             :   // Check if Usr can be simplified to a constant.
    1207             :   if (auto *CI = dyn_cast<CastInst>(Usr)) {
    1208             :     assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
    1209         436 :     if (auto *C = dyn_cast_or_null<ConstantInt>(
    1210             :             SimplifyCastInst(CI->getOpcode(), OpConst,
    1211             :                              CI->getDestTy(), DL))) {
    1212         218 :       return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
    1213             :     }
    1214             :   } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
    1215             :     bool Op0Match = BO->getOperand(0) == Op;
    1216             :     bool Op1Match = BO->getOperand(1) == Op;
    1217             :     assert((Op0Match || Op1Match) &&
    1218             :            "Operand 0 nor Operand 1 isn't a match");
    1219          76 :     Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
    1220          76 :     Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
    1221         152 :     if (auto *C = dyn_cast_or_null<ConstantInt>(
    1222             :             SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
    1223          20 :       return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
    1224             :     }
    1225             :   }
    1226             :   return ValueLatticeElement::getOverdefined();
    1227             : }
    1228             : 
    1229             : /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
    1230             : /// Val is not constrained on the edge.  Result is unspecified if return value
    1231             : /// is false.
    1232     1700716 : static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
    1233             :                               BasicBlock *BBTo, ValueLatticeElement &Result) {
    1234             :   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
    1235             :   // know that v != 0.
    1236             :   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
    1237             :     // If this is a conditional branch and only one successor goes to BBTo, then
    1238             :     // we may be able to infer something from the condition.
    1239     2091861 :     if (BI->isConditional() &&
    1240             :         BI->getSuccessor(0) != BI->getSuccessor(1)) {
    1241      695041 :       bool isTrueDest = BI->getSuccessor(0) == BBTo;
    1242             :       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
    1243             :              "BBTo isn't a successor of BBFrom");
    1244             :       Value *Condition = BI->getCondition();
    1245             : 
    1246             :       // If V is the condition of the branch itself, then we know exactly what
    1247             :       // it is.
    1248      695041 :       if (Condition == Val) {
    1249        2757 :         Result = ValueLatticeElement::get(ConstantInt::get(
    1250        2757 :                               Type::getInt1Ty(Val->getContext()), isTrueDest));
    1251        2757 :         return true;
    1252             :       }
    1253             : 
    1254             :       // If the condition of the branch is an equality comparison, we may be
    1255             :       // able to infer the value.
    1256      692284 :       Result = getValueFromCondition(Val, Condition, isTrueDest);
    1257      692284 :       if (!Result.isOverdefined())
    1258             :         return true;
    1259             : 
    1260             :       if (User *Usr = dyn_cast<User>(Val)) {
    1261             :         assert(Result.isOverdefined() && "Result isn't overdefined");
    1262             :         // Check with isOperationFoldable() first to avoid linearly iterating
    1263             :         // over the operands unnecessarily which can be expensive for
    1264             :         // instructions with many operands.
    1265     1058150 :         if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
    1266       36502 :           const DataLayout &DL = BBTo->getModule()->getDataLayout();
    1267       36502 :           if (usesOperand(Usr, Condition)) {
    1268             :             // If Val has Condition as an operand and Val can be folded into a
    1269             :             // constant with either Condition == true or Condition == false,
    1270             :             // propagate the constant.
    1271             :             // eg.
    1272             :             //   ; %Val is true on the edge to %then.
    1273             :             //   %Val = and i1 %Condition, true.
    1274             :             //   br %Condition, label %then, label %else
    1275          16 :             APInt ConditionVal(1, isTrueDest ? 1 : 0);
    1276          32 :             Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
    1277             :           } else {
    1278             :             // If one of Val's operand has an inferred value, we may be able to
    1279             :             // infer the value of Val.
    1280             :             // eg.
    1281             :             //    ; %Val is 94 on the edge to %then.
    1282             :             //    %Val = add i8 %Op, 1
    1283             :             //    %Condition = icmp eq i8 %Op, 93
    1284             :             //    br i1 %Condition, label %then, label %else
    1285      104969 :             for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
    1286             :               Value *Op = Usr->getOperand(i);
    1287             :               ValueLatticeElement OpLatticeVal =
    1288       68551 :                   getValueFromCondition(Op, Condition, isTrueDest);
    1289       68551 :               if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
    1290         136 :                 Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
    1291             :                 break;
    1292             :               }
    1293             :             }
    1294             :           }
    1295             :         }
    1296             :       }
    1297      630078 :       if (!Result.isOverdefined())
    1298             :         return true;
    1299             :     }
    1300             :   }
    1301             : 
    1302             :   // If the edge was formed by a switch on the value, then we may know exactly
    1303             :   // what it is.
    1304             :   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
    1305             :     Value *Condition = SI->getCondition();
    1306       33374 :     if (!isa<IntegerType>(Val->getType()))
    1307             :       return false;
    1308             :     bool ValUsesConditionAndMayBeFoldable = false;
    1309        4789 :     if (Condition != Val) {
    1310             :       // Check if Val has Condition as an operand.
    1311             :       if (User *Usr = dyn_cast<User>(Val))
    1312        1266 :         ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
    1313        1266 :             usesOperand(Usr, Condition);
    1314        3883 :       if (!ValUsesConditionAndMayBeFoldable)
    1315        4081 :         return false;
    1316             :     }
    1317             :     assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
    1318             :            "Condition != Val nor Val doesn't use Condition");
    1319             : 
    1320         708 :     bool DefaultCase = SI->getDefaultDest() == BBTo;
    1321         708 :     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
    1322        1416 :     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
    1323             : 
    1324        3717 :     for (auto Case : SI->cases()) {
    1325             :       APInt CaseValue = Case.getCaseValue()->getValue();
    1326        6018 :       ConstantRange EdgeVal(CaseValue);
    1327        3009 :       if (ValUsesConditionAndMayBeFoldable) {
    1328             :         User *Usr = cast<User>(Val);
    1329         210 :         const DataLayout &DL = BBTo->getModule()->getDataLayout();
    1330             :         ValueLatticeElement EdgeLatticeVal =
    1331         210 :             constantFoldUser(Usr, Condition, CaseValue, DL);
    1332         210 :         if (EdgeLatticeVal.isOverdefined())
    1333             :           return false;
    1334             :         EdgeVal = EdgeLatticeVal.getConstantRange();
    1335             :       }
    1336        3009 :       if (DefaultCase) {
    1337             :         // It is possible that the default destination is the destination of
    1338             :         // some cases. We cannot perform difference for those cases.
    1339             :         // We know Condition != CaseValue in BBTo.  In some cases we can use
    1340             :         // this to infer Val == f(Condition) is != f(CaseValue).  For now, we
    1341             :         // only do this when f is identity (i.e. Val == Condition), but we
    1342             :         // should be able to do this for any injective f.
    1343        1839 :         if (Case.getCaseSuccessor() != BBTo && Condition == Val)
    1344        1605 :           EdgesVals = EdgesVals.difference(EdgeVal);
    1345        1170 :       } else if (Case.getCaseSuccessor() == BBTo)
    1346         517 :         EdgesVals = EdgesVals.unionWith(EdgeVal);
    1347             :     }
    1348        1416 :     Result = ValueLatticeElement::getRange(std::move(EdgesVals));
    1349         708 :     return true;
    1350             :   }
    1351             :   return false;
    1352             : }
    1353             : 
    1354             : /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
    1355             : /// the basic block if the edge does not constrain Val.
    1356     1889054 : bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
    1357             :                                      BasicBlock *BBTo,
    1358             :                                      ValueLatticeElement &Result,
    1359             :                                      Instruction *CxtI) {
    1360             :   // If already a constant, there is nothing to compute.
    1361             :   if (Constant *VC = dyn_cast<Constant>(Val)) {
    1362      188338 :     Result = ValueLatticeElement::get(VC);
    1363      188338 :     return true;
    1364             :   }
    1365             : 
    1366             :   ValueLatticeElement LocalResult;
    1367     1700716 :   if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
    1368             :     // If we couldn't constrain the value on the edge, LocalResult doesn't
    1369             :     // provide any information.
    1370     3270034 :     LocalResult = ValueLatticeElement::getOverdefined();
    1371             : 
    1372             :   if (hasSingleValue(LocalResult)) {
    1373             :     // Can't get any more precise here
    1374        5474 :     Result = LocalResult;
    1375        5474 :     return true;
    1376             :   }
    1377             : 
    1378     1695242 :   if (!hasBlockValue(Val, BBFrom)) {
    1379      687531 :     if (pushBlockValue(std::make_pair(BBFrom, Val)))
    1380             :       return false;
    1381             :     // No new information.
    1382       19741 :     Result = LocalResult;
    1383       19741 :     return true;
    1384             :   }
    1385             : 
    1386             :   // Try to intersect ranges of the BB and the constraint on the edge.
    1387     1007711 :   ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
    1388     1007711 :   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
    1389             :                                                 BBFrom->getTerminator());
    1390             :   // We can use the context instruction (generically the ultimate instruction
    1391             :   // the calling pass is trying to simplify) here, even though the result of
    1392             :   // this function is generally cached when called from the solve* functions
    1393             :   // (and that cached result might be used with queries using a different
    1394             :   // context instruction), because when this function is called from the solve*
    1395             :   // functions, the context instruction is not provided. When called from
    1396             :   // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
    1397             :   // but then the result is not cached.
    1398     1007711 :   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
    1399             : 
    1400     2015422 :   Result = intersect(LocalResult, InBlock);
    1401             :   return true;
    1402             : }
    1403             : 
    1404      615476 : ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
    1405             :                                                        Instruction *CxtI) {
    1406             :   LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
    1407             :                     << BB->getName() << "'\n");
    1408             : 
    1409             :   assert(BlockValueStack.empty() && BlockValueSet.empty());
    1410      614540 :   if (!hasBlockValue(V, BB)) {
    1411      453808 :     pushBlockValue(std::make_pair(BB, V));
    1412      453808 :     solve();
    1413             :   }
    1414      615476 :   ValueLatticeElement Result = getBlockValue(V, BB);
    1415      615476 :   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
    1416             : 
    1417             :   LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
    1418      615476 :   return Result;
    1419             : }
    1420             : 
    1421      274779 : ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
    1422             :   LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
    1423             :                     << "'\n");
    1424             : 
    1425             :   if (auto *C = dyn_cast<Constant>(V))
    1426             :     return ValueLatticeElement::get(C);
    1427             : 
    1428             :   ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
    1429             :   if (auto *I = dyn_cast<Instruction>(V))
    1430      463782 :     Result = getFromRangeMetadata(I);
    1431      274690 :   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
    1432             : 
    1433             :   LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
    1434             :   return Result;
    1435             : }
    1436             : 
    1437      351695 : ValueLatticeElement LazyValueInfoImpl::
    1438             : getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
    1439             :                Instruction *CxtI) {
    1440             :   LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
    1441             :                     << FromBB->getName() << "' to '" << ToBB->getName()
    1442             :                     << "'\n");
    1443             : 
    1444             :   ValueLatticeElement Result;
    1445      351695 :   if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
    1446      216730 :     solve();
    1447      216730 :     bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
    1448             :     (void)WasFastQuery;
    1449             :     assert(WasFastQuery && "More work to do after problem solved?");
    1450             :   }
    1451             : 
    1452             :   LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
    1453      351695 :   return Result;
    1454             : }
    1455             : 
    1456           0 : void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
    1457             :                                    BasicBlock *NewSucc) {
    1458        2525 :   TheCache.threadEdgeImpl(OldSucc, NewSucc);
    1459           0 : }
    1460             : 
    1461             : //===----------------------------------------------------------------------===//
    1462             : //                            LazyValueInfo Impl
    1463             : //===----------------------------------------------------------------------===//
    1464             : 
    1465             : /// This lazily constructs the LazyValueInfoImpl.
    1466     1685946 : static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
    1467             :                                   const DataLayout *DL,
    1468             :                                   DominatorTree *DT = nullptr) {
    1469     1685946 :   if (!PImpl) {
    1470             :     assert(DL && "getCache() called with a null DataLayout");
    1471      151634 :     PImpl = new LazyValueInfoImpl(AC, *DL, DT);
    1472             :   }
    1473     1685946 :   return *static_cast<LazyValueInfoImpl*>(PImpl);
    1474             : }
    1475             : 
    1476       88362 : bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
    1477       88362 :   Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
    1478       88362 :   const DataLayout &DL = F.getParent()->getDataLayout();
    1479             : 
    1480             :   DominatorTreeWrapperPass *DTWP =
    1481       88362 :       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
    1482       88362 :   Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
    1483       88362 :   Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
    1484             : 
    1485       88362 :   if (Info.PImpl)
    1486           0 :     getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
    1487             : 
    1488             :   // Fully lazy.
    1489       88362 :   return false;
    1490             : }
    1491             : 
    1492        3476 : void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
    1493             :   AU.setPreservesAll();
    1494             :   AU.addRequired<AssumptionCacheTracker>();
    1495             :   AU.addRequired<TargetLibraryInfoWrapperPass>();
    1496        3476 : }
    1497             : 
    1498      175486 : LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
    1499             : 
    1500        4243 : LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
    1501             : 
    1502       92604 : void LazyValueInfo::releaseMemory() {
    1503             :   // If the cache was allocated, free it.
    1504       92604 :   if (PImpl) {
    1505       75817 :     delete &getImpl(PImpl, AC, nullptr);
    1506       75817 :     PImpl = nullptr;
    1507             :   }
    1508       92604 : }
    1509             : 
    1510         201 : bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
    1511             :                                FunctionAnalysisManager::Invalidator &Inv) {
    1512             :   // We need to invalidate if we have either failed to preserve this analyses
    1513             :   // result directly or if any of its dependencies have been invalidated.
    1514             :   auto PAC = PA.getChecker<LazyValueAnalysis>();
    1515         201 :   if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
    1516          50 :       (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
    1517         176 :     return true;
    1518             : 
    1519             :   return false;
    1520             : }
    1521             : 
    1522       88362 : void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
    1523             : 
    1524         261 : LazyValueInfo LazyValueAnalysis::run(Function &F,
    1525             :                                      FunctionAnalysisManager &FAM) {
    1526             :   auto &AC = FAM.getResult<AssumptionAnalysis>(F);
    1527             :   auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
    1528             :   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
    1529             : 
    1530         261 :   return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
    1531             : }
    1532             : 
    1533             : /// Returns true if we can statically tell that this value will never be a
    1534             : /// "useful" constant.  In practice, this means we've got something like an
    1535             : /// alloca or a malloc call for which a comparison against a constant can
    1536             : /// only be guarding dead code.  Note that we are potentially giving up some
    1537             : /// precision in dead code (a constant result) in favour of avoiding a
    1538             : /// expensive search for a easily answered common query.
    1539             : static bool isKnownNonConstant(Value *V) {
    1540             :   V = V->stripPointerCasts();
    1541             :   // The return val of alloc cannot be a Constant.
    1542             :   if (isa<AllocaInst>(V))
    1543             :     return true;
    1544             :   return false;
    1545             : }
    1546             : 
    1547      685434 : Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
    1548             :                                      Instruction *CxtI) {
    1549             :   // Bail out early if V is known not to be a Constant.
    1550             :   if (isKnownNonConstant(V))
    1551             :     return nullptr;
    1552             : 
    1553      611769 :   const DataLayout &DL = BB->getModule()->getDataLayout();
    1554             :   ValueLatticeElement Result =
    1555      611769 :       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
    1556             : 
    1557      611769 :   if (Result.isConstant())
    1558           1 :     return Result.getConstant();
    1559      611768 :   if (Result.isConstantRange()) {
    1560             :     const ConstantRange &CR = Result.getConstantRange();
    1561       10812 :     if (const APInt *SingleVal = CR.getSingleElement())
    1562          12 :       return ConstantInt::get(V->getContext(), *SingleVal);
    1563             :   }
    1564             :   return nullptr;
    1565             : }
    1566             : 
    1567        3596 : ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
    1568             :                                               Instruction *CxtI) {
    1569             :   assert(V->getType()->isIntegerTy());
    1570        3596 :   unsigned Width = V->getType()->getIntegerBitWidth();
    1571        3596 :   const DataLayout &DL = BB->getModule()->getDataLayout();
    1572             :   ValueLatticeElement Result =
    1573        3596 :       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
    1574        3596 :   if (Result.isUndefined())
    1575           0 :     return ConstantRange(Width, /*isFullSet=*/false);
    1576        3596 :   if (Result.isConstantRange())
    1577        2355 :     return Result.getConstantRange();
    1578             :   // We represent ConstantInt constants as constant ranges but other kinds
    1579             :   // of integer constants, i.e. ConstantExpr will be tagged as constants
    1580             :   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
    1581             :          "ConstantInt value must be represented as constantrange");
    1582        1241 :   return ConstantRange(Width, /*isFullSet=*/true);
    1583             : }
    1584             : 
    1585             : /// Determine whether the specified value is known to be a
    1586             : /// constant on the specified edge. Return null if not.
    1587      250900 : Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
    1588             :                                            BasicBlock *ToBB,
    1589             :                                            Instruction *CxtI) {
    1590      250900 :   const DataLayout &DL = FromBB->getModule()->getDataLayout();
    1591             :   ValueLatticeElement Result =
    1592      250900 :       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
    1593             : 
    1594      250900 :   if (Result.isConstant())
    1595         277 :     return Result.getConstant();
    1596      250623 :   if (Result.isConstantRange()) {
    1597             :     const ConstantRange &CR = Result.getConstantRange();
    1598       29282 :     if (const APInt *SingleVal = CR.getSingleElement())
    1599        1588 :       return ConstantInt::get(V->getContext(), *SingleVal);
    1600             :   }
    1601             :   return nullptr;
    1602             : }
    1603             : 
    1604        3436 : ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
    1605             :                                                     BasicBlock *FromBB,
    1606             :                                                     BasicBlock *ToBB,
    1607             :                                                     Instruction *CxtI) {
    1608        3436 :   unsigned Width = V->getType()->getIntegerBitWidth();
    1609        3436 :   const DataLayout &DL = FromBB->getModule()->getDataLayout();
    1610             :   ValueLatticeElement Result =
    1611        3436 :       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
    1612             : 
    1613        3436 :   if (Result.isUndefined())
    1614           0 :     return ConstantRange(Width, /*isFullSet=*/false);
    1615        3436 :   if (Result.isConstantRange())
    1616        2534 :     return Result.getConstantRange();
    1617             :   // We represent ConstantInt constants as constant ranges but other kinds
    1618             :   // of integer constants, i.e. ConstantExpr will be tagged as constants
    1619             :   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
    1620             :          "ConstantInt value must be represented as constantrange");
    1621         902 :   return ConstantRange(Width, /*isFullSet=*/true);
    1622             : }
    1623             : 
    1624             : static LazyValueInfo::Tristate
    1625      372138 : getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
    1626             :                    const DataLayout &DL, TargetLibraryInfo *TLI) {
    1627             :   // If we know the value is a constant, evaluate the conditional.
    1628             :   Constant *Res = nullptr;
    1629      372138 :   if (Val.isConstant()) {
    1630        4560 :     Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
    1631             :     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
    1632        4559 :       return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
    1633             :     return LazyValueInfo::Unknown;
    1634             :   }
    1635             : 
    1636      367578 :   if (Val.isConstantRange()) {
    1637             :     ConstantInt *CI = dyn_cast<ConstantInt>(C);
    1638             :     if (!CI) return LazyValueInfo::Unknown;
    1639             : 
    1640             :     const ConstantRange &CR = Val.getConstantRange();
    1641       38407 :     if (Pred == ICmpInst::ICMP_EQ) {
    1642       21026 :       if (!CR.contains(CI->getValue()))
    1643             :         return LazyValueInfo::False;
    1644             : 
    1645       17453 :       if (CR.isSingleElement())
    1646             :         return LazyValueInfo::True;
    1647       17381 :     } else if (Pred == ICmpInst::ICMP_NE) {
    1648        4556 :       if (!CR.contains(CI->getValue()))
    1649             :         return LazyValueInfo::True;
    1650             : 
    1651        4497 :       if (CR.isSingleElement())
    1652             :         return LazyValueInfo::False;
    1653             :     } else {
    1654             :       // Handle more complex predicates.
    1655             :       ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
    1656       24424 :           (ICmpInst::Predicate)Pred, CI->getValue());
    1657       12825 :       if (TrueValues.contains(CR))
    1658        1226 :         return LazyValueInfo::True;
    1659       12075 :       if (TrueValues.inverse().contains(CR))
    1660             :         return LazyValueInfo::False;
    1661             :     }
    1662       32293 :     return LazyValueInfo::Unknown;
    1663             :   }
    1664             : 
    1665      329163 :   if (Val.isNotConstant()) {
    1666             :     // If this is an equality comparison, we can try to fold it knowing that
    1667             :     // "V != C1".
    1668        4141 :     if (Pred == ICmpInst::ICMP_EQ) {
    1669             :       // !C1 == C -> false iff C1 == C.
    1670        4007 :       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
    1671             :                                             Val.getNotConstant(), C, DL,
    1672             :                                             TLI);
    1673        4007 :       if (Res->isNullValue())
    1674             :         return LazyValueInfo::False;
    1675         134 :     } else if (Pred == ICmpInst::ICMP_NE) {
    1676             :       // !C1 != C -> true iff C1 == C.
    1677          56 :       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
    1678             :                                             Val.getNotConstant(), C, DL,
    1679             :                                             TLI);
    1680          56 :       if (Res->isNullValue())
    1681             :         return LazyValueInfo::True;
    1682             :     }
    1683         135 :     return LazyValueInfo::Unknown;
    1684             :   }
    1685             : 
    1686             :   return LazyValueInfo::Unknown;
    1687             : }
    1688             : 
    1689             : /// Determine whether the specified value comparison with a constant is known to
    1690             : /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
    1691             : LazyValueInfo::Tristate
    1692       97359 : LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
    1693             :                                   BasicBlock *FromBB, BasicBlock *ToBB,
    1694             :                                   Instruction *CxtI) {
    1695       97359 :   const DataLayout &DL = FromBB->getModule()->getDataLayout();
    1696             :   ValueLatticeElement Result =
    1697       97359 :       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
    1698             : 
    1699       97359 :   return getPredicateResult(Pred, C, Result, DL, TLI);
    1700             : }
    1701             : 
    1702             : LazyValueInfo::Tristate
    1703      341646 : LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
    1704             :                               Instruction *CxtI) {
    1705             :   // Is or is not NonNull are common predicates being queried. If
    1706             :   // isKnownNonZero can tell us the result of the predicate, we can
    1707             :   // return it quickly. But this is only a fastpath, and falling
    1708             :   // through would still be correct.
    1709      341646 :   const DataLayout &DL = CxtI->getModule()->getDataLayout();
    1710      934619 :   if (V->getType()->isPointerTy() && C->isNullValue() &&
    1711      251327 :       isKnownNonZero(V->stripPointerCasts(), DL)) {
    1712       66867 :     if (Pred == ICmpInst::ICMP_EQ)
    1713             :       return LazyValueInfo::False;
    1714           2 :     else if (Pred == ICmpInst::ICMP_NE)
    1715             :       return LazyValueInfo::True;
    1716             :   }
    1717      274779 :   ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
    1718      274779 :   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
    1719      274779 :   if (Ret != Unknown)
    1720             :     return Ret;
    1721             : 
    1722             :   // Note: The following bit of code is somewhat distinct from the rest of LVI;
    1723             :   // LVI as a whole tries to compute a lattice value which is conservatively
    1724             :   // correct at a given location.  In this case, we have a predicate which we
    1725             :   // weren't able to prove about the merged result, and we're pushing that
    1726             :   // predicate back along each incoming edge to see if we can prove it
    1727             :   // separately for each input.  As a motivating example, consider:
    1728             :   // bb1:
    1729             :   //   %v1 = ... ; constantrange<1, 5>
    1730             :   //   br label %merge
    1731             :   // bb2:
    1732             :   //   %v2 = ... ; constantrange<10, 20>
    1733             :   //   br label %merge
    1734             :   // merge:
    1735             :   //   %phi = phi [%v1, %v2] ; constantrange<1,20>
    1736             :   //   %pred = icmp eq i32 %phi, 8
    1737             :   // We can't tell from the lattice value for '%phi' that '%pred' is false
    1738             :   // along each path, but by checking the predicate over each input separately,
    1739             :   // we can.
    1740             :   // We limit the search to one step backwards from the current BB and value.
    1741             :   // We could consider extending this to search further backwards through the
    1742             :   // CFG and/or value graph, but there are non-obvious compile time vs quality
    1743             :   // tradeoffs.
    1744      274662 :   if (CxtI) {
    1745      274662 :     BasicBlock *BB = CxtI->getParent();
    1746             : 
    1747             :     // Function entry or an unreachable block.  Bail to avoid confusing
    1748             :     // analysis below.
    1749      274662 :     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
    1750      274662 :     if (PI == PE)
    1751       51357 :       return Unknown;
    1752             : 
    1753             :     // If V is a PHI node in the same block as the context, we need to ask
    1754             :     // questions about the predicate as applied to the incoming value along
    1755             :     // each edge. This is useful for eliminating cases where the predicate is
    1756             :     // known along all incoming edges.
    1757             :     if (auto *PHI = dyn_cast<PHINode>(V))
    1758       17836 :       if (PHI->getParent() == BB) {
    1759             :         Tristate Baseline = Unknown;
    1760       17864 :         for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
    1761             :           Value *Incoming = PHI->getIncomingValue(i);
    1762             :           BasicBlock *PredBB = PHI->getIncomingBlock(i);
    1763             :           // Note that PredBB may be BB itself.
    1764       17603 :           Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
    1765             :                                                CxtI);
    1766             : 
    1767             :           // Keep going as long as we've seen a consistent known result for
    1768             :           // all inputs.
    1769       17603 :           Baseline = (i == 0) ? Result /* First iteration */
    1770        6093 :             : (Baseline == Result ? Baseline : Unknown); /* All others */
    1771       12002 :           if (Baseline == Unknown)
    1772             :             break;
    1773             :         }
    1774       11510 :         if (Baseline != Unknown)
    1775             :           return Baseline;
    1776             :       }
    1777             : 
    1778             :     // For a comparison where the V is outside this block, it's possible
    1779             :     // that we've branched on it before. Look to see if the value is known
    1780             :     // on all incoming edges.
    1781      226267 :     if (!isa<Instruction>(V) ||
    1782      206732 :         cast<Instruction>(V)->getParent() != BB) {
    1783             :       // For predecessor edge, determine if the comparison is true or false
    1784             :       // on that edge. If they're all true or all false, we can conclude
    1785             :       // the value of the comparison in this block.
    1786       50696 :       Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
    1787       50696 :       if (Baseline != Unknown) {
    1788             :         // Check that all remaining incoming values match the first one.
    1789        4777 :         while (++PI != PE) {
    1790        1815 :           Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
    1791        1815 :           if (Ret != Baseline) break;
    1792             :         }
    1793             :         // If we terminated early, then one of the values didn't match.
    1794        4090 :         if (PI == PE) {
    1795             :           return Baseline;
    1796             :         }
    1797             :       }
    1798             :     }
    1799             :   }
    1800             :   return Unknown;
    1801             : }
    1802             : 
    1803        2531 : void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
    1804             :                                BasicBlock *NewSucc) {
    1805        2531 :   if (PImpl) {
    1806        2525 :     const DataLayout &DL = PredBB->getModule()->getDataLayout();
    1807        2525 :     getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
    1808             :   }
    1809        2531 : }
    1810             : 
    1811       36487 : void LazyValueInfo::eraseBlock(BasicBlock *BB) {
    1812       36487 :   if (PImpl) {
    1813       30650 :     const DataLayout &DL = BB->getModule()->getDataLayout();
    1814       30650 :     getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
    1815             :   }
    1816       36487 : }
    1817             : 
    1818             : 
    1819           4 : void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
    1820           4 :   if (PImpl) {
    1821           4 :     getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
    1822             :   }
    1823           4 : }
    1824             : 
    1825      204233 : void LazyValueInfo::disableDT() {
    1826      204233 :   if (PImpl)
    1827      203820 :     getImpl(PImpl, AC, DL, DT).disableDT();
    1828      204233 : }
    1829             : 
    1830      219783 : void LazyValueInfo::enableDT() {
    1831      219783 :   if (PImpl)
    1832      131292 :     getImpl(PImpl, AC, DL, DT).enableDT();
    1833      219783 : }
    1834             : 
    1835             : // Print the LVI for the function arguments at the start of each basic block.
    1836          16 : void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
    1837             :     const BasicBlock *BB, formatted_raw_ostream &OS) {
    1838             :   // Find if there are latticevalues defined for arguments of the function.
    1839          16 :   auto *F = BB->getParent();
    1840          53 :   for (auto &Arg : F->args()) {
    1841          37 :     ValueLatticeElement Result = LVIImpl->getValueInBlock(
    1842          37 :         const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
    1843          37 :     if (Result.isUndefined())
    1844             :       continue;
    1845          74 :     OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
    1846             :   }
    1847          16 : }
    1848             : 
    1849             : // This function prints the LVI analysis for the instruction I at the beginning
    1850             : // of various basic blocks. It relies on calculated values that are stored in
    1851             : // the LazyValueInfoCache, and in the absence of cached values, recalculate the
    1852             : // LazyValueInfo for `I`, and print that info.
    1853          43 : void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
    1854             :     const Instruction *I, formatted_raw_ostream &OS) {
    1855             : 
    1856          43 :   auto *ParentBB = I->getParent();
    1857             :   SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
    1858             :   // We can generate (solve) LVI values only for blocks that are dominated by
    1859             :   // the I's parent. However, to avoid generating LVI for all dominating blocks,
    1860             :   // that contain redundant/uninteresting information, we print LVI for
    1861             :   // blocks that may use this LVI information (such as immediate successor
    1862             :   // blocks, and blocks that contain uses of `I`).
    1863             :   auto printResult = [&](const BasicBlock *BB) {
    1864             :     if (!BlocksContainingLVI.insert(BB).second)
    1865             :       return;
    1866             :     ValueLatticeElement Result = LVIImpl->getValueInBlock(
    1867             :         const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
    1868             :       OS << "; LatticeVal for: '" << *I << "' in BB: '";
    1869             :       BB->printAsOperand(OS, false);
    1870             :       OS << "' is: " << Result << "\n";
    1871          43 :   };
    1872             : 
    1873          43 :   printResult(ParentBB);
    1874             :   // Print the LVI analysis results for the immediate successor blocks, that
    1875             :   // are dominated by `ParentBB`.
    1876         160 :   for (auto *BBSucc : successors(ParentBB))
    1877          74 :     if (DT.dominates(ParentBB, BBSucc))
    1878          39 :       printResult(BBSucc);
    1879             : 
    1880             :   // Print LVI in blocks where `I` is used.
    1881          69 :   for (auto *U : I->users())
    1882             :     if (auto *UseI = dyn_cast<Instruction>(U))
    1883          26 :       if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
    1884          24 :         printResult(UseI->getParent());
    1885             : 
    1886          43 : }
    1887             : 
    1888             : namespace {
    1889             : // Printer class for LazyValueInfo results.
    1890             : class LazyValueInfoPrinter : public FunctionPass {
    1891             : public:
    1892             :   static char ID; // Pass identification, replacement for typeid
    1893           0 :   LazyValueInfoPrinter() : FunctionPass(ID) {
    1894           0 :     initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
    1895             :   }
    1896             : 
    1897           0 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
    1898             :     AU.setPreservesAll();
    1899             :     AU.addRequired<LazyValueInfoWrapperPass>();
    1900             :     AU.addRequired<DominatorTreeWrapperPass>();
    1901           0 :   }
    1902             : 
    1903             :   // Get the mandatory dominator tree analysis and pass this in to the
    1904             :   // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
    1905           0 :   bool runOnFunction(Function &F) override {
    1906           0 :     dbgs() << "LVI for function '" << F.getName() << "':\n";
    1907           0 :     auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
    1908           0 :     auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    1909           0 :     LVI.printLVI(F, DTree, dbgs());
    1910           0 :     return false;
    1911             :   }
    1912             : };
    1913             : }
    1914             : 
    1915             : char LazyValueInfoPrinter::ID = 0;
    1916       10756 : INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
    1917             :                 "Lazy Value Info Printer Pass", false, false)
    1918       10756 : INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
    1919       21512 : INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
    1920             :                 "Lazy Value Info Printer Pass", false, false)

Generated by: LCOV version 1.13