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