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 LazyValueInfo::ID = 0;
42 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
43                 "Lazy Value Information Analysis", false, true)
44 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
45 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
46 INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info",
47                 "Lazy Value Information Analysis", false, true)
48 
49 namespace llvm {
createLazyValueInfoPass()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 ///
63 namespace {
64 class 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 
88 public:
LVILatticeVal()89   LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
90 
get(Constant * C)91   static LVILatticeVal get(Constant *C) {
92     LVILatticeVal Res;
93     if (!isa<UndefValue>(C))
94       Res.markConstant(C);
95     return Res;
96   }
getNot(Constant * C)97   static LVILatticeVal getNot(Constant *C) {
98     LVILatticeVal Res;
99     if (!isa<UndefValue>(C))
100       Res.markNotConstant(C);
101     return Res;
102   }
getRange(ConstantRange CR)103   static LVILatticeVal getRange(ConstantRange CR) {
104     LVILatticeVal Res;
105     Res.markConstantRange(CR);
106     return Res;
107   }
getOverdefined()108   static LVILatticeVal getOverdefined() {
109     LVILatticeVal Res;
110     Res.markOverdefined();
111     return Res;
112   }
113 
isUndefined() const114   bool isUndefined() const     { return Tag == undefined; }
isConstant() const115   bool isConstant() const      { return Tag == constant; }
isNotConstant() const116   bool isNotConstant() const   { return Tag == notconstant; }
isConstantRange() const117   bool isConstantRange() const { return Tag == constantrange; }
isOverdefined() const118   bool isOverdefined() const   { return Tag == overdefined; }
119 
getConstant() const120   Constant *getConstant() const {
121     assert(isConstant() && "Cannot get the constant of a non-constant!");
122     return Val;
123   }
124 
getNotConstant() const125   Constant *getNotConstant() const {
126     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
127     return Val;
128   }
129 
getConstantRange() const130   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.
markOverdefined()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.
markConstant(Constant * V)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.
markNotConstant(Constant * V)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.
markConstantRange(const ConstantRange NewR)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.
mergeIn(const LVILatticeVal & RHS,const DataLayout & DL)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 
279 namespace llvm {
280 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
281     LLVM_ATTRIBUTE_USED;
operator <<(raw_ostream & OS,const LVILatticeVal & Val)282 raw_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 
301 namespace {
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 
LVIValueHandle__anon33ceafee0211::LVIValueHandle307     LVIValueHandle(Value *V, LazyValueInfoCache *P)
308       : CallbackVH(V), Parent(P) { }
309 
310     void deleted() override;
allUsesReplacedWith__anon33ceafee0211::LVIValueHandle311     void allUsesReplacedWith(Value *V) override {
312       deleted();
313     }
314   };
315 }
316 
317 namespace {
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.
pushBlockValue(const std::pair<BasicBlock *,Value * > & BV)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 
insertResult(Value * Val,BasicBlock * BB,const LVILatticeVal & Result)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 
lookup(Value * V)399     ValueCacheEntryTy &lookup(Value *V) {
400       return ValueCache[LVIValueHandle(V, this)];
401     }
402 
isOverdefined(Value * V,BasicBlock * BB) const403     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 
hasCachedValueInfo(Value * V,BasicBlock * BB)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 
getCachedValueInfo(Value * V,BasicBlock * BB)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.
clear()456     void clear() {
457       SeenBlocks.clear();
458       ValueCache.clear();
459       OverDefinedCache.clear();
460     }
461 
LazyValueInfoCache(AssumptionCache * AC,const DataLayout & DL,DominatorTree * DT=nullptr)462     LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL,
463                        DominatorTree *DT = nullptr)
464         : AC(AC), DL(DL), DT(DT) {}
465   };
466 } // end anonymous namespace
467 
deleted()468 void 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 
eraseBlock(BasicBlock * BB)485 void 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 
solve()500 void 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 
hasBlockValue(Value * Val,BasicBlock * BB)520 bool 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 
getBlockValue(Value * Val,BasicBlock * BB)528 LVILatticeVal 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 
getFromRangeMetadata(Instruction * BBI)537 static 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 
solveBlockValue(Value * Val,BasicBlock * BB)556 bool 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 
InstructionDereferencesPointer(Instruction * I,Value * Ptr)632 static 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 
solveBlockValueNonLocal(LVILatticeVal & BBLV,Value * Val,BasicBlock * BB)663 bool 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 
solveBlockValuePHINode(LVILatticeVal & BBLV,PHINode * PN,BasicBlock * BB)739 bool 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 
778 static 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.
mergeAssumeBlockValueConstantRange(Value * Val,LVILatticeVal & BBLV,Instruction * BBI)785 void 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 
solveBlockValueConstantRange(LVILatticeVal & BBLV,Instruction * BBI,BasicBlock * BB)812 bool 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 
getValueFromFromCondition(Value * Val,ICmpInst * ICI,LVILatticeVal & Result,bool isTrueDest)896 bool 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.
getEdgeValueLocal(Value * Val,BasicBlock * BBFrom,BasicBlock * BBTo,LVILatticeVal & Result)939 static 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.
getEdgeValue(Value * Val,BasicBlock * BBFrom,BasicBlock * BBTo,LVILatticeVal & Result,Instruction * CxtI)996 bool 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 
getValueInBlock(Value * V,BasicBlock * BB,Instruction * CxtI)1057 LVILatticeVal 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 
getValueAt(Value * V,Instruction * CxtI)1073 LVILatticeVal 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 
1086 LVILatticeVal LazyValueInfoCache::
getValueOnEdge(Value * V,BasicBlock * FromBB,BasicBlock * ToBB,Instruction * CxtI)1087 getValueOnEdge(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 
threadEdge(BasicBlock * PredBB,BasicBlock * OldSucc,BasicBlock * NewSucc)1104 void 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.
getCache(void * & PImpl,AssumptionCache * AC,const DataLayout * DL,DominatorTree * DT=nullptr)1165 static 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 
runOnFunction(Function & F)1175 bool 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 
getAnalysisUsage(AnalysisUsage & AU) const1192 void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
1193   AU.setPreservesAll();
1194   AU.addRequired<AssumptionCacheTracker>();
1195   AU.addRequired<TargetLibraryInfoWrapperPass>();
1196 }
1197 
releaseMemory()1198 void 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 
getConstant(Value * V,BasicBlock * BB,Instruction * CxtI)1206 Constant *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.
getConstantOnEdge(Value * V,BasicBlock * FromBB,BasicBlock * ToBB,Instruction * CxtI)1224 Constant *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 
getPredicateResult(unsigned Pred,Constant * C,LVILatticeVal & Result,const DataLayout & DL,TargetLibraryInfo * TLI)1241 static 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.
1311 LazyValueInfo::Tristate
getPredicateOnEdge(unsigned Pred,Value * V,Constant * C,BasicBlock * FromBB,BasicBlock * ToBB,Instruction * CxtI)1312 LazyValueInfo::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 
1322 LazyValueInfo::Tristate
getPredicateAt(unsigned Pred,Value * V,Constant * C,Instruction * CxtI)1323 LazyValueInfo::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 
threadEdge(BasicBlock * PredBB,BasicBlock * OldSucc,BasicBlock * NewSucc)1412 void 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 
eraseBlock(BasicBlock * BB)1420 void 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