contrib/llvm/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/Intrinsics.h"
  30 #include "llvm/IR/LLVMContext.h"
  31 #include "llvm/IR/PatternMatch.h"
  32 #include "llvm/IR/ValueHandle.h"
  33 #include "llvm/Support/Debug.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include <map>
  36 #include <stack>
  37 using namespace llvm;
  38 using namespace PatternMatch;
  39
  40 #define DEBUG_TYPE "lazy-value-info"
  41
  42 char LazyValueInfoWrapperPass::ID = 0;
  43 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
  44                 "Lazy Value Information Analysis", false, true)
  45 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  46 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
  47 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
  48                 "Lazy Value Information Analysis", false, true)
  49
  50 namespace llvm {
  51   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
  52 }
  53
  54 AnalysisKey LazyValueAnalysis::Key;
  55
  56 //===----------------------------------------------------------------------===//
  57 //                               LVILatticeVal
  58 //===----------------------------------------------------------------------===//
  59
  60 /// This is the information tracked by LazyValueInfo for each value.
  61 ///
  62 /// FIXME: This is basically just for bringup, this can be made a lot more rich
  63 /// in the future.
  64 ///
  65 namespace {
  66 class LVILatticeVal {
  67   enum LatticeValueTy {
  68     /// This Value has no known value yet.  As a result, this implies the
  69     /// producing instruction is dead.  Caution: We use this as the starting
  70     /// state in our local meet rules.  In this usage, it's taken to mean
  71     /// "nothing known yet".
  72     undefined,
  73
  74     /// This Value has a specific constant value.  (For constant integers,
  75     /// constantrange is used instead.  Integer typed constantexprs can appear
  76     /// as constant.)
  77     constant,
  78
  79     /// This Value is known to not have the specified value.  (For constant
  80     /// integers, constantrange is used instead.  As above, integer typed
  81     /// constantexprs can appear here.)
  82     notconstant,
  83
  84     /// The Value falls within this range. (Used only for integer typed values.)
  85     constantrange,
  86
  87     /// We can not precisely model the dynamic values this value might take.
  88     overdefined
  89   };
  90
  91   /// Val: This stores the current lattice value along with the Constant* for
  92   /// the constant if this is a 'constant' or 'notconstant' value.
  93   LatticeValueTy Tag;
  94   Constant *Val;
  95   ConstantRange Range;
  96
  97 public:
  98   LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
  99
 100   static LVILatticeVal get(Constant *C) {
 101     LVILatticeVal Res;
 102     if (!isa<UndefValue>(C))
 103       Res.markConstant(C);
 104     return Res;
 105   }
 106   static LVILatticeVal getNot(Constant *C) {
 107     LVILatticeVal Res;
 108     if (!isa<UndefValue>(C))
 109       Res.markNotConstant(C);
 110     return Res;
 111   }
 112   static LVILatticeVal getRange(ConstantRange CR) {
 113     LVILatticeVal Res;
 114     Res.markConstantRange(std::move(CR));
 115     return Res;
 116   }
 117   static LVILatticeVal getOverdefined() {
 118     LVILatticeVal Res;
 119     Res.markOverdefined();
 120     return Res;
 121   }
 122
 123   bool isUndefined() const     { return Tag == undefined; }
 124   bool isConstant() const      { return Tag == constant; }
 125   bool isNotConstant() const   { return Tag == notconstant; }
 126   bool isConstantRange() const { return Tag == constantrange; }
 127   bool isOverdefined() const   { return Tag == overdefined; }
 128
 129   Constant *getConstant() const {
 130     assert(isConstant() && "Cannot get the constant of a non-constant!");
 131     return Val;
 132   }
 133
 134   Constant *getNotConstant() const {
 135     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
 136     return Val;
 137   }
 138
 139   ConstantRange getConstantRange() const {
 140     assert(isConstantRange() &&
 141            "Cannot get the constant-range of a non-constant-range!");
 142     return Range;
 143   }
 144
 145 private:
 146   void markOverdefined() {
 147     if (isOverdefined())
 148       return;
 149     Tag = overdefined;
 150   }
 151
 152   void markConstant(Constant *V) {
 153     assert(V && "Marking constant with NULL");
 154     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 155       markConstantRange(ConstantRange(CI->getValue()));
 156       return;
 157     }
 158     if (isa<UndefValue>(V))
 159       return;
 160
 161     assert((!isConstant() || getConstant() == V) &&
 162            "Marking constant with different value");
 163     assert(isUndefined());
 164     Tag = constant;
 165     Val = V;
 166   }
 167
 168   void markNotConstant(Constant *V) {
 169     assert(V && "Marking constant with NULL");
 170     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 171       markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
 172       return;
 173     }
 174     if (isa<UndefValue>(V))
 175       return;
 176
 177     assert((!isConstant() || getConstant() != V) &&
 178            "Marking constant !constant with same value");
 179     assert((!isNotConstant() || getNotConstant() == V) &&
 180            "Marking !constant with different value");
 181     assert(isUndefined() || isConstant());
 182     Tag = notconstant;
 183     Val = V;
 184   }
 185
 186   void markConstantRange(ConstantRange NewR) {
 187     if (isConstantRange()) {
 188       if (NewR.isEmptySet())
 189         markOverdefined();
 190       else {
 191         Range = std::move(NewR);
 192       }
 193       return;
 194     }
 195
 196     assert(isUndefined());
 197     if (NewR.isEmptySet())
 198       markOverdefined();
 199     else {
 200       Tag = constantrange;
 201       Range = std::move(NewR);
 202     }
 203   }
 204
 205 public:
 206
 207   /// Merge the specified lattice value into this one, updating this
 208   /// one and returning true if anything changed.
 209   void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
 210     if (RHS.isUndefined() || isOverdefined())
 211       return;
 212     if (RHS.isOverdefined()) {
 213       markOverdefined();
 214       return;
 215     }
 216
 217     if (isUndefined()) {
 218       *this = RHS;
 219       return;
 220     }
 221
 222     if (isConstant()) {
 223       if (RHS.isConstant() && Val == RHS.Val)
 224           return;
 225       markOverdefined();
 226       return;
 227     }
 228
 229     if (isNotConstant()) {
 230       if (RHS.isNotConstant() && Val == RHS.Val)
 231           return;
 232       markOverdefined();
 233       return;
 234     }
 235
 236     assert(isConstantRange() && "New LVILattice type?");
 237     if (!RHS.isConstantRange()) {
 238       // We can get here if we've encountered a constantexpr of integer type
 239       // and merge it with a constantrange.
 240       markOverdefined();
 241       return;
 242     }
 243     ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
 244     if (NewR.isFullSet())
 245       markOverdefined();
 246     else
 247       markConstantRange(NewR);
 248   }
 249 };
 250
 251 } // end anonymous namespace.
 252
 253 namespace llvm {
 254 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
 255     LLVM_ATTRIBUTE_USED;
 256 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 257   if (Val.isUndefined())
 258     return OS << "undefined";
 259   if (Val.isOverdefined())
 260     return OS << "overdefined";
 261
 262   if (Val.isNotConstant())
 263     return OS << "notconstant<" << *Val.getNotConstant() << '>';
 264   if (Val.isConstantRange())
 265     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
 266               << Val.getConstantRange().getUpper() << '>';
 267   return OS << "constant<" << *Val.getConstant() << '>';
 268 }
 269 }
 270
 271 /// Returns true if this lattice value represents at most one possible value.
 272 /// This is as precise as any lattice value can get while still representing
 273 /// reachable code.
 274 static bool hasSingleValue(const LVILatticeVal &Val) {
 275   if (Val.isConstantRange() &&
 276       Val.getConstantRange().isSingleElement())
 277     // Integer constants are single element ranges
 278     return true;
 279   if (Val.isConstant())
 280     // Non integer constants
 281     return true;
 282   return false;
 283 }
 284
 285 /// Combine two sets of facts about the same value into a single set of
 286 /// facts.  Note that this method is not suitable for merging facts along
 287 /// different paths in a CFG; that's what the mergeIn function is for.  This
 288 /// is for merging facts gathered about the same value at the same location
 289 /// through two independent means.
 290 /// Notes:
 291 /// * This method does not promise to return the most precise possible lattice
 292 ///   value implied by A and B.  It is allowed to return any lattice element
 293 ///   which is at least as strong as *either* A or B (unless our facts
 294 ///   conflict, see below).
 295 /// * Due to unreachable code, the intersection of two lattice values could be
 296 ///   contradictory.  If this happens, we return some valid lattice value so as
 297 ///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
 298 ///   we do not make this guarantee.  TODO: This would be a useful enhancement.
 299 static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
 300   // Undefined is the strongest state.  It means the value is known to be along
 301   // an unreachable path.
 302   if (A.isUndefined())
 303     return A;
 304   if (B.isUndefined())
 305     return B;
 306
 307   // If we gave up for one, but got a useable fact from the other, use it.
 308   if (A.isOverdefined())
 309     return B;
 310   if (B.isOverdefined())
 311     return A;
 312
 313   // Can't get any more precise than constants.
 314   if (hasSingleValue(A))
 315     return A;
 316   if (hasSingleValue(B))
 317     return B;
 318
 319   // Could be either constant range or not constant here.
 320   if (!A.isConstantRange() || !B.isConstantRange()) {
 321     // TODO: Arbitrary choice, could be improved
 322     return A;
 323   }
 324
 325   // Intersect two constant ranges
 326   ConstantRange Range =
 327     A.getConstantRange().intersectWith(B.getConstantRange());
 328   // Note: An empty range is implicitly converted to overdefined internally.
 329   // TODO: We could instead use Undefined here since we've proven a conflict
 330   // and thus know this path must be unreachable.
 331   return LVILatticeVal::getRange(std::move(Range));
 332 }
 333
 334 //===----------------------------------------------------------------------===//
 335 //                          LazyValueInfoCache Decl
 336 //===----------------------------------------------------------------------===//
 337
 338 namespace {
 339   /// A callback value handle updates the cache when values are erased.
 340   class LazyValueInfoCache;
 341   struct LVIValueHandle final : public CallbackVH {
 342     // Needs to access getValPtr(), which is protected.
 343     friend struct DenseMapInfo<LVIValueHandle>;
 344
 345     LazyValueInfoCache *Parent;
 346
 347     LVIValueHandle(Value *V, LazyValueInfoCache *P)
 348       : CallbackVH(V), Parent(P) { }
 349
 350     void deleted() override;
 351     void allUsesReplacedWith(Value *V) override {
 352       deleted();
 353     }
 354   };
 355 } // end anonymous namespace
 356
 357 namespace {
 358   /// This is the cache kept by LazyValueInfo which
 359   /// maintains information about queries across the clients' queries.
 360   class LazyValueInfoCache {
 361     /// This is all of the cached block information for exactly one Value*.
 362     /// The entries are sorted by the BasicBlock* of the
 363     /// entries, allowing us to do a lookup with a binary search.
 364     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
 365     /// memory overhead.
 366     struct ValueCacheEntryTy {
 367       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
 368       LVIValueHandle Handle;
 369       SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
 370     };
 371
 372     /// This is all of the cached information for all values,
 373     /// mapped from Value* to key information.
 374     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
 375
 376     /// This tracks, on a per-block basis, the set of values that are
 377     /// over-defined at the end of that block.
 378     typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
 379         OverDefinedCacheTy;
 380     OverDefinedCacheTy OverDefinedCache;
 381
 382     /// Keep track of all blocks that we have ever seen, so we
 383     /// don't spend time removing unused blocks from our caches.
 384     DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
 385
 386   public:
 387     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
 388       SeenBlocks.insert(BB);
 389
 390       // Insert over-defined values into their own cache to reduce memory
 391       // overhead.
 392       if (Result.isOverdefined())
 393         OverDefinedCache[BB].insert(Val);
 394       else {
 395         auto It = ValueCache.find_as(Val);
 396         if (It == ValueCache.end()) {
 397           ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
 398           It = ValueCache.find_as(Val);
 399           assert(It != ValueCache.end() && "Val was just added to the map!");
 400         }
 401         It->second->BlockVals[BB] = Result;
 402       }
 403     }
 404
 405     bool isOverdefined(Value *V, BasicBlock *BB) const {
 406       auto ODI = OverDefinedCache.find(BB);
 407
 408       if (ODI == OverDefinedCache.end())
 409         return false;
 410
 411       return ODI->second.count(V);
 412     }
 413
 414     bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
 415       if (isOverdefined(V, BB))
 416         return true;
 417
 418       auto I = ValueCache.find_as(V);
 419       if (I == ValueCache.end())
 420         return false;
 421
 422       return I->second->BlockVals.count(BB);
 423     }
 424
 425     LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const {
 426       if (isOverdefined(V, BB))
 427         return LVILatticeVal::getOverdefined();
 428
 429       auto I = ValueCache.find_as(V);
 430       if (I == ValueCache.end())
 431         return LVILatticeVal();
 432       auto BBI = I->second->BlockVals.find(BB);
 433       if (BBI == I->second->BlockVals.end())
 434         return LVILatticeVal();
 435       return BBI->second;
 436     }
 437
 438     /// clear - Empty the cache.
 439     void clear() {
 440       SeenBlocks.clear();
 441       ValueCache.clear();
 442       OverDefinedCache.clear();
 443     }
 444
 445     /// Inform the cache that a given value has been deleted.
 446     void eraseValue(Value *V);
 447
 448     /// This is part of the update interface to inform the cache
 449     /// that a block has been deleted.
 450     void eraseBlock(BasicBlock *BB);
 451
 452     /// Updates the cache to remove any influence an overdefined value in
 453     /// OldSucc might have (unless also overdefined in NewSucc).  This just
 454     /// flushes elements from the cache and does not add any.
 455     void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
 456
 457     friend struct LVIValueHandle;
 458   };
 459 }
 460
 461 void LazyValueInfoCache::eraseValue(Value *V) {
 462   SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
 463   for (auto &I : OverDefinedCache) {
 464     SmallPtrSetImpl<Value *> &ValueSet = I.second;
 465     ValueSet.erase(V);
 466     if (ValueSet.empty())
 467       ToErase.push_back(I.first);
 468   }
 469   for (auto &BB : ToErase)
 470     OverDefinedCache.erase(BB);
 471
 472   ValueCache.erase(V);
 473 }
 474
 475 void LVIValueHandle::deleted() {
 476   // This erasure deallocates *this, so it MUST happen after we're done
 477   // using any and all members of *this.
 478   Parent->eraseValue(*this);
 479 }
 480
 481 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
 482   // Shortcut if we have never seen this block.
 483   DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
 484   if (I == SeenBlocks.end())
 485     return;
 486   SeenBlocks.erase(I);
 487
 488   auto ODI = OverDefinedCache.find(BB);
 489   if (ODI != OverDefinedCache.end())
 490     OverDefinedCache.erase(ODI);
 491
 492   for (auto &I : ValueCache)
 493     I.second->BlockVals.erase(BB);
 494 }
 495
 496 void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
 497                                         BasicBlock *NewSucc) {
 498   // When an edge in the graph has been threaded, values that we could not
 499   // determine a value for before (i.e. were marked overdefined) may be
 500   // possible to solve now. We do NOT try to proactively update these values.
 501   // Instead, we clear their entries from the cache, and allow lazy updating to
 502   // recompute them when needed.
 503
 504   // The updating process is fairly simple: we need to drop cached info
 505   // for all values that were marked overdefined in OldSucc, and for those same
 506   // values in any successor of OldSucc (except NewSucc) in which they were
 507   // also marked overdefined.
 508   std::vector<BasicBlock*> worklist;
 509   worklist.push_back(OldSucc);
 510
 511   auto I = OverDefinedCache.find(OldSucc);
 512   if (I == OverDefinedCache.end())
 513     return; // Nothing to process here.
 514   SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
 515
 516   // Use a worklist to perform a depth-first search of OldSucc's successors.
 517   // NOTE: We do not need a visited list since any blocks we have already
 518   // visited will have had their overdefined markers cleared already, and we
 519   // thus won't loop to their successors.
 520   while (!worklist.empty()) {
 521     BasicBlock *ToUpdate = worklist.back();
 522     worklist.pop_back();
 523
 524     // Skip blocks only accessible through NewSucc.
 525     if (ToUpdate == NewSucc) continue;
 526
 527     // If a value was marked overdefined in OldSucc, and is here too...
 528     auto OI = OverDefinedCache.find(ToUpdate);
 529     if (OI == OverDefinedCache.end())
 530       continue;
 531     SmallPtrSetImpl<Value *> &ValueSet = OI->second;
 532
 533     bool changed = false;
 534     for (Value *V : ValsToClear) {
 535       if (!ValueSet.erase(V))
 536         continue;
 537
 538       // If we removed anything, then we potentially need to update
 539       // blocks successors too.
 540       changed = true;
 541
 542       if (ValueSet.empty()) {
 543         OverDefinedCache.erase(OI);
 544         break;
 545       }
 546     }
 547
 548     if (!changed) continue;
 549
 550     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
 551   }
 552 }
 553
 554 namespace {
 555   // The actual implementation of the lazy analysis and update.  Note that the
 556   // inheritance from LazyValueInfoCache is intended to be temporary while
 557   // splitting the code and then transitioning to a has-a relationship.
 558   class LazyValueInfoImpl {
 559
 560     /// Cached results from previous queries
 561     LazyValueInfoCache TheCache;
 562
 563     /// This stack holds the state of the value solver during a query.
 564     /// It basically emulates the callstack of the naive
 565     /// recursive value lookup process.
 566     std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
 567
 568     /// Keeps track of which block-value pairs are in BlockValueStack.
 569     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
 570
 571     /// Push BV onto BlockValueStack unless it's already in there.
 572     /// Returns true on success.
 573     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
 574       if (!BlockValueSet.insert(BV).second)
 575         return false;  // It's already in the stack.
 576
 577       DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
 578                    << "\n");
 579       BlockValueStack.push(BV);
 580       return true;
 581     }
 582
 583     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
 584     const DataLayout &DL; ///< A mandatory DataLayout
 585     DominatorTree *DT;    ///< An optional DT pointer.
 586
 587   LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
 588   bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
 589                     LVILatticeVal &Result, Instruction *CxtI = nullptr);
 590   bool hasBlockValue(Value *Val, BasicBlock *BB);
 591
 592   // These methods process one work item and may add more. A false value
 593   // returned means that the work item was not completely processed and must
 594   // be revisited after going through the new items.
 595   bool solveBlockValue(Value *Val, BasicBlock *BB);
 596   bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB);
 597   bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
 598   bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
 599   bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
 600                              BasicBlock *BB);
 601   bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI,
 602                                BasicBlock *BB);
 603   bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI,
 604                            BasicBlock *BB);
 605   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
 606                                                      LVILatticeVal &BBLV,
 607                                               Instruction *BBI);
 608
 609   void solve();
 610
 611   public:
 612     /// This is the query interface to determine the lattice
 613     /// value for the specified Value* at the end of the specified block.
 614     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
 615                                   Instruction *CxtI = nullptr);
 616
 617     /// This is the query interface to determine the lattice
 618     /// value for the specified Value* at the specified instruction (generally
 619     /// from an assume intrinsic).
 620     LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
 621
 622     /// This is the query interface to determine the lattice
 623     /// value for the specified Value* that is true on the specified edge.
 624     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
 625                                  Instruction *CxtI = nullptr);
 626
 627     /// Complete flush all previously computed values
 628     void clear() {
 629       TheCache.clear();
 630     }
 631
 632     /// This is part of the update interface to inform the cache
 633     /// that a block has been deleted.
 634     void eraseBlock(BasicBlock *BB) {
 635       TheCache.eraseBlock(BB);
 636     }
 637
 638     /// This is the update interface to inform the cache that an edge from
 639     /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
 640     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 641
 642     LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
 643                        DominatorTree *DT = nullptr)
 644         : AC(AC), DL(DL), DT(DT) {}
 645   };
 646 } // end anonymous namespace
 647
 648 void LazyValueInfoImpl::solve() {
 649   while (!BlockValueStack.empty()) {
 650     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
 651     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
 652
 653     if (solveBlockValue(e.second, e.first)) {
 654       // The work item was completely processed.
 655       assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
 656       assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
 657              "Result should be in cache!");
 658
 659       DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
 660                    << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
 661
 662       BlockValueStack.pop();
 663       BlockValueSet.erase(e);
 664     } else {
 665       // More work needs to be done before revisiting.
 666       assert(BlockValueStack.top() != e && "Stack should have been pushed!");
 667     }
 668   }
 669 }
 670
 671 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
 672   // If already a constant, there is nothing to compute.
 673   if (isa<Constant>(Val))
 674     return true;
 675
 676   return TheCache.hasCachedValueInfo(Val, BB);
 677 }
 678
 679 LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) {
 680   // If already a constant, there is nothing to compute.
 681   if (Constant *VC = dyn_cast<Constant>(Val))
 682     return LVILatticeVal::get(VC);
 683
 684   return TheCache.getCachedValueInfo(Val, BB);
 685 }
 686
 687 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
 688   switch (BBI->getOpcode()) {
 689   default: break;
 690   case Instruction::Load:
 691   case Instruction::Call:
 692   case Instruction::Invoke:
 693     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
 694       if (isa<IntegerType>(BBI->getType())) {
 695         return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
 696       }
 697     break;
 698   };
 699   // Nothing known - will be intersected with other facts
 700   return LVILatticeVal::getOverdefined();
 701 }
 702
 703 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
 704   if (isa<Constant>(Val))
 705     return true;
 706
 707   if (TheCache.hasCachedValueInfo(Val, BB)) {
 708     // If we have a cached value, use that.
 709     DEBUG(dbgs() << "  reuse BB '" << BB->getName()
 710                  << "' val=" << TheCache.getCachedValueInfo(Val, BB) << '\n');
 711
 712     // Since we're reusing a cached value, we don't need to update the
 713     // OverDefinedCache. The cache will have been properly updated whenever the
 714     // cached value was inserted.
 715     return true;
 716   }
 717
 718   // Hold off inserting this value into the Cache in case we have to return
 719   // false and come back later.
 720   LVILatticeVal Res;
 721   if (!solveBlockValueImpl(Res, Val, BB))
 722     // Work pushed, will revisit
 723     return false;
 724
 725   TheCache.insertResult(Val, BB, Res);
 726   return true;
 727 }
 728
 729 bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res,
 730                                             Value *Val, BasicBlock *BB) {
 731
 732   Instruction *BBI = dyn_cast<Instruction>(Val);
 733   if (!BBI || BBI->getParent() != BB)
 734     return solveBlockValueNonLocal(Res, Val, BB);
 735
 736   if (PHINode *PN = dyn_cast<PHINode>(BBI))
 737     return solveBlockValuePHINode(Res, PN, BB);
 738
 739   if (auto *SI = dyn_cast<SelectInst>(BBI))
 740     return solveBlockValueSelect(Res, SI, BB);
 741
 742   // If this value is a nonnull pointer, record it's range and bailout.  Note
 743   // that for all other pointer typed values, we terminate the search at the
 744   // definition.  We could easily extend this to look through geps, bitcasts,
 745   // and the like to prove non-nullness, but it's not clear that's worth it
 746   // compile time wise.  The context-insensative value walk done inside
 747   // isKnownNonNull gets most of the profitable cases at much less expense.
 748   // This does mean that we have a sensativity to where the defining
 749   // instruction is placed, even if it could legally be hoisted much higher.
 750   // That is unfortunate.
 751   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
 752   if (PT && isKnownNonNull(BBI)) {
 753     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
 754     return true;
 755   }
 756   if (BBI->getType()->isIntegerTy()) {
 757     if (isa<CastInst>(BBI))
 758       return solveBlockValueCast(Res, BBI, BB);
 759
 760     BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
 761     if (BO && isa<ConstantInt>(BO->getOperand(1)))
 762       return solveBlockValueBinaryOp(Res, BBI, BB);
 763   }
 764
 765   DEBUG(dbgs() << " compute BB '" << BB->getName()
 766                  << "' - unknown inst def found.\n");
 767   Res = getFromRangeMetadata(BBI);
 768   return true;
 769 }
 770
 771 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
 772   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
 773     return L->getPointerAddressSpace() == 0 &&
 774            GetUnderlyingObject(L->getPointerOperand(),
 775                                L->getModule()->getDataLayout()) == Ptr;
 776   }
 777   if (StoreInst *S = dyn_cast<StoreInst>(I)) {
 778     return S->getPointerAddressSpace() == 0 &&
 779            GetUnderlyingObject(S->getPointerOperand(),
 780                                S->getModule()->getDataLayout()) == Ptr;
 781   }
 782   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
 783     if (MI->isVolatile()) return false;
 784
 785     // FIXME: check whether it has a valuerange that excludes zero?
 786     ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
 787     if (!Len || Len->isZero()) return false;
 788
 789     if (MI->getDestAddressSpace() == 0)
 790       if (GetUnderlyingObject(MI->getRawDest(),
 791                               MI->getModule()->getDataLayout()) == Ptr)
 792         return true;
 793     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
 794       if (MTI->getSourceAddressSpace() == 0)
 795         if (GetUnderlyingObject(MTI->getRawSource(),
 796                                 MTI->getModule()->getDataLayout()) == Ptr)
 797           return true;
 798   }
 799   return false;
 800 }
 801
 802 /// Return true if the allocation associated with Val is ever dereferenced
 803 /// within the given basic block.  This establishes the fact Val is not null,
 804 /// but does not imply that the memory at Val is dereferenceable.  (Val may
 805 /// point off the end of the dereferenceable part of the object.)
 806 static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
 807   assert(Val->getType()->isPointerTy());
 808
 809   const DataLayout &DL = BB->getModule()->getDataLayout();
 810   Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
 811   // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
 812   // inside InstructionDereferencesPointer either.
 813   if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
 814     for (Instruction &I : *BB)
 815       if (InstructionDereferencesPointer(&I, UnderlyingVal))
 816         return true;
 817   return false;
 818 }
 819
 820 bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
 821                                                  Value *Val, BasicBlock *BB) {
 822   LVILatticeVal Result;  // Start Undefined.
 823
 824   // If this is the entry block, we must be asking about an argument.  The
 825   // value is overdefined.
 826   if (BB == &BB->getParent()->getEntryBlock()) {
 827     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
 828     // Bofore giving up, see if we can prove the pointer non-null local to
 829     // this particular block.
 830     if (Val->getType()->isPointerTy() &&
 831         (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) {
 832       PointerType *PTy = cast<PointerType>(Val->getType());
 833       Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
 834     } else {
 835       Result = LVILatticeVal::getOverdefined();
 836     }
 837     BBLV = Result;
 838     return true;
 839   }
 840
 841   // Loop over all of our predecessors, merging what we know from them into
 842   // result.
 843   bool EdgesMissing = false;
 844   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 845     LVILatticeVal EdgeResult;
 846     EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
 847     if (EdgesMissing)
 848       continue;
 849
 850     Result.mergeIn(EdgeResult, DL);
 851
 852     // If we hit overdefined, exit early.  The BlockVals entry is already set
 853     // to overdefined.
 854     if (Result.isOverdefined()) {
 855       DEBUG(dbgs() << " compute BB '" << BB->getName()
 856             << "' - overdefined because of pred (non local).\n");
 857       // Before giving up, see if we can prove the pointer non-null local to
 858       // this particular block.
 859       if (Val->getType()->isPointerTy() &&
 860           isObjectDereferencedInBlock(Val, BB)) {
 861         PointerType *PTy = cast<PointerType>(Val->getType());
 862         Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
 863       }
 864
 865       BBLV = Result;
 866       return true;
 867     }
 868   }
 869   if (EdgesMissing)
 870     return false;
 871
 872   // Return the merged value, which is more precise than 'overdefined'.
 873   assert(!Result.isOverdefined());
 874   BBLV = Result;
 875   return true;
 876 }
 877
 878 bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
 879                                                 PHINode *PN, BasicBlock *BB) {
 880   LVILatticeVal Result;  // Start Undefined.
 881
 882   // Loop over all of our predecessors, merging what we know from them into
 883   // result.
 884   bool EdgesMissing = false;
 885   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 886     BasicBlock *PhiBB = PN->getIncomingBlock(i);
 887     Value *PhiVal = PN->getIncomingValue(i);
 888     LVILatticeVal EdgeResult;
 889     // Note that we can provide PN as the context value to getEdgeValue, even
 890     // though the results will be cached, because PN is the value being used as
 891     // the cache key in the caller.
 892     EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
 893     if (EdgesMissing)
 894       continue;
 895
 896     Result.mergeIn(EdgeResult, DL);
 897
 898     // If we hit overdefined, exit early.  The BlockVals entry is already set
 899     // to overdefined.
 900     if (Result.isOverdefined()) {
 901       DEBUG(dbgs() << " compute BB '" << BB->getName()
 902             << "' - overdefined because of pred (local).\n");
 903
 904       BBLV = Result;
 905       return true;
 906     }
 907   }
 908   if (EdgesMissing)
 909     return false;
 910
 911   // Return the merged value, which is more precise than 'overdefined'.
 912   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
 913   BBLV = Result;
 914   return true;
 915 }
 916
 917 static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
 918                                            bool isTrueDest = true);
 919
 920 // If we can determine a constraint on the value given conditions assumed by
 921 // the program, intersect those constraints with BBLV
 922 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
 923         Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
 924   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
 925   if (!BBI)
 926     return;
 927
 928   for (auto &AssumeVH : AC->assumptions()) {
 929     if (!AssumeVH)
 930       continue;
 931     auto *I = cast<CallInst>(AssumeVH);
 932     if (!isValidAssumeForContext(I, BBI, DT))
 933       continue;
 934
 935     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
 936   }
 937
 938   // If guards are not used in the module, don't spend time looking for them
 939   auto *GuardDecl = BBI->getModule()->getFunction(
 940           Intrinsic::getName(Intrinsic::experimental_guard));
 941   if (!GuardDecl || GuardDecl->use_empty())
 942     return;
 943
 944   for (Instruction &I : make_range(BBI->getIterator().getReverse(),
 945                                    BBI->getParent()->rend())) {
 946     Value *Cond = nullptr;
 947     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
 948       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
 949   }
 950 }
 951
 952 bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV,
 953                                                SelectInst *SI, BasicBlock *BB) {
 954
 955   // Recurse on our inputs if needed
 956   if (!hasBlockValue(SI->getTrueValue(), BB)) {
 957     if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
 958       return false;
 959     BBLV = LVILatticeVal::getOverdefined();
 960     return true;
 961   }
 962   LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
 963   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
 964   // extra slots in the table if we can.
 965   if (TrueVal.isOverdefined()) {
 966     BBLV = LVILatticeVal::getOverdefined();
 967     return true;
 968   }
 969
 970   if (!hasBlockValue(SI->getFalseValue(), BB)) {
 971     if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
 972       return false;
 973     BBLV = LVILatticeVal::getOverdefined();
 974     return true;
 975   }
 976   LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
 977   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
 978   // extra slots in the table if we can.
 979   if (FalseVal.isOverdefined()) {
 980     BBLV = LVILatticeVal::getOverdefined();
 981     return true;
 982   }
 983
 984   if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
 985     ConstantRange TrueCR = TrueVal.getConstantRange();
 986     ConstantRange FalseCR = FalseVal.getConstantRange();
 987     Value *LHS = nullptr;
 988     Value *RHS = nullptr;
 989     SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
 990     // Is this a min specifically of our two inputs?  (Avoid the risk of
 991     // ValueTracking getting smarter looking back past our immediate inputs.)
 992     if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
 993         LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
 994       ConstantRange ResultCR = [&]() {
 995         switch (SPR.Flavor) {
 996         default:
 997           llvm_unreachable("unexpected minmax type!");
 998         case SPF_SMIN:                   /// Signed minimum
 999           return TrueCR.smin(FalseCR);
1000         case SPF_UMIN:                   /// Unsigned minimum
1001           return TrueCR.umin(FalseCR);
1002         case SPF_SMAX:                   /// Signed maximum
1003           return TrueCR.smax(FalseCR);
1004         case SPF_UMAX:                   /// Unsigned maximum
1005           return TrueCR.umax(FalseCR);
1006         };
1007       }();
1008       BBLV = LVILatticeVal::getRange(ResultCR);
1009       return true;
1010     }
1011
1012     // TODO: ABS, NABS from the SelectPatternResult
1013   }
1014
1015   // Can we constrain the facts about the true and false values by using the
1016   // condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
1017   // TODO: We could potentially refine an overdefined true value above.
1018   Value *Cond = SI->getCondition();
1019   TrueVal = intersect(TrueVal,
1020                       getValueFromCondition(SI->getTrueValue(), Cond, true));
1021   FalseVal = intersect(FalseVal,
1022                        getValueFromCondition(SI->getFalseValue(), Cond, false));
1023
1024   // Handle clamp idioms such as:
1025   //   %24 = constantrange<0, 17>
1026   //   %39 = icmp eq i32 %24, 0
1027   //   %40 = add i32 %24, -1
1028   //   %siv.next = select i1 %39, i32 16, i32 %40
1029   //   %siv.next = constantrange<0, 17> not <-1, 17>
1030   // In general, this can handle any clamp idiom which tests the edge
1031   // condition via an equality or inequality.
1032   if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
1033     ICmpInst::Predicate Pred = ICI->getPredicate();
1034     Value *A = ICI->getOperand(0);
1035     if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
1036       auto addConstants = [](ConstantInt *A, ConstantInt *B) {
1037         assert(A->getType() == B->getType());
1038         return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
1039       };
1040       // See if either input is A + C2, subject to the constraint from the
1041       // condition that A != C when that input is used.  We can assume that
1042       // that input doesn't include C + C2.
1043       ConstantInt *CIAdded;
1044       switch (Pred) {
1045       default: break;
1046       case ICmpInst::ICMP_EQ:
1047         if (match(SI->getFalseValue(), m_Add(m_Specific(A),
1048                                              m_ConstantInt(CIAdded)))) {
1049           auto ResNot = addConstants(CIBase, CIAdded);
1050           FalseVal = intersect(FalseVal,
1051                                LVILatticeVal::getNot(ResNot));
1052         }
1053         break;
1054       case ICmpInst::ICMP_NE:
1055         if (match(SI->getTrueValue(), m_Add(m_Specific(A),
1056                                             m_ConstantInt(CIAdded)))) {
1057           auto ResNot = addConstants(CIBase, CIAdded);
1058           TrueVal = intersect(TrueVal,
1059                               LVILatticeVal::getNot(ResNot));
1060         }
1061         break;
1062       };
1063     }
1064   }
1065
1066   LVILatticeVal Result;  // Start Undefined.
1067   Result.mergeIn(TrueVal, DL);
1068   Result.mergeIn(FalseVal, DL);
1069   BBLV = Result;
1070   return true;
1071 }
1072
1073 bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV,
1074                                              Instruction *BBI,
1075                                              BasicBlock *BB) {
1076   if (!BBI->getOperand(0)->getType()->isSized()) {
1077     // Without knowing how wide the input is, we can't analyze it in any useful
1078     // way.
1079     BBLV = LVILatticeVal::getOverdefined();
1080     return true;
1081   }
1082
1083   // Filter out casts we don't know how to reason about before attempting to
1084   // recurse on our operand.  This can cut a long search short if we know we're
1085   // not going to be able to get any useful information anways.
1086   switch (BBI->getOpcode()) {
1087   case Instruction::Trunc:
1088   case Instruction::SExt:
1089   case Instruction::ZExt:
1090   case Instruction::BitCast:
1091     break;
1092   default:
1093     // Unhandled instructions are overdefined.
1094     DEBUG(dbgs() << " compute BB '" << BB->getName()
1095                  << "' - overdefined (unknown cast).\n");
1096     BBLV = LVILatticeVal::getOverdefined();
1097     return true;
1098   }
1099
1100   // Figure out the range of the LHS.  If that fails, we still apply the
1101   // transfer rule on the full set since we may be able to locally infer
1102   // interesting facts.
1103   if (!hasBlockValue(BBI->getOperand(0), BB))
1104     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
1105       // More work to do before applying this transfer rule.
1106       return false;
1107
1108   const unsigned OperandBitWidth =
1109     DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
1110   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1111   if (hasBlockValue(BBI->getOperand(0), BB)) {
1112     LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1113     intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal,
1114                                                   BBI);
1115     if (LHSVal.isConstantRange())
1116       LHSRange = LHSVal.getConstantRange();
1117   }
1118
1119   const unsigned ResultBitWidth =
1120     cast<IntegerType>(BBI->getType())->getBitWidth();
1121
1122   // NOTE: We're currently limited by the set of operations that ConstantRange
1123   // can evaluate symbolically.  Enhancing that set will allows us to analyze
1124   // more definitions.
1125   auto CastOp = (Instruction::CastOps) BBI->getOpcode();
1126   BBLV = LVILatticeVal::getRange(LHSRange.castOp(CastOp, ResultBitWidth));
1127   return true;
1128 }
1129
1130 bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
1131                                                  Instruction *BBI,
1132                                                  BasicBlock *BB) {
1133
1134   assert(BBI->getOperand(0)->getType()->isSized() &&
1135          "all operands to binary operators are sized");
1136
1137   // Filter out operators we don't know how to reason about before attempting to
1138   // recurse on our operand(s).  This can cut a long search short if we know
1139   // we're not going to be able to get any useful information anways.
1140   switch (BBI->getOpcode()) {
1141   case Instruction::Add:
1142   case Instruction::Sub:
1143   case Instruction::Mul:
1144   case Instruction::UDiv:
1145   case Instruction::Shl:
1146   case Instruction::LShr:
1147   case Instruction::And:
1148   case Instruction::Or:
1149     // continue into the code below
1150     break;
1151   default:
1152     // Unhandled instructions are overdefined.
1153     DEBUG(dbgs() << " compute BB '" << BB->getName()
1154                  << "' - overdefined (unknown binary operator).\n");
1155     BBLV = LVILatticeVal::getOverdefined();
1156     return true;
1157   };
1158
1159   // Figure out the range of the LHS.  If that fails, use a conservative range,
1160   // but apply the transfer rule anyways.  This lets us pick up facts from
1161   // expressions like "and i32 (call i32 @foo()), 32"
1162   if (!hasBlockValue(BBI->getOperand(0), BB))
1163     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
1164       // More work to do before applying this transfer rule.
1165       return false;
1166
1167   const unsigned OperandBitWidth =
1168     DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
1169   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1170   if (hasBlockValue(BBI->getOperand(0), BB)) {
1171     LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1172     intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal,
1173                                                   BBI);
1174     if (LHSVal.isConstantRange())
1175       LHSRange = LHSVal.getConstantRange();
1176   }
1177
1178   ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
1179   ConstantRange RHSRange = ConstantRange(RHS->getValue());
1180
1181   // NOTE: We're currently limited by the set of operations that ConstantRange
1182   // can evaluate symbolically.  Enhancing that set will allows us to analyze
1183   // more definitions.
1184   auto BinOp = (Instruction::BinaryOps) BBI->getOpcode();
1185   BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1186   return true;
1187 }
1188
1189 static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1190                                                bool isTrueDest) {
1191   Value *LHS = ICI->getOperand(0);
1192   Value *RHS = ICI->getOperand(1);
1193   CmpInst::Predicate Predicate = ICI->getPredicate();
1194
1195   if (isa<Constant>(RHS)) {
1196     if (ICI->isEquality() && LHS == Val) {
1197       // We know that V has the RHS constant if this is a true SETEQ or
1198       // false SETNE.
1199       if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1200         return LVILatticeVal::get(cast<Constant>(RHS));
1201       else
1202         return LVILatticeVal::getNot(cast<Constant>(RHS));
1203     }
1204   }
1205
1206   if (!Val->getType()->isIntegerTy())
1207     return LVILatticeVal::getOverdefined();
1208
1209   // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1210   // range of Val guaranteed by the condition. Recognize comparisons in the from
1211   // of:
1212   //  icmp <pred> Val, ...
1213   //  icmp <pred> (add Val, Offset), ...
1214   // The latter is the range checking idiom that InstCombine produces. Subtract
1215   // the offset from the allowed range for RHS in this case.
1216
1217   // Val or (add Val, Offset) can be on either hand of the comparison
1218   if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1219     std::swap(LHS, RHS);
1220     Predicate = CmpInst::getSwappedPredicate(Predicate);
1221   }
1222
1223   ConstantInt *Offset = nullptr;
1224   if (LHS != Val)
1225     match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1226
1227   if (LHS == Val || Offset) {
1228     // Calculate the range of values that are allowed by the comparison
1229     ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1230                            /*isFullSet=*/true);
1231     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1232       RHSRange = ConstantRange(CI->getValue());
1233     else if (Instruction *I = dyn_cast<Instruction>(RHS))
1234       if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1235         RHSRange = getConstantRangeFromMetadata(*Ranges);
1236
1237     // If we're interested in the false dest, invert the condition
1238     CmpInst::Predicate Pred =
1239             isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1240     ConstantRange TrueValues =
1241             ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1242
1243     if (Offset) // Apply the offset from above.
1244       TrueValues = TrueValues.subtract(Offset->getValue());
1245
1246     return LVILatticeVal::getRange(std::move(TrueValues));
1247   }
1248
1249   return LVILatticeVal::getOverdefined();
1250 }
1251
1252 static LVILatticeVal
1253 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1254                       DenseMap<Value*, LVILatticeVal> &Visited);
1255
1256 static LVILatticeVal
1257 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1258                           DenseMap<Value*, LVILatticeVal> &Visited) {
1259   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1260     return getValueFromICmpCondition(Val, ICI, isTrueDest);
1261
1262   // Handle conditions in the form of (cond1 && cond2), we know that on the
1263   // true dest path both of the conditions hold.
1264   if (!isTrueDest)
1265     return LVILatticeVal::getOverdefined();
1266
1267   BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1268   if (!BO || BO->getOpcode() != BinaryOperator::And)
1269     return LVILatticeVal::getOverdefined();
1270
1271   auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
1272   auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
1273   return intersect(RHS, LHS);
1274 }
1275
1276 static LVILatticeVal
1277 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1278                       DenseMap<Value*, LVILatticeVal> &Visited) {
1279   auto I = Visited.find(Cond);
1280   if (I != Visited.end())
1281     return I->second;
1282
1283   auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1284   Visited[Cond] = Result;
1285   return Result;
1286 }
1287
1288 LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
1289   assert(Cond && "precondition");
1290   DenseMap<Value*, LVILatticeVal> Visited;
1291   return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1292 }
1293
1294 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1295 /// Val is not constrained on the edge.  Result is unspecified if return value
1296 /// is false.
1297 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1298                               BasicBlock *BBTo, LVILatticeVal &Result) {
1299   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1300   // know that v != 0.
1301   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1302     // If this is a conditional branch and only one successor goes to BBTo, then
1303     // we may be able to infer something from the condition.
1304     if (BI->isConditional() &&
1305         BI->getSuccessor(0) != BI->getSuccessor(1)) {
1306       bool isTrueDest = BI->getSuccessor(0) == BBTo;
1307       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1308              "BBTo isn't a successor of BBFrom");
1309
1310       // If V is the condition of the branch itself, then we know exactly what
1311       // it is.
1312       if (BI->getCondition() == Val) {
1313         Result = LVILatticeVal::get(ConstantInt::get(
1314                               Type::getInt1Ty(Val->getContext()), isTrueDest));
1315         return true;
1316       }
1317
1318       // If the condition of the branch is an equality comparison, we may be
1319       // able to infer the value.
1320       Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest);
1321       if (!Result.isOverdefined())
1322         return true;
1323     }
1324   }
1325
1326   // If the edge was formed by a switch on the value, then we may know exactly
1327   // what it is.
1328   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1329     if (SI->getCondition() != Val)
1330       return false;
1331
1332     bool DefaultCase = SI->getDefaultDest() == BBTo;
1333     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1334     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1335
1336     for (SwitchInst::CaseIt i : SI->cases()) {
1337       ConstantRange EdgeVal(i.getCaseValue()->getValue());
1338       if (DefaultCase) {
1339         // It is possible that the default destination is the destination of
1340         // some cases. There is no need to perform difference for those cases.
1341         if (i.getCaseSuccessor() != BBTo)
1342           EdgesVals = EdgesVals.difference(EdgeVal);
1343       } else if (i.getCaseSuccessor() == BBTo)
1344         EdgesVals = EdgesVals.unionWith(EdgeVal);
1345     }
1346     Result = LVILatticeVal::getRange(std::move(EdgesVals));
1347     return true;
1348   }
1349   return false;
1350 }
1351
1352 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1353 /// the basic block if the edge does not constrain Val.
1354 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1355                                       BasicBlock *BBTo, LVILatticeVal &Result,
1356                                       Instruction *CxtI) {
1357   // If already a constant, there is nothing to compute.
1358   if (Constant *VC = dyn_cast<Constant>(Val)) {
1359     Result = LVILatticeVal::get(VC);
1360     return true;
1361   }
1362
1363   LVILatticeVal LocalResult;
1364   if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1365     // If we couldn't constrain the value on the edge, LocalResult doesn't
1366     // provide any information.
1367     LocalResult = LVILatticeVal::getOverdefined();
1368
1369   if (hasSingleValue(LocalResult)) {
1370     // Can't get any more precise here
1371     Result = LocalResult;
1372     return true;
1373   }
1374
1375   if (!hasBlockValue(Val, BBFrom)) {
1376     if (pushBlockValue(std::make_pair(BBFrom, Val)))
1377       return false;
1378     // No new information.
1379     Result = LocalResult;
1380     return true;
1381   }
1382
1383   // Try to intersect ranges of the BB and the constraint on the edge.
1384   LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
1385   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1386                                                 BBFrom->getTerminator());
1387   // We can use the context instruction (generically the ultimate instruction
1388   // the calling pass is trying to simplify) here, even though the result of
1389   // this function is generally cached when called from the solve* functions
1390   // (and that cached result might be used with queries using a different
1391   // context instruction), because when this function is called from the solve*
1392   // functions, the context instruction is not provided. When called from
1393   // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1394   // but then the result is not cached.
1395   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1396
1397   Result = intersect(LocalResult, InBlock);
1398   return true;
1399 }
1400
1401 LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1402                                                   Instruction *CxtI) {
1403   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1404         << BB->getName() << "'\n");
1405
1406   assert(BlockValueStack.empty() && BlockValueSet.empty());
1407   if (!hasBlockValue(V, BB)) {
1408     pushBlockValue(std::make_pair(BB, V));
1409     solve();
1410   }
1411   LVILatticeVal Result = getBlockValue(V, BB);
1412   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1413
1414   DEBUG(dbgs() << "  Result = " << Result << "\n");
1415   return Result;
1416 }
1417
1418 LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1419   DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1420         << CxtI->getName() << "'\n");
1421
1422   if (auto *C = dyn_cast<Constant>(V))
1423     return LVILatticeVal::get(C);
1424
1425   LVILatticeVal Result = LVILatticeVal::getOverdefined();
1426   if (auto *I = dyn_cast<Instruction>(V))
1427     Result = getFromRangeMetadata(I);
1428   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1429
1430   DEBUG(dbgs() << "  Result = " << Result << "\n");
1431   return Result;
1432 }
1433
1434 LVILatticeVal LazyValueInfoImpl::
1435 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1436                Instruction *CxtI) {
1437   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1438         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1439
1440   LVILatticeVal Result;
1441   if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1442     solve();
1443     bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1444     (void)WasFastQuery;
1445     assert(WasFastQuery && "More work to do after problem solved?");
1446   }
1447
1448   DEBUG(dbgs() << "  Result = " << Result << "\n");
1449   return Result;
1450 }
1451
1452 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1453                                    BasicBlock *NewSucc) {
1454   TheCache.threadEdgeImpl(OldSucc, NewSucc);
1455 }
1456
1457 //===----------------------------------------------------------------------===//
1458 //                            LazyValueInfo Impl
1459 //===----------------------------------------------------------------------===//
1460
1461 /// This lazily constructs the LazyValueInfoImpl.
1462 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1463                                   const DataLayout *DL,
1464                                   DominatorTree *DT = nullptr) {
1465   if (!PImpl) {
1466     assert(DL && "getCache() called with a null DataLayout");
1467     PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1468   }
1469   return *static_cast<LazyValueInfoImpl*>(PImpl);
1470 }
1471
1472 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1473   Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1474   const DataLayout &DL = F.getParent()->getDataLayout();
1475
1476   DominatorTreeWrapperPass *DTWP =
1477       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1478   Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1479   Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1480
1481   if (Info.PImpl)
1482     getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1483
1484   // Fully lazy.
1485   return false;
1486 }
1487
1488 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1489   AU.setPreservesAll();
1490   AU.addRequired<AssumptionCacheTracker>();
1491   AU.addRequired<TargetLibraryInfoWrapperPass>();
1492 }
1493
1494 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1495
1496 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1497
1498 void LazyValueInfo::releaseMemory() {
1499   // If the cache was allocated, free it.
1500   if (PImpl) {
1501     delete &getImpl(PImpl, AC, nullptr);
1502     PImpl = nullptr;
1503   }
1504 }
1505
1506 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1507
1508 LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
1509   auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1510   auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1511   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1512
1513   return LazyValueInfo(&AC, &TLI, DT);
1514 }
1515
1516 /// Returns true if we can statically tell that this value will never be a
1517 /// "useful" constant.  In practice, this means we've got something like an
1518 /// alloca or a malloc call for which a comparison against a constant can
1519 /// only be guarding dead code.  Note that we are potentially giving up some
1520 /// precision in dead code (a constant result) in favour of avoiding a
1521 /// expensive search for a easily answered common query.
1522 static bool isKnownNonConstant(Value *V) {
1523   V = V->stripPointerCasts();
1524   // The return val of alloc cannot be a Constant.
1525   if (isa<AllocaInst>(V))
1526     return true;
1527   return false;
1528 }
1529
1530 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1531                                      Instruction *CxtI) {
1532   // Bail out early if V is known not to be a Constant.
1533   if (isKnownNonConstant(V))
1534     return nullptr;
1535
1536   const DataLayout &DL = BB->getModule()->getDataLayout();
1537   LVILatticeVal Result =
1538       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1539
1540   if (Result.isConstant())
1541     return Result.getConstant();
1542   if (Result.isConstantRange()) {
1543     ConstantRange CR = Result.getConstantRange();
1544     if (const APInt *SingleVal = CR.getSingleElement())
1545       return ConstantInt::get(V->getContext(), *SingleVal);
1546   }
1547   return nullptr;
1548 }
1549
1550 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1551                                               Instruction *CxtI) {
1552   assert(V->getType()->isIntegerTy());
1553   unsigned Width = V->getType()->getIntegerBitWidth();
1554   const DataLayout &DL = BB->getModule()->getDataLayout();
1555   LVILatticeVal Result =
1556       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1557   if (Result.isUndefined())
1558     return ConstantRange(Width, /*isFullSet=*/false);
1559   if (Result.isConstantRange())
1560     return Result.getConstantRange();
1561   // We represent ConstantInt constants as constant ranges but other kinds
1562   // of integer constants, i.e. ConstantExpr will be tagged as constants
1563   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1564          "ConstantInt value must be represented as constantrange");
1565   return ConstantRange(Width, /*isFullSet=*/true);
1566 }
1567
1568 /// Determine whether the specified value is known to be a
1569 /// constant on the specified edge. Return null if not.
1570 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1571                                            BasicBlock *ToBB,
1572                                            Instruction *CxtI) {
1573   const DataLayout &DL = FromBB->getModule()->getDataLayout();
1574   LVILatticeVal Result =
1575       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1576
1577   if (Result.isConstant())
1578     return Result.getConstant();
1579   if (Result.isConstantRange()) {
1580     ConstantRange CR = Result.getConstantRange();
1581     if (const APInt *SingleVal = CR.getSingleElement())
1582       return ConstantInt::get(V->getContext(), *SingleVal);
1583   }
1584   return nullptr;
1585 }
1586
1587 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1588                                                   LVILatticeVal &Result,
1589                                                   const DataLayout &DL,
1590                                                   TargetLibraryInfo *TLI) {
1591
1592   // If we know the value is a constant, evaluate the conditional.
1593   Constant *Res = nullptr;
1594   if (Result.isConstant()) {
1595     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
1596                                           TLI);
1597     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1598       return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1599     return LazyValueInfo::Unknown;
1600   }
1601
1602   if (Result.isConstantRange()) {
1603     ConstantInt *CI = dyn_cast<ConstantInt>(C);
1604     if (!CI) return LazyValueInfo::Unknown;
1605
1606     ConstantRange CR = Result.getConstantRange();
1607     if (Pred == ICmpInst::ICMP_EQ) {
1608       if (!CR.contains(CI->getValue()))
1609         return LazyValueInfo::False;
1610
1611       if (CR.isSingleElement() && CR.contains(CI->getValue()))
1612         return LazyValueInfo::True;
1613     } else if (Pred == ICmpInst::ICMP_NE) {
1614       if (!CR.contains(CI->getValue()))
1615         return LazyValueInfo::True;
1616
1617       if (CR.isSingleElement() && CR.contains(CI->getValue()))
1618         return LazyValueInfo::False;
1619     }
1620
1621     // Handle more complex predicates.
1622     ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1623         (ICmpInst::Predicate)Pred, CI->getValue());
1624     if (TrueValues.contains(CR))
1625       return LazyValueInfo::True;
1626     if (TrueValues.inverse().contains(CR))
1627       return LazyValueInfo::False;
1628     return LazyValueInfo::Unknown;
1629   }
1630
1631   if (Result.isNotConstant()) {
1632     // If this is an equality comparison, we can try to fold it knowing that
1633     // "V != C1".
1634     if (Pred == ICmpInst::ICMP_EQ) {
1635       // !C1 == C -> false iff C1 == C.
1636       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1637                                             Result.getNotConstant(), C, DL,
1638                                             TLI);
1639       if (Res->isNullValue())
1640         return LazyValueInfo::False;
1641     } else if (Pred == ICmpInst::ICMP_NE) {
1642       // !C1 != C -> true iff C1 == C.
1643       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1644                                             Result.getNotConstant(), C, DL,
1645                                             TLI);
1646       if (Res->isNullValue())
1647         return LazyValueInfo::True;
1648     }
1649     return LazyValueInfo::Unknown;
1650   }
1651
1652   return LazyValueInfo::Unknown;
1653 }
1654
1655 /// Determine whether the specified value comparison with a constant is known to
1656 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1657 LazyValueInfo::Tristate
1658 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1659                                   BasicBlock *FromBB, BasicBlock *ToBB,
1660                                   Instruction *CxtI) {
1661   const DataLayout &DL = FromBB->getModule()->getDataLayout();
1662   LVILatticeVal Result =
1663       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1664
1665   return getPredicateResult(Pred, C, Result, DL, TLI);
1666 }
1667
1668 LazyValueInfo::Tristate
1669 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1670                               Instruction *CxtI) {
1671   // Is or is not NonNull are common predicates being queried. If
1672   // isKnownNonNull can tell us the result of the predicate, we can
1673   // return it quickly. But this is only a fastpath, and falling
1674   // through would still be correct.
1675   if (V->getType()->isPointerTy() && C->isNullValue() &&
1676       isKnownNonNull(V->stripPointerCasts())) {
1677     if (Pred == ICmpInst::ICMP_EQ)
1678       return LazyValueInfo::False;
1679     else if (Pred == ICmpInst::ICMP_NE)
1680       return LazyValueInfo::True;
1681   }
1682   const DataLayout &DL = CxtI->getModule()->getDataLayout();
1683   LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1684   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1685   if (Ret != Unknown)
1686     return Ret;
1687
1688   // Note: The following bit of code is somewhat distinct from the rest of LVI;
1689   // LVI as a whole tries to compute a lattice value which is conservatively
1690   // correct at a given location.  In this case, we have a predicate which we
1691   // weren't able to prove about the merged result, and we're pushing that
1692   // predicate back along each incoming edge to see if we can prove it
1693   // separately for each input.  As a motivating example, consider:
1694   // bb1:
1695   //   %v1 = ... ; constantrange<1, 5>
1696   //   br label %merge
1697   // bb2:
1698   //   %v2 = ... ; constantrange<10, 20>
1699   //   br label %merge
1700   // merge:
1701   //   %phi = phi [%v1, %v2] ; constantrange<1,20>
1702   //   %pred = icmp eq i32 %phi, 8
1703   // We can't tell from the lattice value for '%phi' that '%pred' is false
1704   // along each path, but by checking the predicate over each input separately,
1705   // we can.
1706   // We limit the search to one step backwards from the current BB and value.
1707   // We could consider extending this to search further backwards through the
1708   // CFG and/or value graph, but there are non-obvious compile time vs quality
1709   // tradeoffs.
1710   if (CxtI) {
1711     BasicBlock *BB = CxtI->getParent();
1712
1713     // Function entry or an unreachable block.  Bail to avoid confusing
1714     // analysis below.
1715     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1716     if (PI == PE)
1717       return Unknown;
1718
1719     // If V is a PHI node in the same block as the context, we need to ask
1720     // questions about the predicate as applied to the incoming value along
1721     // each edge. This is useful for eliminating cases where the predicate is
1722     // known along all incoming edges.
1723     if (auto *PHI = dyn_cast<PHINode>(V))
1724       if (PHI->getParent() == BB) {
1725         Tristate Baseline = Unknown;
1726         for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1727           Value *Incoming = PHI->getIncomingValue(i);
1728           BasicBlock *PredBB = PHI->getIncomingBlock(i);
1729           // Note that PredBB may be BB itself.
1730           Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1731                                                CxtI);
1732
1733           // Keep going as long as we've seen a consistent known result for
1734           // all inputs.
1735           Baseline = (i == 0) ? Result /* First iteration */
1736             : (Baseline == Result ? Baseline : Unknown); /* All others */
1737           if (Baseline == Unknown)
1738             break;
1739         }
1740         if (Baseline != Unknown)
1741           return Baseline;
1742       }
1743
1744     // For a comparison where the V is outside this block, it's possible
1745     // that we've branched on it before. Look to see if the value is known
1746     // on all incoming edges.
1747     if (!isa<Instruction>(V) ||
1748         cast<Instruction>(V)->getParent() != BB) {
1749       // For predecessor edge, determine if the comparison is true or false
1750       // on that edge. If they're all true or all false, we can conclude
1751       // the value of the comparison in this block.
1752       Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1753       if (Baseline != Unknown) {
1754         // Check that all remaining incoming values match the first one.
1755         while (++PI != PE) {
1756           Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1757           if (Ret != Baseline) break;
1758         }
1759         // If we terminated early, then one of the values didn't match.
1760         if (PI == PE) {
1761           return Baseline;
1762         }
1763       }
1764     }
1765   }
1766   return Unknown;
1767 }
1768
1769 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1770                                BasicBlock *NewSucc) {
1771   if (PImpl) {
1772     const DataLayout &DL = PredBB->getModule()->getDataLayout();
1773     getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1774   }
1775 }
1776
1777 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1778   if (PImpl) {
1779     const DataLayout &DL = BB->getModule()->getDataLayout();
1780     getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1781   }
1782 }