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