lib/Analysis/LazyValueInfo.cpp

   1 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the interface for lazy computation of value constraint
  11 // information.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/LazyValueInfo.h"
  16 #include "llvm/ADT/DenseSet.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/Analysis/AssumptionCache.h"
  19 #include "llvm/Analysis/ConstantFolding.h"
  20 #include "llvm/Analysis/TargetLibraryInfo.h"
  21 #include "llvm/Analysis/ValueTracking.h"
  22 #include "llvm/IR/CFG.h"
  23 #include "llvm/IR/ConstantRange.h"
  24 #include "llvm/IR/Constants.h"
  25 #include "llvm/IR/DataLayout.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/IntrinsicInst.h"
  29 #include "llvm/IR/LLVMContext.h"
  30 #include "llvm/IR/PatternMatch.h"
  31 #include "llvm/IR/ValueHandle.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include <map>
  35 #include <stack>
  36 using namespace llvm;
  37 using namespace PatternMatch;
  38
  39 #define DEBUG_TYPE "lazy-value-info"
  40
  41 char LazyValueInfo::ID = 0;
  42 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
  43                 "Lazy Value Information Analysis", false, true)
  44 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  45 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
  46 INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info",
  47                 "Lazy Value Information Analysis", false, true)
  48
  49 namespace llvm {
  50   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
  51 }
  52
  53
  54 //===----------------------------------------------------------------------===//
  55 //                               LVILatticeVal
  56 //===----------------------------------------------------------------------===//
  57
  58 /// This is the information tracked by LazyValueInfo for each value.
  59 ///
  60 /// FIXME: This is basically just for bringup, this can be made a lot more rich
  61 /// in the future.
  62 ///
  63 namespace {
  64 class LVILatticeVal {
  65   enum LatticeValueTy {
  66     /// This Value has no known value yet.
  67     undefined,
  68
  69     /// This Value has a specific constant value.
  70     constant,
  71
  72     /// This Value is known to not have the specified value.
  73     notconstant,
  74
  75     /// The Value falls within this range.
  76     constantrange,
  77
  78     /// This value is not known to be constant, and we know that it has a value.
  79     overdefined
  80   };
  81
  82   /// Val: This stores the current lattice value along with the Constant* for
  83   /// the constant if this is a 'constant' or 'notconstant' value.
  84   LatticeValueTy Tag;
  85   Constant *Val;
  86   ConstantRange Range;
  87
  88 public:
  89   LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
  90
  91   static LVILatticeVal get(Constant *C) {
  92     LVILatticeVal Res;
  93     if (!isa<UndefValue>(C))
  94       Res.markConstant(C);
  95     return Res;
  96   }
  97   static LVILatticeVal getNot(Constant *C) {
  98     LVILatticeVal Res;
  99     if (!isa<UndefValue>(C))
 100       Res.markNotConstant(C);
 101     return Res;
 102   }
 103   static LVILatticeVal getRange(ConstantRange CR) {
 104     LVILatticeVal Res;
 105     Res.markConstantRange(CR);
 106     return Res;
 107   }
 108   static LVILatticeVal getOverdefined() {
 109     LVILatticeVal Res;
 110     Res.markOverdefined();
 111     return Res;
 112   }
 113
 114   bool isUndefined() const     { return Tag == undefined; }
 115   bool isConstant() const      { return Tag == constant; }
 116   bool isNotConstant() const   { return Tag == notconstant; }
 117   bool isConstantRange() const { return Tag == constantrange; }
 118   bool isOverdefined() const   { return Tag == overdefined; }
 119
 120   Constant *getConstant() const {
 121     assert(isConstant() && "Cannot get the constant of a non-constant!");
 122     return Val;
 123   }
 124
 125   Constant *getNotConstant() const {
 126     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
 127     return Val;
 128   }
 129
 130   ConstantRange getConstantRange() const {
 131     assert(isConstantRange() &&
 132            "Cannot get the constant-range of a non-constant-range!");
 133     return Range;
 134   }
 135
 136   /// Return true if this is a change in status.
 137   bool markOverdefined() {
 138     if (isOverdefined())
 139       return false;
 140     Tag = overdefined;
 141     return true;
 142   }
 143
 144   /// Return true if this is a change in status.
 145   bool markConstant(Constant *V) {
 146     assert(V && "Marking constant with NULL");
 147     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 148       return markConstantRange(ConstantRange(CI->getValue()));
 149     if (isa<UndefValue>(V))
 150       return false;
 151
 152     assert((!isConstant() || getConstant() == V) &&
 153            "Marking constant with different value");
 154     assert(isUndefined());
 155     Tag = constant;
 156     Val = V;
 157     return true;
 158   }
 159
 160   /// Return true if this is a change in status.
 161   bool markNotConstant(Constant *V) {
 162     assert(V && "Marking constant with NULL");
 163     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 164       return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
 165     if (isa<UndefValue>(V))
 166       return false;
 167
 168     assert((!isConstant() || getConstant() != V) &&
 169            "Marking constant !constant with same value");
 170     assert((!isNotConstant() || getNotConstant() == V) &&
 171            "Marking !constant with different value");
 172     assert(isUndefined() || isConstant());
 173     Tag = notconstant;
 174     Val = V;
 175     return true;
 176   }
 177
 178   /// Return true if this is a change in status.
 179   bool markConstantRange(const ConstantRange NewR) {
 180     if (isConstantRange()) {
 181       if (NewR.isEmptySet())
 182         return markOverdefined();
 183
 184       bool changed = Range != NewR;
 185       Range = NewR;
 186       return changed;
 187     }
 188
 189     assert(isUndefined());
 190     if (NewR.isEmptySet())
 191       return markOverdefined();
 192
 193     Tag = constantrange;
 194     Range = NewR;
 195     return true;
 196   }
 197
 198   /// Merge the specified lattice value into this one, updating this
 199   /// one and returning true if anything changed.
 200   bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
 201     if (RHS.isUndefined() || isOverdefined()) return false;
 202     if (RHS.isOverdefined()) return markOverdefined();
 203
 204     if (isUndefined()) {
 205       Tag = RHS.Tag;
 206       Val = RHS.Val;
 207       Range = RHS.Range;
 208       return true;
 209     }
 210
 211     if (isConstant()) {
 212       if (RHS.isConstant()) {
 213         if (Val == RHS.Val)
 214           return false;
 215         return markOverdefined();
 216       }
 217
 218       if (RHS.isNotConstant()) {
 219         if (Val == RHS.Val)
 220           return markOverdefined();
 221
 222         // Unless we can prove that the two Constants are different, we must
 223         // move to overdefined.
 224         if (ConstantInt *Res =
 225                 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
 226                     CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL)))
 227           if (Res->isOne())
 228             return markNotConstant(RHS.getNotConstant());
 229
 230         return markOverdefined();
 231       }
 232
 233       // RHS is a ConstantRange, LHS is a non-integer Constant.
 234
 235       // FIXME: consider the case where RHS is a range [1, 0) and LHS is
 236       // a function. The correct result is to pick up RHS.
 237
 238       return markOverdefined();
 239     }
 240
 241     if (isNotConstant()) {
 242       if (RHS.isConstant()) {
 243         if (Val == RHS.Val)
 244           return markOverdefined();
 245
 246         // Unless we can prove that the two Constants are different, we must
 247         // move to overdefined.
 248         if (ConstantInt *Res =
 249                 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
 250                     CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL)))
 251           if (Res->isOne())
 252             return false;
 253
 254         return markOverdefined();
 255       }
 256
 257       if (RHS.isNotConstant()) {
 258         if (Val == RHS.Val)
 259           return false;
 260         return markOverdefined();
 261       }
 262
 263       return markOverdefined();
 264     }
 265
 266     assert(isConstantRange() && "New LVILattice type?");
 267     if (!RHS.isConstantRange())
 268       return markOverdefined();
 269
 270     ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
 271     if (NewR.isFullSet())
 272       return markOverdefined();
 273     return markConstantRange(NewR);
 274   }
 275 };
 276
 277 } // end anonymous namespace.
 278
 279 namespace llvm {
 280 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
 281     LLVM_ATTRIBUTE_USED;
 282 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 283   if (Val.isUndefined())
 284     return OS << "undefined";
 285   if (Val.isOverdefined())
 286     return OS << "overdefined";
 287
 288   if (Val.isNotConstant())
 289     return OS << "notconstant<" << *Val.getNotConstant() << '>';
 290   else if (Val.isConstantRange())
 291     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
 292               << Val.getConstantRange().getUpper() << '>';
 293   return OS << "constant<" << *Val.getConstant() << '>';
 294 }
 295 }
 296
 297 //===----------------------------------------------------------------------===//
 298 //                          LazyValueInfoCache Decl
 299 //===----------------------------------------------------------------------===//
 300
 301 namespace {
 302   /// A callback value handle updates the cache when values are erased.
 303   class LazyValueInfoCache;
 304   struct LVIValueHandle final : public CallbackVH {
 305     LazyValueInfoCache *Parent;
 306
 307     LVIValueHandle(Value *V, LazyValueInfoCache *P)
 308       : CallbackVH(V), Parent(P) { }
 309
 310     void deleted() override;
 311     void allUsesReplacedWith(Value *V) override {
 312       deleted();
 313     }
 314   };
 315 }
 316
 317 namespace {
 318   /// This is the cache kept by LazyValueInfo which
 319   /// maintains information about queries across the clients' queries.
 320   class LazyValueInfoCache {
 321     /// This is all of the cached block information for exactly one Value*.
 322     /// The entries are sorted by the BasicBlock* of the
 323     /// entries, allowing us to do a lookup with a binary search.
 324     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
 325     /// memory overhead.
 326     typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
 327         ValueCacheEntryTy;
 328
 329     /// This is all of the cached information for all values,
 330     /// mapped from Value* to key information.
 331     std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
 332
 333     /// This tracks, on a per-block basis, the set of values that are
 334     /// over-defined at the end of that block.
 335     typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
 336         OverDefinedCacheTy;
 337     OverDefinedCacheTy OverDefinedCache;
 338
 339     /// Keep track of all blocks that we have ever seen, so we
 340     /// don't spend time removing unused blocks from our caches.
 341     DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
 342
 343     /// This stack holds the state of the value solver during a query.
 344     /// It basically emulates the callstack of the naive
 345     /// recursive value lookup process.
 346     std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
 347
 348     /// Keeps track of which block-value pairs are in BlockValueStack.
 349     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
 350
 351     /// Push BV onto BlockValueStack unless it's already in there.
 352     /// Returns true on success.
 353     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
 354       if (!BlockValueSet.insert(BV).second)
 355         return false;  // It's already in the stack.
 356
 357       BlockValueStack.push(BV);
 358       return true;
 359     }
 360
 361     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
 362     const DataLayout &DL; ///< A mandatory DataLayout
 363     DominatorTree *DT;    ///< An optional DT pointer.
 364
 365     friend struct LVIValueHandle;
 366
 367     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
 368       SeenBlocks.insert(BB);
 369
 370       // Insert over-defined values into their own cache to reduce memory
 371       // overhead.
 372       if (Result.isOverdefined())
 373         OverDefinedCache[BB].insert(Val);
 374       else
 375         lookup(Val)[BB] = Result;
 376     }
 377
 378     LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
 379     bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
 380                       LVILatticeVal &Result,
 381                       Instruction *CxtI = nullptr);
 382     bool hasBlockValue(Value *Val, BasicBlock *BB);
 383
 384     // These methods process one work item and may add more. A false value
 385     // returned means that the work item was not completely processed and must
 386     // be revisited after going through the new items.
 387     bool solveBlockValue(Value *Val, BasicBlock *BB);
 388     bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
 389                                  Value *Val, BasicBlock *BB);
 390     bool solveBlockValuePHINode(LVILatticeVal &BBLV,
 391                                 PHINode *PN, BasicBlock *BB);
 392     bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
 393                                       Instruction *BBI, BasicBlock *BB);
 394     void mergeAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
 395                                             Instruction *BBI);
 396
 397     void solve();
 398
 399     ValueCacheEntryTy &lookup(Value *V) {
 400       return ValueCache[LVIValueHandle(V, this)];
 401     }
 402
 403     bool isOverdefined(Value *V, BasicBlock *BB) const {
 404       auto ODI = OverDefinedCache.find(BB);
 405
 406       if (ODI == OverDefinedCache.end())
 407         return false;
 408
 409       return ODI->second.count(V);
 410     }
 411
 412     bool hasCachedValueInfo(Value *V, BasicBlock *BB) {
 413       if (isOverdefined(V, BB))
 414         return true;
 415
 416       LVIValueHandle ValHandle(V, this);
 417       auto I = ValueCache.find(ValHandle);
 418       if (I == ValueCache.end())
 419         return false;
 420
 421       return I->second.count(BB);
 422     }
 423
 424     LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
 425       if (isOverdefined(V, BB))
 426         return LVILatticeVal::getOverdefined();
 427
 428       return lookup(V)[BB];
 429     }
 430
 431   public:
 432     /// This is the query interface to determine the lattice
 433     /// value for the specified Value* at the end of the specified block.
 434     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
 435                                   Instruction *CxtI = nullptr);
 436
 437     /// This is the query interface to determine the lattice
 438     /// value for the specified Value* at the specified instruction (generally
 439     /// from an assume intrinsic).
 440     LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
 441
 442     /// This is the query interface to determine the lattice
 443     /// value for the specified Value* that is true on the specified edge.
 444     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
 445                                  Instruction *CxtI = nullptr);
 446
 447     /// This is the update interface to inform the cache that an edge from
 448     /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
 449     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 450
 451     /// This is part of the update interface to inform the cache
 452     /// that a block has been deleted.
 453     void eraseBlock(BasicBlock *BB);
 454
 455     /// clear - Empty the cache.
 456     void clear() {
 457       SeenBlocks.clear();
 458       ValueCache.clear();
 459       OverDefinedCache.clear();
 460     }
 461
 462     LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL,
 463                        DominatorTree *DT = nullptr)
 464         : AC(AC), DL(DL), DT(DT) {}
 465   };
 466 } // end anonymous namespace
 467
 468 void LVIValueHandle::deleted() {
 469   SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
 470   for (auto &I : Parent->OverDefinedCache) {
 471     SmallPtrSetImpl<Value *> &ValueSet = I.second;
 472     if (ValueSet.count(getValPtr()))
 473       ValueSet.erase(getValPtr());
 474     if (ValueSet.empty())
 475       ToErase.push_back(I.first);
 476   }
 477   for (auto &BB : ToErase)
 478     Parent->OverDefinedCache.erase(BB);
 479
 480   // This erasure deallocates *this, so it MUST happen after we're done
 481   // using any and all members of *this.
 482   Parent->ValueCache.erase(*this);
 483 }
 484
 485 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
 486   // Shortcut if we have never seen this block.
 487   DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
 488   if (I == SeenBlocks.end())
 489     return;
 490   SeenBlocks.erase(I);
 491
 492   auto ODI = OverDefinedCache.find(BB);
 493   if (ODI != OverDefinedCache.end())
 494     OverDefinedCache.erase(ODI);
 495
 496   for (auto I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
 497     I->second.erase(BB);
 498 }
 499
 500 void LazyValueInfoCache::solve() {
 501   while (!BlockValueStack.empty()) {
 502     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
 503     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
 504
 505     if (solveBlockValue(e.second, e.first)) {
 506       // The work item was completely processed.
 507       assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
 508       assert(hasCachedValueInfo(e.second, e.first) &&
 509              "Result should be in cache!");
 510
 511       BlockValueStack.pop();
 512       BlockValueSet.erase(e);
 513     } else {
 514       // More work needs to be done before revisiting.
 515       assert(BlockValueStack.top() != e && "Stack should have been pushed!");
 516     }
 517   }
 518 }
 519
 520 bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
 521   // If already a constant, there is nothing to compute.
 522   if (isa<Constant>(Val))
 523     return true;
 524
 525   return hasCachedValueInfo(Val, BB);
 526 }
 527
 528 LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
 529   // If already a constant, there is nothing to compute.
 530   if (Constant *VC = dyn_cast<Constant>(Val))
 531     return LVILatticeVal::get(VC);
 532
 533   SeenBlocks.insert(BB);
 534   return getCachedValueInfo(Val, BB);
 535 }
 536
 537 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
 538   switch (BBI->getOpcode()) {
 539   default: break;
 540   case Instruction::Load:
 541   case Instruction::Call:
 542   case Instruction::Invoke:
 543     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
 544       if (isa<IntegerType>(BBI->getType())) {
 545         ConstantRange Result = getConstantRangeFromMetadata(*Ranges);
 546         return LVILatticeVal::getRange(Result);
 547       }
 548     break;
 549   };
 550   // Nothing known - Note that we do not want overdefined here.  We may know
 551   // something else about the value and not having range metadata shouldn't
 552   // cause us to throw away those facts.
 553   return LVILatticeVal();
 554 }
 555
 556 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
 557   if (isa<Constant>(Val))
 558     return true;
 559
 560   if (hasCachedValueInfo(Val, BB)) {
 561     // If we have a cached value, use that.
 562     DEBUG(dbgs() << "  reuse BB '" << BB->getName()
 563                  << "' val=" << getCachedValueInfo(Val, BB) << '\n');
 564
 565     // Since we're reusing a cached value, we don't need to update the
 566     // OverDefinedCache. The cache will have been properly updated whenever the
 567     // cached value was inserted.
 568     return true;
 569   }
 570
 571   // Hold off inserting this value into the Cache in case we have to return
 572   // false and come back later.
 573   LVILatticeVal Res;
 574
 575   Instruction *BBI = dyn_cast<Instruction>(Val);
 576   if (!BBI || BBI->getParent() != BB) {
 577     if (!solveBlockValueNonLocal(Res, Val, BB))
 578       return false;
 579    insertResult(Val, BB, Res);
 580    return true;
 581   }
 582
 583   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 584     if (!solveBlockValuePHINode(Res, PN, BB))
 585       return false;
 586     insertResult(Val, BB, Res);
 587     return true;
 588   }
 589
 590   // If this value is a nonnull pointer, record it's range and bailout.
 591   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
 592   if (PT && isKnownNonNull(BBI)) {
 593     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
 594     insertResult(Val, BB, Res);
 595     return true;
 596   }
 597
 598   // If this is an instruction which supports range metadata, return the
 599   // implied range.  TODO: This should be an intersection, not a union.
 600   Res.mergeIn(getFromRangeMetadata(BBI), DL);
 601
 602   // We can only analyze the definitions of certain classes of instructions
 603   // (integral binops and casts at the moment), so bail if this isn't one.
 604   LVILatticeVal Result;
 605   if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
 606      !BBI->getType()->isIntegerTy()) {
 607     DEBUG(dbgs() << " compute BB '" << BB->getName()
 608                  << "' - overdefined because inst def found.\n");
 609     Res.markOverdefined();
 610     insertResult(Val, BB, Res);
 611     return true;
 612   }
 613
 614   // FIXME: We're currently limited to binops with a constant RHS.  This should
 615   // be improved.
 616   BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
 617   if (BO && !isa<ConstantInt>(BO->getOperand(1))) {
 618     DEBUG(dbgs() << " compute BB '" << BB->getName()
 619                  << "' - overdefined because inst def found.\n");
 620
 621     Res.markOverdefined();
 622     insertResult(Val, BB, Res);
 623     return true;
 624   }
 625
 626   if (!solveBlockValueConstantRange(Res, BBI, BB))
 627     return false;
 628   insertResult(Val, BB, Res);
 629   return true;
 630 }
 631
 632 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
 633   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
 634     return L->getPointerAddressSpace() == 0 &&
 635            GetUnderlyingObject(L->getPointerOperand(),
 636                                L->getModule()->getDataLayout()) == Ptr;
 637   }
 638   if (StoreInst *S = dyn_cast<StoreInst>(I)) {
 639     return S->getPointerAddressSpace() == 0 &&
 640            GetUnderlyingObject(S->getPointerOperand(),
 641                                S->getModule()->getDataLayout()) == Ptr;
 642   }
 643   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
 644     if (MI->isVolatile()) return false;
 645
 646     // FIXME: check whether it has a valuerange that excludes zero?
 647     ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
 648     if (!Len || Len->isZero()) return false;
 649
 650     if (MI->getDestAddressSpace() == 0)
 651       if (GetUnderlyingObject(MI->getRawDest(),
 652                               MI->getModule()->getDataLayout()) == Ptr)
 653         return true;
 654     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
 655       if (MTI->getSourceAddressSpace() == 0)
 656         if (GetUnderlyingObject(MTI->getRawSource(),
 657                                 MTI->getModule()->getDataLayout()) == Ptr)
 658           return true;
 659   }
 660   return false;
 661 }
 662
 663 bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
 664                                                  Value *Val, BasicBlock *BB) {
 665   LVILatticeVal Result;  // Start Undefined.
 666
 667   // If this is a pointer, and there's a load from that pointer in this BB,
 668   // then we know that the pointer can't be NULL.
 669   bool NotNull = false;
 670   if (Val->getType()->isPointerTy()) {
 671     if (isKnownNonNull(Val)) {
 672       NotNull = true;
 673     } else {
 674       const DataLayout &DL = BB->getModule()->getDataLayout();
 675       Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
 676       // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
 677       // inside InstructionDereferencesPointer either.
 678       if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) {
 679         for (Instruction &I : *BB) {
 680           if (InstructionDereferencesPointer(&I, UnderlyingVal)) {
 681             NotNull = true;
 682             break;
 683           }
 684         }
 685       }
 686     }
 687   }
 688
 689   // If this is the entry block, we must be asking about an argument.  The
 690   // value is overdefined.
 691   if (BB == &BB->getParent()->getEntryBlock()) {
 692     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
 693     if (NotNull) {
 694       PointerType *PTy = cast<PointerType>(Val->getType());
 695       Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
 696     } else {
 697       Result.markOverdefined();
 698     }
 699     BBLV = Result;
 700     return true;
 701   }
 702
 703   // Loop over all of our predecessors, merging what we know from them into
 704   // result.
 705   bool EdgesMissing = false;
 706   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 707     LVILatticeVal EdgeResult;
 708     EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
 709     if (EdgesMissing)
 710       continue;
 711
 712     Result.mergeIn(EdgeResult, DL);
 713
 714     // If we hit overdefined, exit early.  The BlockVals entry is already set
 715     // to overdefined.
 716     if (Result.isOverdefined()) {
 717       DEBUG(dbgs() << " compute BB '" << BB->getName()
 718             << "' - overdefined because of pred.\n");
 719       // If we previously determined that this is a pointer that can't be null
 720       // then return that rather than giving up entirely.
 721       if (NotNull) {
 722         PointerType *PTy = cast<PointerType>(Val->getType());
 723         Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
 724       }
 725
 726       BBLV = Result;
 727       return true;
 728     }
 729   }
 730   if (EdgesMissing)
 731     return false;
 732
 733   // Return the merged value, which is more precise than 'overdefined'.
 734   assert(!Result.isOverdefined());
 735   BBLV = Result;
 736   return true;
 737 }
 738
 739 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
 740                                                 PHINode *PN, BasicBlock *BB) {
 741   LVILatticeVal Result;  // Start Undefined.
 742
 743   // Loop over all of our predecessors, merging what we know from them into
 744   // result.
 745   bool EdgesMissing = false;
 746   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 747     BasicBlock *PhiBB = PN->getIncomingBlock(i);
 748     Value *PhiVal = PN->getIncomingValue(i);
 749     LVILatticeVal EdgeResult;
 750     // Note that we can provide PN as the context value to getEdgeValue, even
 751     // though the results will be cached, because PN is the value being used as
 752     // the cache key in the caller.
 753     EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
 754     if (EdgesMissing)
 755       continue;
 756
 757     Result.mergeIn(EdgeResult, DL);
 758
 759     // If we hit overdefined, exit early.  The BlockVals entry is already set
 760     // to overdefined.
 761     if (Result.isOverdefined()) {
 762       DEBUG(dbgs() << " compute BB '" << BB->getName()
 763             << "' - overdefined because of pred.\n");
 764
 765       BBLV = Result;
 766       return true;
 767     }
 768   }
 769   if (EdgesMissing)
 770     return false;
 771
 772   // Return the merged value, which is more precise than 'overdefined'.
 773   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
 774   BBLV = Result;
 775   return true;
 776 }
 777
 778 static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
 779                                       LVILatticeVal &Result,
 780                                       bool isTrueDest = true);
 781
 782 // If we can determine a constant range for the value Val in the context
 783 // provided by the instruction BBI, then merge it into BBLV. If we did find a
 784 // constant range, return true.
 785 void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val,
 786                                                             LVILatticeVal &BBLV,
 787                                                             Instruction *BBI) {
 788   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
 789   if (!BBI)
 790     return;
 791
 792   for (auto &AssumeVH : AC->assumptions()) {
 793     if (!AssumeVH)
 794       continue;
 795     auto *I = cast<CallInst>(AssumeVH);
 796     if (!isValidAssumeForContext(I, BBI, DT))
 797       continue;
 798
 799     Value *C = I->getArgOperand(0);
 800     if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) {
 801       LVILatticeVal Result;
 802       if (getValueFromFromCondition(Val, ICI, Result)) {
 803         if (BBLV.isOverdefined())
 804           BBLV = Result;
 805         else
 806           BBLV.mergeIn(Result, DL);
 807       }
 808     }
 809   }
 810 }
 811
 812 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
 813                                                       Instruction *BBI,
 814                                                       BasicBlock *BB) {
 815   // Figure out the range of the LHS.  If that fails, bail.
 816   if (!hasBlockValue(BBI->getOperand(0), BB)) {
 817     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
 818       return false;
 819     BBLV.markOverdefined();
 820     return true;
 821   }
 822
 823   LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
 824   mergeAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
 825   if (!LHSVal.isConstantRange()) {
 826     BBLV.markOverdefined();
 827     return true;
 828   }
 829
 830   ConstantRange LHSRange = LHSVal.getConstantRange();
 831   ConstantRange RHSRange(1);
 832   IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
 833   if (isa<BinaryOperator>(BBI)) {
 834     if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
 835       RHSRange = ConstantRange(RHS->getValue());
 836     } else {
 837       BBLV.markOverdefined();
 838       return true;
 839     }
 840   }
 841
 842   // NOTE: We're currently limited by the set of operations that ConstantRange
 843   // can evaluate symbolically.  Enhancing that set will allows us to analyze
 844   // more definitions.
 845   LVILatticeVal Result;
 846   switch (BBI->getOpcode()) {
 847   case Instruction::Add:
 848     Result.markConstantRange(LHSRange.add(RHSRange));
 849     break;
 850   case Instruction::Sub:
 851     Result.markConstantRange(LHSRange.sub(RHSRange));
 852     break;
 853   case Instruction::Mul:
 854     Result.markConstantRange(LHSRange.multiply(RHSRange));
 855     break;
 856   case Instruction::UDiv:
 857     Result.markConstantRange(LHSRange.udiv(RHSRange));
 858     break;
 859   case Instruction::Shl:
 860     Result.markConstantRange(LHSRange.shl(RHSRange));
 861     break;
 862   case Instruction::LShr:
 863     Result.markConstantRange(LHSRange.lshr(RHSRange));
 864     break;
 865   case Instruction::Trunc:
 866     Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth()));
 867     break;
 868   case Instruction::SExt:
 869     Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth()));
 870     break;
 871   case Instruction::ZExt:
 872     Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth()));
 873     break;
 874   case Instruction::BitCast:
 875     Result.markConstantRange(LHSRange);
 876     break;
 877   case Instruction::And:
 878     Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
 879     break;
 880   case Instruction::Or:
 881     Result.markConstantRange(LHSRange.binaryOr(RHSRange));
 882     break;
 883
 884   // Unhandled instructions are overdefined.
 885   default:
 886     DEBUG(dbgs() << " compute BB '" << BB->getName()
 887                  << "' - overdefined because inst def found.\n");
 888     Result.markOverdefined();
 889     break;
 890   }
 891
 892   BBLV = Result;
 893   return true;
 894 }
 895
 896 bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
 897                                LVILatticeVal &Result, bool isTrueDest) {
 898   if (ICI && isa<Constant>(ICI->getOperand(1))) {
 899     if (ICI->isEquality() && ICI->getOperand(0) == Val) {
 900       // We know that V has the RHS constant if this is a true SETEQ or
 901       // false SETNE.
 902       if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 903         Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 904       else
 905         Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 906       return true;
 907     }
 908
 909     // Recognize the range checking idiom that InstCombine produces.
 910     // (X-C1) u< C2 --> [C1, C1+C2)
 911     ConstantInt *NegOffset = nullptr;
 912     if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
 913       match(ICI->getOperand(0), m_Add(m_Specific(Val),
 914                                       m_ConstantInt(NegOffset)));
 915
 916     ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
 917     if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
 918       // Calculate the range of values that are allowed by the comparison
 919       ConstantRange CmpRange(CI->getValue());
 920       ConstantRange TrueValues =
 921           ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange);
 922
 923       if (NegOffset) // Apply the offset from above.
 924         TrueValues = TrueValues.subtract(NegOffset->getValue());
 925
 926       // If we're interested in the false dest, invert the condition.
 927       if (!isTrueDest) TrueValues = TrueValues.inverse();
 928
 929       Result = LVILatticeVal::getRange(TrueValues);
 930       return true;
 931     }
 932   }
 933
 934   return false;
 935 }
 936
 937 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 938 /// Val is not constrained on the edge.
 939 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
 940                               BasicBlock *BBTo, LVILatticeVal &Result) {
 941   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
 942   // know that v != 0.
 943   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 944     // If this is a conditional branch and only one successor goes to BBTo, then
 945     // we may be able to infer something from the condition.
 946     if (BI->isConditional() &&
 947         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 948       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 949       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 950              "BBTo isn't a successor of BBFrom");
 951
 952       // If V is the condition of the branch itself, then we know exactly what
 953       // it is.
 954       if (BI->getCondition() == Val) {
 955         Result = LVILatticeVal::get(ConstantInt::get(
 956                               Type::getInt1Ty(Val->getContext()), isTrueDest));
 957         return true;
 958       }
 959
 960       // If the condition of the branch is an equality comparison, we may be
 961       // able to infer the value.
 962       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 963         if (getValueFromFromCondition(Val, ICI, Result, isTrueDest))
 964           return true;
 965     }
 966   }
 967
 968   // If the edge was formed by a switch on the value, then we may know exactly
 969   // what it is.
 970   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
 971     if (SI->getCondition() != Val)
 972       return false;
 973
 974     bool DefaultCase = SI->getDefaultDest() == BBTo;
 975     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
 976     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
 977
 978     for (SwitchInst::CaseIt i : SI->cases()) {
 979       ConstantRange EdgeVal(i.getCaseValue()->getValue());
 980       if (DefaultCase) {
 981         // It is possible that the default destination is the destination of
 982         // some cases. There is no need to perform difference for those cases.
 983         if (i.getCaseSuccessor() != BBTo)
 984           EdgesVals = EdgesVals.difference(EdgeVal);
 985       } else if (i.getCaseSuccessor() == BBTo)
 986         EdgesVals = EdgesVals.unionWith(EdgeVal);
 987     }
 988     Result = LVILatticeVal::getRange(EdgesVals);
 989     return true;
 990   }
 991   return false;
 992 }
 993
 994 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
 995 /// the basic block if the edge does not constrain Val.
 996 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 997                                       BasicBlock *BBTo, LVILatticeVal &Result,
 998                                       Instruction *CxtI) {
 999   // If already a constant, there is nothing to compute.
1000   if (Constant *VC = dyn_cast<Constant>(Val)) {
1001     Result = LVILatticeVal::get(VC);
1002     return true;
1003   }
1004
1005   if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
1006     if (!Result.isConstantRange() ||
1007         Result.getConstantRange().getSingleElement())
1008       return true;
1009
1010     // FIXME: this check should be moved to the beginning of the function when
1011     // LVI better supports recursive values. Even for the single value case, we
1012     // can intersect to detect dead code (an empty range).
1013     if (!hasBlockValue(Val, BBFrom)) {
1014       if (pushBlockValue(std::make_pair(BBFrom, Val)))
1015         return false;
1016       Result.markOverdefined();
1017       return true;
1018     }
1019
1020     // Try to intersect ranges of the BB and the constraint on the edge.
1021     LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
1022     mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
1023     // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange,
1024     // and caching, below.
1025     mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
1026     if (!InBlock.isConstantRange())
1027       return true;
1028
1029     ConstantRange Range =
1030       Result.getConstantRange().intersectWith(InBlock.getConstantRange());
1031     Result = LVILatticeVal::getRange(Range);
1032     return true;
1033   }
1034
1035   if (!hasBlockValue(Val, BBFrom)) {
1036     if (pushBlockValue(std::make_pair(BBFrom, Val)))
1037       return false;
1038     Result.markOverdefined();
1039     return true;
1040   }
1041
1042   // If we couldn't compute the value on the edge, use the value from the BB.
1043   Result = getBlockValue(Val, BBFrom);
1044   mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
1045   // We can use the context instruction (generically the ultimate instruction
1046   // the calling pass is trying to simplify) here, even though the result of
1047   // this function is generally cached when called from the solve* functions
1048   // (and that cached result might be used with queries using a different
1049   // context instruction), because when this function is called from the solve*
1050   // functions, the context instruction is not provided. When called from
1051   // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
1052   // but then the result is not cached.
1053   mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
1054   return true;
1055 }
1056
1057 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
1058                                                   Instruction *CxtI) {
1059   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1060         << BB->getName() << "'\n");
1061
1062   assert(BlockValueStack.empty() && BlockValueSet.empty());
1063   pushBlockValue(std::make_pair(BB, V));
1064
1065   solve();
1066   LVILatticeVal Result = getBlockValue(V, BB);
1067   mergeAssumeBlockValueConstantRange(V, Result, CxtI);
1068
1069   DEBUG(dbgs() << "  Result = " << Result << "\n");
1070   return Result;
1071 }
1072
1073 LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
1074   DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1075         << CxtI->getName() << "'\n");
1076
1077   LVILatticeVal Result;
1078   if (auto *I = dyn_cast<Instruction>(V))
1079     Result = getFromRangeMetadata(I);
1080   mergeAssumeBlockValueConstantRange(V, Result, CxtI);
1081
1082   DEBUG(dbgs() << "  Result = " << Result << "\n");
1083   return Result;
1084 }
1085
1086 LVILatticeVal LazyValueInfoCache::
1087 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1088                Instruction *CxtI) {
1089   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1090         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1091
1092   LVILatticeVal Result;
1093   if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1094     solve();
1095     bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1096     (void)WasFastQuery;
1097     assert(WasFastQuery && "More work to do after problem solved?");
1098   }
1099
1100   DEBUG(dbgs() << "  Result = " << Result << "\n");
1101   return Result;
1102 }
1103
1104 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1105                                     BasicBlock *NewSucc) {
1106   // When an edge in the graph has been threaded, values that we could not
1107   // determine a value for before (i.e. were marked overdefined) may be
1108   // possible to solve now. We do NOT try to proactively update these values.
1109   // Instead, we clear their entries from the cache, and allow lazy updating to
1110   // recompute them when needed.
1111
1112   // The updating process is fairly simple: we need to drop cached info
1113   // for all values that were marked overdefined in OldSucc, and for those same
1114   // values in any successor of OldSucc (except NewSucc) in which they were
1115   // also marked overdefined.
1116   std::vector<BasicBlock*> worklist;
1117   worklist.push_back(OldSucc);
1118
1119   auto I = OverDefinedCache.find(OldSucc);
1120   if (I == OverDefinedCache.end())
1121     return; // Nothing to process here.
1122   SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
1123
1124   // Use a worklist to perform a depth-first search of OldSucc's successors.
1125   // NOTE: We do not need a visited list since any blocks we have already
1126   // visited will have had their overdefined markers cleared already, and we
1127   // thus won't loop to their successors.
1128   while (!worklist.empty()) {
1129     BasicBlock *ToUpdate = worklist.back();
1130     worklist.pop_back();
1131
1132     // Skip blocks only accessible through NewSucc.
1133     if (ToUpdate == NewSucc) continue;
1134
1135     bool changed = false;
1136     for (Value *V : ValsToClear) {
1137       // If a value was marked overdefined in OldSucc, and is here too...
1138       auto OI = OverDefinedCache.find(ToUpdate);
1139       if (OI == OverDefinedCache.end())
1140         continue;
1141       SmallPtrSetImpl<Value *> &ValueSet = OI->second;
1142       if (!ValueSet.count(V))
1143         continue;
1144
1145       ValueSet.erase(V);
1146       if (ValueSet.empty())
1147         OverDefinedCache.erase(OI);
1148
1149       // If we removed anything, then we potentially need to update
1150       // blocks successors too.
1151       changed = true;
1152     }
1153
1154     if (!changed) continue;
1155
1156     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
1157   }
1158 }
1159
1160 //===----------------------------------------------------------------------===//
1161 //                            LazyValueInfo Impl
1162 //===----------------------------------------------------------------------===//
1163
1164 /// This lazily constructs the LazyValueInfoCache.
1165 static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC,
1166                                     const DataLayout *DL,
1167                                     DominatorTree *DT = nullptr) {
1168   if (!PImpl) {
1169     assert(DL && "getCache() called with a null DataLayout");
1170     PImpl = new LazyValueInfoCache(AC, *DL, DT);
1171   }
1172   return *static_cast<LazyValueInfoCache*>(PImpl);
1173 }
1174
1175 bool LazyValueInfo::runOnFunction(Function &F) {
1176   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1177   const DataLayout &DL = F.getParent()->getDataLayout();
1178
1179   DominatorTreeWrapperPass *DTWP =
1180       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1181   DT = DTWP ? &DTWP->getDomTree() : nullptr;
1182
1183   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1184
1185   if (PImpl)
1186     getCache(PImpl, AC, &DL, DT).clear();
1187
1188   // Fully lazy.
1189   return false;
1190 }
1191
1192 void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
1193   AU.setPreservesAll();
1194   AU.addRequired<AssumptionCacheTracker>();
1195   AU.addRequired<TargetLibraryInfoWrapperPass>();
1196 }
1197
1198 void LazyValueInfo::releaseMemory() {
1199   // If the cache was allocated, free it.
1200   if (PImpl) {
1201     delete &getCache(PImpl, AC, nullptr);
1202     PImpl = nullptr;
1203   }
1204 }
1205
1206 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1207                                      Instruction *CxtI) {
1208   const DataLayout &DL = BB->getModule()->getDataLayout();
1209   LVILatticeVal Result =
1210       getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1211
1212   if (Result.isConstant())
1213     return Result.getConstant();
1214   if (Result.isConstantRange()) {
1215     ConstantRange CR = Result.getConstantRange();
1216     if (const APInt *SingleVal = CR.getSingleElement())
1217       return ConstantInt::get(V->getContext(), *SingleVal);
1218   }
1219   return nullptr;
1220 }
1221
1222 /// Determine whether the specified value is known to be a
1223 /// constant on the specified edge. Return null if not.
1224 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1225                                            BasicBlock *ToBB,
1226                                            Instruction *CxtI) {
1227   const DataLayout &DL = FromBB->getModule()->getDataLayout();
1228   LVILatticeVal Result =
1229       getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1230
1231   if (Result.isConstant())
1232     return Result.getConstant();
1233   if (Result.isConstantRange()) {
1234     ConstantRange CR = Result.getConstantRange();
1235     if (const APInt *SingleVal = CR.getSingleElement())
1236       return ConstantInt::get(V->getContext(), *SingleVal);
1237   }
1238   return nullptr;
1239 }
1240
1241 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1242                                                   LVILatticeVal &Result,
1243                                                   const DataLayout &DL,
1244                                                   TargetLibraryInfo *TLI) {
1245
1246   // If we know the value is a constant, evaluate the conditional.
1247   Constant *Res = nullptr;
1248   if (Result.isConstant()) {
1249     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
1250                                           TLI);
1251     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1252       return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1253     return LazyValueInfo::Unknown;
1254   }
1255
1256   if (Result.isConstantRange()) {
1257     ConstantInt *CI = dyn_cast<ConstantInt>(C);
1258     if (!CI) return LazyValueInfo::Unknown;
1259
1260     ConstantRange CR = Result.getConstantRange();
1261     if (Pred == ICmpInst::ICMP_EQ) {
1262       if (!CR.contains(CI->getValue()))
1263         return LazyValueInfo::False;
1264
1265       if (CR.isSingleElement() && CR.contains(CI->getValue()))
1266         return LazyValueInfo::True;
1267     } else if (Pred == ICmpInst::ICMP_NE) {
1268       if (!CR.contains(CI->getValue()))
1269         return LazyValueInfo::True;
1270
1271       if (CR.isSingleElement() && CR.contains(CI->getValue()))
1272         return LazyValueInfo::False;
1273     }
1274
1275     // Handle more complex predicates.
1276     ConstantRange TrueValues =
1277         ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
1278     if (TrueValues.contains(CR))
1279       return LazyValueInfo::True;
1280     if (TrueValues.inverse().contains(CR))
1281       return LazyValueInfo::False;
1282     return LazyValueInfo::Unknown;
1283   }
1284
1285   if (Result.isNotConstant()) {
1286     // If this is an equality comparison, we can try to fold it knowing that
1287     // "V != C1".
1288     if (Pred == ICmpInst::ICMP_EQ) {
1289       // !C1 == C -> false iff C1 == C.
1290       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1291                                             Result.getNotConstant(), C, DL,
1292                                             TLI);
1293       if (Res->isNullValue())
1294         return LazyValueInfo::False;
1295     } else if (Pred == ICmpInst::ICMP_NE) {
1296       // !C1 != C -> true iff C1 == C.
1297       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1298                                             Result.getNotConstant(), C, DL,
1299                                             TLI);
1300       if (Res->isNullValue())
1301         return LazyValueInfo::True;
1302     }
1303     return LazyValueInfo::Unknown;
1304   }
1305
1306   return LazyValueInfo::Unknown;
1307 }
1308
1309 /// Determine whether the specified value comparison with a constant is known to
1310 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1311 LazyValueInfo::Tristate
1312 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1313                                   BasicBlock *FromBB, BasicBlock *ToBB,
1314                                   Instruction *CxtI) {
1315   const DataLayout &DL = FromBB->getModule()->getDataLayout();
1316   LVILatticeVal Result =
1317       getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1318
1319   return getPredicateResult(Pred, C, Result, DL, TLI);
1320 }
1321
1322 LazyValueInfo::Tristate
1323 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1324                               Instruction *CxtI) {
1325   const DataLayout &DL = CxtI->getModule()->getDataLayout();
1326   LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1327   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1328   if (Ret != Unknown)
1329     return Ret;
1330
1331   // Note: The following bit of code is somewhat distinct from the rest of LVI;
1332   // LVI as a whole tries to compute a lattice value which is conservatively
1333   // correct at a given location.  In this case, we have a predicate which we
1334   // weren't able to prove about the merged result, and we're pushing that
1335   // predicate back along each incoming edge to see if we can prove it
1336   // separately for each input.  As a motivating example, consider:
1337   // bb1:
1338   //   %v1 = ... ; constantrange<1, 5>
1339   //   br label %merge
1340   // bb2:
1341   //   %v2 = ... ; constantrange<10, 20>
1342   //   br label %merge
1343   // merge:
1344   //   %phi = phi [%v1, %v2] ; constantrange<1,20>
1345   //   %pred = icmp eq i32 %phi, 8
1346   // We can't tell from the lattice value for '%phi' that '%pred' is false
1347   // along each path, but by checking the predicate over each input separately,
1348   // we can.
1349   // We limit the search to one step backwards from the current BB and value.
1350   // We could consider extending this to search further backwards through the
1351   // CFG and/or value graph, but there are non-obvious compile time vs quality
1352   // tradeoffs.
1353   if (CxtI) {
1354     BasicBlock *BB = CxtI->getParent();
1355
1356     // Function entry or an unreachable block.  Bail to avoid confusing
1357     // analysis below.
1358     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1359     if (PI == PE)
1360       return Unknown;
1361
1362     // If V is a PHI node in the same block as the context, we need to ask
1363     // questions about the predicate as applied to the incoming value along
1364     // each edge. This is useful for eliminating cases where the predicate is
1365     // known along all incoming edges.
1366     if (auto *PHI = dyn_cast<PHINode>(V))
1367       if (PHI->getParent() == BB) {
1368         Tristate Baseline = Unknown;
1369         for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1370           Value *Incoming = PHI->getIncomingValue(i);
1371           BasicBlock *PredBB = PHI->getIncomingBlock(i);
1372           // Note that PredBB may be BB itself.
1373           Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1374                                                CxtI);
1375
1376           // Keep going as long as we've seen a consistent known result for
1377           // all inputs.
1378           Baseline = (i == 0) ? Result /* First iteration */
1379             : (Baseline == Result ? Baseline : Unknown); /* All others */
1380           if (Baseline == Unknown)
1381             break;
1382         }
1383         if (Baseline != Unknown)
1384           return Baseline;
1385       }
1386
1387     // For a comparison where the V is outside this block, it's possible
1388     // that we've branched on it before. Look to see if the value is known
1389     // on all incoming edges.
1390     if (!isa<Instruction>(V) ||
1391         cast<Instruction>(V)->getParent() != BB) {
1392       // For predecessor edge, determine if the comparison is true or false
1393       // on that edge. If they're all true or all false, we can conclude
1394       // the value of the comparison in this block.
1395       Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1396       if (Baseline != Unknown) {
1397         // Check that all remaining incoming values match the first one.
1398         while (++PI != PE) {
1399           Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1400           if (Ret != Baseline) break;
1401         }
1402         // If we terminated early, then one of the values didn't match.
1403         if (PI == PE) {
1404           return Baseline;
1405         }
1406       }
1407     }
1408   }
1409   return Unknown;
1410 }
1411
1412 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1413                                BasicBlock *NewSucc) {
1414   if (PImpl) {
1415     const DataLayout &DL = PredBB->getModule()->getDataLayout();
1416     getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1417   }
1418 }
1419
1420 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1421   if (PImpl) {
1422     const DataLayout &DL = BB->getModule()->getDataLayout();
1423     getCache(PImpl, AC, &DL, DT).eraseBlock(BB);
1424   }
1425 }