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