contrib/llvm/lib/Analysis/LazyValueInfo.cpp

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