LLVM API Documentation

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