1//===- LazyValueInfo.cpp - Value constraint analysis ----------------------===//
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#define DEBUG_TYPE "lazy-value-info"
16#include "llvm/Analysis/LazyValueInfo.h"
17#include "llvm/Analysis/ValueTracking.h"
18#include "llvm/Constants.h"
19#include "llvm/Instructions.h"
20#include "llvm/IntrinsicInst.h"
21#include "llvm/Analysis/ConstantFolding.h"
22#include "llvm/Target/TargetData.h"
23#include "llvm/Target/TargetLibraryInfo.h"
24#include "llvm/Support/CFG.h"
25#include "llvm/Support/ConstantRange.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/PatternMatch.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/Support/ValueHandle.h"
30#include "llvm/ADT/DenseSet.h"
31#include "llvm/ADT/STLExtras.h"
32#include <map>
33#include <stack>
34using namespace llvm;
35using namespace PatternMatch;
36
37char LazyValueInfo::ID = 0;
38INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
39                "Lazy Value Information Analysis", false, true)
40INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
41INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info",
42                "Lazy Value Information Analysis", false, true)
43
44namespace llvm {
45  FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
46}
47
48
49//===----------------------------------------------------------------------===//
50//                               LVILatticeVal
51//===----------------------------------------------------------------------===//
52
53/// LVILatticeVal - This is the information tracked by LazyValueInfo for each
54/// value.
55///
56/// FIXME: This is basically just for bringup, this can be made a lot more rich
57/// in the future.
58///
59namespace {
60class LVILatticeVal {
61  enum LatticeValueTy {
62    /// undefined - This Value has no known value yet.
63    undefined,
64
65    /// constant - This Value has a specific constant value.
66    constant,
67    /// notconstant - This Value is known to not have the specified value.
68    notconstant,
69
70    /// constantrange - The Value falls within this range.
71    constantrange,
72
73    /// overdefined - This value is not known to be constant, and we know that
74    /// it has a value.
75    overdefined
76  };
77
78  /// Val: This stores the current lattice value along with the Constant* for
79  /// the constant if this is a 'constant' or 'notconstant' value.
80  LatticeValueTy Tag;
81  Constant *Val;
82  ConstantRange Range;
83
84public:
85  LVILatticeVal() : Tag(undefined), Val(0), Range(1, true) {}
86
87  static LVILatticeVal get(Constant *C) {
88    LVILatticeVal Res;
89    if (!isa<UndefValue>(C))
90      Res.markConstant(C);
91    return Res;
92  }
93  static LVILatticeVal getNot(Constant *C) {
94    LVILatticeVal Res;
95    if (!isa<UndefValue>(C))
96      Res.markNotConstant(C);
97    return Res;
98  }
99  static LVILatticeVal getRange(ConstantRange CR) {
100    LVILatticeVal Res;
101    Res.markConstantRange(CR);
102    return Res;
103  }
104
105  bool isUndefined() const     { return Tag == undefined; }
106  bool isConstant() const      { return Tag == constant; }
107  bool isNotConstant() const   { return Tag == notconstant; }
108  bool isConstantRange() const { return Tag == constantrange; }
109  bool isOverdefined() const   { return Tag == overdefined; }
110
111  Constant *getConstant() const {
112    assert(isConstant() && "Cannot get the constant of a non-constant!");
113    return Val;
114  }
115
116  Constant *getNotConstant() const {
117    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
118    return Val;
119  }
120
121  ConstantRange getConstantRange() const {
122    assert(isConstantRange() &&
123           "Cannot get the constant-range of a non-constant-range!");
124    return Range;
125  }
126
127  /// markOverdefined - Return true if this is a change in status.
128  bool markOverdefined() {
129    if (isOverdefined())
130      return false;
131    Tag = overdefined;
132    return true;
133  }
134
135  /// markConstant - Return true if this is a change in status.
136  bool markConstant(Constant *V) {
137    assert(V && "Marking constant with NULL");
138    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
139      return markConstantRange(ConstantRange(CI->getValue()));
140    if (isa<UndefValue>(V))
141      return false;
142
143    assert((!isConstant() || getConstant() == V) &&
144           "Marking constant with different value");
145    assert(isUndefined());
146    Tag = constant;
147    Val = V;
148    return true;
149  }
150
151  /// markNotConstant - Return true if this is a change in status.
152  bool markNotConstant(Constant *V) {
153    assert(V && "Marking constant with NULL");
154    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
155      return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
156    if (isa<UndefValue>(V))
157      return false;
158
159    assert((!isConstant() || getConstant() != V) &&
160           "Marking constant !constant with same value");
161    assert((!isNotConstant() || getNotConstant() == V) &&
162           "Marking !constant with different value");
163    assert(isUndefined() || isConstant());
164    Tag = notconstant;
165    Val = V;
166    return true;
167  }
168
169  /// markConstantRange - Return true if this is a change in status.
170  bool markConstantRange(const ConstantRange NewR) {
171    if (isConstantRange()) {
172      if (NewR.isEmptySet())
173        return markOverdefined();
174
175      bool changed = Range != NewR;
176      Range = NewR;
177      return changed;
178    }
179
180    assert(isUndefined());
181    if (NewR.isEmptySet())
182      return markOverdefined();
183
184    Tag = constantrange;
185    Range = NewR;
186    return true;
187  }
188
189  /// mergeIn - Merge the specified lattice value into this one, updating this
190  /// one and returning true if anything changed.
191  bool mergeIn(const LVILatticeVal &RHS) {
192    if (RHS.isUndefined() || isOverdefined()) return false;
193    if (RHS.isOverdefined()) return markOverdefined();
194
195    if (isUndefined()) {
196      Tag = RHS.Tag;
197      Val = RHS.Val;
198      Range = RHS.Range;
199      return true;
200    }
201
202    if (isConstant()) {
203      if (RHS.isConstant()) {
204        if (Val == RHS.Val)
205          return false;
206        return markOverdefined();
207      }
208
209      if (RHS.isNotConstant()) {
210        if (Val == RHS.Val)
211          return markOverdefined();
212
213        // Unless we can prove that the two Constants are different, we must
214        // move to overdefined.
215        // FIXME: use TargetData/TargetLibraryInfo for smarter constant folding.
216        if (ConstantInt *Res = dyn_cast<ConstantInt>(
217                ConstantFoldCompareInstOperands(CmpInst::ICMP_NE,
218                                                getConstant(),
219                                                RHS.getNotConstant())))
220          if (Res->isOne())
221            return markNotConstant(RHS.getNotConstant());
222
223        return markOverdefined();
224      }
225
226      // RHS is a ConstantRange, LHS is a non-integer Constant.
227
228      // FIXME: consider the case where RHS is a range [1, 0) and LHS is
229      // a function. The correct result is to pick up RHS.
230
231      return markOverdefined();
232    }
233
234    if (isNotConstant()) {
235      if (RHS.isConstant()) {
236        if (Val == RHS.Val)
237          return markOverdefined();
238
239        // Unless we can prove that the two Constants are different, we must
240        // move to overdefined.
241        // FIXME: use TargetData/TargetLibraryInfo for smarter constant folding.
242        if (ConstantInt *Res = dyn_cast<ConstantInt>(
243                ConstantFoldCompareInstOperands(CmpInst::ICMP_NE,
244                                                getNotConstant(),
245                                                RHS.getConstant())))
246          if (Res->isOne())
247            return false;
248
249        return markOverdefined();
250      }
251
252      if (RHS.isNotConstant()) {
253        if (Val == RHS.Val)
254          return false;
255        return markOverdefined();
256      }
257
258      return markOverdefined();
259    }
260
261    assert(isConstantRange() && "New LVILattice type?");
262    if (!RHS.isConstantRange())
263      return markOverdefined();
264
265    ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
266    if (NewR.isFullSet())
267      return markOverdefined();
268    return markConstantRange(NewR);
269  }
270};
271
272} // end anonymous namespace.
273
274namespace llvm {
275raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
276    LLVM_ATTRIBUTE_USED;
277raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
278  if (Val.isUndefined())
279    return OS << "undefined";
280  if (Val.isOverdefined())
281    return OS << "overdefined";
282
283  if (Val.isNotConstant())
284    return OS << "notconstant<" << *Val.getNotConstant() << '>';
285  else if (Val.isConstantRange())
286    return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
287              << Val.getConstantRange().getUpper() << '>';
288  return OS << "constant<" << *Val.getConstant() << '>';
289}
290}
291
292//===----------------------------------------------------------------------===//
293//                          LazyValueInfoCache Decl
294//===----------------------------------------------------------------------===//
295
296namespace {
297  /// LVIValueHandle - A callback value handle update the cache when
298  /// values are erased.
299  class LazyValueInfoCache;
300  struct LVIValueHandle : public CallbackVH {
301    LazyValueInfoCache *Parent;
302
303    LVIValueHandle(Value *V, LazyValueInfoCache *P)
304      : CallbackVH(V), Parent(P) { }
305
306    void deleted();
307    void allUsesReplacedWith(Value *V) {
308      deleted();
309    }
310  };
311}
312
313namespace {
314  /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
315  /// maintains information about queries across the clients' queries.
316  class LazyValueInfoCache {
317    /// ValueCacheEntryTy - This is all of the cached block information for
318    /// exactly one Value*.  The entries are sorted by the BasicBlock* of the
319    /// entries, allowing us to do a lookup with a binary search.
320    typedef std::map<AssertingVH<BasicBlock>, LVILatticeVal> ValueCacheEntryTy;
321
322    /// ValueCache - This is all of the cached information for all values,
323    /// mapped from Value* to key information.
324    std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
325
326    /// OverDefinedCache - This tracks, on a per-block basis, the set of
327    /// values that are over-defined at the end of that block.  This is required
328    /// for cache updating.
329    typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
330    DenseSet<OverDefinedPairTy> OverDefinedCache;
331
332    /// SeenBlocks - Keep track of all blocks that we have ever seen, so we
333    /// don't spend time removing unused blocks from our caches.
334    DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
335
336    /// BlockValueStack - This stack holds the state of the value solver
337    /// during a query.  It basically emulates the callstack of the naive
338    /// recursive value lookup process.
339    std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
340
341    friend struct LVIValueHandle;
342
343    /// OverDefinedCacheUpdater - A helper object that ensures that the
344    /// OverDefinedCache is updated whenever solveBlockValue returns.
345    struct OverDefinedCacheUpdater {
346      LazyValueInfoCache *Parent;
347      Value *Val;
348      BasicBlock *BB;
349      LVILatticeVal &BBLV;
350
351      OverDefinedCacheUpdater(Value *V, BasicBlock *B, LVILatticeVal &LV,
352                       LazyValueInfoCache *P)
353        : Parent(P), Val(V), BB(B), BBLV(LV) { }
354
355      bool markResult(bool changed) {
356        if (changed && BBLV.isOverdefined())
357          Parent->OverDefinedCache.insert(std::make_pair(BB, Val));
358        return changed;
359      }
360    };
361
362
363
364    LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
365    bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
366                      LVILatticeVal &Result);
367    bool hasBlockValue(Value *Val, BasicBlock *BB);
368
369    // These methods process one work item and may add more. A false value
370    // returned means that the work item was not completely processed and must
371    // be revisited after going through the new items.
372    bool solveBlockValue(Value *Val, BasicBlock *BB);
373    bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
374                                 Value *Val, BasicBlock *BB);
375    bool solveBlockValuePHINode(LVILatticeVal &BBLV,
376                                PHINode *PN, BasicBlock *BB);
377    bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
378                                      Instruction *BBI, BasicBlock *BB);
379
380    void solve();
381
382    ValueCacheEntryTy &lookup(Value *V) {
383      return ValueCache[LVIValueHandle(V, this)];
384    }
385
386  public:
387    /// getValueInBlock - This is the query interface to determine the lattice
388    /// value for the specified Value* at the end of the specified block.
389    LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
390
391    /// getValueOnEdge - This is the query interface to determine the lattice
392    /// value for the specified Value* that is true on the specified edge.
393    LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
394
395    /// threadEdge - This is the update interface to inform the cache that an
396    /// edge from PredBB to OldSucc has been threaded to be from PredBB to
397    /// NewSucc.
398    void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
399
400    /// eraseBlock - This is part of the update interface to inform the cache
401    /// that a block has been deleted.
402    void eraseBlock(BasicBlock *BB);
403
404    /// clear - Empty the cache.
405    void clear() {
406      SeenBlocks.clear();
407      ValueCache.clear();
408      OverDefinedCache.clear();
409    }
410  };
411} // end anonymous namespace
412
413void LVIValueHandle::deleted() {
414  typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
415
416  SmallVector<OverDefinedPairTy, 4> ToErase;
417  for (DenseSet<OverDefinedPairTy>::iterator
418       I = Parent->OverDefinedCache.begin(),
419       E = Parent->OverDefinedCache.end();
420       I != E; ++I) {
421    if (I->second == getValPtr())
422      ToErase.push_back(*I);
423  }
424
425  for (SmallVector<OverDefinedPairTy, 4>::iterator I = ToErase.begin(),
426       E = ToErase.end(); I != E; ++I)
427    Parent->OverDefinedCache.erase(*I);
428
429  // This erasure deallocates *this, so it MUST happen after we're done
430  // using any and all members of *this.
431  Parent->ValueCache.erase(*this);
432}
433
434void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
435  // Shortcut if we have never seen this block.
436  DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
437  if (I == SeenBlocks.end())
438    return;
439  SeenBlocks.erase(I);
440
441  SmallVector<OverDefinedPairTy, 4> ToErase;
442  for (DenseSet<OverDefinedPairTy>::iterator  I = OverDefinedCache.begin(),
443       E = OverDefinedCache.end(); I != E; ++I) {
444    if (I->first == BB)
445      ToErase.push_back(*I);
446  }
447
448  for (SmallVector<OverDefinedPairTy, 4>::iterator I = ToErase.begin(),
449       E = ToErase.end(); I != E; ++I)
450    OverDefinedCache.erase(*I);
451
452  for (std::map<LVIValueHandle, ValueCacheEntryTy>::iterator
453       I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
454    I->second.erase(BB);
455}
456
457void LazyValueInfoCache::solve() {
458  while (!BlockValueStack.empty()) {
459    std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
460    if (solveBlockValue(e.second, e.first)) {
461      assert(BlockValueStack.top() == e);
462      BlockValueStack.pop();
463    }
464  }
465}
466
467bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
468  // If already a constant, there is nothing to compute.
469  if (isa<Constant>(Val))
470    return true;
471
472  LVIValueHandle ValHandle(Val, this);
473  std::map<LVIValueHandle, ValueCacheEntryTy>::iterator I =
474    ValueCache.find(ValHandle);
475  if (I == ValueCache.end()) return false;
476  return I->second.count(BB);
477}
478
479LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
480  // If already a constant, there is nothing to compute.
481  if (Constant *VC = dyn_cast<Constant>(Val))
482    return LVILatticeVal::get(VC);
483
484  SeenBlocks.insert(BB);
485  return lookup(Val)[BB];
486}
487
488bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
489  if (isa<Constant>(Val))
490    return true;
491
492  ValueCacheEntryTy &Cache = lookup(Val);
493  SeenBlocks.insert(BB);
494  LVILatticeVal &BBLV = Cache[BB];
495
496  // OverDefinedCacheUpdater is a helper object that will update
497  // the OverDefinedCache for us when this method exits.  Make sure to
498  // call markResult on it as we exist, passing a bool to indicate if the
499  // cache needs updating, i.e. if we have solve a new value or not.
500  OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
501
502  // If we've already computed this block's value, return it.
503  if (!BBLV.isUndefined()) {
504    DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
505
506    // Since we're reusing a cached value here, we don't need to update the
507    // OverDefinedCahce.  The cache will have been properly updated
508    // whenever the cached value was inserted.
509    ODCacheUpdater.markResult(false);
510    return true;
511  }
512
513  // Otherwise, this is the first time we're seeing this block.  Reset the
514  // lattice value to overdefined, so that cycles will terminate and be
515  // conservatively correct.
516  BBLV.markOverdefined();
517
518  Instruction *BBI = dyn_cast<Instruction>(Val);
519  if (BBI == 0 || BBI->getParent() != BB) {
520    return ODCacheUpdater.markResult(solveBlockValueNonLocal(BBLV, Val, BB));
521  }
522
523  if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
524    return ODCacheUpdater.markResult(solveBlockValuePHINode(BBLV, PN, BB));
525  }
526
527  if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
528    BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
529    return ODCacheUpdater.markResult(true);
530  }
531
532  // We can only analyze the definitions of certain classes of instructions
533  // (integral binops and casts at the moment), so bail if this isn't one.
534  LVILatticeVal Result;
535  if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
536     !BBI->getType()->isIntegerTy()) {
537    DEBUG(dbgs() << " compute BB '" << BB->getName()
538                 << "' - overdefined because inst def found.\n");
539    BBLV.markOverdefined();
540    return ODCacheUpdater.markResult(true);
541  }
542
543  // FIXME: We're currently limited to binops with a constant RHS.  This should
544  // be improved.
545  BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
546  if (BO && !isa<ConstantInt>(BO->getOperand(1))) {
547    DEBUG(dbgs() << " compute BB '" << BB->getName()
548                 << "' - overdefined because inst def found.\n");
549
550    BBLV.markOverdefined();
551    return ODCacheUpdater.markResult(true);
552  }
553
554  return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB));
555}
556
557static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
558  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
559    return L->getPointerAddressSpace() == 0 &&
560        GetUnderlyingObject(L->getPointerOperand()) ==
561        GetUnderlyingObject(Ptr);
562  }
563  if (StoreInst *S = dyn_cast<StoreInst>(I)) {
564    return S->getPointerAddressSpace() == 0 &&
565        GetUnderlyingObject(S->getPointerOperand()) ==
566        GetUnderlyingObject(Ptr);
567  }
568  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
569    if (MI->isVolatile()) return false;
570
571    // FIXME: check whether it has a valuerange that excludes zero?
572    ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
573    if (!Len || Len->isZero()) return false;
574
575    if (MI->getDestAddressSpace() == 0)
576      if (MI->getRawDest() == Ptr || MI->getDest() == Ptr)
577        return true;
578    if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
579      if (MTI->getSourceAddressSpace() == 0)
580        if (MTI->getRawSource() == Ptr || MTI->getSource() == Ptr)
581          return true;
582  }
583  return false;
584}
585
586bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
587                                                 Value *Val, BasicBlock *BB) {
588  LVILatticeVal Result;  // Start Undefined.
589
590  // If this is a pointer, and there's a load from that pointer in this BB,
591  // then we know that the pointer can't be NULL.
592  bool NotNull = false;
593  if (Val->getType()->isPointerTy()) {
594    if (isa<AllocaInst>(Val)) {
595      NotNull = true;
596    } else {
597      for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();BI != BE;++BI){
598        if (InstructionDereferencesPointer(BI, Val)) {
599          NotNull = true;
600          break;
601        }
602      }
603    }
604  }
605
606  // If this is the entry block, we must be asking about an argument.  The
607  // value is overdefined.
608  if (BB == &BB->getParent()->getEntryBlock()) {
609    assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
610    if (NotNull) {
611      PointerType *PTy = cast<PointerType>(Val->getType());
612      Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
613    } else {
614      Result.markOverdefined();
615    }
616    BBLV = Result;
617    return true;
618  }
619
620  // Loop over all of our predecessors, merging what we know from them into
621  // result.
622  bool EdgesMissing = false;
623  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
624    LVILatticeVal EdgeResult;
625    EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
626    if (EdgesMissing)
627      continue;
628
629    Result.mergeIn(EdgeResult);
630
631    // If we hit overdefined, exit early.  The BlockVals entry is already set
632    // to overdefined.
633    if (Result.isOverdefined()) {
634      DEBUG(dbgs() << " compute BB '" << BB->getName()
635            << "' - overdefined because of pred.\n");
636      // If we previously determined that this is a pointer that can't be null
637      // then return that rather than giving up entirely.
638      if (NotNull) {
639        PointerType *PTy = cast<PointerType>(Val->getType());
640        Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
641      }
642
643      BBLV = Result;
644      return true;
645    }
646  }
647  if (EdgesMissing)
648    return false;
649
650  // Return the merged value, which is more precise than 'overdefined'.
651  assert(!Result.isOverdefined());
652  BBLV = Result;
653  return true;
654}
655
656bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
657                                                PHINode *PN, BasicBlock *BB) {
658  LVILatticeVal Result;  // Start Undefined.
659
660  // Loop over all of our predecessors, merging what we know from them into
661  // result.
662  bool EdgesMissing = false;
663  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
664    BasicBlock *PhiBB = PN->getIncomingBlock(i);
665    Value *PhiVal = PN->getIncomingValue(i);
666    LVILatticeVal EdgeResult;
667    EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult);
668    if (EdgesMissing)
669      continue;
670
671    Result.mergeIn(EdgeResult);
672
673    // If we hit overdefined, exit early.  The BlockVals entry is already set
674    // to overdefined.
675    if (Result.isOverdefined()) {
676      DEBUG(dbgs() << " compute BB '" << BB->getName()
677            << "' - overdefined because of pred.\n");
678
679      BBLV = Result;
680      return true;
681    }
682  }
683  if (EdgesMissing)
684    return false;
685
686  // Return the merged value, which is more precise than 'overdefined'.
687  assert(!Result.isOverdefined() && "Possible PHI in entry block?");
688  BBLV = Result;
689  return true;
690}
691
692bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
693                                                      Instruction *BBI,
694                                                      BasicBlock *BB) {
695  // Figure out the range of the LHS.  If that fails, bail.
696  if (!hasBlockValue(BBI->getOperand(0), BB)) {
697    BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
698    return false;
699  }
700
701  LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
702  if (!LHSVal.isConstantRange()) {
703    BBLV.markOverdefined();
704    return true;
705  }
706
707  ConstantRange LHSRange = LHSVal.getConstantRange();
708  ConstantRange RHSRange(1);
709  IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
710  if (isa<BinaryOperator>(BBI)) {
711    if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
712      RHSRange = ConstantRange(RHS->getValue());
713    } else {
714      BBLV.markOverdefined();
715      return true;
716    }
717  }
718
719  // NOTE: We're currently limited by the set of operations that ConstantRange
720  // can evaluate symbolically.  Enhancing that set will allows us to analyze
721  // more definitions.
722  LVILatticeVal Result;
723  switch (BBI->getOpcode()) {
724  case Instruction::Add:
725    Result.markConstantRange(LHSRange.add(RHSRange));
726    break;
727  case Instruction::Sub:
728    Result.markConstantRange(LHSRange.sub(RHSRange));
729    break;
730  case Instruction::Mul:
731    Result.markConstantRange(LHSRange.multiply(RHSRange));
732    break;
733  case Instruction::UDiv:
734    Result.markConstantRange(LHSRange.udiv(RHSRange));
735    break;
736  case Instruction::Shl:
737    Result.markConstantRange(LHSRange.shl(RHSRange));
738    break;
739  case Instruction::LShr:
740    Result.markConstantRange(LHSRange.lshr(RHSRange));
741    break;
742  case Instruction::Trunc:
743    Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth()));
744    break;
745  case Instruction::SExt:
746    Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth()));
747    break;
748  case Instruction::ZExt:
749    Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth()));
750    break;
751  case Instruction::BitCast:
752    Result.markConstantRange(LHSRange);
753    break;
754  case Instruction::And:
755    Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
756    break;
757  case Instruction::Or:
758    Result.markConstantRange(LHSRange.binaryOr(RHSRange));
759    break;
760
761  // Unhandled instructions are overdefined.
762  default:
763    DEBUG(dbgs() << " compute BB '" << BB->getName()
764                 << "' - overdefined because inst def found.\n");
765    Result.markOverdefined();
766    break;
767  }
768
769  BBLV = Result;
770  return true;
771}
772
773/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
774/// Val is not constrained on the edge.
775static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
776                              BasicBlock *BBTo, LVILatticeVal &Result) {
777  // TODO: Handle more complex conditionals.  If (v == 0 || v2 < 1) is false, we
778  // know that v != 0.
779  if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
780    // If this is a conditional branch and only one successor goes to BBTo, then
781    // we maybe able to infer something from the condition.
782    if (BI->isConditional() &&
783        BI->getSuccessor(0) != BI->getSuccessor(1)) {
784      bool isTrueDest = BI->getSuccessor(0) == BBTo;
785      assert(BI->getSuccessor(!isTrueDest) == BBTo &&
786             "BBTo isn't a successor of BBFrom");
787
788      // If V is the condition of the branch itself, then we know exactly what
789      // it is.
790      if (BI->getCondition() == Val) {
791        Result = LVILatticeVal::get(ConstantInt::get(
792                              Type::getInt1Ty(Val->getContext()), isTrueDest));
793        return true;
794      }
795
796      // If the condition of the branch is an equality comparison, we may be
797      // able to infer the value.
798      ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition());
799      if (ICI && isa<Constant>(ICI->getOperand(1))) {
800        if (ICI->isEquality() && ICI->getOperand(0) == Val) {
801          // We know that V has the RHS constant if this is a true SETEQ or
802          // false SETNE.
803          if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
804            Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
805          else
806            Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
807          return true;
808        }
809
810        // Recognize the range checking idiom that InstCombine produces.
811        // (X-C1) u< C2 --> [C1, C1+C2)
812        ConstantInt *NegOffset = 0;
813        if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
814          match(ICI->getOperand(0), m_Add(m_Specific(Val),
815                                          m_ConstantInt(NegOffset)));
816
817        ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
818        if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
819          // Calculate the range of values that would satisfy the comparison.
820          ConstantRange CmpRange(CI->getValue());
821          ConstantRange TrueValues =
822            ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange);
823
824          if (NegOffset) // Apply the offset from above.
825            TrueValues = TrueValues.subtract(NegOffset->getValue());
826
827          // If we're interested in the false dest, invert the condition.
828          if (!isTrueDest) TrueValues = TrueValues.inverse();
829
830          Result = LVILatticeVal::getRange(TrueValues);
831          return true;
832        }
833      }
834    }
835  }
836
837  // If the edge was formed by a switch on the value, then we may know exactly
838  // what it is.
839  if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
840    if (SI->getCondition() != Val)
841      return false;
842
843    bool DefaultCase = SI->getDefaultDest() == BBTo;
844    unsigned BitWidth = Val->getType()->getIntegerBitWidth();
845    ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
846
847    for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
848         i != e; ++i) {
849      ConstantRange EdgeVal(i.getCaseValue()->getValue());
850      if (DefaultCase) {
851        // It is possible that the default destination is the destination of
852        // some cases. There is no need to perform difference for those cases.
853        if (i.getCaseSuccessor() != BBTo)
854          EdgesVals = EdgesVals.difference(EdgeVal);
855      } else if (i.getCaseSuccessor() == BBTo)
856        EdgesVals = EdgesVals.unionWith(EdgeVal);
857    }
858    Result = LVILatticeVal::getRange(EdgesVals);
859    return true;
860  }
861  return false;
862}
863
864/// \brief Compute the value of Val on the edge BBFrom -> BBTo, or the value at
865/// the basic block if the edge does not constraint Val.
866bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
867                                      BasicBlock *BBTo, LVILatticeVal &Result) {
868  // If already a constant, there is nothing to compute.
869  if (Constant *VC = dyn_cast<Constant>(Val)) {
870    Result = LVILatticeVal::get(VC);
871    return true;
872  }
873
874  if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
875    if (!Result.isConstantRange() ||
876      Result.getConstantRange().getSingleElement())
877      return true;
878
879    // FIXME: this check should be moved to the beginning of the function when
880    // LVI better supports recursive values. Even for the single value case, we
881    // can intersect to detect dead code (an empty range).
882    if (!hasBlockValue(Val, BBFrom)) {
883      BlockValueStack.push(std::make_pair(BBFrom, Val));
884      return false;
885    }
886
887    // Try to intersect ranges of the BB and the constraint on the edge.
888    LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
889    if (!InBlock.isConstantRange())
890      return true;
891
892    ConstantRange Range =
893      Result.getConstantRange().intersectWith(InBlock.getConstantRange());
894    Result = LVILatticeVal::getRange(Range);
895    return true;
896  }
897
898  if (!hasBlockValue(Val, BBFrom)) {
899    BlockValueStack.push(std::make_pair(BBFrom, Val));
900    return false;
901  }
902
903  // if we couldn't compute the value on the edge, use the value from the BB
904  Result = getBlockValue(Val, BBFrom);
905  return true;
906}
907
908LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
909  DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
910        << BB->getName() << "'\n");
911
912  BlockValueStack.push(std::make_pair(BB, V));
913  solve();
914  LVILatticeVal Result = getBlockValue(V, BB);
915
916  DEBUG(dbgs() << "  Result = " << Result << "\n");
917  return Result;
918}
919
920LVILatticeVal LazyValueInfoCache::
921getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
922  DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
923        << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
924
925  LVILatticeVal Result;
926  if (!getEdgeValue(V, FromBB, ToBB, Result)) {
927    solve();
928    bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result);
929    (void)WasFastQuery;
930    assert(WasFastQuery && "More work to do after problem solved?");
931  }
932
933  DEBUG(dbgs() << "  Result = " << Result << "\n");
934  return Result;
935}
936
937void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
938                                    BasicBlock *NewSucc) {
939  // When an edge in the graph has been threaded, values that we could not
940  // determine a value for before (i.e. were marked overdefined) may be possible
941  // to solve now.  We do NOT try to proactively update these values.  Instead,
942  // we clear their entries from the cache, and allow lazy updating to recompute
943  // them when needed.
944
945  // The updating process is fairly simple: we need to dropped cached info
946  // for all values that were marked overdefined in OldSucc, and for those same
947  // values in any successor of OldSucc (except NewSucc) in which they were
948  // also marked overdefined.
949  std::vector<BasicBlock*> worklist;
950  worklist.push_back(OldSucc);
951
952  DenseSet<Value*> ClearSet;
953  for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(),
954       E = OverDefinedCache.end(); I != E; ++I) {
955    if (I->first == OldSucc)
956      ClearSet.insert(I->second);
957  }
958
959  // Use a worklist to perform a depth-first search of OldSucc's successors.
960  // NOTE: We do not need a visited list since any blocks we have already
961  // visited will have had their overdefined markers cleared already, and we
962  // thus won't loop to their successors.
963  while (!worklist.empty()) {
964    BasicBlock *ToUpdate = worklist.back();
965    worklist.pop_back();
966
967    // Skip blocks only accessible through NewSucc.
968    if (ToUpdate == NewSucc) continue;
969
970    bool changed = false;
971    for (DenseSet<Value*>::iterator I = ClearSet.begin(), E = ClearSet.end();
972         I != E; ++I) {
973      // If a value was marked overdefined in OldSucc, and is here too...
974      DenseSet<OverDefinedPairTy>::iterator OI =
975        OverDefinedCache.find(std::make_pair(ToUpdate, *I));
976      if (OI == OverDefinedCache.end()) continue;
977
978      // Remove it from the caches.
979      ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(*I, this)];
980      ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
981
982      assert(CI != Entry.end() && "Couldn't find entry to update?");
983      Entry.erase(CI);
984      OverDefinedCache.erase(OI);
985
986      // If we removed anything, then we potentially need to update
987      // blocks successors too.
988      changed = true;
989    }
990
991    if (!changed) continue;
992
993    worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
994  }
995}
996
997//===----------------------------------------------------------------------===//
998//                            LazyValueInfo Impl
999//===----------------------------------------------------------------------===//
1000
1001/// getCache - This lazily constructs the LazyValueInfoCache.
1002static LazyValueInfoCache &getCache(void *&PImpl) {
1003  if (!PImpl)
1004    PImpl = new LazyValueInfoCache();
1005  return *static_cast<LazyValueInfoCache*>(PImpl);
1006}
1007
1008bool LazyValueInfo::runOnFunction(Function &F) {
1009  if (PImpl)
1010    getCache(PImpl).clear();
1011
1012  TD = getAnalysisIfAvailable<TargetData>();
1013  TLI = &getAnalysis<TargetLibraryInfo>();
1014
1015  // Fully lazy.
1016  return false;
1017}
1018
1019void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
1020  AU.setPreservesAll();
1021  AU.addRequired<TargetLibraryInfo>();
1022}
1023
1024void LazyValueInfo::releaseMemory() {
1025  // If the cache was allocated, free it.
1026  if (PImpl) {
1027    delete &getCache(PImpl);
1028    PImpl = 0;
1029  }
1030}
1031
1032Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
1033  LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
1034
1035  if (Result.isConstant())
1036    return Result.getConstant();
1037  if (Result.isConstantRange()) {
1038    ConstantRange CR = Result.getConstantRange();
1039    if (const APInt *SingleVal = CR.getSingleElement())
1040      return ConstantInt::get(V->getContext(), *SingleVal);
1041  }
1042  return 0;
1043}
1044
1045/// getConstantOnEdge - Determine whether the specified value is known to be a
1046/// constant on the specified edge.  Return null if not.
1047Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1048                                           BasicBlock *ToBB) {
1049  LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
1050
1051  if (Result.isConstant())
1052    return Result.getConstant();
1053  if (Result.isConstantRange()) {
1054    ConstantRange CR = Result.getConstantRange();
1055    if (const APInt *SingleVal = CR.getSingleElement())
1056      return ConstantInt::get(V->getContext(), *SingleVal);
1057  }
1058  return 0;
1059}
1060
1061/// getPredicateOnEdge - Determine whether the specified value comparison
1062/// with a constant is known to be true or false on the specified CFG edge.
1063/// Pred is a CmpInst predicate.
1064LazyValueInfo::Tristate
1065LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1066                                  BasicBlock *FromBB, BasicBlock *ToBB) {
1067  LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
1068
1069  // If we know the value is a constant, evaluate the conditional.
1070  Constant *Res = 0;
1071  if (Result.isConstant()) {
1072    Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD,
1073                                          TLI);
1074    if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1075      return ResCI->isZero() ? False : True;
1076    return Unknown;
1077  }
1078
1079  if (Result.isConstantRange()) {
1080    ConstantInt *CI = dyn_cast<ConstantInt>(C);
1081    if (!CI) return Unknown;
1082
1083    ConstantRange CR = Result.getConstantRange();
1084    if (Pred == ICmpInst::ICMP_EQ) {
1085      if (!CR.contains(CI->getValue()))
1086        return False;
1087
1088      if (CR.isSingleElement() && CR.contains(CI->getValue()))
1089        return True;
1090    } else if (Pred == ICmpInst::ICMP_NE) {
1091      if (!CR.contains(CI->getValue()))
1092        return True;
1093
1094      if (CR.isSingleElement() && CR.contains(CI->getValue()))
1095        return False;
1096    }
1097
1098    // Handle more complex predicates.
1099    ConstantRange TrueValues =
1100        ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
1101    if (TrueValues.contains(CR))
1102      return True;
1103    if (TrueValues.inverse().contains(CR))
1104      return False;
1105    return Unknown;
1106  }
1107
1108  if (Result.isNotConstant()) {
1109    // If this is an equality comparison, we can try to fold it knowing that
1110    // "V != C1".
1111    if (Pred == ICmpInst::ICMP_EQ) {
1112      // !C1 == C -> false iff C1 == C.
1113      Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1114                                            Result.getNotConstant(), C, TD,
1115                                            TLI);
1116      if (Res->isNullValue())
1117        return False;
1118    } else if (Pred == ICmpInst::ICMP_NE) {
1119      // !C1 != C -> true iff C1 == C.
1120      Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1121                                            Result.getNotConstant(), C, TD,
1122                                            TLI);
1123      if (Res->isNullValue())
1124        return True;
1125    }
1126    return Unknown;
1127  }
1128
1129  return Unknown;
1130}
1131
1132void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1133                               BasicBlock *NewSucc) {
1134  if (PImpl) getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc);
1135}
1136
1137void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1138  if (PImpl) getCache(PImpl).eraseBlock(BB);
1139}
1140