LCOV - code coverage report
Current view: top level - lib/Analysis - LazyValueInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 733 781 93.9 %
Date: 2017-09-14 15:23:50 Functions: 79 87 90.8 %
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/IR/AssemblyAnnotationWriter.h"
      24             : #include "llvm/IR/CFG.h"
      25             : #include "llvm/IR/ConstantRange.h"
      26             : #include "llvm/IR/Constants.h"
      27             : #include "llvm/IR/DataLayout.h"
      28             : #include "llvm/IR/Dominators.h"
      29             : #include "llvm/IR/Instructions.h"
      30             : #include "llvm/IR/IntrinsicInst.h"
      31             : #include "llvm/IR/Intrinsics.h"
      32             : #include "llvm/IR/LLVMContext.h"
      33             : #include "llvm/IR/PatternMatch.h"
      34             : #include "llvm/IR/ValueHandle.h"
      35             : #include "llvm/Support/Debug.h"
      36             : #include "llvm/Support/FormattedStream.h"
      37             : #include "llvm/Support/raw_ostream.h"
      38             : #include <map>
      39             : #include <stack>
      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       26586 : INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
      51             :                 "Lazy Value Information Analysis", false, true)
      52       26586 : INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
      53       26586 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
      54      278994 : 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             : //===----------------------------------------------------------------------===//
      64             : //                               LVILatticeVal
      65             : //===----------------------------------------------------------------------===//
      66             : 
      67             : /// This is the information tracked by LazyValueInfo for each value.
      68             : ///
      69             : /// FIXME: This is basically just for bringup, this can be made a lot more rich
      70             : /// in the future.
      71             : ///
      72             : namespace {
      73    16402918 : class LVILatticeVal {
      74             :   enum LatticeValueTy {
      75             :     /// This Value has no known value yet.  As a result, this implies the
      76             :     /// producing instruction is dead.  Caution: We use this as the starting
      77             :     /// state in our local meet rules.  In this usage, it's taken to mean
      78             :     /// "nothing known yet".
      79             :     undefined,
      80             : 
      81             :     /// This Value has a specific constant value.  (For constant integers,
      82             :     /// constantrange is used instead.  Integer typed constantexprs can appear
      83             :     /// as constant.) 
      84             :     constant,
      85             : 
      86             :     /// This Value is known to not have the specified value.  (For constant
      87             :     /// integers, constantrange is used instead.  As above, integer typed
      88             :     /// constantexprs can appear here.)
      89             :     notconstant,
      90             : 
      91             :     /// The Value falls within this range. (Used only for integer typed values.)
      92             :     constantrange,
      93             : 
      94             :     /// We can not precisely model the dynamic values this value might take.
      95             :     overdefined
      96             :   };
      97             : 
      98             :   /// Val: This stores the current lattice value along with the Constant* for
      99             :   /// the constant if this is a 'constant' or 'notconstant' value.
     100             :   LatticeValueTy Tag;
     101             :   Constant *Val;
     102             :   ConstantRange Range;
     103             : 
     104             : public:
     105     7576204 :   LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
     106             : 
     107       19779 :   static LVILatticeVal get(Constant *C) {
     108       19779 :     LVILatticeVal Res;
     109       39558 :     if (!isa<UndefValue>(C))
     110       19735 :       Res.markConstant(C);
     111       19779 :     return Res;
     112             :   }
     113      149025 :   static LVILatticeVal getNot(Constant *C) {
     114      149025 :     LVILatticeVal Res;
     115      298050 :     if (!isa<UndefValue>(C))
     116      149025 :       Res.markNotConstant(C);
     117      149025 :     return Res;
     118             :   }
     119       61257 :   static LVILatticeVal getRange(ConstantRange CR) {
     120       61257 :     LVILatticeVal Res;
     121      122514 :     Res.markConstantRange(std::move(CR));
     122       61257 :     return Res;
     123             :   }
     124             :   static LVILatticeVal getOverdefined() {
     125     2593053 :     LVILatticeVal Res;
     126     1258138 :     Res.markOverdefined();
     127             :     return Res;
     128             :   }
     129             : 
     130             :   bool isUndefined() const     { return Tag == undefined; }
     131             :   bool isConstant() const      { return Tag == constant; }
     132             :   bool isNotConstant() const   { return Tag == notconstant; }
     133             :   bool isConstantRange() const { return Tag == constantrange; }
     134             :   bool isOverdefined() const   { return Tag == overdefined; }
     135             : 
     136             :   Constant *getConstant() const {
     137             :     assert(isConstant() && "Cannot get the constant of a non-constant!");
     138             :     return Val;
     139             :   }
     140             : 
     141             :   Constant *getNotConstant() const {
     142             :     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
     143             :     return Val;
     144             :   }
     145             : 
     146             :   const ConstantRange &getConstantRange() const {
     147             :     assert(isConstantRange() &&
     148             :            "Cannot get the constant-range of a non-constant-range!");
     149       78543 :     return Range;
     150             :   }
     151             : 
     152       37138 :   Optional<APInt> asConstantInteger() const {
     153       37138 :     if (isConstant() && isa<ConstantInt>(Val)) {
     154           0 :       return cast<ConstantInt>(Val)->getValue();
     155       41454 :     } else if (isConstantRange() && Range.isSingleElement()) {
     156          64 :       return *Range.getSingleElement();
     157             :     }
     158             :     return None;
     159             :   }
     160             : 
     161             : private:
     162             :   void markOverdefined() {
     163     2791601 :     if (isOverdefined())
     164             :       return;
     165     2791601 :     Tag = overdefined;
     166             :   }
     167             : 
     168       19735 :   void markConstant(Constant *V) {
     169             :     assert(V && "Marking constant with NULL");
     170       35746 :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     171       48033 :       markConstantRange(ConstantRange(CI->getValue()));
     172       16011 :       return;
     173             :     }
     174        7448 :     if (isa<UndefValue>(V))
     175             :       return;
     176             : 
     177             :     assert((!isConstant() || getConstant() == V) &&
     178             :            "Marking constant with different value");
     179             :     assert(isUndefined());
     180        3724 :     Tag = constant;
     181        3724 :     Val = V;
     182             :   }
     183             : 
     184      149025 :   void markNotConstant(Constant *V) {
     185             :     assert(V && "Marking constant with NULL");
     186      163322 :     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     187      100079 :       markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
     188       14297 :       return;
     189             :     }
     190      269456 :     if (isa<UndefValue>(V))
     191             :       return;
     192             : 
     193             :     assert((!isConstant() || getConstant() != V) &&
     194             :            "Marking constant !constant with same value");
     195             :     assert((!isNotConstant() || getNotConstant() == V) &&
     196             :            "Marking !constant with different value");
     197             :     assert(isUndefined() || isConstant());
     198      134728 :     Tag = notconstant;
     199      134728 :     Val = V;
     200             :   }
     201             : 
     202      105192 :   void markConstantRange(ConstantRange NewR) {
     203      105192 :     if (isConstantRange()) {
     204       13627 :       if (NewR.isEmptySet())
     205             :         markOverdefined();
     206             :       else {
     207       13627 :         Range = std::move(NewR);
     208             :       }
     209             :       return;
     210             :     }
     211             : 
     212             :     assert(isUndefined());
     213       91565 :     if (NewR.isEmptySet())
     214             :       markOverdefined();
     215             :     else {
     216       91554 :       Tag = constantrange;
     217       91554 :       Range = std::move(NewR);
     218             :     }
     219             :   }
     220             : 
     221             : public:
     222             : 
     223             :   /// Merge the specified lattice value into this one, updating this
     224             :   /// one and returning true if anything changed.
     225      478822 :   void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
     226      478822 :     if (RHS.isUndefined() || isOverdefined())
     227      461426 :       return;
     228      478779 :     if (RHS.isOverdefined()) {
     229             :       markOverdefined();
     230             :       return;
     231             :     }
     232             : 
     233      285365 :     if (isUndefined()) {
     234      220625 :       *this = RHS;
     235             :       return;
     236             :     }
     237             : 
     238       64740 :     if (isConstant()) {
     239        1288 :       if (RHS.isConstant() && Val == RHS.Val)
     240             :           return;
     241             :       markOverdefined();
     242             :       return;
     243             :     }
     244             : 
     245       63452 :     if (isNotConstant()) {
     246       46056 :       if (RHS.isNotConstant() && Val == RHS.Val)
     247             :           return;
     248             :       markOverdefined();
     249             :       return;
     250             :     }
     251             : 
     252             :     assert(isConstantRange() && "New LVILattice type?");
     253       17396 :     if (!RHS.isConstantRange()) {
     254             :       // We can get here if we've encountered a constantexpr of integer type
     255             :       // and merge it with a constantrange.
     256             :       markOverdefined();
     257             :       return;
     258             :     }
     259       52188 :     ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
     260       17396 :     if (NewR.isFullSet())
     261             :       markOverdefined();
     262             :     else
     263       27254 :       markConstantRange(std::move(NewR));
     264             :   }
     265             : };
     266             : 
     267             : } // end anonymous namespace.
     268             : 
     269             : namespace llvm {
     270             : raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
     271             :     LLVM_ATTRIBUTE_USED;
     272         107 : raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
     273         107 :   if (Val.isUndefined())
     274           0 :     return OS << "undefined";
     275         107 :   if (Val.isOverdefined())
     276          89 :     return OS << "overdefined";
     277             : 
     278          18 :   if (Val.isNotConstant())
     279           0 :     return OS << "notconstant<" << *Val.getNotConstant() << '>';
     280          18 :   if (Val.isConstantRange())
     281          54 :     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
     282          54 :               << Val.getConstantRange().getUpper() << '>';
     283           0 :   return OS << "constant<" << *Val.getConstant() << '>';
     284             : }
     285             : }
     286             : 
     287             : /// Returns true if this lattice value represents at most one possible value.
     288             : /// This is as precise as any lattice value can get while still representing
     289             : /// reachable code.
     290             : static bool hasSingleValue(const LVILatticeVal &Val) {
     291     1211613 :   if (Val.isConstantRange() &&
     292      116784 :       Val.getConstantRange().isSingleElement())
     293             :     // Integer constants are single element ranges
     294             :     return true;
     295     1150650 :   if (Val.isConstant())
     296             :     // Non integer constants
     297             :     return true;
     298             :   return false;
     299             : }
     300             : 
     301             : /// Combine two sets of facts about the same value into a single set of
     302             : /// facts.  Note that this method is not suitable for merging facts along
     303             : /// different paths in a CFG; that's what the mergeIn function is for.  This
     304             : /// is for merging facts gathered about the same value at the same location
     305             : /// through two independent means.
     306             : /// Notes:
     307             : /// * This method does not promise to return the most precise possible lattice
     308             : ///   value implied by A and B.  It is allowed to return any lattice element
     309             : ///   which is at least as strong as *either* A or B (unless our facts
     310             : ///   conflict, see below).
     311             : /// * Due to unreachable code, the intersection of two lattice values could be
     312             : ///   contradictory.  If this happens, we return some valid lattice value so as
     313             : ///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
     314             : ///   we do not make this guarantee.  TODO: This would be a useful enhancement.
     315      659461 : static LVILatticeVal intersect(const LVILatticeVal &A, const LVILatticeVal &B) {
     316             :   // Undefined is the strongest state.  It means the value is known to be along
     317             :   // an unreachable path.
     318      659461 :   if (A.isUndefined())
     319             :     return A;
     320      659461 :   if (B.isUndefined())
     321             :     return B;
     322             : 
     323             :   // If we gave up for one, but got a useable fact from the other, use it.
     324      659461 :   if (A.isOverdefined())
     325             :     return B;
     326       24819 :   if (B.isOverdefined())
     327             :     return A;
     328             : 
     329             :   // Can't get any more precise than constants.
     330        9149 :   if (hasSingleValue(A))
     331             :     return A;
     332        9133 :   if (hasSingleValue(B))
     333             :     return B;
     334             : 
     335             :   // Could be either constant range or not constant here.
     336       18251 :   if (!A.isConstantRange() || !B.isConstantRange()) {
     337             :     // TODO: Arbitrary choice, could be improved
     338             :     return A;
     339             :   }
     340             : 
     341             :   // Intersect two constant ranges
     342             :   ConstantRange Range =
     343       27354 :     A.getConstantRange().intersectWith(B.getConstantRange());
     344             :   // Note: An empty range is implicitly converted to overdefined internally.
     345             :   // TODO: We could instead use Undefined here since we've proven a conflict
     346             :   // and thus know this path must be unreachable.
     347       18236 :   return LVILatticeVal::getRange(std::move(Range));
     348             : }
     349             : 
     350             : //===----------------------------------------------------------------------===//
     351             : //                          LazyValueInfoCache Decl
     352             : //===----------------------------------------------------------------------===//
     353             : 
     354             : namespace {
     355             :   /// A callback value handle updates the cache when values are erased.
     356             :   class LazyValueInfoCache;
     357      314274 :   struct LVIValueHandle final : public CallbackVH {
     358             :     // Needs to access getValPtr(), which is protected.
     359             :     friend struct DenseMapInfo<LVIValueHandle>;
     360             : 
     361             :     LazyValueInfoCache *Parent;
     362             : 
     363             :     LVIValueHandle(Value *V, LazyValueInfoCache *P)
     364      314274 :       : CallbackVH(V), Parent(P) { }
     365             : 
     366             :     void deleted() override;
     367          60 :     void allUsesReplacedWith(Value *V) override {
     368          60 :       deleted();
     369          60 :     }
     370             :   };
     371             : } // end anonymous namespace
     372             : 
     373             : namespace {
     374             :   /// This is the cache kept by LazyValueInfo which
     375             :   /// maintains information about queries across the clients' queries.
     376      567736 :   class LazyValueInfoCache {
     377             :     /// This is all of the cached block information for exactly one Value*.
     378             :     /// The entries are sorted by the BasicBlock* of the
     379             :     /// entries, allowing us to do a lookup with a binary search.
     380             :     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     381             :     /// memory overhead.
     382      314274 :     struct ValueCacheEntryTy {
     383      471411 :       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
     384             :       LVIValueHandle Handle;
     385             :       SmallDenseMap<PoisoningVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
     386             :     };
     387             : 
     388             :     /// This tracks, on a per-block basis, the set of values that are
     389             :     /// over-defined at the end of that block.
     390             :     typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
     391             :         OverDefinedCacheTy;
     392             :     /// Keep track of all blocks that we have ever seen, so we
     393             :     /// don't spend time removing unused blocks from our caches.
     394             :     DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
     395             : 
     396             :     /// This is all of the cached information for all values,
     397             :     /// mapped from Value* to key information.
     398             :     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
     399             :     OverDefinedCacheTy OverDefinedCache;
     400             : 
     401             : 
     402             :   public:
     403      793507 :     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
     404     2380521 :       SeenBlocks.insert(BB);
     405             : 
     406             :       // Insert over-defined values into their own cache to reduce memory
     407             :       // overhead.
     408      793507 :       if (Result.isOverdefined())
     409      926830 :         OverDefinedCache[BB].insert(Val);
     410             :       else {
     411      330092 :         auto It = ValueCache.find_as(Val);
     412      990276 :         if (It == ValueCache.end()) {
     413      471411 :           ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
     414      157137 :           It = ValueCache.find_as(Val);
     415             :           assert(It != ValueCache.end() && "Val was just added to the map!");
     416             :         }
     417      990276 :         It->second->BlockVals[BB] = Result;
     418             :       }
     419      793507 :     }
     420             : 
     421     3801679 :     bool isOverdefined(Value *V, BasicBlock *BB) const {
     422     7603358 :       auto ODI = OverDefinedCache.find(BB);
     423             : 
     424     7603358 :       if (ODI == OverDefinedCache.end())
     425             :         return false;
     426             : 
     427     2361097 :       return ODI->second.count(V);
     428             :     }
     429             : 
     430     2713900 :     bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
     431     2713900 :       if (isOverdefined(V, BB))
     432             :         return true;
     433             : 
     434     2302664 :       auto I = ValueCache.find_as(V);
     435     4605328 :       if (I == ValueCache.end())
     436             :         return false;
     437             : 
     438     3428504 :       return I->second->BlockVals.count(BB);
     439             :     }
     440             : 
     441     1087779 :     LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const {
     442     1087779 :       if (isOverdefined(V, BB))
     443             :         return LVILatticeVal::getOverdefined();
     444             : 
     445      513635 :       auto I = ValueCache.find_as(V);
     446     1027270 :       if (I == ValueCache.end())
     447             :         return LVILatticeVal();
     448     1540905 :       auto BBI = I->second->BlockVals.find(BB);
     449     2054540 :       if (BBI == I->second->BlockVals.end())
     450             :         return LVILatticeVal();
     451      513635 :       return BBI->second;
     452             :     }
     453             : 
     454             :     /// clear - Empty the cache.
     455           0 :     void clear() {
     456           0 :       SeenBlocks.clear();
     457           0 :       ValueCache.clear();
     458           0 :       OverDefinedCache.clear();
     459           0 :     }
     460             : 
     461             :     /// Inform the cache that a given value has been deleted.
     462             :     void eraseValue(Value *V);
     463             : 
     464             :     /// This is part of the update interface to inform the cache
     465             :     /// that a block has been deleted.
     466             :     void eraseBlock(BasicBlock *BB);
     467             : 
     468             :     /// Updates the cache to remove any influence an overdefined value in
     469             :     /// OldSucc might have (unless also overdefined in NewSucc).  This just
     470             :     /// flushes elements from the cache and does not add any.
     471             :     void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
     472             : 
     473             :     friend struct LVIValueHandle;
     474             :   };
     475             : }
     476             : 
     477          83 : void LazyValueInfoCache::eraseValue(Value *V) {
     478        3465 :   for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
     479             :     // Copy and increment the iterator immediately so we can erase behind
     480             :     // ourselves.
     481        3216 :     auto Iter = I++;
     482        1608 :     SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
     483        3216 :     ValueSet.erase(V);
     484        3216 :     if (ValueSet.empty())
     485           5 :       OverDefinedCache.erase(Iter);
     486             :   }
     487             : 
     488          83 :   ValueCache.erase(V);
     489          83 : }
     490             : 
     491          23 : void LVIValueHandle::deleted() {
     492             :   // This erasure deallocates *this, so it MUST happen after we're done
     493             :   // using any and all members of *this.
     494         166 :   Parent->eraseValue(*this);
     495          23 : }
     496             : 
     497       26084 : void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
     498             :   // Shortcut if we have never seen this block.
     499       78252 :   DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
     500      104336 :   if (I == SeenBlocks.end())
     501       22397 :     return;
     502        7374 :   SeenBlocks.erase(I);
     503             : 
     504        7374 :   auto ODI = OverDefinedCache.find(BB);
     505       11061 :   if (ODI != OverDefinedCache.end())
     506        1066 :     OverDefinedCache.erase(ODI);
     507             : 
     508       33715 :   for (auto &I : ValueCache)
     509       67962 :     I.second->BlockVals.erase(BB);
     510             : }
     511             : 
     512        1294 : void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
     513             :                                         BasicBlock *NewSucc) {
     514             :   // When an edge in the graph has been threaded, values that we could not
     515             :   // determine a value for before (i.e. were marked overdefined) may be
     516             :   // possible to solve now. We do NOT try to proactively update these values.
     517             :   // Instead, we clear their entries from the cache, and allow lazy updating to
     518             :   // recompute them when needed.
     519             : 
     520             :   // The updating process is fairly simple: we need to drop cached info
     521             :   // for all values that were marked overdefined in OldSucc, and for those same
     522             :   // values in any successor of OldSucc (except NewSucc) in which they were
     523             :   // also marked overdefined.
     524        1327 :   std::vector<BasicBlock*> worklist;
     525        1294 :   worklist.push_back(OldSucc);
     526             : 
     527        2588 :   auto I = OverDefinedCache.find(OldSucc);
     528        3882 :   if (I == OverDefinedCache.end())
     529        1261 :     return; // Nothing to process here.
     530          66 :   SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
     531             : 
     532             :   // Use a worklist to perform a depth-first search of OldSucc's successors.
     533             :   // NOTE: We do not need a visited list since any blocks we have already
     534             :   // visited will have had their overdefined markers cleared already, and we
     535             :   // thus won't loop to their successors.
     536         166 :   while (!worklist.empty()) {
     537         133 :     BasicBlock *ToUpdate = worklist.back();
     538         133 :     worklist.pop_back();
     539             : 
     540             :     // Skip blocks only accessible through NewSucc.
     541         214 :     if (ToUpdate == NewSucc) continue;
     542             : 
     543             :     // If a value was marked overdefined in OldSucc, and is here too...
     544         196 :     auto OI = OverDefinedCache.find(ToUpdate);
     545         294 :     if (OI == OverDefinedCache.end())
     546          38 :       continue;
     547          60 :     SmallPtrSetImpl<Value *> &ValueSet = OI->second;
     548             : 
     549          60 :     bool changed = false;
     550         199 :     for (Value *V : ValsToClear) {
     551          66 :       if (!ValueSet.erase(V))
     552           9 :         continue;
     553             : 
     554             :       // If we removed anything, then we potentially need to update
     555             :       // blocks successors too.
     556          57 :       changed = true;
     557             : 
     558         114 :       if (ValueSet.empty()) {
     559          47 :         OverDefinedCache.erase(OI);
     560             :         break;
     561             :       }
     562             :     }
     563             : 
     564          13 :     if (!changed) continue;
     565             : 
     566         208 :     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
     567             :   }
     568             : }
     569             : 
     570             : 
     571             : namespace {
     572             : /// An assembly annotator class to print LazyValueCache information in
     573             : /// comments.
     574             : class LazyValueInfoImpl;
     575           4 : class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
     576             :   LazyValueInfoImpl *LVIImpl;
     577             :   // While analyzing which blocks we can solve values for, we need the dominator
     578             :   // information. Since this is an optional parameter in LVI, we require this
     579             :   // DomTreeAnalysis pass in the printer pass, and pass the dominator
     580             :   // tree to the LazyValueInfoAnnotatedWriter.
     581             :   DominatorTree &DT;
     582             : 
     583             : public:
     584             :   LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
     585           4 :       : LVIImpl(L), DT(DTree) {}
     586             : 
     587             :   virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
     588             :                                         formatted_raw_ostream &OS);
     589             : 
     590             :   virtual void emitInstructionAnnot(const Instruction *I,
     591             :                                     formatted_raw_ostream &OS);
     592             : };
     593             : }
     594             : namespace {
     595             :   // The actual implementation of the lazy analysis and update.  Note that the
     596             :   // inheritance from LazyValueInfoCache is intended to be temporary while
     597             :   // splitting the code and then transitioning to a has-a relationship.
     598      212901 :   class LazyValueInfoImpl {
     599             : 
     600             :     /// Cached results from previous queries
     601             :     LazyValueInfoCache TheCache;
     602             : 
     603             :     /// This stack holds the state of the value solver during a query.
     604             :     /// It basically emulates the callstack of the naive
     605             :     /// recursive value lookup process.
     606             :     SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
     607             : 
     608             :     /// Keeps track of which block-value pairs are in BlockValueStack.
     609             :     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
     610             : 
     611             :     /// Push BV onto BlockValueStack unless it's already in there.
     612             :     /// Returns true on success.
     613      807343 :     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
     614     1614686 :       if (!BlockValueSet.insert(BV).second)
     615             :         return false;  // It's already in the stack.
     616             : 
     617             :       DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
     618             :                    << "\n");
     619      793507 :       BlockValueStack.push_back(BV);
     620      793507 :       return true;
     621             :     }
     622             : 
     623             :     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     624             :     const DataLayout &DL; ///< A mandatory DataLayout
     625             :     DominatorTree *DT;    ///< An optional DT pointer.
     626             : 
     627             :   LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
     628             :   bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
     629             :                     LVILatticeVal &Result, Instruction *CxtI = nullptr);
     630             :   bool hasBlockValue(Value *Val, BasicBlock *BB);
     631             : 
     632             :   // These methods process one work item and may add more. A false value
     633             :   // returned means that the work item was not completely processed and must
     634             :   // be revisited after going through the new items.
     635             :   bool solveBlockValue(Value *Val, BasicBlock *BB);
     636             :   bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB);
     637             :   bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
     638             :   bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
     639             :   bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
     640             :                              BasicBlock *BB);
     641             :   bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, BinaryOperator *BBI,
     642             :                                BasicBlock *BB);
     643             :   bool solveBlockValueCast(LVILatticeVal &BBLV, CastInst *CI,
     644             :                            BasicBlock *BB);
     645             :   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
     646             :                                                      LVILatticeVal &BBLV,
     647             :                                                      Instruction *BBI);
     648             : 
     649             :   void solve();
     650             : 
     651             :   public:
     652             :     /// This is the query interface to determine the lattice
     653             :     /// value for the specified Value* at the end of the specified block.
     654             :     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
     655             :                                   Instruction *CxtI = nullptr);
     656             : 
     657             :     /// This is the query interface to determine the lattice
     658             :     /// value for the specified Value* at the specified instruction (generally
     659             :     /// from an assume intrinsic).
     660             :     LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
     661             : 
     662             :     /// This is the query interface to determine the lattice
     663             :     /// value for the specified Value* that is true on the specified edge.
     664             :     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
     665             :                                  Instruction *CxtI = nullptr);
     666             : 
     667             :     /// Complete flush all previously computed values
     668             :     void clear() {
     669           0 :       TheCache.clear();
     670             :     }
     671             : 
     672             :     /// Printing the LazyValueInfo Analysis.
     673           4 :     void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
     674           8 :         LazyValueInfoAnnotatedWriter Writer(this, DTree);
     675           4 :         F.print(OS, &Writer);
     676           4 :     }
     677             : 
     678             :     /// This is part of the update interface to inform the cache
     679             :     /// that a block has been deleted.
     680             :     void eraseBlock(BasicBlock *BB) {
     681       26084 :       TheCache.eraseBlock(BB);
     682             :     }
     683             : 
     684             :     /// This is the update interface to inform the cache that an edge from
     685             :     /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
     686             :     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
     687             : 
     688             :     LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
     689             :                        DominatorTree *DT = nullptr)
     690      212901 :         : AC(AC), DL(DL), DT(DT) {}
     691             :   };
     692             : } // end anonymous namespace
     693             : 
     694             : 
     695      462784 : void LazyValueInfoImpl::solve() {
     696             :   SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
     697     2313920 :       BlockValueStack.begin(), BlockValueStack.end());
     698             : 
     699      462784 :   unsigned processedCount = 0;
     700     2711244 :   while (!BlockValueStack.empty()) {
     701     1124230 :     processedCount++;
     702             :     // Abort if we have to process too many values to get a result for this one.
     703             :     // Because of the design of the overdefined cache currently being per-block
     704             :     // to avoid naming-related issues (IE it wants to try to give different
     705             :     // results for the same name in different blocks), overdefined results don't
     706             :     // get cached globally, which in turn means we will often try to rediscover
     707             :     // the same overdefined result again and again.  Once something like
     708             :     // PredicateInfo is used in LVI or CVP, we should be able to make the
     709             :     // overdefined cache global, and remove this throttle.
     710     1124230 :     if (processedCount > MaxProcessedPerValue) {
     711             :       DEBUG(dbgs() << "Giving up on stack because we are getting too deep\n");
     712             :       // Fill in the original values
     713           0 :       while (!StartingStack.empty()) {
     714           0 :         std::pair<BasicBlock *, Value *> &e = StartingStack.back();
     715           0 :         TheCache.insertResult(e.second, e.first,
     716           0 :                               LVILatticeVal::getOverdefined());
     717             :         StartingStack.pop_back();
     718             :       }
     719           0 :       BlockValueSet.clear();
     720           0 :       BlockValueStack.clear();
     721           0 :       return;
     722             :     }
     723     2248460 :     std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
     724             :     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
     725             : 
     726     1124230 :     if (solveBlockValue(e.second, e.first)) {
     727             :       // The work item was completely processed.
     728             :       assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
     729             :       assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
     730             :              "Result should be in cache!");
     731             : 
     732             :       DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
     733             :                    << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
     734             : 
     735     1587014 :       BlockValueStack.pop_back();
     736      793507 :       BlockValueSet.erase(e);
     737             :     } else {
     738             :       // More work needs to be done before revisiting.
     739             :       assert(BlockValueStack.back() != e && "Stack should have been pushed!");
     740             :     }
     741             :   }
     742             : }
     743             : 
     744             : bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
     745             :   // If already a constant, there is nothing to compute.
     746     1590382 :   if (isa<Constant>(Val))
     747             :     return true;
     748             : 
     749     1589670 :   return TheCache.hasCachedValueInfo(Val, BB);
     750             : }
     751             : 
     752     1088479 : LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) {
     753             :   // If already a constant, there is nothing to compute.
     754         700 :   if (Constant *VC = dyn_cast<Constant>(Val))
     755         700 :     return LVILatticeVal::get(VC);
     756             : 
     757     1087779 :   return TheCache.getCachedValueInfo(Val, BB);
     758             : }
     759             : 
     760      381773 : static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
     761      381773 :   switch (BBI->getOpcode()) {
     762             :   default: break;
     763      137266 :   case Instruction::Load:
     764             :   case Instruction::Call:
     765             :   case Instruction::Invoke:
     766      130884 :     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
     767       25210 :       if (isa<IntegerType>(BBI->getType())) {
     768       12605 :         return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
     769             :       }
     770             :     break;
     771             :   };
     772             :   // Nothing known - will be intersected with other facts
     773             :   return LVILatticeVal::getOverdefined();
     774             : }
     775             : 
     776     1124230 : bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
     777     1124230 :   if (isa<Constant>(Val))
     778             :     return true;
     779             : 
     780     1124230 :   if (TheCache.hasCachedValueInfo(Val, BB)) {
     781             :     // If we have a cached value, use that.
     782             :     DEBUG(dbgs() << "  reuse BB '" << BB->getName()
     783             :                  << "' val=" << TheCache.getCachedValueInfo(Val, BB) << '\n');
     784             : 
     785             :     // Since we're reusing a cached value, we don't need to update the
     786             :     // OverDefinedCache. The cache will have been properly updated whenever the
     787             :     // cached value was inserted.
     788             :     return true;
     789             :   }
     790             : 
     791             :   // Hold off inserting this value into the Cache in case we have to return
     792             :   // false and come back later.
     793     1124230 :   LVILatticeVal Res;
     794     1124230 :   if (!solveBlockValueImpl(Res, Val, BB))
     795             :     // Work pushed, will revisit
     796             :     return false;
     797             : 
     798      793507 :   TheCache.insertResult(Val, BB, Res);
     799      793507 :   return true;
     800             : }
     801             : 
     802     1124230 : bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res,
     803             :                                             Value *Val, BasicBlock *BB) {
     804             : 
     805     1054758 :   Instruction *BBI = dyn_cast<Instruction>(Val);
     806     1054758 :   if (!BBI || BBI->getParent() != BB)
     807      628293 :     return solveBlockValueNonLocal(Res, Val, BB);
     808             : 
     809      495937 :   if (PHINode *PN = dyn_cast<PHINode>(BBI))
     810       91407 :     return solveBlockValuePHINode(Res, PN, BB);
     811             : 
     812      404530 :   if (auto *SI = dyn_cast<SelectInst>(BBI))
     813        2882 :     return solveBlockValueSelect(Res, SI, BB);
     814             : 
     815             :   // If this value is a nonnull pointer, record it's range and bailout.  Note
     816             :   // that for all other pointer typed values, we terminate the search at the
     817             :   // definition.  We could easily extend this to look through geps, bitcasts,
     818             :   // and the like to prove non-nullness, but it's not clear that's worth it
     819             :   // compile time wise.  The context-insensitive value walk done inside
     820             :   // isKnownNonZero gets most of the profitable cases at much less expense.
     821             :   // This does mean that we have a sensativity to where the defining
     822             :   // instruction is placed, even if it could legally be hoisted much higher.
     823             :   // That is unfortunate.
     824      629234 :   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
     825      227586 :   if (PT && isKnownNonZero(BBI, DL)) {
     826      323286 :     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
     827      107762 :     return true;
     828             :   }
     829      587772 :   if (BBI->getType()->isIntegerTy()) {
     830      165679 :     if (auto *CI = dyn_cast<CastInst>(BBI))
     831        4249 :       return solveBlockValueCast(Res, CI, BB);
     832             : 
     833       28631 :     BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
     834       57262 :     if (BO && isa<ConstantInt>(BO->getOperand(1)))
     835       24181 :       return solveBlockValueBinaryOp(Res, BO, BB);
     836             :   }
     837             : 
     838             :   DEBUG(dbgs() << " compute BB '" << BB->getName()
     839             :                  << "' - unknown inst def found.\n");
     840      796368 :   Res = getFromRangeMetadata(BBI);
     841      265456 :   return true;
     842             : }
     843             : 
     844     1411050 : static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
     845      307781 :   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
     846      615238 :     return L->getPointerAddressSpace() == 0 &&
     847      922371 :            GetUnderlyingObject(L->getPointerOperand(),
     848             :                                L->getModule()->getDataLayout()) == Ptr;
     849             :   }
     850      337142 :   if (StoreInst *S = dyn_cast<StoreInst>(I)) {
     851      673384 :     return S->getPointerAddressSpace() == 0 &&
     852     1008726 :            GetUnderlyingObject(S->getPointerOperand(),
     853             :                                S->getModule()->getDataLayout()) == Ptr;
     854             :   }
     855        1377 :   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
     856        1377 :     if (MI->isVolatile()) return false;
     857             : 
     858             :     // FIXME: check whether it has a valuerange that excludes zero?
     859        2193 :     ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
     860         818 :     if (!Len || Len->isZero()) return false;
     861             : 
     862         818 :     if (MI->getDestAddressSpace() == 0)
     863        2448 :       if (GetUnderlyingObject(MI->getRawDest(),
     864             :                               MI->getModule()->getDataLayout()) == Ptr)
     865             :         return true;
     866         329 :     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
     867         329 :       if (MTI->getSourceAddressSpace() == 0)
     868         981 :         if (GetUnderlyingObject(MTI->getRawSource(),
     869             :                                 MTI->getModule()->getDataLayout()) == Ptr)
     870             :           return true;
     871             :   }
     872             :   return false;
     873             : }
     874             : 
     875             : /// Return true if the allocation associated with Val is ever dereferenced
     876             : /// within the given basic block.  This establishes the fact Val is not null,
     877             : /// but does not imply that the memory at Val is dereferenceable.  (Val may
     878             : /// point off the end of the dereferenceable part of the object.)
     879      107292 : static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
     880             :   assert(Val->getType()->isPointerTy());
     881             : 
     882      107292 :   const DataLayout &DL = BB->getModule()->getDataLayout();
     883      107292 :   Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
     884             :   // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
     885             :   // inside InstructionDereferencesPointer either.
     886      107292 :   if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
     887     1732926 :     for (Instruction &I : *BB)
     888     1411050 :       if (InstructionDereferencesPointer(&I, UnderlyingVal))
     889             :         return true;
     890             :   return false;
     891             : }
     892             : 
     893      628293 : bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
     894             :                                                  Value *Val, BasicBlock *BB) {
     895     1256586 :   LVILatticeVal Result;  // Start Undefined.
     896             : 
     897             :   // If this is the entry block, we must be asking about an argument.  The
     898             :   // value is overdefined.
     899     1256586 :   if (BB == &BB->getParent()->getEntryBlock()) {
     900             :     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
     901             :     // Before giving up, see if we can prove the pointer non-null local to
     902             :     // this particular block.
     903       71939 :     if (Val->getType()->isPointerTy() &&
     904       36407 :         (isKnownNonZero(Val, DL) || isObjectDereferencedInBlock(Val, BB))) {
     905       20084 :       PointerType *PTy = cast<PointerType>(Val->getType());
     906       30126 :       Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
     907             :     } else {
     908       44607 :       Result = LVILatticeVal::getOverdefined();
     909             :     }
     910       24911 :     BBLV = Result;
     911       24911 :     return true;
     912             :   }
     913             : 
     914             :   // Loop over all of our predecessors, merging what we know from them into
     915             :   // result.  If we encounter an unexplored predecessor, we eagerly explore it
     916             :   // in a depth first manner.  In practice, this has the effect of discovering
     917             :   // paths we can't analyze eagerly without spending compile times analyzing
     918             :   // other paths.  This heuristic benefits from the fact that predecessors are
     919             :   // frequently arranged such that dominating ones come first and we quickly
     920             :   // find a path to function entry.  TODO: We should consider explicitly
     921             :   // canonicalizing to make this true rather than relying on this happy
     922             :   // accident.  
     923     2068050 :   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     924      944626 :     LVILatticeVal EdgeResult;
     925      686722 :     if (!getEdgeValue(Val, *PI, BB, EdgeResult))
     926             :       // Explore that input, then return here
     927      428818 :       return false;
     928             : 
     929      403817 :     Result.mergeIn(EdgeResult, DL);
     930             : 
     931             :     // If we hit overdefined, exit early.  The BlockVals entry is already set
     932             :     // to overdefined.
     933      403817 :     if (Result.isOverdefined()) {
     934             :       DEBUG(dbgs() << " compute BB '" << BB->getName()
     935             :             << "' - overdefined because of pred (non local).\n");
     936             :       // Before giving up, see if we can prove the pointer non-null local to
     937             :       // this particular block.
     938      384828 :       if (Val->getType()->isPointerTy() &&
     939       93002 :           isObjectDereferencedInBlock(Val, BB)) {
     940       27666 :         PointerType *PTy = cast<PointerType>(Val->getType());
     941       41499 :         Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
     942             :       }
     943             : 
     944      145913 :       BBLV = Result;
     945      145913 :       return true;
     946             :     }
     947             :   }
     948             : 
     949             :   // Return the merged value, which is more precise than 'overdefined'.
     950             :   assert(!Result.isOverdefined());
     951      174564 :   BBLV = Result;
     952      174564 :   return true;
     953             : }
     954             : 
     955       91407 : bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
     956             :                                                 PHINode *PN, BasicBlock *BB) {
     957      182814 :   LVILatticeVal Result;  // Start Undefined.
     958             : 
     959             :   // Loop over all of our predecessors, merging what we know from them into
     960             :   // result.  See the comment about the chosen traversal order in
     961             :   // solveBlockValueNonLocal; the same reasoning applies here.
     962      204797 :   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     963      108055 :     BasicBlock *PhiBB = PN->getIncomingBlock(i);
     964      108055 :     Value *PhiVal = PN->getIncomingValue(i);
     965      130038 :     LVILatticeVal EdgeResult;
     966             :     // Note that we can provide PN as the context value to getEdgeValue, even
     967             :     // though the results will be cached, because PN is the value being used as
     968             :     // the cache key in the caller.
     969      108055 :     if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
     970             :       // Explore that input, then return here
     971       86072 :       return false;
     972             : 
     973       74505 :     Result.mergeIn(EdgeResult, DL);
     974             : 
     975             :     // If we hit overdefined, exit early.  The BlockVals entry is already set
     976             :     // to overdefined.
     977       74505 :     if (Result.isOverdefined()) {
     978             :       DEBUG(dbgs() << " compute BB '" << BB->getName()
     979             :             << "' - overdefined because of pred (local).\n");
     980             : 
     981       52522 :       BBLV = Result;
     982       52522 :       return true;
     983             :     }
     984             :   }
     985             : 
     986             :   // Return the merged value, which is more precise than 'overdefined'.
     987             :   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
     988        5335 :   BBLV = Result;
     989        5335 :   return true;
     990             : }
     991             : 
     992             : static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
     993             :                                            bool isTrueDest = true);
     994             : 
     995             : // If we can determine a constraint on the value given conditions assumed by
     996             : // the program, intersect those constraints with BBLV
     997     1892774 : void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
     998             :         Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
     999     3759124 :   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
    1000     1866350 :   if (!BBI)
    1001             :     return;
    1002             : 
    1003     5599088 :   for (auto &AssumeVH : AC->assumptionsFor(Val)) {
    1004          38 :     if (!AssumeVH)
    1005             :       continue;
    1006          38 :     auto *I = cast<CallInst>(AssumeVH);
    1007          38 :     if (!isValidAssumeForContext(I, BBI, DT))
    1008             :       continue;
    1009             : 
    1010          88 :     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
    1011             :   }
    1012             : 
    1013             :   // If guards are not used in the module, don't spend time looking for them
    1014     1866350 :   auto *GuardDecl = BBI->getModule()->getFunction(
    1015     1866350 :           Intrinsic::getName(Intrinsic::experimental_guard));
    1016     1866626 :   if (!GuardDecl || GuardDecl->use_empty())
    1017             :     return;
    1018             : 
    1019         552 :   for (Instruction &I : make_range(BBI->getIterator().getReverse(),
    1020        1914 :                                    BBI->getParent()->rend())) {
    1021         810 :     Value *Cond = nullptr;
    1022        2430 :     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
    1023         148 :       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
    1024             :   }
    1025             : }
    1026             : 
    1027        2882 : bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV,
    1028             :                                                SelectInst *SI, BasicBlock *BB) {
    1029             : 
    1030             :   // Recurse on our inputs if needed
    1031        8124 :   if (!hasBlockValue(SI->getTrueValue(), BB)) {
    1032        2176 :     if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
    1033             :       return false;
    1034           0 :     BBLV = LVILatticeVal::getOverdefined();
    1035           0 :     return true;
    1036             :   }
    1037        3588 :   LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
    1038             :   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
    1039             :   // extra slots in the table if we can.
    1040        1794 :   if (TrueVal.isOverdefined()) {
    1041        2751 :     BBLV = LVILatticeVal::getOverdefined();
    1042         917 :     return true;
    1043             :   }
    1044             : 
    1045        2484 :   if (!hasBlockValue(SI->getFalseValue(), BB)) {
    1046         690 :     if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
    1047             :       return false;
    1048           0 :     BBLV = LVILatticeVal::getOverdefined();
    1049           0 :     return true;
    1050             :   }
    1051        1064 :   LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
    1052             :   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
    1053             :   // extra slots in the table if we can.
    1054         532 :   if (FalseVal.isOverdefined()) {
    1055         717 :     BBLV = LVILatticeVal::getOverdefined();
    1056         239 :     return true;
    1057             :   }
    1058             : 
    1059         293 :   if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
    1060         226 :     const ConstantRange &TrueCR = TrueVal.getConstantRange();
    1061         226 :     const ConstantRange &FalseCR = FalseVal.getConstantRange();
    1062         226 :     Value *LHS = nullptr;
    1063         226 :     Value *RHS = nullptr;
    1064         226 :     SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
    1065             :     // Is this a min specifically of our two inputs?  (Avoid the risk of
    1066             :     // ValueTracking getting smarter looking back past our immediate inputs.)
    1067         352 :     if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
    1068         106 :         LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
    1069          43 :       ConstantRange ResultCR = [&]() {
    1070          43 :         switch (SPR.Flavor) {
    1071           0 :         default:
    1072           0 :           llvm_unreachable("unexpected minmax type!");
    1073           5 :         case SPF_SMIN:                   /// Signed minimum
    1074          43 :           return TrueCR.smin(FalseCR);
    1075          36 :         case SPF_UMIN:                   /// Unsigned minimum
    1076          36 :           return TrueCR.umin(FalseCR);
    1077           1 :         case SPF_SMAX:                   /// Signed maximum
    1078           1 :           return TrueCR.smax(FalseCR);
    1079           1 :         case SPF_UMAX:                   /// Unsigned maximum
    1080           1 :           return TrueCR.umax(FalseCR);
    1081             :         };
    1082          86 :       }();
    1083         129 :       BBLV = LVILatticeVal::getRange(ResultCR);
    1084             :       return true;
    1085             :     }
    1086             : 
    1087             :     // TODO: ABS, NABS from the SelectPatternResult
    1088             :   }
    1089             : 
    1090             :   // Can we constrain the facts about the true and false values by using the
    1091             :   // condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
    1092             :   // TODO: We could potentially refine an overdefined true value above.
    1093         250 :   Value *Cond = SI->getCondition();
    1094         750 :   TrueVal = intersect(TrueVal,
    1095         500 :                       getValueFromCondition(SI->getTrueValue(), Cond, true));
    1096         750 :   FalseVal = intersect(FalseVal,
    1097         500 :                        getValueFromCondition(SI->getFalseValue(), Cond, false));
    1098             : 
    1099             :   // Handle clamp idioms such as:
    1100             :   //   %24 = constantrange<0, 17>
    1101             :   //   %39 = icmp eq i32 %24, 0
    1102             :   //   %40 = add i32 %24, -1
    1103             :   //   %siv.next = select i1 %39, i32 16, i32 %40
    1104             :   //   %siv.next = constantrange<0, 17> not <-1, 17>
    1105             :   // In general, this can handle any clamp idiom which tests the edge
    1106             :   // condition via an equality or inequality.
    1107         232 :   if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
    1108         464 :     ICmpInst::Predicate Pred = ICI->getPredicate();
    1109         464 :     Value *A = ICI->getOperand(0);
    1110         582 :     if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
    1111           2 :       auto addConstants = [](ConstantInt *A, ConstantInt *B) {
    1112             :         assert(A->getType() == B->getType());
    1113          14 :         return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
    1114             :       };
    1115             :       // See if either input is A + C2, subject to the constraint from the
    1116             :       // condition that A != C when that input is used.  We can assume that
    1117             :       // that input doesn't include C + C2.
    1118             :       ConstantInt *CIAdded;
    1119         118 :       switch (Pred) {
    1120             :       default: break;
    1121          99 :       case ICmpInst::ICMP_EQ:
    1122         396 :         if (match(SI->getFalseValue(), m_Add(m_Specific(A),
    1123          99 :                                              m_ConstantInt(CIAdded)))) {
    1124           2 :           auto ResNot = addConstants(CIBase, CIAdded);
    1125           6 :           FalseVal = intersect(FalseVal,
    1126           4 :                                LVILatticeVal::getNot(ResNot));
    1127             :         }
    1128             :         break;
    1129           4 :       case ICmpInst::ICMP_NE:
    1130          16 :         if (match(SI->getTrueValue(), m_Add(m_Specific(A),
    1131           4 :                                             m_ConstantInt(CIAdded)))) {
    1132           0 :           auto ResNot = addConstants(CIBase, CIAdded);
    1133           0 :           TrueVal = intersect(TrueVal,
    1134           0 :                               LVILatticeVal::getNot(ResNot));
    1135             :         }
    1136             :         break;
    1137             :       };
    1138             :     }
    1139             :   }
    1140             : 
    1141         250 :   LVILatticeVal Result;  // Start Undefined.
    1142         250 :   Result.mergeIn(TrueVal, DL);
    1143         250 :   Result.mergeIn(FalseVal, DL);
    1144         250 :   BBLV = Result;
    1145         250 :   return true;
    1146             : }
    1147             : 
    1148        4249 : bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV,
    1149             :                                             CastInst *CI,
    1150             :                                             BasicBlock *BB) {
    1151        8498 :   if (!CI->getOperand(0)->getType()->isSized()) {
    1152             :     // Without knowing how wide the input is, we can't analyze it in any useful
    1153             :     // way.
    1154           0 :     BBLV = LVILatticeVal::getOverdefined();
    1155           0 :     return true;
    1156             :   }
    1157             : 
    1158             :   // Filter out casts we don't know how to reason about before attempting to
    1159             :   // recurse on our operand.  This can cut a long search short if we know we're
    1160             :   // not going to be able to get any useful information anways.
    1161        4249 :   switch (CI->getOpcode()) {
    1162             :   case Instruction::Trunc:
    1163             :   case Instruction::SExt:
    1164             :   case Instruction::ZExt:
    1165             :   case Instruction::BitCast:
    1166             :     break;
    1167             :   default:
    1168             :     // Unhandled instructions are overdefined.
    1169             :     DEBUG(dbgs() << " compute BB '" << BB->getName()
    1170             :                  << "' - overdefined (unknown cast).\n");
    1171        2259 :     BBLV = LVILatticeVal::getOverdefined();
    1172         753 :     return true;
    1173             :   }
    1174             : 
    1175             :   // Figure out the range of the LHS.  If that fails, we still apply the
    1176             :   // transfer rule on the full set since we may be able to locally infer
    1177             :   // interesting facts.
    1178       10488 :   if (!hasBlockValue(CI->getOperand(0), BB))
    1179        5220 :     if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
    1180             :       // More work to do before applying this transfer rule.
    1181             :       return false;
    1182             : 
    1183             :   const unsigned OperandBitWidth =
    1184        3512 :     DL.getTypeSizeInBits(CI->getOperand(0)->getType());
    1185        3512 :   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
    1186        5268 :   if (hasBlockValue(CI->getOperand(0), BB)) {
    1187        5268 :     LVILatticeVal LHSVal = getBlockValue(CI->getOperand(0), BB);
    1188        3512 :     intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
    1189             :                                                   CI);
    1190        1756 :     if (LHSVal.isConstantRange())
    1191          67 :       LHSRange = LHSVal.getConstantRange();
    1192             :   }
    1193             : 
    1194        3512 :   const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
    1195             : 
    1196             :   // NOTE: We're currently limited by the set of operations that ConstantRange
    1197             :   // can evaluate symbolically.  Enhancing that set will allows us to analyze
    1198             :   // more definitions.
    1199        5268 :   BBLV = LVILatticeVal::getRange(LHSRange.castOp(CI->getOpcode(),
    1200             :                                                  ResultBitWidth));
    1201             :   return true;
    1202             : }
    1203             : 
    1204       24181 : bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
    1205             :                                                  BinaryOperator *BO,
    1206             :                                                  BasicBlock *BB) {
    1207             : 
    1208             :   assert(BO->getOperand(0)->getType()->isSized() &&
    1209             :          "all operands to binary operators are sized");
    1210             : 
    1211             :   // Filter out operators we don't know how to reason about before attempting to
    1212             :   // recurse on our operand(s).  This can cut a long search short if we know
    1213             :   // we're not going to be able to get any useful information anyways.
    1214       24181 :   switch (BO->getOpcode()) {
    1215             :   case Instruction::Add:
    1216             :   case Instruction::Sub:
    1217             :   case Instruction::Mul:
    1218             :   case Instruction::UDiv:
    1219             :   case Instruction::Shl:
    1220             :   case Instruction::LShr:
    1221             :   case Instruction::And:
    1222             :   case Instruction::Or:
    1223             :     // continue into the code below
    1224             :     break;
    1225             :   default:
    1226             :     // Unhandled instructions are overdefined.
    1227             :     DEBUG(dbgs() << " compute BB '" << BB->getName()
    1228             :                  << "' - overdefined (unknown binary operator).\n");
    1229        3828 :     BBLV = LVILatticeVal::getOverdefined();
    1230        1276 :     return true;
    1231             :   };
    1232             : 
    1233             :   // Figure out the range of the LHS.  If that fails, use a conservative range,
    1234             :   // but apply the transfer rule anyways.  This lets us pick up facts from
    1235             :   // expressions like "and i32 (call i32 @foo()), 32"
    1236       68703 :   if (!hasBlockValue(BO->getOperand(0), BB))
    1237       22208 :     if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
    1238             :       // More work to do before applying this transfer rule.
    1239             :       return false;
    1240             : 
    1241             :   const unsigned OperandBitWidth =
    1242       23620 :     DL.getTypeSizeInBits(BO->getOperand(0)->getType());
    1243       23620 :   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
    1244       35418 :   if (hasBlockValue(BO->getOperand(0), BB)) {
    1245       35403 :     LVILatticeVal LHSVal = getBlockValue(BO->getOperand(0), BB);
    1246       11801 :     intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
    1247             :                                                   BO);
    1248       11801 :     if (LHSVal.isConstantRange())
    1249        5129 :       LHSRange = LHSVal.getConstantRange();
    1250             :   }
    1251             : 
    1252       23620 :   ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
    1253       47240 :   ConstantRange RHSRange = ConstantRange(RHS->getValue());
    1254             : 
    1255             :   // NOTE: We're currently limited by the set of operations that ConstantRange
    1256             :   // can evaluate symbolically.  Enhancing that set will allows us to analyze
    1257             :   // more definitions.
    1258       11810 :   Instruction::BinaryOps BinOp = BO->getOpcode();
    1259       35430 :   BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange));
    1260             :   return true;
    1261             : }
    1262             : 
    1263      383586 : static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
    1264             :                                                bool isTrueDest) {
    1265      767172 :   Value *LHS = ICI->getOperand(0);
    1266      767172 :   Value *RHS = ICI->getOperand(1);
    1267      767172 :   CmpInst::Predicate Predicate = ICI->getPredicate();
    1268             : 
    1269      383586 :   if (isa<Constant>(RHS)) {
    1270      274538 :     if (ICI->isEquality() && LHS == Val) {
    1271             :       // We know that V has the RHS constant if this is a true SETEQ or
    1272             :       // false SETNE.
    1273       18817 :       if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
    1274        2862 :         return LVILatticeVal::get(cast<Constant>(RHS));
    1275             :       else
    1276       34772 :         return LVILatticeVal::getNot(cast<Constant>(RHS));
    1277             :     }
    1278             :   }
    1279             : 
    1280      729538 :   if (!Val->getType()->isIntegerTy())
    1281             :     return LVILatticeVal::getOverdefined();
    1282             : 
    1283             :   // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
    1284             :   // range of Val guaranteed by the condition. Recognize comparisons in the from
    1285             :   // of:
    1286             :   //  icmp <pred> Val, ...
    1287             :   //  icmp <pred> (add Val, Offset), ...
    1288             :   // The latter is the range checking idiom that InstCombine produces. Subtract
    1289             :   // the offset from the allowed range for RHS in this case.
    1290             : 
    1291             :   // Val or (add Val, Offset) can be on either hand of the comparison
    1292      540896 :   if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
    1293      129592 :     std::swap(LHS, RHS);
    1294      129592 :     Predicate = CmpInst::getSwappedPredicate(Predicate);
    1295             :   }
    1296             : 
    1297      150992 :   ConstantInt *Offset = nullptr;
    1298      150992 :   if (LHS != Val)
    1299      505096 :     match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
    1300             : 
    1301      150992 :   if (LHS == Val || Offset) {
    1302             :     // Calculate the range of values that are allowed by the comparison
    1303             :     ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
    1304       75777 :                            /*isFullSet=*/true);
    1305       41138 :     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
    1306       47637 :       RHSRange = ConstantRange(CI->getValue());
    1307       17399 :     else if (Instruction *I = dyn_cast<Instruction>(RHS))
    1308        5712 :       if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
    1309           4 :         RHSRange = getConstantRangeFromMetadata(*Ranges);
    1310             : 
    1311             :     // If we're interested in the false dest, invert the condition
    1312             :     CmpInst::Predicate Pred =
    1313       25259 :             isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
    1314             :     ConstantRange TrueValues =
    1315       50518 :             ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
    1316             : 
    1317       25259 :     if (Offset) // Apply the offset from above.
    1318        1082 :       TrueValues = TrueValues.subtract(Offset->getValue());
    1319             : 
    1320       50518 :     return LVILatticeVal::getRange(std::move(TrueValues));
    1321             :   }
    1322             : 
    1323             :   return LVILatticeVal::getOverdefined();
    1324             : }
    1325             : 
    1326             : static LVILatticeVal
    1327             : getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
    1328             :                       DenseMap<Value*, LVILatticeVal> &Visited);
    1329             : 
    1330             : static LVILatticeVal
    1331      436808 : getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
    1332             :                           DenseMap<Value*, LVILatticeVal> &Visited) {
    1333      383586 :   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
    1334      383586 :     return getValueFromICmpCondition(Val, ICI, isTrueDest);
    1335             : 
    1336             :   // Handle conditions in the form of (cond1 && cond2), we know that on the
    1337             :   // true dest path both of the conditions hold. Similarly for conditions of
    1338             :   // the form (cond1 || cond2), we know that on the false dest path neither
    1339             :   // condition holds.
    1340        6633 :   BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
    1341       10625 :   if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
    1342        2641 :              (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
    1343             :     return LVILatticeVal::getOverdefined();
    1344             : 
    1345        2354 :   auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
    1346        3531 :   auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
    1347        1177 :   return intersect(RHS, LHS);
    1348             : }
    1349             : 
    1350             : static LVILatticeVal
    1351      437064 : getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
    1352             :                       DenseMap<Value*, LVILatticeVal> &Visited) {
    1353      437064 :   auto I = Visited.find(Cond);
    1354      874128 :   if (I != Visited.end())
    1355         256 :     return I->second;
    1356             : 
    1357      436808 :   auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
    1358      436808 :   Visited[Cond] = Result;
    1359      436808 :   return Result;
    1360             : }
    1361             : 
    1362      434710 : LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
    1363             :   assert(Cond && "precondition");
    1364      869420 :   DenseMap<Value*, LVILatticeVal> Visited;
    1365      869420 :   return getValueFromCondition(Val, Cond, isTrueDest, Visited);
    1366             : }
    1367             : 
    1368             : // Return true if Usr has Op as an operand, otherwise false.
    1369       19447 : static bool usesOperand(User *Usr, Value *Op) {
    1370       58341 :   return find(Usr->operands(), Op) != Usr->op_end();
    1371             : }
    1372             : 
    1373             : // Return true if the instruction type of Val is supported by
    1374             : // constantFoldUser(). Currently CastInst and BinaryOperator only.  Call this
    1375             : // before calling constantFoldUser() to find out if it's even worth attempting
    1376             : // to call it.
    1377             : static bool isOperationFoldable(User *Usr) {
    1378      202624 :   return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
    1379             : }
    1380             : 
    1381             : // Check if Usr can be simplified to an integer constant when the value of one
    1382             : // of its operands Op is an integer constant OpConstVal. If so, return it as an
    1383             : // lattice value range with a single element or otherwise return an overdefined
    1384             : // lattice value.
    1385         408 : static LVILatticeVal constantFoldUser(User *Usr, Value *Op,
    1386             :                                       const APInt &OpConstVal,
    1387             :                                       const DataLayout &DL) {
    1388             :   assert(isOperationFoldable(Usr) && "Precondition");
    1389         408 :   Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
    1390             :   // Check if Usr can be simplified to a constant.
    1391         204 :   if (auto *CI = dyn_cast<CastInst>(Usr)) {
    1392             :     assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
    1393         816 :     if (auto *C = dyn_cast_or_null<ConstantInt>(
    1394         204 :             SimplifyCastInst(CI->getOpcode(), OpConst,
    1395         204 :                              CI->getDestTy(), DL))) {
    1396         612 :       return LVILatticeVal::getRange(ConstantRange(C->getValue()));
    1397             :     }
    1398         204 :   } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
    1399         204 :     bool Op0Match = BO->getOperand(0) == Op;
    1400         204 :     bool Op1Match = BO->getOperand(1) == Op;
    1401             :     assert((Op0Match || Op1Match) &&
    1402             :            "Operand 0 nor Operand 1 isn't a match");
    1403         408 :     Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
    1404         408 :     Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
    1405         612 :     if (auto *C = dyn_cast_or_null<ConstantInt>(
    1406         408 :             SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
    1407         468 :       return LVILatticeVal::getRange(ConstantRange(C->getValue()));
    1408             :     }
    1409             :   }
    1410             :   return LVILatticeVal::getOverdefined();
    1411             : }
    1412             : 
    1413             : /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
    1414             : /// Val is not constrained on the edge.  Result is unspecified if return value
    1415             : /// is false.
    1416     1134911 : static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
    1417             :                               BasicBlock *BBTo, LVILatticeVal &Result) {
    1418             :   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
    1419             :   // know that v != 0.
    1420     2046748 :   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
    1421             :     // If this is a conditional branch and only one successor goes to BBTo, then
    1422             :     // we may be able to infer something from the condition.
    1423     1310540 :     if (BI->isConditional() &&
    1424      797406 :         BI->getSuccessor(0) != BI->getSuccessor(1)) {
    1425      398668 :       bool isTrueDest = BI->getSuccessor(0) == BBTo;
    1426             :       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
    1427             :              "BBTo isn't a successor of BBFrom");
    1428      398668 :       Value *Condition = BI->getCondition();
    1429             : 
    1430             :       // If V is the condition of the branch itself, then we know exactly what
    1431             :       // it is.
    1432      398668 :       if (Condition == Val) {
    1433        4965 :         Result = LVILatticeVal::get(ConstantInt::get(
    1434             :                               Type::getInt1Ty(Val->getContext()), isTrueDest));
    1435        1655 :         return true;
    1436             :       }
    1437             : 
    1438             :       // If the condition of the branch is an equality comparison, we may be
    1439             :       // able to infer the value.
    1440     1191039 :       Result = getValueFromCondition(Val, Condition, isTrueDest);
    1441      397013 :       if (!Result.isOverdefined())
    1442             :         return true;
    1443             : 
    1444      311414 :       if (User *Usr = dyn_cast<User>(Val)) {
    1445             :         assert(Result.isOverdefined() && "Result isn't overdefined");
    1446             :         // Check with isOperationFoldable() first to avoid linearly iterating
    1447             :         // over the operands unnecessarily which can be expensive for
    1448             :         // instructions with many operands.
    1449      622828 :         if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
    1450       19294 :           const DataLayout &DL = BBTo->getModule()->getDataLayout();
    1451       19294 :           if (usesOperand(Usr, Condition)) {
    1452             :             // If Val has Condition as an operand and Val can be folded into a
    1453             :             // constant with either Condition == true or Condition == false,
    1454             :             // propagate the constant.
    1455             :             // eg.
    1456             :             //   ; %Val is true on the edge to %then.
    1457             :             //   %Val = and i1 %Condition, true.
    1458             :             //   br %Condition, label %then, label %else
    1459           6 :             APInt ConditionVal(1, isTrueDest ? 1 : 0);
    1460           6 :             Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
    1461             :           } else {
    1462             :             // If one of Val's operand has an inferred value, we may be able to
    1463             :             // infer the value of Val.
    1464             :             // eg.
    1465             :             //    ; %Val is 94 on the edge to %then.
    1466             :             //    %Val = add i8 %Op, 1
    1467             :             //    %Condition = icmp eq i8 %Op, 93
    1468             :             //    br i1 %Condition, label %then, label %else
    1469       93440 :             for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
    1470       37138 :               Value *Op = Usr->getOperand(i);
    1471             :               LVILatticeVal OpLatticeVal =
    1472       74212 :                   getValueFromCondition(Op, Condition, isTrueDest);
    1473       74212 :               if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
    1474         192 :                 Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
    1475          64 :                 break;
    1476             :               }
    1477             :             }
    1478             :           }
    1479             :         }
    1480             :       }
    1481      355267 :       if (!Result.isOverdefined())
    1482             :         return true;
    1483             :     }
    1484             :   }
    1485             : 
    1486             :   // If the edge was formed by a switch on the value, then we may know exactly
    1487             :   // what it is.
    1488     1097460 :   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
    1489        5968 :     Value *Condition = SI->getCondition();
    1490       11936 :     if (!isa<IntegerType>(Val->getType()))
    1491             :       return false;
    1492        1273 :     bool ValUsesConditionAndMayBeFoldable = false;
    1493        1273 :     if (Condition != Val) {
    1494             :       // Check if Val has Condition as an operand.
    1495         893 :       if (User *Usr = dyn_cast<User>(Val))
    1496         153 :         ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
    1497         153 :             usesOperand(Usr, Condition);
    1498         893 :       if (!ValUsesConditionAndMayBeFoldable)
    1499             :         return false;
    1500             :     }
    1501             :     assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
    1502             :            "Condition != Val nor Val doesn't use Condition");
    1503             : 
    1504         306 :     bool DefaultCase = SI->getDefaultDest() == BBTo;
    1505         612 :     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
    1506         612 :     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
    1507             : 
    1508        2428 :     for (auto Case : SI->cases()) {
    1509        7264 :       APInt CaseValue = Case.getCaseValue()->getValue();
    1510        5448 :       ConstantRange EdgeVal(CaseValue);
    1511        1816 :       if (ValUsesConditionAndMayBeFoldable) {
    1512         342 :         User *Usr = cast<User>(Val);
    1513         342 :         const DataLayout &DL = BBTo->getModule()->getDataLayout();
    1514             :         LVILatticeVal EdgeLatticeVal =
    1515         684 :             constantFoldUser(Usr, Condition, CaseValue, DL);
    1516         342 :         if (EdgeLatticeVal.isOverdefined())
    1517           0 :           return false;
    1518         684 :         EdgeVal = EdgeLatticeVal.getConstantRange();
    1519             :       }
    1520        1816 :       if (DefaultCase) {
    1521             :         // It is possible that the default destination is the destination of
    1522             :         // some cases. We cannot perform difference for those cases.
    1523             :         // We know Condition != CaseValue in BBTo.  In some cases we can use
    1524             :         // this to infer Val == f(Condition) is != f(CaseValue).  For now, we
    1525             :         // only do this when f is identity (i.e. Val == Condition), but we
    1526             :         // should be able to do this for any injective f.
    1527         872 :         if (Case.getCaseSuccessor() != BBTo && Condition == Val)
    1528         554 :           EdgesVals = EdgesVals.difference(EdgeVal);
    1529         944 :       } else if (Case.getCaseSuccessor() == BBTo)
    1530         215 :         EdgesVals = EdgesVals.unionWith(EdgeVal);
    1531             :     }
    1532        1224 :     Result = LVILatticeVal::getRange(std::move(EdgesVals));
    1533         306 :     return true;
    1534             :   }
    1535             :   return false;
    1536             : }
    1537             : 
    1538             : /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
    1539             : /// the basic block if the edge does not constrain Val.
    1540     1150877 : bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
    1541             :                                      BasicBlock *BBTo, LVILatticeVal &Result,
    1542             :                                      Instruction *CxtI) {
    1543             :   // If already a constant, there is nothing to compute.
    1544     1166843 :   if (Constant *VC = dyn_cast<Constant>(Val)) {
    1545       47898 :     Result = LVILatticeVal::get(VC);
    1546       15966 :     return true;
    1547             :   }
    1548             : 
    1549     1134911 :   LVILatticeVal LocalResult;
    1550     1134911 :   if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
    1551             :     // If we couldn't constrain the value on the edge, LocalResult doesn't
    1552             :     // provide any information.
    1553     3273558 :     LocalResult = LVILatticeVal::getOverdefined();
    1554             : 
    1555     1131783 :   if (hasSingleValue(LocalResult)) {
    1556             :     // Can't get any more precise here
    1557        3128 :     Result = LocalResult;
    1558        3128 :     return true;
    1559             :   }
    1560             : 
    1561     2263566 :   if (!hasBlockValue(Val, BBFrom)) {
    1562      948120 :     if (pushBlockValue(std::make_pair(BBFrom, Val)))
    1563             :       return false;
    1564             :     // No new information.
    1565       13827 :     Result = LocalResult;
    1566       13827 :     return true;
    1567             :   }
    1568             : 
    1569             :   // Try to intersect ranges of the BB and the constraint on the edge.
    1570      657723 :   LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
    1571      657723 :   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
    1572     1315446 :                                                 BBFrom->getTerminator());
    1573             :   // We can use the context instruction (generically the ultimate instruction
    1574             :   // the calling pass is trying to simplify) here, even though the result of
    1575             :   // this function is generally cached when called from the solve* functions
    1576             :   // (and that cached result might be used with queries using a different
    1577             :   // context instruction), because when this function is called from the solve*
    1578             :   // functions, the context instruction is not provided. When called from
    1579             :   // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
    1580             :   // but then the result is not cached.
    1581      657723 :   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
    1582             : 
    1583     1973169 :   Result = intersect(LocalResult, InBlock);
    1584      657723 :   return true;
    1585             : }
    1586             : 
    1587      414873 : LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
    1588             :                                                   Instruction *CxtI) {
    1589             :   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
    1590             :         << BB->getName() << "'\n");
    1591             : 
    1592             :   assert(BlockValueStack.empty() && BlockValueSet.empty());
    1593      829727 :   if (!hasBlockValue(V, BB)) {
    1594      638012 :     pushBlockValue(std::make_pair(BB, V));
    1595      319006 :     solve();
    1596             :   }
    1597      414873 :   LVILatticeVal Result = getBlockValue(V, BB);
    1598      414873 :   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
    1599             : 
    1600             :   DEBUG(dbgs() << "  Result = " << Result << "\n");
    1601      414873 :   return Result;
    1602             : }
    1603             : 
    1604      148925 : LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
    1605             :   DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
    1606             :         << CxtI->getName() << "'\n");
    1607             : 
    1608          27 :   if (auto *C = dyn_cast<Constant>(V))
    1609          27 :     return LVILatticeVal::get(C);
    1610             : 
    1611      148898 :   LVILatticeVal Result = LVILatticeVal::getOverdefined();
    1612      116317 :   if (auto *I = dyn_cast<Instruction>(V))
    1613      348951 :     Result = getFromRangeMetadata(I);
    1614      148898 :   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
    1615             : 
    1616             :   DEBUG(dbgs() << "  Result = " << Result << "\n");
    1617      148898 :   return Result;
    1618             : }
    1619             : 
    1620      212322 : LVILatticeVal LazyValueInfoImpl::
    1621             : getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
    1622             :                Instruction *CxtI) {
    1623             :   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
    1624             :         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
    1625             : 
    1626      212322 :   LVILatticeVal Result;
    1627      212322 :   if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
    1628      143778 :     solve();
    1629      143778 :     bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
    1630             :     (void)WasFastQuery;
    1631             :     assert(WasFastQuery && "More work to do after problem solved?");
    1632             :   }
    1633             : 
    1634             :   DEBUG(dbgs() << "  Result = " << Result << "\n");
    1635      212322 :   return Result;
    1636             : }
    1637             : 
    1638             : void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
    1639             :                                    BasicBlock *NewSucc) {
    1640        1294 :   TheCache.threadEdgeImpl(OldSucc, NewSucc);
    1641             : }
    1642             : 
    1643             : //===----------------------------------------------------------------------===//
    1644             : //                            LazyValueInfo Impl
    1645             : //===----------------------------------------------------------------------===//
    1646             : 
    1647             : /// This lazily constructs the LazyValueInfoImpl.
    1648      874362 : static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
    1649             :                                   const DataLayout *DL,
    1650             :                                   DominatorTree *DT = nullptr) {
    1651      874362 :   if (!PImpl) {
    1652             :     assert(DL && "getCache() called with a null DataLayout");
    1653      141934 :     PImpl = new LazyValueInfoImpl(AC, *DL, DT);
    1654             :   }
    1655      874362 :   return *static_cast<LazyValueInfoImpl*>(PImpl);
    1656             : }
    1657             : 
    1658      134988 : bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
    1659      134988 :   Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
    1660      134988 :   const DataLayout &DL = F.getParent()->getDataLayout();
    1661             : 
    1662             :   DominatorTreeWrapperPass *DTWP =
    1663      134988 :       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
    1664      168682 :   Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
    1665      269976 :   Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
    1666             : 
    1667      134988 :   if (Info.PImpl)
    1668           0 :     getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
    1669             : 
    1670             :   // Fully lazy.
    1671      134988 :   return false;
    1672             : }
    1673             : 
    1674        4012 : void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
    1675        8024 :   AU.setPreservesAll();
    1676        4012 :   AU.addRequired<AssumptionCacheTracker>();
    1677        4012 :   AU.addRequired<TargetLibraryInfoWrapperPass>();
    1678        4012 : }
    1679             : 
    1680      134756 : LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
    1681             : 
    1682        4630 : LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
    1683             : 
    1684      139618 : void LazyValueInfo::releaseMemory() {
    1685             :   // If the cache was allocated, free it.
    1686      139618 :   if (PImpl) {
    1687       70967 :     delete &getImpl(PImpl, AC, nullptr);
    1688       70967 :     PImpl = nullptr;
    1689             :   }
    1690      139618 : }
    1691             : 
    1692         155 : bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
    1693             :                                FunctionAnalysisManager::Invalidator &Inv) {
    1694             :   // We need to invalidate if we have either failed to preserve this analyses
    1695             :   // result directly or if any of its dependencies have been invalidated.
    1696         155 :   auto PAC = PA.getChecker<LazyValueAnalysis>();
    1697         158 :   if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
    1698           4 :       (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
    1699             :     return true;
    1700             : 
    1701             :   return false;
    1702             : }
    1703             : 
    1704      134988 : void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
    1705             : 
    1706         206 : LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
    1707         206 :   auto &AC = FAM.getResult<AssumptionAnalysis>(F);
    1708         206 :   auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
    1709         206 :   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
    1710             : 
    1711         412 :   return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
    1712             : }
    1713             : 
    1714             : /// Returns true if we can statically tell that this value will never be a
    1715             : /// "useful" constant.  In practice, this means we've got something like an
    1716             : /// alloca or a malloc call for which a comparison against a constant can
    1717             : /// only be guarding dead code.  Note that we are potentially giving up some
    1718             : /// precision in dead code (a constant result) in favour of avoiding a
    1719             : /// expensive search for a easily answered common query.
    1720             : static bool isKnownNonConstant(Value *V) {
    1721      890630 :   V = V->stripPointerCasts();
    1722             :   // The return val of alloc cannot be a Constant.
    1723      445315 :   if (isa<AllocaInst>(V))
    1724             :     return true;
    1725             :   return false;
    1726             : }
    1727             : 
    1728      445315 : Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
    1729             :                                      Instruction *CxtI) {
    1730             :   // Bail out early if V is known not to be a Constant.
    1731             :   if (isKnownNonConstant(V))
    1732             :     return nullptr;
    1733             : 
    1734      414728 :   const DataLayout &DL = BB->getModule()->getDataLayout();
    1735             :   LVILatticeVal Result =
    1736      414728 :       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
    1737             : 
    1738      414728 :   if (Result.isConstant())
    1739           1 :     return Result.getConstant();
    1740      414727 :   if (Result.isConstantRange()) {
    1741        9832 :     const ConstantRange &CR = Result.getConstantRange();
    1742        9832 :     if (const APInt *SingleVal = CR.getSingleElement())
    1743          42 :       return ConstantInt::get(V->getContext(), *SingleVal);
    1744             :   }
    1745             :   return nullptr;
    1746             : }
    1747             : 
    1748          38 : ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
    1749             :                                               Instruction *CxtI) {
    1750             :   assert(V->getType()->isIntegerTy());
    1751          76 :   unsigned Width = V->getType()->getIntegerBitWidth();
    1752          38 :   const DataLayout &DL = BB->getModule()->getDataLayout();
    1753             :   LVILatticeVal Result =
    1754          76 :       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
    1755          38 :   if (Result.isUndefined())
    1756           0 :     return ConstantRange(Width, /*isFullSet=*/false);
    1757          38 :   if (Result.isConstantRange())
    1758          33 :     return Result.getConstantRange();
    1759             :   // We represent ConstantInt constants as constant ranges but other kinds
    1760             :   // of integer constants, i.e. ConstantExpr will be tagged as constants
    1761             :   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
    1762             :          "ConstantInt value must be represented as constantrange");
    1763           5 :   return ConstantRange(Width, /*isFullSet=*/true);
    1764             : }
    1765             : 
    1766             : /// Determine whether the specified value is known to be a
    1767             : /// constant on the specified edge. Return null if not.
    1768      157214 : Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
    1769             :                                            BasicBlock *ToBB,
    1770             :                                            Instruction *CxtI) {
    1771      157214 :   const DataLayout &DL = FromBB->getModule()->getDataLayout();
    1772             :   LVILatticeVal Result =
    1773      314428 :       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
    1774             : 
    1775      157214 :   if (Result.isConstant())
    1776          35 :     return Result.getConstant();
    1777      157179 :   if (Result.isConstantRange()) {
    1778       13256 :     const ConstantRange &CR = Result.getConstantRange();
    1779       13256 :     if (const APInt *SingleVal = CR.getSingleElement())
    1780        1472 :       return ConstantInt::get(V->getContext(), *SingleVal);
    1781             :   }
    1782             :   return nullptr;
    1783             : }
    1784             : 
    1785        1800 : ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
    1786             :                                                     BasicBlock *FromBB,
    1787             :                                                     BasicBlock *ToBB,
    1788             :                                                     Instruction *CxtI) {
    1789        3600 :   unsigned Width = V->getType()->getIntegerBitWidth();
    1790        1800 :   const DataLayout &DL = FromBB->getModule()->getDataLayout();
    1791             :   LVILatticeVal Result =
    1792        3600 :       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
    1793             : 
    1794        1800 :   if (Result.isUndefined())
    1795           0 :     return ConstantRange(Width, /*isFullSet=*/false);
    1796        1800 :   if (Result.isConstantRange())
    1797        1398 :     return Result.getConstantRange();
    1798             :   // We represent ConstantInt constants as constant ranges but other kinds
    1799             :   // of integer constants, i.e. ConstantExpr will be tagged as constants
    1800             :   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
    1801             :          "ConstantInt value must be represented as constantrange");
    1802         402 :   return ConstantRange(Width, /*isFullSet=*/true);
    1803             : }
    1804             : 
    1805      202233 : static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
    1806             :                                                   const LVILatticeVal &Val,
    1807             :                                                   const DataLayout &DL,
    1808             :                                                   TargetLibraryInfo *TLI) {
    1809             : 
    1810             :   // If we know the value is a constant, evaluate the conditional.
    1811      202233 :   Constant *Res = nullptr;
    1812      202233 :   if (Val.isConstant()) {
    1813        1101 :     Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
    1814        1099 :     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
    1815        1099 :       return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
    1816             :     return LazyValueInfo::Unknown;
    1817             :   }
    1818             : 
    1819      201132 :   if (Val.isConstantRange()) {
    1820       24622 :     ConstantInt *CI = dyn_cast<ConstantInt>(C);
    1821             :     if (!CI) return LazyValueInfo::Unknown;
    1822             : 
    1823       24622 :     const ConstantRange &CR = Val.getConstantRange();
    1824       24622 :     if (Pred == ICmpInst::ICMP_EQ) {
    1825        7988 :       if (!CR.contains(CI->getValue()))
    1826             :         return LazyValueInfo::False;
    1827             : 
    1828        6516 :       if (CR.isSingleElement())
    1829             :         return LazyValueInfo::True;
    1830       16634 :     } else if (Pred == ICmpInst::ICMP_NE) {
    1831        8350 :       if (!CR.contains(CI->getValue()))
    1832             :         return LazyValueInfo::True;
    1833             : 
    1834        8245 :       if (CR.isSingleElement())
    1835             :         return LazyValueInfo::False;
    1836             :     } else {
    1837             :       // Handle more complex predicates.
    1838             :       ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
    1839       14640 :           (ICmpInst::Predicate)Pred, CI->getValue());
    1840        8284 :       if (TrueValues.contains(CR))
    1841        1928 :         return LazyValueInfo::True;
    1842        6566 :       if (TrueValues.inverse().contains(CR))
    1843             :         return LazyValueInfo::False;
    1844             :     }
    1845             :     return LazyValueInfo::Unknown;
    1846             :   }
    1847             : 
    1848      176502 :   if (Val.isNotConstant()) {
    1849             :     // If this is an equality comparison, we can try to fold it knowing that
    1850             :     // "V != C1".
    1851        2422 :     if (Pred == ICmpInst::ICMP_EQ) {
    1852             :       // !C1 == C -> false iff C1 == C.
    1853        2081 :       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
    1854             :                                             Val.getNotConstant(), C, DL,
    1855             :                                             TLI);
    1856        2081 :       if (Res->isNullValue())
    1857             :         return LazyValueInfo::False;
    1858         341 :     } else if (Pred == ICmpInst::ICMP_NE) {
    1859             :       // !C1 != C -> true iff C1 == C.
    1860         263 :       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
    1861             :                                             Val.getNotConstant(), C, DL,
    1862             :                                             TLI);
    1863         263 :       if (Res->isNullValue())
    1864             :         return LazyValueInfo::True;
    1865             :     }
    1866             :     return LazyValueInfo::Unknown;
    1867             :   }
    1868             : 
    1869             :   return LazyValueInfo::Unknown;
    1870             : }
    1871             : 
    1872             : /// Determine whether the specified value comparison with a constant is known to
    1873             : /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
    1874             : LazyValueInfo::Tristate
    1875       53308 : LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
    1876             :                                   BasicBlock *FromBB, BasicBlock *ToBB,
    1877             :                                   Instruction *CxtI) {
    1878       53308 :   const DataLayout &DL = FromBB->getModule()->getDataLayout();
    1879             :   LVILatticeVal Result =
    1880      106616 :       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
    1881             : 
    1882      106616 :   return getPredicateResult(Pred, C, Result, DL, TLI);
    1883             : }
    1884             : 
    1885             : LazyValueInfo::Tristate
    1886      188275 : LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
    1887             :                               Instruction *CxtI) {
    1888             :   // Is or is not NonNull are common predicates being queried. If
    1889             :   // isKnownNonZero can tell us the result of the predicate, we can
    1890             :   // return it quickly. But this is only a fastpath, and falling
    1891             :   // through would still be correct.
    1892      188275 :   const DataLayout &DL = CxtI->getModule()->getDataLayout();
    1893      519324 :   if (V->getType()->isPointerTy() && C->isNullValue() &&
    1894      285548 :       isKnownNonZero(V->stripPointerCasts(), DL)) {
    1895       39350 :     if (Pred == ICmpInst::ICMP_EQ)
    1896             :       return LazyValueInfo::False;
    1897           1 :     else if (Pred == ICmpInst::ICMP_NE)
    1898             :       return LazyValueInfo::True;
    1899             :   }
    1900      148925 :   LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
    1901      148925 :   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
    1902      148925 :   if (Ret != Unknown)
    1903             :     return Ret;
    1904             : 
    1905             :   // Note: The following bit of code is somewhat distinct from the rest of LVI;
    1906             :   // LVI as a whole tries to compute a lattice value which is conservatively
    1907             :   // correct at a given location.  In this case, we have a predicate which we
    1908             :   // weren't able to prove about the merged result, and we're pushing that
    1909             :   // predicate back along each incoming edge to see if we can prove it
    1910             :   // separately for each input.  As a motivating example, consider:
    1911             :   // bb1:
    1912             :   //   %v1 = ... ; constantrange<1, 5>
    1913             :   //   br label %merge
    1914             :   // bb2:
    1915             :   //   %v2 = ... ; constantrange<10, 20>
    1916             :   //   br label %merge
    1917             :   // merge:
    1918             :   //   %phi = phi [%v1, %v2] ; constantrange<1,20>
    1919             :   //   %pred = icmp eq i32 %phi, 8
    1920             :   // We can't tell from the lattice value for '%phi' that '%pred' is false
    1921             :   // along each path, but by checking the predicate over each input separately,
    1922             :   // we can.
    1923             :   // We limit the search to one step backwards from the current BB and value.
    1924             :   // We could consider extending this to search further backwards through the
    1925             :   // CFG and/or value graph, but there are non-obvious compile time vs quality
    1926             :   // tradeoffs.
    1927      148879 :   if (CxtI) {
    1928      148879 :     BasicBlock *BB = CxtI->getParent();
    1929             : 
    1930             :     // Function entry or an unreachable block.  Bail to avoid confusing
    1931             :     // analysis below.
    1932      297758 :     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
    1933      148879 :     if (PI == PE)
    1934       34073 :       return Unknown;
    1935             : 
    1936             :     // If V is a PHI node in the same block as the context, we need to ask
    1937             :     // questions about the predicate as applied to the incoming value along
    1938             :     // each edge. This is useful for eliminating cases where the predicate is
    1939             :     // known along all incoming edges.
    1940      128010 :     if (auto *PHI = dyn_cast<PHINode>(V))
    1941       11426 :       if (PHI->getParent() == BB) {
    1942        8012 :         Tristate Baseline = Unknown;
    1943       19189 :         for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
    1944       11101 :           Value *Incoming = PHI->getIncomingValue(i);
    1945       11101 :           BasicBlock *PredBB = PHI->getIncomingBlock(i);
    1946             :           // Note that PredBB may be BB itself.
    1947             :           Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
    1948       11101 :                                                CxtI);
    1949             : 
    1950             :           // Keep going as long as we've seen a consistent known result for
    1951             :           // all inputs.
    1952       19213 :           Baseline = (i == 0) ? Result /* First iteration */
    1953        3089 :             : (Baseline == Result ? Baseline : Unknown); /* All others */
    1954        8112 :           if (Baseline == Unknown)
    1955             :             break;
    1956             :         }
    1957        8012 :         if (Baseline != Unknown)
    1958             :           return Baseline;
    1959             :       }
    1960             : 
    1961             :     // For a comparison where the V is outside this block, it's possible
    1962             :     // that we've branched on it before. Look to see if the value is known
    1963             :     // on all incoming edges.
    1964      334713 :     if (!isa<Instruction>(V) ||
    1965      203394 :         cast<Instruction>(V)->getParent() != BB) {
    1966             :       // For predecessor edge, determine if the comparison is true or false
    1967             :       // on that edge. If they're all true or all false, we can conclude
    1968             :       // the value of the comparison in this block.
    1969       29758 :       Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
    1970       29758 :       if (Baseline != Unknown) {
    1971             :         // Check that all remaining incoming values match the first one.
    1972        4938 :         while (++PI != PE) {
    1973         767 :           Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
    1974         767 :           if (Ret != Baseline) break;
    1975             :         }
    1976             :         // If we terminated early, then one of the values didn't match.
    1977        2147 :         if (PI == PE) {
    1978             :           return Baseline;
    1979             :         }
    1980             :       }
    1981             :     }
    1982             :   }
    1983             :   return Unknown;
    1984             : }
    1985             : 
    1986        1297 : void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
    1987             :                                BasicBlock *NewSucc) {
    1988        1297 :   if (PImpl) {
    1989        1294 :     const DataLayout &DL = PredBB->getModule()->getDataLayout();
    1990        1294 :     getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
    1991             :   }
    1992        1297 : }
    1993             : 
    1994       33924 : void LazyValueInfo::eraseBlock(BasicBlock *BB) {
    1995       33924 :   if (PImpl) {
    1996       26084 :     const DataLayout &DL = BB->getModule()->getDataLayout();
    1997       26084 :     getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
    1998             :   }
    1999       33924 : }
    2000             : 
    2001             : 
    2002           4 : void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
    2003           4 :   if (PImpl) {
    2004           4 :     getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
    2005             :   }
    2006           4 : }
    2007             : 
    2008             : // Print the LVI for the function arguments at the start of each basic block.
    2009          16 : void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
    2010             :     const BasicBlock *BB, formatted_raw_ostream &OS) {
    2011             :   // Find if there are latticevalues defined for arguments of the function.
    2012          16 :   auto *F = BB->getParent();
    2013          53 :   for (auto &Arg : F->args()) {
    2014          37 :     LVILatticeVal Result = LVIImpl->getValueInBlock(
    2015          74 :         const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
    2016          37 :     if (Result.isUndefined())
    2017           0 :       continue;
    2018          74 :     OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
    2019             :   }
    2020          16 : }
    2021             : 
    2022             : // This function prints the LVI analysis for the instruction I at the beginning
    2023             : // of various basic blocks. It relies on calculated values that are stored in
    2024             : // the LazyValueInfoCache, and in the absence of cached values, recalculte the
    2025             : // LazyValueInfo for `I`, and print that info.
    2026          43 : void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
    2027             :     const Instruction *I, formatted_raw_ostream &OS) {
    2028             : 
    2029          43 :   auto *ParentBB = I->getParent();
    2030          86 :   SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
    2031             :   // We can generate (solve) LVI values only for blocks that are dominated by
    2032             :   // the I's parent. However, to avoid generating LVI for all dominating blocks,
    2033             :   // that contain redundant/uninteresting information, we print LVI for
    2034             :   // blocks that may use this LVI information (such as immediate successor
    2035             :   // blocks, and blocks that contain uses of `I`).
    2036         102 :   auto printResult = [&](const BasicBlock *BB) {
    2037         102 :     if (!BlocksContainingLVI.insert(BB).second)
    2038          32 :       return;
    2039          70 :     LVILatticeVal Result = LVIImpl->getValueInBlock(
    2040         210 :         const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
    2041         350 :       OS << "; LatticeVal for: '" << *I << "' in BB: '";
    2042         140 :       BB->printAsOperand(OS, false);
    2043          70 :       OS << "' is: " << Result << "\n";
    2044          43 :   };
    2045             : 
    2046          43 :   printResult(ParentBB);
    2047             :   // Print the LVI analysis results for the the immediate successor blocks, that
    2048             :   // are dominated by `ParentBB`.
    2049         234 :   for (auto *BBSucc : successors(ParentBB))
    2050          74 :     if (DT.dominates(ParentBB, BBSucc))
    2051          35 :       printResult(BBSucc);
    2052             : 
    2053             :   // Print LVI in blocks where `I` is used.
    2054         181 :   for (auto *U : I->users())
    2055          26 :     if (auto *UseI = dyn_cast<Instruction>(U))
    2056          52 :       if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
    2057          24 :         printResult(UseI->getParent());
    2058             : 
    2059          43 : }
    2060             : 
    2061             : namespace {
    2062             : // Printer class for LazyValueInfo results.
    2063           0 : class LazyValueInfoPrinter : public FunctionPass {
    2064             : public:
    2065             :   static char ID; // Pass identification, replacement for typeid
    2066           0 :   LazyValueInfoPrinter() : FunctionPass(ID) {
    2067           0 :     initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
    2068             :   }
    2069             : 
    2070           0 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
    2071           0 :     AU.setPreservesAll();
    2072           0 :     AU.addRequired<LazyValueInfoWrapperPass>();
    2073           0 :     AU.addRequired<DominatorTreeWrapperPass>();
    2074           0 :   }
    2075             : 
    2076             :   // Get the mandatory dominator tree analysis and pass this in to the
    2077             :   // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
    2078           0 :   bool runOnFunction(Function &F) override {
    2079           0 :     dbgs() << "LVI for function '" << F.getName() << "':\n";
    2080           0 :     auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
    2081           0 :     auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    2082           0 :     LVI.printLVI(F, DTree, dbgs());
    2083           0 :     return false;
    2084             :   }
    2085             : };
    2086             : }
    2087             : 
    2088             : char LazyValueInfoPrinter::ID = 0;
    2089        9158 : INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
    2090             :                 "Lazy Value Info Printer Pass", false, false)
    2091        9158 : INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
    2092       45790 : INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
    2093             :                 "Lazy Value Info Printer Pass", false, false)

Generated by: LCOV version 1.13