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