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