LLVM  mainline
LazyValueInfo.cpp
Go to the documentation of this file.
00001 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the interface for lazy computation of value constraint
00011 // information.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Analysis/LazyValueInfo.h"
00016 #include "llvm/ADT/DenseSet.h"
00017 #include "llvm/ADT/STLExtras.h"
00018 #include "llvm/Analysis/AssumptionCache.h"
00019 #include "llvm/Analysis/ConstantFolding.h"
00020 #include "llvm/Analysis/TargetLibraryInfo.h"
00021 #include "llvm/Analysis/ValueTracking.h"
00022 #include "llvm/IR/CFG.h"
00023 #include "llvm/IR/ConstantRange.h"
00024 #include "llvm/IR/Constants.h"
00025 #include "llvm/IR/DataLayout.h"
00026 #include "llvm/IR/Dominators.h"
00027 #include "llvm/IR/Instructions.h"
00028 #include "llvm/IR/IntrinsicInst.h"
00029 #include "llvm/IR/LLVMContext.h"
00030 #include "llvm/IR/PatternMatch.h"
00031 #include "llvm/IR/ValueHandle.h"
00032 #include "llvm/Support/Debug.h"
00033 #include "llvm/Support/raw_ostream.h"
00034 #include <map>
00035 #include <stack>
00036 using namespace llvm;
00037 using namespace PatternMatch;
00038 
00039 #define DEBUG_TYPE "lazy-value-info"
00040 
00041 char LazyValueInfo::ID = 0;
00042 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
00043                 "Lazy Value Information Analysis", false, true)
00044 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
00045 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
00046 INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info",
00047                 "Lazy Value Information Analysis", false, true)
00048 
00049 namespace llvm {
00050   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
00051 }
00052 
00053 
00054 //===----------------------------------------------------------------------===//
00055 //                               LVILatticeVal
00056 //===----------------------------------------------------------------------===//
00057 
00058 /// This is the information tracked by LazyValueInfo for each value.
00059 ///
00060 /// FIXME: This is basically just for bringup, this can be made a lot more rich
00061 /// in the future.
00062 ///
00063 namespace {
00064 class LVILatticeVal {
00065   enum LatticeValueTy {
00066     /// This Value has no known value yet.
00067     undefined,
00068 
00069     /// This Value has a specific constant value.
00070     constant,
00071 
00072     /// This Value is known to not have the specified value.
00073     notconstant,
00074 
00075     /// The Value falls within this range.
00076     constantrange,
00077 
00078     /// This value is not known to be constant, and we know that it has a value.
00079     overdefined
00080   };
00081 
00082   /// Val: This stores the current lattice value along with the Constant* for
00083   /// the constant if this is a 'constant' or 'notconstant' value.
00084   LatticeValueTy Tag;
00085   Constant *Val;
00086   ConstantRange Range;
00087 
00088 public:
00089   LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
00090 
00091   static LVILatticeVal get(Constant *C) {
00092     LVILatticeVal Res;
00093     if (!isa<UndefValue>(C))
00094       Res.markConstant(C);
00095     return Res;
00096   }
00097   static LVILatticeVal getNot(Constant *C) {
00098     LVILatticeVal Res;
00099     if (!isa<UndefValue>(C))
00100       Res.markNotConstant(C);
00101     return Res;
00102   }
00103   static LVILatticeVal getRange(ConstantRange CR) {
00104     LVILatticeVal Res;
00105     Res.markConstantRange(CR);
00106     return Res;
00107   }
00108   static LVILatticeVal getOverdefined() {
00109     LVILatticeVal Res;
00110     Res.markOverdefined();
00111     return Res;
00112   }
00113   
00114   bool isUndefined() const     { return Tag == undefined; }
00115   bool isConstant() const      { return Tag == constant; }
00116   bool isNotConstant() const   { return Tag == notconstant; }
00117   bool isConstantRange() const { return Tag == constantrange; }
00118   bool isOverdefined() const   { return Tag == overdefined; }
00119 
00120   Constant *getConstant() const {
00121     assert(isConstant() && "Cannot get the constant of a non-constant!");
00122     return Val;
00123   }
00124 
00125   Constant *getNotConstant() const {
00126     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
00127     return Val;
00128   }
00129 
00130   ConstantRange getConstantRange() const {
00131     assert(isConstantRange() &&
00132            "Cannot get the constant-range of a non-constant-range!");
00133     return Range;
00134   }
00135 
00136   /// Return true if this is a change in status.
00137   bool markOverdefined() {
00138     if (isOverdefined())
00139       return false;
00140     Tag = overdefined;
00141     return true;
00142   }
00143 
00144   /// Return true if this is a change in status.
00145   bool markConstant(Constant *V) {
00146     assert(V && "Marking constant with NULL");
00147     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
00148       return markConstantRange(ConstantRange(CI->getValue()));
00149     if (isa<UndefValue>(V))
00150       return false;
00151 
00152     assert((!isConstant() || getConstant() == V) &&
00153            "Marking constant with different value");
00154     assert(isUndefined());
00155     Tag = constant;
00156     Val = V;
00157     return true;
00158   }
00159 
00160   /// Return true if this is a change in status.
00161   bool markNotConstant(Constant *V) {
00162     assert(V && "Marking constant with NULL");
00163     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
00164       return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
00165     if (isa<UndefValue>(V))
00166       return false;
00167 
00168     assert((!isConstant() || getConstant() != V) &&
00169            "Marking constant !constant with same value");
00170     assert((!isNotConstant() || getNotConstant() == V) &&
00171            "Marking !constant with different value");
00172     assert(isUndefined() || isConstant());
00173     Tag = notconstant;
00174     Val = V;
00175     return true;
00176   }
00177 
00178   /// Return true if this is a change in status.
00179   bool markConstantRange(const ConstantRange NewR) {
00180     if (isConstantRange()) {
00181       if (NewR.isEmptySet())
00182         return markOverdefined();
00183 
00184       bool changed = Range != NewR;
00185       Range = NewR;
00186       return changed;
00187     }
00188 
00189     assert(isUndefined());
00190     if (NewR.isEmptySet())
00191       return markOverdefined();
00192 
00193     Tag = constantrange;
00194     Range = NewR;
00195     return true;
00196   }
00197 
00198   /// Merge the specified lattice value into this one, updating this
00199   /// one and returning true if anything changed.
00200   bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
00201     if (RHS.isUndefined() || isOverdefined()) return false;
00202     if (RHS.isOverdefined()) return markOverdefined();
00203 
00204     if (isUndefined()) {
00205       Tag = RHS.Tag;
00206       Val = RHS.Val;
00207       Range = RHS.Range;
00208       return true;
00209     }
00210 
00211     if (isConstant()) {
00212       if (RHS.isConstant()) {
00213         if (Val == RHS.Val)
00214           return false;
00215         return markOverdefined();
00216       }
00217 
00218       if (RHS.isNotConstant()) {
00219         if (Val == RHS.Val)
00220           return markOverdefined();
00221 
00222         // Unless we can prove that the two Constants are different, we must
00223         // move to overdefined.
00224         if (ConstantInt *Res =
00225                 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
00226                     CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL)))
00227           if (Res->isOne())
00228             return markNotConstant(RHS.getNotConstant());
00229 
00230         return markOverdefined();
00231       }
00232 
00233       // RHS is a ConstantRange, LHS is a non-integer Constant.
00234 
00235       // FIXME: consider the case where RHS is a range [1, 0) and LHS is
00236       // a function. The correct result is to pick up RHS.
00237 
00238       return markOverdefined();
00239     }
00240 
00241     if (isNotConstant()) {
00242       if (RHS.isConstant()) {
00243         if (Val == RHS.Val)
00244           return markOverdefined();
00245 
00246         // Unless we can prove that the two Constants are different, we must
00247         // move to overdefined.
00248         if (ConstantInt *Res =
00249                 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
00250                     CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL)))
00251           if (Res->isOne())
00252             return false;
00253 
00254         return markOverdefined();
00255       }
00256 
00257       if (RHS.isNotConstant()) {
00258         if (Val == RHS.Val)
00259           return false;
00260         return markOverdefined();
00261       }
00262 
00263       return markOverdefined();
00264     }
00265 
00266     assert(isConstantRange() && "New LVILattice type?");
00267     if (!RHS.isConstantRange())
00268       return markOverdefined();
00269 
00270     ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
00271     if (NewR.isFullSet())
00272       return markOverdefined();
00273     return markConstantRange(NewR);
00274   }
00275 };
00276 
00277 } // end anonymous namespace.
00278 
00279 namespace llvm {
00280 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
00281     LLVM_ATTRIBUTE_USED;
00282 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
00283   if (Val.isUndefined())
00284     return OS << "undefined";
00285   if (Val.isOverdefined())
00286     return OS << "overdefined";
00287 
00288   if (Val.isNotConstant())
00289     return OS << "notconstant<" << *Val.getNotConstant() << '>';
00290   else if (Val.isConstantRange())
00291     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
00292               << Val.getConstantRange().getUpper() << '>';
00293   return OS << "constant<" << *Val.getConstant() << '>';
00294 }
00295 }
00296 
00297 //===----------------------------------------------------------------------===//
00298 //                          LazyValueInfoCache Decl
00299 //===----------------------------------------------------------------------===//
00300 
00301 namespace {
00302   /// A callback value handle updates the cache when values are erased.
00303   class LazyValueInfoCache;
00304   struct LVIValueHandle final : public CallbackVH {
00305     LazyValueInfoCache *Parent;
00306 
00307     LVIValueHandle(Value *V, LazyValueInfoCache *P)
00308       : CallbackVH(V), Parent(P) { }
00309 
00310     void deleted() override;
00311     void allUsesReplacedWith(Value *V) override {
00312       deleted();
00313     }
00314   };
00315 }
00316 
00317 namespace {
00318   /// This is the cache kept by LazyValueInfo which
00319   /// maintains information about queries across the clients' queries.
00320   class LazyValueInfoCache {
00321     /// This is all of the cached block information for exactly one Value*.
00322     /// The entries are sorted by the BasicBlock* of the
00323     /// entries, allowing us to do a lookup with a binary search.
00324     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
00325     /// memory overhead.
00326     typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
00327         ValueCacheEntryTy;
00328 
00329     /// This is all of the cached information for all values,
00330     /// mapped from Value* to key information.
00331     std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
00332 
00333     /// This tracks, on a per-block basis, the set of values that are
00334     /// over-defined at the end of that block.
00335     typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
00336         OverDefinedCacheTy;
00337     OverDefinedCacheTy OverDefinedCache;
00338 
00339     /// Keep track of all blocks that we have ever seen, so we
00340     /// don't spend time removing unused blocks from our caches.
00341     DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
00342 
00343     /// This stack holds the state of the value solver during a query.
00344     /// It basically emulates the callstack of the naive
00345     /// recursive value lookup process.
00346     std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
00347 
00348     /// Keeps track of which block-value pairs are in BlockValueStack.
00349     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
00350 
00351     /// Push BV onto BlockValueStack unless it's already in there.
00352     /// Returns true on success.
00353     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
00354       if (!BlockValueSet.insert(BV).second)
00355         return false;  // It's already in the stack.
00356 
00357       BlockValueStack.push(BV);
00358       return true;
00359     }
00360 
00361     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
00362     const DataLayout &DL; ///< A mandatory DataLayout
00363     DominatorTree *DT;    ///< An optional DT pointer.
00364 
00365     friend struct LVIValueHandle;
00366 
00367     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
00368       SeenBlocks.insert(BB);
00369 
00370       // Insert over-defined values into their own cache to reduce memory
00371       // overhead.
00372       if (Result.isOverdefined())
00373         OverDefinedCache[BB].insert(Val);
00374       else
00375         lookup(Val)[BB] = Result;
00376     }
00377 
00378     LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
00379     bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
00380                       LVILatticeVal &Result,
00381                       Instruction *CxtI = nullptr);
00382     bool hasBlockValue(Value *Val, BasicBlock *BB);
00383 
00384     // These methods process one work item and may add more. A false value
00385     // returned means that the work item was not completely processed and must
00386     // be revisited after going through the new items.
00387     bool solveBlockValue(Value *Val, BasicBlock *BB);
00388     bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
00389                                  Value *Val, BasicBlock *BB);
00390     bool solveBlockValuePHINode(LVILatticeVal &BBLV,
00391                                 PHINode *PN, BasicBlock *BB);
00392     bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
00393                                       Instruction *BBI, BasicBlock *BB);
00394     void mergeAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
00395                                             Instruction *BBI);
00396 
00397     void solve();
00398 
00399     ValueCacheEntryTy &lookup(Value *V) {
00400       return ValueCache[LVIValueHandle(V, this)];
00401     }
00402 
00403     bool isOverdefined(Value *V, BasicBlock *BB) const {
00404       auto ODI = OverDefinedCache.find(BB);
00405 
00406       if (ODI == OverDefinedCache.end())
00407         return false;
00408 
00409       return ODI->second.count(V);
00410     }
00411 
00412     bool hasCachedValueInfo(Value *V, BasicBlock *BB) {
00413       if (isOverdefined(V, BB))
00414         return true;
00415 
00416       LVIValueHandle ValHandle(V, this);
00417       auto I = ValueCache.find(ValHandle);
00418       if (I == ValueCache.end())
00419         return false;
00420 
00421       return I->second.count(BB);
00422     }
00423 
00424     LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
00425       if (isOverdefined(V, BB))
00426         return LVILatticeVal::getOverdefined();
00427 
00428       return lookup(V)[BB];
00429     }
00430     
00431   public:
00432     /// This is the query interface to determine the lattice
00433     /// value for the specified Value* at the end of the specified block.
00434     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
00435                                   Instruction *CxtI = nullptr);
00436 
00437     /// This is the query interface to determine the lattice
00438     /// value for the specified Value* at the specified instruction (generally
00439     /// from an assume intrinsic).
00440     LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
00441 
00442     /// This is the query interface to determine the lattice
00443     /// value for the specified Value* that is true on the specified edge.
00444     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
00445                                  Instruction *CxtI = nullptr);
00446 
00447     /// This is the update interface to inform the cache that an edge from
00448     /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
00449     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
00450 
00451     /// This is part of the update interface to inform the cache
00452     /// that a block has been deleted.
00453     void eraseBlock(BasicBlock *BB);
00454 
00455     /// clear - Empty the cache.
00456     void clear() {
00457       SeenBlocks.clear();
00458       ValueCache.clear();
00459       OverDefinedCache.clear();
00460     }
00461 
00462     LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL,
00463                        DominatorTree *DT = nullptr)
00464         : AC(AC), DL(DL), DT(DT) {}
00465   };
00466 } // end anonymous namespace
00467 
00468 void LVIValueHandle::deleted() {
00469   SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
00470   for (auto &I : Parent->OverDefinedCache) {
00471     SmallPtrSetImpl<Value *> &ValueSet = I.second;
00472     if (ValueSet.count(getValPtr()))
00473       ValueSet.erase(getValPtr());
00474     if (ValueSet.empty())
00475       ToErase.push_back(I.first);
00476   }
00477   for (auto &BB : ToErase)
00478     Parent->OverDefinedCache.erase(BB);
00479 
00480   // This erasure deallocates *this, so it MUST happen after we're done
00481   // using any and all members of *this.
00482   Parent->ValueCache.erase(*this);
00483 }
00484 
00485 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
00486   // Shortcut if we have never seen this block.
00487   DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
00488   if (I == SeenBlocks.end())
00489     return;
00490   SeenBlocks.erase(I);
00491 
00492   auto ODI = OverDefinedCache.find(BB);
00493   if (ODI != OverDefinedCache.end())
00494     OverDefinedCache.erase(ODI);
00495 
00496   for (auto I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
00497     I->second.erase(BB);
00498 }
00499 
00500 void LazyValueInfoCache::solve() {
00501   while (!BlockValueStack.empty()) {
00502     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
00503     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
00504 
00505     if (solveBlockValue(e.second, e.first)) {
00506       // The work item was completely processed.
00507       assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
00508       assert(hasCachedValueInfo(e.second, e.first) &&
00509              "Result should be in cache!");
00510 
00511       BlockValueStack.pop();
00512       BlockValueSet.erase(e);
00513     } else {
00514       // More work needs to be done before revisiting.
00515       assert(BlockValueStack.top() != e && "Stack should have been pushed!");
00516     }
00517   }
00518 }
00519 
00520 bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
00521   // If already a constant, there is nothing to compute.
00522   if (isa<Constant>(Val))
00523     return true;
00524 
00525   return hasCachedValueInfo(Val, BB);
00526 }
00527 
00528 LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
00529   // If already a constant, there is nothing to compute.
00530   if (Constant *VC = dyn_cast<Constant>(Val))
00531     return LVILatticeVal::get(VC);
00532 
00533   SeenBlocks.insert(BB);
00534   return getCachedValueInfo(Val, BB);
00535 }
00536 
00537 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
00538   switch (BBI->getOpcode()) {
00539   default: break;
00540   case Instruction::Load:
00541   case Instruction::Call:
00542   case Instruction::Invoke:
00543     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) 
00544       if (isa<IntegerType>(BBI->getType())) {
00545         ConstantRange Result = getConstantRangeFromMetadata(*Ranges);
00546         return LVILatticeVal::getRange(Result);
00547       }
00548     break;
00549   };
00550   // Nothing known - Note that we do not want overdefined here.  We may know
00551   // something else about the value and not having range metadata shouldn't
00552   // cause us to throw away those facts.
00553   return LVILatticeVal();
00554 }
00555 
00556 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
00557   if (isa<Constant>(Val))
00558     return true;
00559 
00560   if (hasCachedValueInfo(Val, BB)) {
00561     // If we have a cached value, use that.
00562     DEBUG(dbgs() << "  reuse BB '" << BB->getName()
00563                  << "' val=" << getCachedValueInfo(Val, BB) << '\n');
00564 
00565     // Since we're reusing a cached value, we don't need to update the
00566     // OverDefinedCache. The cache will have been properly updated whenever the
00567     // cached value was inserted.
00568     return true;
00569   }
00570 
00571   // Hold off inserting this value into the Cache in case we have to return
00572   // false and come back later.
00573   LVILatticeVal Res;
00574 
00575   Instruction *BBI = dyn_cast<Instruction>(Val);
00576   if (!BBI || BBI->getParent() != BB) {
00577     if (!solveBlockValueNonLocal(Res, Val, BB))
00578       return false;
00579    insertResult(Val, BB, Res);
00580    return true;
00581   }
00582 
00583   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
00584     if (!solveBlockValuePHINode(Res, PN, BB))
00585       return false;
00586     insertResult(Val, BB, Res);
00587     return true;
00588   }
00589 
00590   // If this value is a nonnull pointer, record it's range and bailout.
00591   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
00592   if (PT && isKnownNonNull(BBI)) {
00593     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
00594     insertResult(Val, BB, Res);
00595     return true;
00596   }
00597 
00598   // If this is an instruction which supports range metadata, return the
00599   // implied range.  TODO: This should be an intersection, not a union.
00600   Res.mergeIn(getFromRangeMetadata(BBI), DL);
00601 
00602   // We can only analyze the definitions of certain classes of instructions
00603   // (integral binops and casts at the moment), so bail if this isn't one.
00604   LVILatticeVal Result;
00605   if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
00606      !BBI->getType()->isIntegerTy()) {
00607     DEBUG(dbgs() << " compute BB '" << BB->getName()
00608                  << "' - overdefined because inst def found.\n");
00609     Res.markOverdefined();
00610     insertResult(Val, BB, Res);
00611     return true;
00612   }
00613 
00614   // FIXME: We're currently limited to binops with a constant RHS.  This should
00615   // be improved.
00616   BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
00617   if (BO && !isa<ConstantInt>(BO->getOperand(1))) { 
00618     DEBUG(dbgs() << " compute BB '" << BB->getName()
00619                  << "' - overdefined because inst def found.\n");
00620 
00621     Res.markOverdefined();
00622     insertResult(Val, BB, Res);
00623     return true;
00624   }
00625 
00626   if (!solveBlockValueConstantRange(Res, BBI, BB))
00627     return false;
00628   insertResult(Val, BB, Res);
00629   return true;
00630 }
00631 
00632 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
00633   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
00634     return L->getPointerAddressSpace() == 0 &&
00635            GetUnderlyingObject(L->getPointerOperand(),
00636                                L->getModule()->getDataLayout()) == Ptr;
00637   }
00638   if (StoreInst *S = dyn_cast<StoreInst>(I)) {
00639     return S->getPointerAddressSpace() == 0 &&
00640            GetUnderlyingObject(S->getPointerOperand(),
00641                                S->getModule()->getDataLayout()) == Ptr;
00642   }
00643   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
00644     if (MI->isVolatile()) return false;
00645 
00646     // FIXME: check whether it has a valuerange that excludes zero?
00647     ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
00648     if (!Len || Len->isZero()) return false;
00649 
00650     if (MI->getDestAddressSpace() == 0)
00651       if (GetUnderlyingObject(MI->getRawDest(),
00652                               MI->getModule()->getDataLayout()) == Ptr)
00653         return true;
00654     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
00655       if (MTI->getSourceAddressSpace() == 0)
00656         if (GetUnderlyingObject(MTI->getRawSource(),
00657                                 MTI->getModule()->getDataLayout()) == Ptr)
00658           return true;
00659   }
00660   return false;
00661 }
00662 
00663 bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
00664                                                  Value *Val, BasicBlock *BB) {
00665   LVILatticeVal Result;  // Start Undefined.
00666 
00667   // If this is a pointer, and there's a load from that pointer in this BB,
00668   // then we know that the pointer can't be NULL.
00669   bool NotNull = false;
00670   if (Val->getType()->isPointerTy()) {
00671     if (isKnownNonNull(Val)) {
00672       NotNull = true;
00673     } else {
00674       const DataLayout &DL = BB->getModule()->getDataLayout();
00675       Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
00676       // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
00677       // inside InstructionDereferencesPointer either.
00678       if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) {
00679         for (Instruction &I : *BB) {
00680           if (InstructionDereferencesPointer(&I, UnderlyingVal)) {
00681             NotNull = true;
00682             break;
00683           }
00684         }
00685       }
00686     }
00687   }
00688 
00689   // If this is the entry block, we must be asking about an argument.  The
00690   // value is overdefined.
00691   if (BB == &BB->getParent()->getEntryBlock()) {
00692     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
00693     if (NotNull) {
00694       PointerType *PTy = cast<PointerType>(Val->getType());
00695       Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
00696     } else {
00697       Result.markOverdefined();
00698     }
00699     BBLV = Result;
00700     return true;
00701   }
00702 
00703   // Loop over all of our predecessors, merging what we know from them into
00704   // result.
00705   bool EdgesMissing = false;
00706   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
00707     LVILatticeVal EdgeResult;
00708     EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
00709     if (EdgesMissing)
00710       continue;
00711 
00712     Result.mergeIn(EdgeResult, DL);
00713 
00714     // If we hit overdefined, exit early.  The BlockVals entry is already set
00715     // to overdefined.
00716     if (Result.isOverdefined()) {
00717       DEBUG(dbgs() << " compute BB '" << BB->getName()
00718             << "' - overdefined because of pred.\n");
00719       // If we previously determined that this is a pointer that can't be null
00720       // then return that rather than giving up entirely.
00721       if (NotNull) {
00722         PointerType *PTy = cast<PointerType>(Val->getType());
00723         Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
00724       }
00725 
00726       BBLV = Result;
00727       return true;
00728     }
00729   }
00730   if (EdgesMissing)
00731     return false;
00732 
00733   // Return the merged value, which is more precise than 'overdefined'.
00734   assert(!Result.isOverdefined());
00735   BBLV = Result;
00736   return true;
00737 }
00738 
00739 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
00740                                                 PHINode *PN, BasicBlock *BB) {
00741   LVILatticeVal Result;  // Start Undefined.
00742 
00743   // Loop over all of our predecessors, merging what we know from them into
00744   // result.
00745   bool EdgesMissing = false;
00746   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00747     BasicBlock *PhiBB = PN->getIncomingBlock(i);
00748     Value *PhiVal = PN->getIncomingValue(i);
00749     LVILatticeVal EdgeResult;
00750     // Note that we can provide PN as the context value to getEdgeValue, even
00751     // though the results will be cached, because PN is the value being used as
00752     // the cache key in the caller.
00753     EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
00754     if (EdgesMissing)
00755       continue;
00756 
00757     Result.mergeIn(EdgeResult, DL);
00758 
00759     // If we hit overdefined, exit early.  The BlockVals entry is already set
00760     // to overdefined.
00761     if (Result.isOverdefined()) {
00762       DEBUG(dbgs() << " compute BB '" << BB->getName()
00763             << "' - overdefined because of pred.\n");
00764 
00765       BBLV = Result;
00766       return true;
00767     }
00768   }
00769   if (EdgesMissing)
00770     return false;
00771 
00772   // Return the merged value, which is more precise than 'overdefined'.
00773   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
00774   BBLV = Result;
00775   return true;
00776 }
00777 
00778 static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
00779                                       LVILatticeVal &Result,
00780                                       bool isTrueDest = true);
00781 
00782 // If we can determine a constant range for the value Val in the context
00783 // provided by the instruction BBI, then merge it into BBLV. If we did find a
00784 // constant range, return true.
00785 void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val,
00786                                                             LVILatticeVal &BBLV,
00787                                                             Instruction *BBI) {
00788   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
00789   if (!BBI)
00790     return;
00791 
00792   for (auto &AssumeVH : AC->assumptions()) {
00793     if (!AssumeVH)
00794       continue;
00795     auto *I = cast<CallInst>(AssumeVH);
00796     if (!isValidAssumeForContext(I, BBI, DT))
00797       continue;
00798 
00799     Value *C = I->getArgOperand(0);
00800     if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) {
00801       LVILatticeVal Result;
00802       if (getValueFromFromCondition(Val, ICI, Result)) {
00803         if (BBLV.isOverdefined())
00804           BBLV = Result;
00805         else
00806           BBLV.mergeIn(Result, DL);
00807       }
00808     }
00809   }
00810 }
00811 
00812 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
00813                                                       Instruction *BBI,
00814                                                       BasicBlock *BB) {
00815   // Figure out the range of the LHS.  If that fails, bail.
00816   if (!hasBlockValue(BBI->getOperand(0), BB)) {
00817     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
00818       return false;
00819     BBLV.markOverdefined();
00820     return true;
00821   }
00822 
00823   LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
00824   mergeAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
00825   if (!LHSVal.isConstantRange()) {
00826     BBLV.markOverdefined();
00827     return true;
00828   }
00829 
00830   ConstantRange LHSRange = LHSVal.getConstantRange();
00831   ConstantRange RHSRange(1);
00832   IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
00833   if (isa<BinaryOperator>(BBI)) {
00834     if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
00835       RHSRange = ConstantRange(RHS->getValue());
00836     } else {
00837       BBLV.markOverdefined();
00838       return true;
00839     }
00840   }
00841 
00842   // NOTE: We're currently limited by the set of operations that ConstantRange
00843   // can evaluate symbolically.  Enhancing that set will allows us to analyze
00844   // more definitions.
00845   LVILatticeVal Result;
00846   switch (BBI->getOpcode()) {
00847   case Instruction::Add:
00848     Result.markConstantRange(LHSRange.add(RHSRange));
00849     break;
00850   case Instruction::Sub:
00851     Result.markConstantRange(LHSRange.sub(RHSRange));
00852     break;
00853   case Instruction::Mul:
00854     Result.markConstantRange(LHSRange.multiply(RHSRange));
00855     break;
00856   case Instruction::UDiv:
00857     Result.markConstantRange(LHSRange.udiv(RHSRange));
00858     break;
00859   case Instruction::Shl:
00860     Result.markConstantRange(LHSRange.shl(RHSRange));
00861     break;
00862   case Instruction::LShr:
00863     Result.markConstantRange(LHSRange.lshr(RHSRange));
00864     break;
00865   case Instruction::Trunc:
00866     Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth()));
00867     break;
00868   case Instruction::SExt:
00869     Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth()));
00870     break;
00871   case Instruction::ZExt:
00872     Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth()));
00873     break;
00874   case Instruction::BitCast:
00875     Result.markConstantRange(LHSRange);
00876     break;
00877   case Instruction::And:
00878     Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
00879     break;
00880   case Instruction::Or:
00881     Result.markConstantRange(LHSRange.binaryOr(RHSRange));
00882     break;
00883 
00884   // Unhandled instructions are overdefined.
00885   default:
00886     DEBUG(dbgs() << " compute BB '" << BB->getName()
00887                  << "' - overdefined because inst def found.\n");
00888     Result.markOverdefined();
00889     break;
00890   }
00891 
00892   BBLV = Result;
00893   return true;
00894 }
00895 
00896 bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
00897                                LVILatticeVal &Result, bool isTrueDest) {
00898   if (ICI && isa<Constant>(ICI->getOperand(1))) {
00899     if (ICI->isEquality() && ICI->getOperand(0) == Val) {
00900       // We know that V has the RHS constant if this is a true SETEQ or
00901       // false SETNE. 
00902       if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
00903         Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
00904       else
00905         Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
00906       return true;
00907     }
00908 
00909     // Recognize the range checking idiom that InstCombine produces.
00910     // (X-C1) u< C2 --> [C1, C1+C2)
00911     ConstantInt *NegOffset = nullptr;
00912     if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
00913       match(ICI->getOperand(0), m_Add(m_Specific(Val),
00914                                       m_ConstantInt(NegOffset)));
00915 
00916     ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
00917     if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
00918       // Calculate the range of values that are allowed by the comparison
00919       ConstantRange CmpRange(CI->getValue());
00920       ConstantRange TrueValues =
00921           ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange);
00922 
00923       if (NegOffset) // Apply the offset from above.
00924         TrueValues = TrueValues.subtract(NegOffset->getValue());
00925 
00926       // If we're interested in the false dest, invert the condition.
00927       if (!isTrueDest) TrueValues = TrueValues.inverse();
00928 
00929       Result = LVILatticeVal::getRange(TrueValues);
00930       return true;
00931     }
00932   }
00933 
00934   return false;
00935 }
00936 
00937 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
00938 /// Val is not constrained on the edge.
00939 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
00940                               BasicBlock *BBTo, LVILatticeVal &Result) {
00941   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
00942   // know that v != 0.
00943   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
00944     // If this is a conditional branch and only one successor goes to BBTo, then
00945     // we may be able to infer something from the condition.
00946     if (BI->isConditional() &&
00947         BI->getSuccessor(0) != BI->getSuccessor(1)) {
00948       bool isTrueDest = BI->getSuccessor(0) == BBTo;
00949       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
00950              "BBTo isn't a successor of BBFrom");
00951 
00952       // If V is the condition of the branch itself, then we know exactly what
00953       // it is.
00954       if (BI->getCondition() == Val) {
00955         Result = LVILatticeVal::get(ConstantInt::get(
00956                               Type::getInt1Ty(Val->getContext()), isTrueDest));
00957         return true;
00958       }
00959 
00960       // If the condition of the branch is an equality comparison, we may be
00961       // able to infer the value.
00962       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
00963         if (getValueFromFromCondition(Val, ICI, Result, isTrueDest))
00964           return true;
00965     }
00966   }
00967 
00968   // If the edge was formed by a switch on the value, then we may know exactly
00969   // what it is.
00970   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
00971     if (SI->getCondition() != Val)
00972       return false;
00973 
00974     bool DefaultCase = SI->getDefaultDest() == BBTo;
00975     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
00976     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
00977 
00978     for (SwitchInst::CaseIt i : SI->cases()) {
00979       ConstantRange EdgeVal(i.getCaseValue()->getValue());
00980       if (DefaultCase) {
00981         // It is possible that the default destination is the destination of
00982         // some cases. There is no need to perform difference for those cases.
00983         if (i.getCaseSuccessor() != BBTo)
00984           EdgesVals = EdgesVals.difference(EdgeVal);
00985       } else if (i.getCaseSuccessor() == BBTo)
00986         EdgesVals = EdgesVals.unionWith(EdgeVal);
00987     }
00988     Result = LVILatticeVal::getRange(EdgesVals);
00989     return true;
00990   }
00991   return false;
00992 }
00993 
00994 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
00995 /// the basic block if the edge does not constrain Val.
00996 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
00997                                       BasicBlock *BBTo, LVILatticeVal &Result,
00998                                       Instruction *CxtI) {
00999   // If already a constant, there is nothing to compute.
01000   if (Constant *VC = dyn_cast<Constant>(Val)) {
01001     Result = LVILatticeVal::get(VC);
01002     return true;
01003   }
01004 
01005   if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
01006     if (!Result.isConstantRange() ||
01007         Result.getConstantRange().getSingleElement())
01008       return true;
01009 
01010     // FIXME: this check should be moved to the beginning of the function when
01011     // LVI better supports recursive values. Even for the single value case, we
01012     // can intersect to detect dead code (an empty range).
01013     if (!hasBlockValue(Val, BBFrom)) {
01014       if (pushBlockValue(std::make_pair(BBFrom, Val)))
01015         return false;
01016       Result.markOverdefined();
01017       return true;
01018     }
01019 
01020     // Try to intersect ranges of the BB and the constraint on the edge.
01021     LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
01022     mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
01023     // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange,
01024     // and caching, below.
01025     mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
01026     if (!InBlock.isConstantRange())
01027       return true;
01028 
01029     ConstantRange Range =
01030       Result.getConstantRange().intersectWith(InBlock.getConstantRange());
01031     Result = LVILatticeVal::getRange(Range);
01032     return true;
01033   }
01034 
01035   if (!hasBlockValue(Val, BBFrom)) {
01036     if (pushBlockValue(std::make_pair(BBFrom, Val)))
01037       return false;
01038     Result.markOverdefined();
01039     return true;
01040   }
01041 
01042   // If we couldn't compute the value on the edge, use the value from the BB.
01043   Result = getBlockValue(Val, BBFrom);
01044   mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
01045   // We can use the context instruction (generically the ultimate instruction
01046   // the calling pass is trying to simplify) here, even though the result of
01047   // this function is generally cached when called from the solve* functions
01048   // (and that cached result might be used with queries using a different
01049   // context instruction), because when this function is called from the solve*
01050   // functions, the context instruction is not provided. When called from
01051   // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
01052   // but then the result is not cached.
01053   mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
01054   return true;
01055 }
01056 
01057 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
01058                                                   Instruction *CxtI) {
01059   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
01060         << BB->getName() << "'\n");
01061 
01062   assert(BlockValueStack.empty() && BlockValueSet.empty());
01063   pushBlockValue(std::make_pair(BB, V));
01064 
01065   solve();
01066   LVILatticeVal Result = getBlockValue(V, BB);
01067   mergeAssumeBlockValueConstantRange(V, Result, CxtI);
01068 
01069   DEBUG(dbgs() << "  Result = " << Result << "\n");
01070   return Result;
01071 }
01072 
01073 LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
01074   DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
01075         << CxtI->getName() << "'\n");
01076 
01077   LVILatticeVal Result;
01078   if (auto *I = dyn_cast<Instruction>(V))
01079     Result = getFromRangeMetadata(I);
01080   mergeAssumeBlockValueConstantRange(V, Result, CxtI);
01081 
01082   DEBUG(dbgs() << "  Result = " << Result << "\n");
01083   return Result;
01084 }
01085 
01086 LVILatticeVal LazyValueInfoCache::
01087 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
01088                Instruction *CxtI) {
01089   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
01090         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
01091 
01092   LVILatticeVal Result;
01093   if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
01094     solve();
01095     bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
01096     (void)WasFastQuery;
01097     assert(WasFastQuery && "More work to do after problem solved?");
01098   }
01099 
01100   DEBUG(dbgs() << "  Result = " << Result << "\n");
01101   return Result;
01102 }
01103 
01104 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
01105                                     BasicBlock *NewSucc) {
01106   // When an edge in the graph has been threaded, values that we could not
01107   // determine a value for before (i.e. were marked overdefined) may be
01108   // possible to solve now. We do NOT try to proactively update these values.
01109   // Instead, we clear their entries from the cache, and allow lazy updating to
01110   // recompute them when needed.
01111 
01112   // The updating process is fairly simple: we need to drop cached info
01113   // for all values that were marked overdefined in OldSucc, and for those same
01114   // values in any successor of OldSucc (except NewSucc) in which they were
01115   // also marked overdefined.
01116   std::vector<BasicBlock*> worklist;
01117   worklist.push_back(OldSucc);
01118 
01119   auto I = OverDefinedCache.find(OldSucc);
01120   if (I == OverDefinedCache.end())
01121     return; // Nothing to process here.
01122   SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
01123 
01124   // Use a worklist to perform a depth-first search of OldSucc's successors.
01125   // NOTE: We do not need a visited list since any blocks we have already
01126   // visited will have had their overdefined markers cleared already, and we
01127   // thus won't loop to their successors.
01128   while (!worklist.empty()) {
01129     BasicBlock *ToUpdate = worklist.back();
01130     worklist.pop_back();
01131 
01132     // Skip blocks only accessible through NewSucc.
01133     if (ToUpdate == NewSucc) continue;
01134 
01135     bool changed = false;
01136     for (Value *V : ValsToClear) {
01137       // If a value was marked overdefined in OldSucc, and is here too...
01138       auto OI = OverDefinedCache.find(ToUpdate);
01139       if (OI == OverDefinedCache.end())
01140         continue;
01141       SmallPtrSetImpl<Value *> &ValueSet = OI->second;
01142       if (!ValueSet.count(V))
01143         continue;
01144 
01145       ValueSet.erase(V);
01146       if (ValueSet.empty())
01147         OverDefinedCache.erase(OI);
01148 
01149       // If we removed anything, then we potentially need to update
01150       // blocks successors too.
01151       changed = true;
01152     }
01153 
01154     if (!changed) continue;
01155 
01156     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
01157   }
01158 }
01159 
01160 //===----------------------------------------------------------------------===//
01161 //                            LazyValueInfo Impl
01162 //===----------------------------------------------------------------------===//
01163 
01164 /// This lazily constructs the LazyValueInfoCache.
01165 static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC,
01166                                     const DataLayout *DL,
01167                                     DominatorTree *DT = nullptr) {
01168   if (!PImpl) {
01169     assert(DL && "getCache() called with a null DataLayout");
01170     PImpl = new LazyValueInfoCache(AC, *DL, DT);
01171   }
01172   return *static_cast<LazyValueInfoCache*>(PImpl);
01173 }
01174 
01175 bool LazyValueInfo::runOnFunction(Function &F) {
01176   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
01177   const DataLayout &DL = F.getParent()->getDataLayout();
01178 
01179   DominatorTreeWrapperPass *DTWP =
01180       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
01181   DT = DTWP ? &DTWP->getDomTree() : nullptr;
01182 
01183   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
01184 
01185   if (PImpl)
01186     getCache(PImpl, AC, &DL, DT).clear();
01187 
01188   // Fully lazy.
01189   return false;
01190 }
01191 
01192 void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
01193   AU.setPreservesAll();
01194   AU.addRequired<AssumptionCacheTracker>();
01195   AU.addRequired<TargetLibraryInfoWrapperPass>();
01196 }
01197 
01198 void LazyValueInfo::releaseMemory() {
01199   // If the cache was allocated, free it.
01200   if (PImpl) {
01201     delete &getCache(PImpl, AC, nullptr);
01202     PImpl = nullptr;
01203   }
01204 }
01205 
01206 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
01207                                      Instruction *CxtI) {
01208   const DataLayout &DL = BB->getModule()->getDataLayout();
01209   LVILatticeVal Result =
01210       getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
01211 
01212   if (Result.isConstant())
01213     return Result.getConstant();
01214   if (Result.isConstantRange()) {
01215     ConstantRange CR = Result.getConstantRange();
01216     if (const APInt *SingleVal = CR.getSingleElement())
01217       return ConstantInt::get(V->getContext(), *SingleVal);
01218   }
01219   return nullptr;
01220 }
01221 
01222 /// Determine whether the specified value is known to be a
01223 /// constant on the specified edge. Return null if not.
01224 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
01225                                            BasicBlock *ToBB,
01226                                            Instruction *CxtI) {
01227   const DataLayout &DL = FromBB->getModule()->getDataLayout();
01228   LVILatticeVal Result =
01229       getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
01230 
01231   if (Result.isConstant())
01232     return Result.getConstant();
01233   if (Result.isConstantRange()) {
01234     ConstantRange CR = Result.getConstantRange();
01235     if (const APInt *SingleVal = CR.getSingleElement())
01236       return ConstantInt::get(V->getContext(), *SingleVal);
01237   }
01238   return nullptr;
01239 }
01240 
01241 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
01242                                                   LVILatticeVal &Result,
01243                                                   const DataLayout &DL,
01244                                                   TargetLibraryInfo *TLI) {
01245 
01246   // If we know the value is a constant, evaluate the conditional.
01247   Constant *Res = nullptr;
01248   if (Result.isConstant()) {
01249     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
01250                                           TLI);
01251     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
01252       return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
01253     return LazyValueInfo::Unknown;
01254   }
01255 
01256   if (Result.isConstantRange()) {
01257     ConstantInt *CI = dyn_cast<ConstantInt>(C);
01258     if (!CI) return LazyValueInfo::Unknown;
01259 
01260     ConstantRange CR = Result.getConstantRange();
01261     if (Pred == ICmpInst::ICMP_EQ) {
01262       if (!CR.contains(CI->getValue()))
01263         return LazyValueInfo::False;
01264 
01265       if (CR.isSingleElement() && CR.contains(CI->getValue()))
01266         return LazyValueInfo::True;
01267     } else if (Pred == ICmpInst::ICMP_NE) {
01268       if (!CR.contains(CI->getValue()))
01269         return LazyValueInfo::True;
01270 
01271       if (CR.isSingleElement() && CR.contains(CI->getValue()))
01272         return LazyValueInfo::False;
01273     }
01274 
01275     // Handle more complex predicates.
01276     ConstantRange TrueValues =
01277         ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
01278     if (TrueValues.contains(CR))
01279       return LazyValueInfo::True;
01280     if (TrueValues.inverse().contains(CR))
01281       return LazyValueInfo::False;
01282     return LazyValueInfo::Unknown;
01283   }
01284 
01285   if (Result.isNotConstant()) {
01286     // If this is an equality comparison, we can try to fold it knowing that
01287     // "V != C1".
01288     if (Pred == ICmpInst::ICMP_EQ) {
01289       // !C1 == C -> false iff C1 == C.
01290       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
01291                                             Result.getNotConstant(), C, DL,
01292                                             TLI);
01293       if (Res->isNullValue())
01294         return LazyValueInfo::False;
01295     } else if (Pred == ICmpInst::ICMP_NE) {
01296       // !C1 != C -> true iff C1 == C.
01297       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
01298                                             Result.getNotConstant(), C, DL,
01299                                             TLI);
01300       if (Res->isNullValue())
01301         return LazyValueInfo::True;
01302     }
01303     return LazyValueInfo::Unknown;
01304   }
01305 
01306   return LazyValueInfo::Unknown;
01307 }
01308 
01309 /// Determine whether the specified value comparison with a constant is known to
01310 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
01311 LazyValueInfo::Tristate
01312 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
01313                                   BasicBlock *FromBB, BasicBlock *ToBB,
01314                                   Instruction *CxtI) {
01315   const DataLayout &DL = FromBB->getModule()->getDataLayout();
01316   LVILatticeVal Result =
01317       getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
01318 
01319   return getPredicateResult(Pred, C, Result, DL, TLI);
01320 }
01321 
01322 LazyValueInfo::Tristate
01323 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
01324                               Instruction *CxtI) {
01325   const DataLayout &DL = CxtI->getModule()->getDataLayout();
01326   LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
01327   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
01328   if (Ret != Unknown)
01329     return Ret;
01330 
01331   // Note: The following bit of code is somewhat distinct from the rest of LVI;
01332   // LVI as a whole tries to compute a lattice value which is conservatively
01333   // correct at a given location.  In this case, we have a predicate which we
01334   // weren't able to prove about the merged result, and we're pushing that
01335   // predicate back along each incoming edge to see if we can prove it
01336   // separately for each input.  As a motivating example, consider:
01337   // bb1:
01338   //   %v1 = ... ; constantrange<1, 5>
01339   //   br label %merge
01340   // bb2:
01341   //   %v2 = ... ; constantrange<10, 20>
01342   //   br label %merge
01343   // merge:
01344   //   %phi = phi [%v1, %v2] ; constantrange<1,20>
01345   //   %pred = icmp eq i32 %phi, 8
01346   // We can't tell from the lattice value for '%phi' that '%pred' is false
01347   // along each path, but by checking the predicate over each input separately,
01348   // we can.
01349   // We limit the search to one step backwards from the current BB and value.
01350   // We could consider extending this to search further backwards through the
01351   // CFG and/or value graph, but there are non-obvious compile time vs quality
01352   // tradeoffs.  
01353   if (CxtI) {
01354     BasicBlock *BB = CxtI->getParent();
01355 
01356     // Function entry or an unreachable block.  Bail to avoid confusing
01357     // analysis below.
01358     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
01359     if (PI == PE)
01360       return Unknown;
01361 
01362     // If V is a PHI node in the same block as the context, we need to ask
01363     // questions about the predicate as applied to the incoming value along
01364     // each edge. This is useful for eliminating cases where the predicate is
01365     // known along all incoming edges.
01366     if (auto *PHI = dyn_cast<PHINode>(V))
01367       if (PHI->getParent() == BB) {
01368         Tristate Baseline = Unknown;
01369         for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
01370           Value *Incoming = PHI->getIncomingValue(i);
01371           BasicBlock *PredBB = PHI->getIncomingBlock(i);
01372           // Note that PredBB may be BB itself.        
01373           Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
01374                                                CxtI);
01375           
01376           // Keep going as long as we've seen a consistent known result for
01377           // all inputs.
01378           Baseline = (i == 0) ? Result /* First iteration */
01379             : (Baseline == Result ? Baseline : Unknown); /* All others */
01380           if (Baseline == Unknown)
01381             break;
01382         }
01383         if (Baseline != Unknown)
01384           return Baseline;
01385       }    
01386 
01387     // For a comparison where the V is outside this block, it's possible
01388     // that we've branched on it before. Look to see if the value is known
01389     // on all incoming edges.
01390     if (!isa<Instruction>(V) ||
01391         cast<Instruction>(V)->getParent() != BB) {
01392       // For predecessor edge, determine if the comparison is true or false
01393       // on that edge. If they're all true or all false, we can conclude
01394       // the value of the comparison in this block.
01395       Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
01396       if (Baseline != Unknown) {
01397         // Check that all remaining incoming values match the first one.
01398         while (++PI != PE) {
01399           Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
01400           if (Ret != Baseline) break;
01401         }
01402         // If we terminated early, then one of the values didn't match.
01403         if (PI == PE) {
01404           return Baseline;
01405         }
01406       }
01407     }
01408   }
01409   return Unknown;
01410 }
01411 
01412 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
01413                                BasicBlock *NewSucc) {
01414   if (PImpl) {
01415     const DataLayout &DL = PredBB->getModule()->getDataLayout();
01416     getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
01417   }
01418 }
01419 
01420 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
01421   if (PImpl) {
01422     const DataLayout &DL = BB->getModule()->getDataLayout();
01423     getCache(PImpl, AC, &DL, DT).eraseBlock(BB);
01424   }
01425 }