LLVM  6.0.0svn
LazyValueInfo.cpp
Go to the documentation of this file.
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 
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/ConstantRange.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DataLayout.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/IR/Intrinsics.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/IR/ValueHandle.h"
34 #include "llvm/Support/Debug.h"
37 #include <map>
38 #include <stack>
39 using namespace llvm;
40 using namespace PatternMatch;
41 
42 #define DEBUG_TYPE "lazy-value-info"
43 
44 // This is the number of worklist items we will process to try to discover an
45 // answer for a given value.
46 static const unsigned MaxProcessedPerValue = 500;
47 
50  "Lazy Value Information Analysis", false, true)
55 
56 namespace llvm {
57  FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
58 }
59 
60 AnalysisKey LazyValueAnalysis::Key;
61 
62 //===----------------------------------------------------------------------===//
63 // LVILatticeVal
64 //===----------------------------------------------------------------------===//
65 
66 /// This is the information tracked by LazyValueInfo for each value.
67 ///
68 /// FIXME: This is basically just for bringup, this can be made a lot more rich
69 /// in the future.
70 ///
71 namespace {
72 class LVILatticeVal {
73  enum LatticeValueTy {
74  /// This Value has no known value yet. As a result, this implies the
75  /// producing instruction is dead. Caution: We use this as the starting
76  /// state in our local meet rules. In this usage, it's taken to mean
77  /// "nothing known yet".
78  undefined,
79 
80  /// This Value has a specific constant value. (For constant integers,
81  /// constantrange is used instead. Integer typed constantexprs can appear
82  /// as constant.)
83  constant,
84 
85  /// This Value is known to not have the specified value. (For constant
86  /// integers, constantrange is used instead. As above, integer typed
87  /// constantexprs can appear here.)
88  notconstant,
89 
90  /// The Value falls within this range. (Used only for integer typed values.)
91  constantrange,
92 
93  /// We can not precisely model the dynamic values this value might take.
94  overdefined
95  };
96 
97  /// Val: This stores the current lattice value along with the Constant* for
98  /// the constant if this is a 'constant' or 'notconstant' value.
99  LatticeValueTy Tag;
100  Constant *Val;
101  ConstantRange Range;
102 
103 public:
104  LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
105 
106  static LVILatticeVal get(Constant *C) {
107  LVILatticeVal Res;
108  if (!isa<UndefValue>(C))
109  Res.markConstant(C);
110  return Res;
111  }
112  static LVILatticeVal getNot(Constant *C) {
113  LVILatticeVal Res;
114  if (!isa<UndefValue>(C))
115  Res.markNotConstant(C);
116  return Res;
117  }
118  static LVILatticeVal getRange(ConstantRange CR) {
119  LVILatticeVal Res;
120  Res.markConstantRange(std::move(CR));
121  return Res;
122  }
123  static LVILatticeVal getOverdefined() {
124  LVILatticeVal Res;
125  Res.markOverdefined();
126  return Res;
127  }
128 
129  bool isUndefined() const { return Tag == undefined; }
130  bool isConstant() const { return Tag == constant; }
131  bool isNotConstant() const { return Tag == notconstant; }
132  bool isConstantRange() const { return Tag == constantrange; }
133  bool isOverdefined() const { return Tag == overdefined; }
134 
135  Constant *getConstant() const {
136  assert(isConstant() && "Cannot get the constant of a non-constant!");
137  return Val;
138  }
139 
140  Constant *getNotConstant() const {
141  assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
142  return Val;
143  }
144 
145  const ConstantRange &getConstantRange() const {
146  assert(isConstantRange() &&
147  "Cannot get the constant-range of a non-constant-range!");
148  return Range;
149  }
150 
151 private:
152  void markOverdefined() {
153  if (isOverdefined())
154  return;
155  Tag = overdefined;
156  }
157 
158  void markConstant(Constant *V) {
159  assert(V && "Marking constant with NULL");
160  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
161  markConstantRange(ConstantRange(CI->getValue()));
162  return;
163  }
164  if (isa<UndefValue>(V))
165  return;
166 
167  assert((!isConstant() || getConstant() == V) &&
168  "Marking constant with different value");
169  assert(isUndefined());
170  Tag = constant;
171  Val = V;
172  }
173 
174  void markNotConstant(Constant *V) {
175  assert(V && "Marking constant with NULL");
176  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
177  markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
178  return;
179  }
180  if (isa<UndefValue>(V))
181  return;
182 
183  assert((!isConstant() || getConstant() != V) &&
184  "Marking constant !constant with same value");
185  assert((!isNotConstant() || getNotConstant() == V) &&
186  "Marking !constant with different value");
187  assert(isUndefined() || isConstant());
188  Tag = notconstant;
189  Val = V;
190  }
191 
192  void markConstantRange(ConstantRange NewR) {
193  if (isConstantRange()) {
194  if (NewR.isEmptySet())
195  markOverdefined();
196  else {
197  Range = std::move(NewR);
198  }
199  return;
200  }
201 
202  assert(isUndefined());
203  if (NewR.isEmptySet())
204  markOverdefined();
205  else {
206  Tag = constantrange;
207  Range = std::move(NewR);
208  }
209  }
210 
211 public:
212 
213  /// Merge the specified lattice value into this one, updating this
214  /// one and returning true if anything changed.
215  void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
216  if (RHS.isUndefined() || isOverdefined())
217  return;
218  if (RHS.isOverdefined()) {
219  markOverdefined();
220  return;
221  }
222 
223  if (isUndefined()) {
224  *this = RHS;
225  return;
226  }
227 
228  if (isConstant()) {
229  if (RHS.isConstant() && Val == RHS.Val)
230  return;
231  markOverdefined();
232  return;
233  }
234 
235  if (isNotConstant()) {
236  if (RHS.isNotConstant() && Val == RHS.Val)
237  return;
238  markOverdefined();
239  return;
240  }
241 
242  assert(isConstantRange() && "New LVILattice type?");
243  if (!RHS.isConstantRange()) {
244  // We can get here if we've encountered a constantexpr of integer type
245  // and merge it with a constantrange.
246  markOverdefined();
247  return;
248  }
249  ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
250  if (NewR.isFullSet())
251  markOverdefined();
252  else
253  markConstantRange(std::move(NewR));
254  }
255 };
256 
257 } // end anonymous namespace.
258 
259 namespace llvm {
260 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
262 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
263  if (Val.isUndefined())
264  return OS << "undefined";
265  if (Val.isOverdefined())
266  return OS << "overdefined";
267 
268  if (Val.isNotConstant())
269  return OS << "notconstant<" << *Val.getNotConstant() << '>';
270  if (Val.isConstantRange())
271  return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
272  << Val.getConstantRange().getUpper() << '>';
273  return OS << "constant<" << *Val.getConstant() << '>';
274 }
275 }
276 
277 /// Returns true if this lattice value represents at most one possible value.
278 /// This is as precise as any lattice value can get while still representing
279 /// reachable code.
280 static bool hasSingleValue(const LVILatticeVal &Val) {
281  if (Val.isConstantRange() &&
282  Val.getConstantRange().isSingleElement())
283  // Integer constants are single element ranges
284  return true;
285  if (Val.isConstant())
286  // Non integer constants
287  return true;
288  return false;
289 }
290 
291 /// Combine two sets of facts about the same value into a single set of
292 /// facts. Note that this method is not suitable for merging facts along
293 /// different paths in a CFG; that's what the mergeIn function is for. This
294 /// is for merging facts gathered about the same value at the same location
295 /// through two independent means.
296 /// Notes:
297 /// * This method does not promise to return the most precise possible lattice
298 /// value implied by A and B. It is allowed to return any lattice element
299 /// which is at least as strong as *either* A or B (unless our facts
300 /// conflict, see below).
301 /// * Due to unreachable code, the intersection of two lattice values could be
302 /// contradictory. If this happens, we return some valid lattice value so as
303 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
304 /// we do not make this guarantee. TODO: This would be a useful enhancement.
305 static LVILatticeVal intersect(const LVILatticeVal &A, const LVILatticeVal &B) {
306  // Undefined is the strongest state. It means the value is known to be along
307  // an unreachable path.
308  if (A.isUndefined())
309  return A;
310  if (B.isUndefined())
311  return B;
312 
313  // If we gave up for one, but got a useable fact from the other, use it.
314  if (A.isOverdefined())
315  return B;
316  if (B.isOverdefined())
317  return A;
318 
319  // Can't get any more precise than constants.
320  if (hasSingleValue(A))
321  return A;
322  if (hasSingleValue(B))
323  return B;
324 
325  // Could be either constant range or not constant here.
326  if (!A.isConstantRange() || !B.isConstantRange()) {
327  // TODO: Arbitrary choice, could be improved
328  return A;
329  }
330 
331  // Intersect two constant ranges
332  ConstantRange Range =
333  A.getConstantRange().intersectWith(B.getConstantRange());
334  // Note: An empty range is implicitly converted to overdefined internally.
335  // TODO: We could instead use Undefined here since we've proven a conflict
336  // and thus know this path must be unreachable.
337  return LVILatticeVal::getRange(std::move(Range));
338 }
339 
340 //===----------------------------------------------------------------------===//
341 // LazyValueInfoCache Decl
342 //===----------------------------------------------------------------------===//
343 
344 namespace {
345  /// A callback value handle updates the cache when values are erased.
346  class LazyValueInfoCache;
347  struct LVIValueHandle final : public CallbackVH {
348  // Needs to access getValPtr(), which is protected.
349  friend struct DenseMapInfo<LVIValueHandle>;
350 
351  LazyValueInfoCache *Parent;
352 
353  LVIValueHandle(Value *V, LazyValueInfoCache *P)
354  : CallbackVH(V), Parent(P) { }
355 
356  void deleted() override;
357  void allUsesReplacedWith(Value *V) override {
358  deleted();
359  }
360  };
361 } // end anonymous namespace
362 
363 namespace {
364  /// This is the cache kept by LazyValueInfo which
365  /// maintains information about queries across the clients' queries.
366  class LazyValueInfoCache {
367  /// This is all of the cached block information for exactly one Value*.
368  /// The entries are sorted by the BasicBlock* of the
369  /// entries, allowing us to do a lookup with a binary search.
370  /// Over-defined lattice values are recorded in OverDefinedCache to reduce
371  /// memory overhead.
372  struct ValueCacheEntryTy {
373  ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
374  LVIValueHandle Handle;
375  SmallDenseMap<PoisoningVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
376  };
377 
378  /// This tracks, on a per-block basis, the set of values that are
379  /// over-defined at the end of that block.
381  OverDefinedCacheTy;
382  /// Keep track of all blocks that we have ever seen, so we
383  /// don't spend time removing unused blocks from our caches.
385 
386  /// This is all of the cached information for all values,
387  /// mapped from Value* to key information.
389  OverDefinedCacheTy OverDefinedCache;
390 
391 
392  public:
393  void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
394  SeenBlocks.insert(BB);
395 
396  // Insert over-defined values into their own cache to reduce memory
397  // overhead.
398  if (Result.isOverdefined())
399  OverDefinedCache[BB].insert(Val);
400  else {
401  auto It = ValueCache.find_as(Val);
402  if (It == ValueCache.end()) {
403  ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
404  It = ValueCache.find_as(Val);
405  assert(It != ValueCache.end() && "Val was just added to the map!");
406  }
407  It->second->BlockVals[BB] = Result;
408  }
409  }
410 
411  bool isOverdefined(Value *V, BasicBlock *BB) const {
412  auto ODI = OverDefinedCache.find(BB);
413 
414  if (ODI == OverDefinedCache.end())
415  return false;
416 
417  return ODI->second.count(V);
418  }
419 
420  bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
421  if (isOverdefined(V, BB))
422  return true;
423 
424  auto I = ValueCache.find_as(V);
425  if (I == ValueCache.end())
426  return false;
427 
428  return I->second->BlockVals.count(BB);
429  }
430 
431  LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const {
432  if (isOverdefined(V, BB))
433  return LVILatticeVal::getOverdefined();
434 
435  auto I = ValueCache.find_as(V);
436  if (I == ValueCache.end())
437  return LVILatticeVal();
438  auto BBI = I->second->BlockVals.find(BB);
439  if (BBI == I->second->BlockVals.end())
440  return LVILatticeVal();
441  return BBI->second;
442  }
443 
444  /// clear - Empty the cache.
445  void clear() {
446  SeenBlocks.clear();
447  ValueCache.clear();
448  OverDefinedCache.clear();
449  }
450 
451  /// Inform the cache that a given value has been deleted.
452  void eraseValue(Value *V);
453 
454  /// This is part of the update interface to inform the cache
455  /// that a block has been deleted.
456  void eraseBlock(BasicBlock *BB);
457 
458  /// Updates the cache to remove any influence an overdefined value in
459  /// OldSucc might have (unless also overdefined in NewSucc). This just
460  /// flushes elements from the cache and does not add any.
461  void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
462 
463  friend struct LVIValueHandle;
464  };
465 }
466 
467 void LazyValueInfoCache::eraseValue(Value *V) {
468  for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
469  // Copy and increment the iterator immediately so we can erase behind
470  // ourselves.
471  auto Iter = I++;
472  SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
473  ValueSet.erase(V);
474  if (ValueSet.empty())
475  OverDefinedCache.erase(Iter);
476  }
477 
478  ValueCache.erase(V);
479 }
480 
481 void LVIValueHandle::deleted() {
482  // This erasure deallocates *this, so it MUST happen after we're done
483  // using any and all members of *this.
484  Parent->eraseValue(*this);
485 }
486 
487 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
488  // Shortcut if we have never seen this block.
489  DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
490  if (I == SeenBlocks.end())
491  return;
492  SeenBlocks.erase(I);
493 
494  auto ODI = OverDefinedCache.find(BB);
495  if (ODI != OverDefinedCache.end())
496  OverDefinedCache.erase(ODI);
497 
498  for (auto &I : ValueCache)
499  I.second->BlockVals.erase(BB);
500 }
501 
502 void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
503  BasicBlock *NewSucc) {
504  // When an edge in the graph has been threaded, values that we could not
505  // determine a value for before (i.e. were marked overdefined) may be
506  // possible to solve now. We do NOT try to proactively update these values.
507  // Instead, we clear their entries from the cache, and allow lazy updating to
508  // recompute them when needed.
509 
510  // The updating process is fairly simple: we need to drop cached info
511  // for all values that were marked overdefined in OldSucc, and for those same
512  // values in any successor of OldSucc (except NewSucc) in which they were
513  // also marked overdefined.
514  std::vector<BasicBlock*> worklist;
515  worklist.push_back(OldSucc);
516 
517  auto I = OverDefinedCache.find(OldSucc);
518  if (I == OverDefinedCache.end())
519  return; // Nothing to process here.
520  SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
521 
522  // Use a worklist to perform a depth-first search of OldSucc's successors.
523  // NOTE: We do not need a visited list since any blocks we have already
524  // visited will have had their overdefined markers cleared already, and we
525  // thus won't loop to their successors.
526  while (!worklist.empty()) {
527  BasicBlock *ToUpdate = worklist.back();
528  worklist.pop_back();
529 
530  // Skip blocks only accessible through NewSucc.
531  if (ToUpdate == NewSucc) continue;
532 
533  // If a value was marked overdefined in OldSucc, and is here too...
534  auto OI = OverDefinedCache.find(ToUpdate);
535  if (OI == OverDefinedCache.end())
536  continue;
537  SmallPtrSetImpl<Value *> &ValueSet = OI->second;
538 
539  bool changed = false;
540  for (Value *V : ValsToClear) {
541  if (!ValueSet.erase(V))
542  continue;
543 
544  // If we removed anything, then we potentially need to update
545  // blocks successors too.
546  changed = true;
547 
548  if (ValueSet.empty()) {
549  OverDefinedCache.erase(OI);
550  break;
551  }
552  }
553 
554  if (!changed) continue;
555 
556  worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
557  }
558 }
559 
560 
561 namespace {
562 /// An assembly annotator class to print LazyValueCache information in
563 /// comments.
564 class LazyValueInfoImpl;
565 class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
566  LazyValueInfoImpl *LVIImpl;
567  // While analyzing which blocks we can solve values for, we need the dominator
568  // information. Since this is an optional parameter in LVI, we require this
569  // DomTreeAnalysis pass in the printer pass, and pass the dominator
570  // tree to the LazyValueInfoAnnotatedWriter.
571  DominatorTree &DT;
572 
573 public:
574  LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
575  : LVIImpl(L), DT(DTree) {}
576 
577  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
579 
580  virtual void emitInstructionAnnot(const Instruction *I,
582 };
583 }
584 namespace {
585  // The actual implementation of the lazy analysis and update. Note that the
586  // inheritance from LazyValueInfoCache is intended to be temporary while
587  // splitting the code and then transitioning to a has-a relationship.
588  class LazyValueInfoImpl {
589 
590  /// Cached results from previous queries
591  LazyValueInfoCache TheCache;
592 
593  /// This stack holds the state of the value solver during a query.
594  /// It basically emulates the callstack of the naive
595  /// recursive value lookup process.
596  SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
597 
598  /// Keeps track of which block-value pairs are in BlockValueStack.
600 
601  /// Push BV onto BlockValueStack unless it's already in there.
602  /// Returns true on success.
603  bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
604  if (!BlockValueSet.insert(BV).second)
605  return false; // It's already in the stack.
606 
607  DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
608  << "\n");
609  BlockValueStack.push_back(BV);
610  return true;
611  }
612 
613  AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
614  const DataLayout &DL; ///< A mandatory DataLayout
615  DominatorTree *DT; ///< An optional DT pointer.
616 
617  LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
618  bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
619  LVILatticeVal &Result, Instruction *CxtI = nullptr);
620  bool hasBlockValue(Value *Val, BasicBlock *BB);
621 
622  // These methods process one work item and may add more. A false value
623  // returned means that the work item was not completely processed and must
624  // be revisited after going through the new items.
625  bool solveBlockValue(Value *Val, BasicBlock *BB);
626  bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB);
627  bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
628  bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
629  bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
630  BasicBlock *BB);
631  bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, BinaryOperator *BBI,
632  BasicBlock *BB);
633  bool solveBlockValueCast(LVILatticeVal &BBLV, CastInst *CI,
634  BasicBlock *BB);
635  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
636  LVILatticeVal &BBLV,
637  Instruction *BBI);
638 
639  void solve();
640 
641  public:
642  /// This is the query interface to determine the lattice
643  /// value for the specified Value* at the end of the specified block.
644  LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
645  Instruction *CxtI = nullptr);
646 
647  /// This is the query interface to determine the lattice
648  /// value for the specified Value* at the specified instruction (generally
649  /// from an assume intrinsic).
650  LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
651 
652  /// This is the query interface to determine the lattice
653  /// value for the specified Value* that is true on the specified edge.
654  LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
655  Instruction *CxtI = nullptr);
656 
657  /// Complete flush all previously computed values
658  void clear() {
659  TheCache.clear();
660  }
661 
662  /// Printing the LazyValueInfo Analysis.
663  void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
664  LazyValueInfoAnnotatedWriter Writer(this, DTree);
665  F.print(OS, &Writer);
666  }
667 
668  /// This is part of the update interface to inform the cache
669  /// that a block has been deleted.
670  void eraseBlock(BasicBlock *BB) {
671  TheCache.eraseBlock(BB);
672  }
673 
674  /// This is the update interface to inform the cache that an edge from
675  /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
676  void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
677 
678  LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
679  DominatorTree *DT = nullptr)
680  : AC(AC), DL(DL), DT(DT) {}
681  };
682 } // end anonymous namespace
683 
684 
687  BlockValueStack.begin(), BlockValueStack.end());
688 
689  unsigned processedCount = 0;
690  while (!BlockValueStack.empty()) {
691  processedCount++;
692  // Abort if we have to process too many values to get a result for this one.
693  // Because of the design of the overdefined cache currently being per-block
694  // to avoid naming-related issues (IE it wants to try to give different
695  // results for the same name in different blocks), overdefined results don't
696  // get cached globally, which in turn means we will often try to rediscover
697  // the same overdefined result again and again. Once something like
698  // PredicateInfo is used in LVI or CVP, we should be able to make the
699  // overdefined cache global, and remove this throttle.
700  if (processedCount > MaxProcessedPerValue) {
701  DEBUG(dbgs() << "Giving up on stack because we are getting too deep\n");
702  // Fill in the original values
703  while (!StartingStack.empty()) {
704  std::pair<BasicBlock *, Value *> &e = StartingStack.back();
705  TheCache.insertResult(e.second, e.first,
706  LVILatticeVal::getOverdefined());
707  StartingStack.pop_back();
708  }
709  BlockValueSet.clear();
710  BlockValueStack.clear();
711  return;
712  }
713  std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
714  assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
715 
716  if (solveBlockValue(e.second, e.first)) {
717  // The work item was completely processed.
718  assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
719  assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
720  "Result should be in cache!");
721 
722  DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
723  << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
724 
725  BlockValueStack.pop_back();
726  BlockValueSet.erase(e);
727  } else {
728  // More work needs to be done before revisiting.
729  assert(BlockValueStack.back() != e && "Stack should have been pushed!");
730  }
731  }
732 }
733 
734 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
735  // If already a constant, there is nothing to compute.
736  if (isa<Constant>(Val))
737  return true;
738 
739  return TheCache.hasCachedValueInfo(Val, BB);
740 }
741 
742 LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) {
743  // If already a constant, there is nothing to compute.
744  if (Constant *VC = dyn_cast<Constant>(Val))
745  return LVILatticeVal::get(VC);
746 
747  return TheCache.getCachedValueInfo(Val, BB);
748 }
749 
750 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
751  switch (BBI->getOpcode()) {
752  default: break;
753  case Instruction::Load:
754  case Instruction::Call:
755  case Instruction::Invoke:
756  if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
757  if (isa<IntegerType>(BBI->getType())) {
758  return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
759  }
760  break;
761  };
762  // Nothing known - will be intersected with other facts
763  return LVILatticeVal::getOverdefined();
764 }
765 
766 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
767  if (isa<Constant>(Val))
768  return true;
769 
770  if (TheCache.hasCachedValueInfo(Val, BB)) {
771  // If we have a cached value, use that.
772  DEBUG(dbgs() << " reuse BB '" << BB->getName()
773  << "' val=" << TheCache.getCachedValueInfo(Val, BB) << '\n');
774 
775  // Since we're reusing a cached value, we don't need to update the
776  // OverDefinedCache. The cache will have been properly updated whenever the
777  // cached value was inserted.
778  return true;
779  }
780 
781  // Hold off inserting this value into the Cache in case we have to return
782  // false and come back later.
783  LVILatticeVal Res;
784  if (!solveBlockValueImpl(Res, Val, BB))
785  // Work pushed, will revisit
786  return false;
787 
788  TheCache.insertResult(Val, BB, Res);
789  return true;
790 }
791 
792 bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res,
793  Value *Val, BasicBlock *BB) {
794 
795  Instruction *BBI = dyn_cast<Instruction>(Val);
796  if (!BBI || BBI->getParent() != BB)
797  return solveBlockValueNonLocal(Res, Val, BB);
798 
799  if (PHINode *PN = dyn_cast<PHINode>(BBI))
800  return solveBlockValuePHINode(Res, PN, BB);
801 
802  if (auto *SI = dyn_cast<SelectInst>(BBI))
803  return solveBlockValueSelect(Res, SI, BB);
804 
805  // If this value is a nonnull pointer, record it's range and bailout. Note
806  // that for all other pointer typed values, we terminate the search at the
807  // definition. We could easily extend this to look through geps, bitcasts,
808  // and the like to prove non-nullness, but it's not clear that's worth it
809  // compile time wise. The context-insensitive value walk done inside
810  // isKnownNonNull gets most of the profitable cases at much less expense.
811  // This does mean that we have a sensativity to where the defining
812  // instruction is placed, even if it could legally be hoisted much higher.
813  // That is unfortunate.
814  PointerType *PT = dyn_cast<PointerType>(BBI->getType());
815  if (PT && isKnownNonNull(BBI)) {
816  Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
817  return true;
818  }
819  if (BBI->getType()->isIntegerTy()) {
820  if (auto *CI = dyn_cast<CastInst>(BBI))
821  return solveBlockValueCast(Res, CI, BB);
822 
824  if (BO && isa<ConstantInt>(BO->getOperand(1)))
825  return solveBlockValueBinaryOp(Res, BO, BB);
826  }
827 
828  DEBUG(dbgs() << " compute BB '" << BB->getName()
829  << "' - unknown inst def found.\n");
830  Res = getFromRangeMetadata(BBI);
831  return true;
832 }
833 
835  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
836  return L->getPointerAddressSpace() == 0 &&
837  GetUnderlyingObject(L->getPointerOperand(),
838  L->getModule()->getDataLayout()) == Ptr;
839  }
840  if (StoreInst *S = dyn_cast<StoreInst>(I)) {
841  return S->getPointerAddressSpace() == 0 &&
842  GetUnderlyingObject(S->getPointerOperand(),
843  S->getModule()->getDataLayout()) == Ptr;
844  }
845  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
846  if (MI->isVolatile()) return false;
847 
848  // FIXME: check whether it has a valuerange that excludes zero?
849  ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
850  if (!Len || Len->isZero()) return false;
851 
852  if (MI->getDestAddressSpace() == 0)
853  if (GetUnderlyingObject(MI->getRawDest(),
854  MI->getModule()->getDataLayout()) == Ptr)
855  return true;
856  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
857  if (MTI->getSourceAddressSpace() == 0)
858  if (GetUnderlyingObject(MTI->getRawSource(),
859  MTI->getModule()->getDataLayout()) == Ptr)
860  return true;
861  }
862  return false;
863 }
864 
865 /// Return true if the allocation associated with Val is ever dereferenced
866 /// within the given basic block. This establishes the fact Val is not null,
867 /// but does not imply that the memory at Val is dereferenceable. (Val may
868 /// point off the end of the dereferenceable part of the object.)
870  assert(Val->getType()->isPointerTy());
871 
872  const DataLayout &DL = BB->getModule()->getDataLayout();
873  Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
874  // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
875  // inside InstructionDereferencesPointer either.
876  if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
877  for (Instruction &I : *BB)
878  if (InstructionDereferencesPointer(&I, UnderlyingVal))
879  return true;
880  return false;
881 }
882 
883 bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
884  Value *Val, BasicBlock *BB) {
885  LVILatticeVal Result; // Start Undefined.
886 
887  // If this is the entry block, we must be asking about an argument. The
888  // value is overdefined.
889  if (BB == &BB->getParent()->getEntryBlock()) {
890  assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
891  // Before giving up, see if we can prove the pointer non-null local to
892  // this particular block.
893  if (Val->getType()->isPointerTy() &&
894  (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) {
895  PointerType *PTy = cast<PointerType>(Val->getType());
896  Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
897  } else {
898  Result = LVILatticeVal::getOverdefined();
899  }
900  BBLV = Result;
901  return true;
902  }
903 
904  // Loop over all of our predecessors, merging what we know from them into
905  // result. If we encounter an unexplored predecessor, we eagerly explore it
906  // in a depth first manner. In practice, this has the effect of discovering
907  // paths we can't analyze eagerly without spending compile times analyzing
908  // other paths. This heuristic benefits from the fact that predecessors are
909  // frequently arranged such that dominating ones come first and we quickly
910  // find a path to function entry. TODO: We should consider explicitly
911  // canonicalizing to make this true rather than relying on this happy
912  // accident.
913  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
914  LVILatticeVal EdgeResult;
915  if (!getEdgeValue(Val, *PI, BB, EdgeResult))
916  // Explore that input, then return here
917  return false;
918 
919  Result.mergeIn(EdgeResult, DL);
920 
921  // If we hit overdefined, exit early. The BlockVals entry is already set
922  // to overdefined.
923  if (Result.isOverdefined()) {
924  DEBUG(dbgs() << " compute BB '" << BB->getName()
925  << "' - overdefined because of pred (non local).\n");
926  // Before giving up, see if we can prove the pointer non-null local to
927  // this particular block.
928  if (Val->getType()->isPointerTy() &&
929  isObjectDereferencedInBlock(Val, BB)) {
930  PointerType *PTy = cast<PointerType>(Val->getType());
931  Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
932  }
933 
934  BBLV = Result;
935  return true;
936  }
937  }
938 
939  // Return the merged value, which is more precise than 'overdefined'.
940  assert(!Result.isOverdefined());
941  BBLV = Result;
942  return true;
943 }
944 
945 bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
946  PHINode *PN, BasicBlock *BB) {
947  LVILatticeVal Result; // Start Undefined.
948 
949  // Loop over all of our predecessors, merging what we know from them into
950  // result. See the comment about the chosen traversal order in
951  // solveBlockValueNonLocal; the same reasoning applies here.
952  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
953  BasicBlock *PhiBB = PN->getIncomingBlock(i);
954  Value *PhiVal = PN->getIncomingValue(i);
955  LVILatticeVal EdgeResult;
956  // Note that we can provide PN as the context value to getEdgeValue, even
957  // though the results will be cached, because PN is the value being used as
958  // the cache key in the caller.
959  if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
960  // Explore that input, then return here
961  return false;
962 
963  Result.mergeIn(EdgeResult, DL);
964 
965  // If we hit overdefined, exit early. The BlockVals entry is already set
966  // to overdefined.
967  if (Result.isOverdefined()) {
968  DEBUG(dbgs() << " compute BB '" << BB->getName()
969  << "' - overdefined because of pred (local).\n");
970 
971  BBLV = Result;
972  return true;
973  }
974  }
975 
976  // Return the merged value, which is more precise than 'overdefined'.
977  assert(!Result.isOverdefined() && "Possible PHI in entry block?");
978  BBLV = Result;
979  return true;
980 }
981 
982 static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
983  bool isTrueDest = true);
984 
985 // If we can determine a constraint on the value given conditions assumed by
986 // the program, intersect those constraints with BBLV
987 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
988  Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
989  BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
990  if (!BBI)
991  return;
992 
993  for (auto &AssumeVH : AC->assumptionsFor(Val)) {
994  if (!AssumeVH)
995  continue;
996  auto *I = cast<CallInst>(AssumeVH);
997  if (!isValidAssumeForContext(I, BBI, DT))
998  continue;
999 
1000  BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
1001  }
1002 
1003  // If guards are not used in the module, don't spend time looking for them
1004  auto *GuardDecl = BBI->getModule()->getFunction(
1005  Intrinsic::getName(Intrinsic::experimental_guard));
1006  if (!GuardDecl || GuardDecl->use_empty())
1007  return;
1008 
1009  for (Instruction &I : make_range(BBI->getIterator().getReverse(),
1010  BBI->getParent()->rend())) {
1011  Value *Cond = nullptr;
1012  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
1013  BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
1014  }
1015 }
1016 
1017 bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV,
1018  SelectInst *SI, BasicBlock *BB) {
1019 
1020  // Recurse on our inputs if needed
1021  if (!hasBlockValue(SI->getTrueValue(), BB)) {
1022  if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
1023  return false;
1024  BBLV = LVILatticeVal::getOverdefined();
1025  return true;
1026  }
1027  LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
1028  // If we hit overdefined, don't ask more queries. We want to avoid poisoning
1029  // extra slots in the table if we can.
1030  if (TrueVal.isOverdefined()) {
1031  BBLV = LVILatticeVal::getOverdefined();
1032  return true;
1033  }
1034 
1035  if (!hasBlockValue(SI->getFalseValue(), BB)) {
1036  if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
1037  return false;
1038  BBLV = LVILatticeVal::getOverdefined();
1039  return true;
1040  }
1041  LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
1042  // If we hit overdefined, don't ask more queries. We want to avoid poisoning
1043  // extra slots in the table if we can.
1044  if (FalseVal.isOverdefined()) {
1045  BBLV = LVILatticeVal::getOverdefined();
1046  return true;
1047  }
1048 
1049  if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
1050  const ConstantRange &TrueCR = TrueVal.getConstantRange();
1051  const ConstantRange &FalseCR = FalseVal.getConstantRange();
1052  Value *LHS = nullptr;
1053  Value *RHS = nullptr;
1054  SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
1055  // Is this a min specifically of our two inputs? (Avoid the risk of
1056  // ValueTracking getting smarter looking back past our immediate inputs.)
1058  LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
1059  ConstantRange ResultCR = [&]() {
1060  switch (SPR.Flavor) {
1061  default:
1062  llvm_unreachable("unexpected minmax type!");
1063  case SPF_SMIN: /// Signed minimum
1064  return TrueCR.smin(FalseCR);
1065  case SPF_UMIN: /// Unsigned minimum
1066  return TrueCR.umin(FalseCR);
1067  case SPF_SMAX: /// Signed maximum
1068  return TrueCR.smax(FalseCR);
1069  case SPF_UMAX: /// Unsigned maximum
1070  return TrueCR.umax(FalseCR);
1071  };
1072  }();
1073  BBLV = LVILatticeVal::getRange(ResultCR);
1074  return true;
1075  }
1076 
1077  // TODO: ABS, NABS from the SelectPatternResult
1078  }
1079 
1080  // Can we constrain the facts about the true and false values by using the
1081  // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
1082  // TODO: We could potentially refine an overdefined true value above.
1083  Value *Cond = SI->getCondition();
1084  TrueVal = intersect(TrueVal,
1085  getValueFromCondition(SI->getTrueValue(), Cond, true));
1086  FalseVal = intersect(FalseVal,
1087  getValueFromCondition(SI->getFalseValue(), Cond, false));
1088 
1089  // Handle clamp idioms such as:
1090  // %24 = constantrange<0, 17>
1091  // %39 = icmp eq i32 %24, 0
1092  // %40 = add i32 %24, -1
1093  // %siv.next = select i1 %39, i32 16, i32 %40
1094  // %siv.next = constantrange<0, 17> not <-1, 17>
1095  // In general, this can handle any clamp idiom which tests the edge
1096  // condition via an equality or inequality.
1097  if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
1098  ICmpInst::Predicate Pred = ICI->getPredicate();
1099  Value *A = ICI->getOperand(0);
1100  if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
1101  auto addConstants = [](ConstantInt *A, ConstantInt *B) {
1102  assert(A->getType() == B->getType());
1103  return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
1104  };
1105  // See if either input is A + C2, subject to the constraint from the
1106  // condition that A != C when that input is used. We can assume that
1107  // that input doesn't include C + C2.
1108  ConstantInt *CIAdded;
1109  switch (Pred) {
1110  default: break;
1111  case ICmpInst::ICMP_EQ:
1112  if (match(SI->getFalseValue(), m_Add(m_Specific(A),
1113  m_ConstantInt(CIAdded)))) {
1114  auto ResNot = addConstants(CIBase, CIAdded);
1115  FalseVal = intersect(FalseVal,
1116  LVILatticeVal::getNot(ResNot));
1117  }
1118  break;
1119  case ICmpInst::ICMP_NE:
1120  if (match(SI->getTrueValue(), m_Add(m_Specific(A),
1121  m_ConstantInt(CIAdded)))) {
1122  auto ResNot = addConstants(CIBase, CIAdded);
1123  TrueVal = intersect(TrueVal,
1124  LVILatticeVal::getNot(ResNot));
1125  }
1126  break;
1127  };
1128  }
1129  }
1130 
1131  LVILatticeVal Result; // Start Undefined.
1132  Result.mergeIn(TrueVal, DL);
1133  Result.mergeIn(FalseVal, DL);
1134  BBLV = Result;
1135  return true;
1136 }
1137 
1138 bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV,
1139  CastInst *CI,
1140  BasicBlock *BB) {
1141  if (!CI->getOperand(0)->getType()->isSized()) {
1142  // Without knowing how wide the input is, we can't analyze it in any useful
1143  // way.
1144  BBLV = LVILatticeVal::getOverdefined();
1145  return true;
1146  }
1147 
1148  // Filter out casts we don't know how to reason about before attempting to
1149  // recurse on our operand. This can cut a long search short if we know we're
1150  // not going to be able to get any useful information anways.
1151  switch (CI->getOpcode()) {
1152  case Instruction::Trunc:
1153  case Instruction::SExt:
1154  case Instruction::ZExt:
1155  case Instruction::BitCast:
1156  break;
1157  default:
1158  // Unhandled instructions are overdefined.
1159  DEBUG(dbgs() << " compute BB '" << BB->getName()
1160  << "' - overdefined (unknown cast).\n");
1161  BBLV = LVILatticeVal::getOverdefined();
1162  return true;
1163  }
1164 
1165  // Figure out the range of the LHS. If that fails, we still apply the
1166  // transfer rule on the full set since we may be able to locally infer
1167  // interesting facts.
1168  if (!hasBlockValue(CI->getOperand(0), BB))
1169  if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
1170  // More work to do before applying this transfer rule.
1171  return false;
1172 
1173  const unsigned OperandBitWidth =
1174  DL.getTypeSizeInBits(CI->getOperand(0)->getType());
1175  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1176  if (hasBlockValue(CI->getOperand(0), BB)) {
1177  LVILatticeVal LHSVal = getBlockValue(CI->getOperand(0), BB);
1178  intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
1179  CI);
1180  if (LHSVal.isConstantRange())
1181  LHSRange = LHSVal.getConstantRange();
1182  }
1183 
1184  const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
1185 
1186  // NOTE: We're currently limited by the set of operations that ConstantRange
1187  // can evaluate symbolically. Enhancing that set will allows us to analyze
1188  // more definitions.
1189  BBLV = LVILatticeVal::getRange(LHSRange.castOp(CI->getOpcode(),
1190  ResultBitWidth));
1191  return true;
1192 }
1193 
1194 bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
1195  BinaryOperator *BO,
1196  BasicBlock *BB) {
1197 
1198  assert(BO->getOperand(0)->getType()->isSized() &&
1199  "all operands to binary operators are sized");
1200 
1201  // Filter out operators we don't know how to reason about before attempting to
1202  // recurse on our operand(s). This can cut a long search short if we know
1203  // we're not going to be able to get any useful information anyways.
1204  switch (BO->getOpcode()) {
1205  case Instruction::Add:
1206  case Instruction::Sub:
1207  case Instruction::Mul:
1208  case Instruction::UDiv:
1209  case Instruction::Shl:
1210  case Instruction::LShr:
1211  case Instruction::And:
1212  case Instruction::Or:
1213  // continue into the code below
1214  break;
1215  default:
1216  // Unhandled instructions are overdefined.
1217  DEBUG(dbgs() << " compute BB '" << BB->getName()
1218  << "' - overdefined (unknown binary operator).\n");
1219  BBLV = LVILatticeVal::getOverdefined();
1220  return true;
1221  };
1222 
1223  // Figure out the range of the LHS. If that fails, use a conservative range,
1224  // but apply the transfer rule anyways. This lets us pick up facts from
1225  // expressions like "and i32 (call i32 @foo()), 32"
1226  if (!hasBlockValue(BO->getOperand(0), BB))
1227  if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
1228  // More work to do before applying this transfer rule.
1229  return false;
1230 
1231  const unsigned OperandBitWidth =
1232  DL.getTypeSizeInBits(BO->getOperand(0)->getType());
1233  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1234  if (hasBlockValue(BO->getOperand(0), BB)) {
1235  LVILatticeVal LHSVal = getBlockValue(BO->getOperand(0), BB);
1236  intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
1237  BO);
1238  if (LHSVal.isConstantRange())
1239  LHSRange = LHSVal.getConstantRange();
1240  }
1241 
1242  ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
1243  ConstantRange RHSRange = ConstantRange(RHS->getValue());
1244 
1245  // NOTE: We're currently limited by the set of operations that ConstantRange
1246  // can evaluate symbolically. Enhancing that set will allows us to analyze
1247  // more definitions.
1248  Instruction::BinaryOps BinOp = BO->getOpcode();
1249  BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1250  return true;
1251 }
1252 
1253 static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1254  bool isTrueDest) {
1255  Value *LHS = ICI->getOperand(0);
1256  Value *RHS = ICI->getOperand(1);
1258 
1259  if (isa<Constant>(RHS)) {
1260  if (ICI->isEquality() && LHS == Val) {
1261  // We know that V has the RHS constant if this is a true SETEQ or
1262  // false SETNE.
1263  if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1264  return LVILatticeVal::get(cast<Constant>(RHS));
1265  else
1266  return LVILatticeVal::getNot(cast<Constant>(RHS));
1267  }
1268  }
1269 
1270  if (!Val->getType()->isIntegerTy())
1271  return LVILatticeVal::getOverdefined();
1272 
1273  // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1274  // range of Val guaranteed by the condition. Recognize comparisons in the from
1275  // of:
1276  // icmp <pred> Val, ...
1277  // icmp <pred> (add Val, Offset), ...
1278  // The latter is the range checking idiom that InstCombine produces. Subtract
1279  // the offset from the allowed range for RHS in this case.
1280 
1281  // Val or (add Val, Offset) can be on either hand of the comparison
1282  if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1283  std::swap(LHS, RHS);
1284  Predicate = CmpInst::getSwappedPredicate(Predicate);
1285  }
1286 
1287  ConstantInt *Offset = nullptr;
1288  if (LHS != Val)
1289  match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1290 
1291  if (LHS == Val || Offset) {
1292  // Calculate the range of values that are allowed by the comparison
1293  ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1294  /*isFullSet=*/true);
1295  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1296  RHSRange = ConstantRange(CI->getValue());
1297  else if (Instruction *I = dyn_cast<Instruction>(RHS))
1298  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1299  RHSRange = getConstantRangeFromMetadata(*Ranges);
1300 
1301  // If we're interested in the false dest, invert the condition
1302  CmpInst::Predicate Pred =
1303  isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1304  ConstantRange TrueValues =
1305  ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1306 
1307  if (Offset) // Apply the offset from above.
1308  TrueValues = TrueValues.subtract(Offset->getValue());
1309 
1310  return LVILatticeVal::getRange(std::move(TrueValues));
1311  }
1312 
1313  return LVILatticeVal::getOverdefined();
1314 }
1315 
1316 static LVILatticeVal
1317 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1319 
1320 static LVILatticeVal
1321 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1323  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1324  return getValueFromICmpCondition(Val, ICI, isTrueDest);
1325 
1326  // Handle conditions in the form of (cond1 && cond2), we know that on the
1327  // true dest path both of the conditions hold. Similarly for conditions of
1328  // the form (cond1 || cond2), we know that on the false dest path neither
1329  // condition holds.
1330  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1331  if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
1332  (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
1333  return LVILatticeVal::getOverdefined();
1334 
1335  auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
1336  auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
1337  return intersect(RHS, LHS);
1338 }
1339 
1340 static LVILatticeVal
1341 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1343  auto I = Visited.find(Cond);
1344  if (I != Visited.end())
1345  return I->second;
1346 
1347  auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1348  Visited[Cond] = Result;
1349  return Result;
1350 }
1351 
1352 LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
1353  assert(Cond && "precondition");
1355  return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1356 }
1357 
1358 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1359 /// Val is not constrained on the edge. Result is unspecified if return value
1360 /// is false.
1361 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1362  BasicBlock *BBTo, LVILatticeVal &Result) {
1363  // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1364  // know that v != 0.
1365  if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1366  // If this is a conditional branch and only one successor goes to BBTo, then
1367  // we may be able to infer something from the condition.
1368  if (BI->isConditional() &&
1369  BI->getSuccessor(0) != BI->getSuccessor(1)) {
1370  bool isTrueDest = BI->getSuccessor(0) == BBTo;
1371  assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1372  "BBTo isn't a successor of BBFrom");
1373 
1374  // If V is the condition of the branch itself, then we know exactly what
1375  // it is.
1376  if (BI->getCondition() == Val) {
1377  Result = LVILatticeVal::get(ConstantInt::get(
1378  Type::getInt1Ty(Val->getContext()), isTrueDest));
1379  return true;
1380  }
1381 
1382  // If the condition of the branch is an equality comparison, we may be
1383  // able to infer the value.
1384  Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest);
1385  if (!Result.isOverdefined())
1386  return true;
1387  }
1388  }
1389 
1390  // If the edge was formed by a switch on the value, then we may know exactly
1391  // what it is.
1392  if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1393  if (SI->getCondition() != Val)
1394  return false;
1395 
1396  bool DefaultCase = SI->getDefaultDest() == BBTo;
1397  unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1398  ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1399 
1400  for (auto Case : SI->cases()) {
1401  ConstantRange EdgeVal(Case.getCaseValue()->getValue());
1402  if (DefaultCase) {
1403  // It is possible that the default destination is the destination of
1404  // some cases. There is no need to perform difference for those cases.
1405  if (Case.getCaseSuccessor() != BBTo)
1406  EdgesVals = EdgesVals.difference(EdgeVal);
1407  } else if (Case.getCaseSuccessor() == BBTo)
1408  EdgesVals = EdgesVals.unionWith(EdgeVal);
1409  }
1410  Result = LVILatticeVal::getRange(std::move(EdgesVals));
1411  return true;
1412  }
1413  return false;
1414 }
1415 
1416 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1417 /// the basic block if the edge does not constrain Val.
1418 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1419  BasicBlock *BBTo, LVILatticeVal &Result,
1420  Instruction *CxtI) {
1421  // If already a constant, there is nothing to compute.
1422  if (Constant *VC = dyn_cast<Constant>(Val)) {
1423  Result = LVILatticeVal::get(VC);
1424  return true;
1425  }
1426 
1427  LVILatticeVal LocalResult;
1428  if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1429  // If we couldn't constrain the value on the edge, LocalResult doesn't
1430  // provide any information.
1431  LocalResult = LVILatticeVal::getOverdefined();
1432 
1433  if (hasSingleValue(LocalResult)) {
1434  // Can't get any more precise here
1435  Result = LocalResult;
1436  return true;
1437  }
1438 
1439  if (!hasBlockValue(Val, BBFrom)) {
1440  if (pushBlockValue(std::make_pair(BBFrom, Val)))
1441  return false;
1442  // No new information.
1443  Result = LocalResult;
1444  return true;
1445  }
1446 
1447  // Try to intersect ranges of the BB and the constraint on the edge.
1448  LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
1449  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1450  BBFrom->getTerminator());
1451  // We can use the context instruction (generically the ultimate instruction
1452  // the calling pass is trying to simplify) here, even though the result of
1453  // this function is generally cached when called from the solve* functions
1454  // (and that cached result might be used with queries using a different
1455  // context instruction), because when this function is called from the solve*
1456  // functions, the context instruction is not provided. When called from
1457  // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1458  // but then the result is not cached.
1459  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1460 
1461  Result = intersect(LocalResult, InBlock);
1462  return true;
1463 }
1464 
1465 LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1466  Instruction *CxtI) {
1467  DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1468  << BB->getName() << "'\n");
1469 
1470  assert(BlockValueStack.empty() && BlockValueSet.empty());
1471  if (!hasBlockValue(V, BB)) {
1472  pushBlockValue(std::make_pair(BB, V));
1473  solve();
1474  }
1475  LVILatticeVal Result = getBlockValue(V, BB);
1476  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1477 
1478  DEBUG(dbgs() << " Result = " << Result << "\n");
1479  return Result;
1480 }
1481 
1482 LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1483  DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1484  << CxtI->getName() << "'\n");
1485 
1486  if (auto *C = dyn_cast<Constant>(V))
1487  return LVILatticeVal::get(C);
1488 
1489  LVILatticeVal Result = LVILatticeVal::getOverdefined();
1490  if (auto *I = dyn_cast<Instruction>(V))
1491  Result = getFromRangeMetadata(I);
1492  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1493 
1494  DEBUG(dbgs() << " Result = " << Result << "\n");
1495  return Result;
1496 }
1497 
1498 LVILatticeVal LazyValueInfoImpl::
1499 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1500  Instruction *CxtI) {
1501  DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1502  << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1503 
1504  LVILatticeVal Result;
1505  if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1506  solve();
1507  bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1508  (void)WasFastQuery;
1509  assert(WasFastQuery && "More work to do after problem solved?");
1510  }
1511 
1512  DEBUG(dbgs() << " Result = " << Result << "\n");
1513  return Result;
1514 }
1515 
1516 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1517  BasicBlock *NewSucc) {
1518  TheCache.threadEdgeImpl(OldSucc, NewSucc);
1519 }
1520 
1521 //===----------------------------------------------------------------------===//
1522 // LazyValueInfo Impl
1523 //===----------------------------------------------------------------------===//
1524 
1525 /// This lazily constructs the LazyValueInfoImpl.
1526 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1527  const DataLayout *DL,
1528  DominatorTree *DT = nullptr) {
1529  if (!PImpl) {
1530  assert(DL && "getCache() called with a null DataLayout");
1531  PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1532  }
1533  return *static_cast<LazyValueInfoImpl*>(PImpl);
1534 }
1535 
1537  Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1538  const DataLayout &DL = F.getParent()->getDataLayout();
1539 
1540  DominatorTreeWrapperPass *DTWP =
1541  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1542  Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1543  Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1544 
1545  if (Info.PImpl)
1546  getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1547 
1548  // Fully lazy.
1549  return false;
1550 }
1551 
1553  AU.setPreservesAll();
1556 }
1557 
1559 
1560 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1561 
1563  // If the cache was allocated, free it.
1564  if (PImpl) {
1565  delete &getImpl(PImpl, AC, nullptr);
1566  PImpl = nullptr;
1567  }
1568 }
1569 
1572  // We need to invalidate if we have either failed to preserve this analyses
1573  // result directly or if any of its dependencies have been invalidated.
1574  auto PAC = PA.getChecker<LazyValueAnalysis>();
1575  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1576  (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1577  return true;
1578 
1579  return false;
1580 }
1581 
1582 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1583 
1585  auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1586  auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1587  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1588 
1589  return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1590 }
1591 
1592 /// Returns true if we can statically tell that this value will never be a
1593 /// "useful" constant. In practice, this means we've got something like an
1594 /// alloca or a malloc call for which a comparison against a constant can
1595 /// only be guarding dead code. Note that we are potentially giving up some
1596 /// precision in dead code (a constant result) in favour of avoiding a
1597 /// expensive search for a easily answered common query.
1598 static bool isKnownNonConstant(Value *V) {
1599  V = V->stripPointerCasts();
1600  // The return val of alloc cannot be a Constant.
1601  if (isa<AllocaInst>(V))
1602  return true;
1603  return false;
1604 }
1605 
1607  Instruction *CxtI) {
1608  // Bail out early if V is known not to be a Constant.
1609  if (isKnownNonConstant(V))
1610  return nullptr;
1611 
1612  const DataLayout &DL = BB->getModule()->getDataLayout();
1613  LVILatticeVal Result =
1614  getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1615 
1616  if (Result.isConstant())
1617  return Result.getConstant();
1618  if (Result.isConstantRange()) {
1619  const ConstantRange &CR = Result.getConstantRange();
1620  if (const APInt *SingleVal = CR.getSingleElement())
1621  return ConstantInt::get(V->getContext(), *SingleVal);
1622  }
1623  return nullptr;
1624 }
1625 
1627  Instruction *CxtI) {
1628  assert(V->getType()->isIntegerTy());
1629  unsigned Width = V->getType()->getIntegerBitWidth();
1630  const DataLayout &DL = BB->getModule()->getDataLayout();
1631  LVILatticeVal Result =
1632  getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1633  if (Result.isUndefined())
1634  return ConstantRange(Width, /*isFullSet=*/false);
1635  if (Result.isConstantRange())
1636  return Result.getConstantRange();
1637  // We represent ConstantInt constants as constant ranges but other kinds
1638  // of integer constants, i.e. ConstantExpr will be tagged as constants
1639  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1640  "ConstantInt value must be represented as constantrange");
1641  return ConstantRange(Width, /*isFullSet=*/true);
1642 }
1643 
1644 /// Determine whether the specified value is known to be a
1645 /// constant on the specified edge. Return null if not.
1647  BasicBlock *ToBB,
1648  Instruction *CxtI) {
1649  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1650  LVILatticeVal Result =
1651  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1652 
1653  if (Result.isConstant())
1654  return Result.getConstant();
1655  if (Result.isConstantRange()) {
1656  const ConstantRange &CR = Result.getConstantRange();
1657  if (const APInt *SingleVal = CR.getSingleElement())
1658  return ConstantInt::get(V->getContext(), *SingleVal);
1659  }
1660  return nullptr;
1661 }
1662 
1664  BasicBlock *FromBB,
1665  BasicBlock *ToBB,
1666  Instruction *CxtI) {
1667  unsigned Width = V->getType()->getIntegerBitWidth();
1668  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1669  LVILatticeVal Result =
1670  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1671 
1672  if (Result.isUndefined())
1673  return ConstantRange(Width, /*isFullSet=*/false);
1674  if (Result.isConstantRange())
1675  return Result.getConstantRange();
1676  // We represent ConstantInt constants as constant ranges but other kinds
1677  // of integer constants, i.e. ConstantExpr will be tagged as constants
1678  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1679  "ConstantInt value must be represented as constantrange");
1680  return ConstantRange(Width, /*isFullSet=*/true);
1681 }
1682 
1684  const LVILatticeVal &Val,
1685  const DataLayout &DL,
1686  TargetLibraryInfo *TLI) {
1687 
1688  // If we know the value is a constant, evaluate the conditional.
1689  Constant *Res = nullptr;
1690  if (Val.isConstant()) {
1691  Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1692  if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1693  return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1694  return LazyValueInfo::Unknown;
1695  }
1696 
1697  if (Val.isConstantRange()) {
1699  if (!CI) return LazyValueInfo::Unknown;
1700 
1701  const ConstantRange &CR = Val.getConstantRange();
1702  if (Pred == ICmpInst::ICMP_EQ) {
1703  if (!CR.contains(CI->getValue()))
1704  return LazyValueInfo::False;
1705 
1706  if (CR.isSingleElement())
1707  return LazyValueInfo::True;
1708  } else if (Pred == ICmpInst::ICMP_NE) {
1709  if (!CR.contains(CI->getValue()))
1710  return LazyValueInfo::True;
1711 
1712  if (CR.isSingleElement())
1713  return LazyValueInfo::False;
1714  } else {
1715  // Handle more complex predicates.
1717  (ICmpInst::Predicate)Pred, CI->getValue());
1718  if (TrueValues.contains(CR))
1719  return LazyValueInfo::True;
1720  if (TrueValues.inverse().contains(CR))
1721  return LazyValueInfo::False;
1722  }
1723  return LazyValueInfo::Unknown;
1724  }
1725 
1726  if (Val.isNotConstant()) {
1727  // If this is an equality comparison, we can try to fold it knowing that
1728  // "V != C1".
1729  if (Pred == ICmpInst::ICMP_EQ) {
1730  // !C1 == C -> false iff C1 == C.
1732  Val.getNotConstant(), C, DL,
1733  TLI);
1734  if (Res->isNullValue())
1735  return LazyValueInfo::False;
1736  } else if (Pred == ICmpInst::ICMP_NE) {
1737  // !C1 != C -> true iff C1 == C.
1739  Val.getNotConstant(), C, DL,
1740  TLI);
1741  if (Res->isNullValue())
1742  return LazyValueInfo::True;
1743  }
1744  return LazyValueInfo::Unknown;
1745  }
1746 
1747  return LazyValueInfo::Unknown;
1748 }
1749 
1750 /// Determine whether the specified value comparison with a constant is known to
1751 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1754  BasicBlock *FromBB, BasicBlock *ToBB,
1755  Instruction *CxtI) {
1756  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1757  LVILatticeVal Result =
1758  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1759 
1760  return getPredicateResult(Pred, C, Result, DL, TLI);
1761 }
1762 
1765  Instruction *CxtI) {
1766  // Is or is not NonNull are common predicates being queried. If
1767  // isKnownNonNull can tell us the result of the predicate, we can
1768  // return it quickly. But this is only a fastpath, and falling
1769  // through would still be correct.
1770  if (V->getType()->isPointerTy() && C->isNullValue() &&
1772  if (Pred == ICmpInst::ICMP_EQ)
1773  return LazyValueInfo::False;
1774  else if (Pred == ICmpInst::ICMP_NE)
1775  return LazyValueInfo::True;
1776  }
1777  const DataLayout &DL = CxtI->getModule()->getDataLayout();
1778  LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1779  Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1780  if (Ret != Unknown)
1781  return Ret;
1782 
1783  // Note: The following bit of code is somewhat distinct from the rest of LVI;
1784  // LVI as a whole tries to compute a lattice value which is conservatively
1785  // correct at a given location. In this case, we have a predicate which we
1786  // weren't able to prove about the merged result, and we're pushing that
1787  // predicate back along each incoming edge to see if we can prove it
1788  // separately for each input. As a motivating example, consider:
1789  // bb1:
1790  // %v1 = ... ; constantrange<1, 5>
1791  // br label %merge
1792  // bb2:
1793  // %v2 = ... ; constantrange<10, 20>
1794  // br label %merge
1795  // merge:
1796  // %phi = phi [%v1, %v2] ; constantrange<1,20>
1797  // %pred = icmp eq i32 %phi, 8
1798  // We can't tell from the lattice value for '%phi' that '%pred' is false
1799  // along each path, but by checking the predicate over each input separately,
1800  // we can.
1801  // We limit the search to one step backwards from the current BB and value.
1802  // We could consider extending this to search further backwards through the
1803  // CFG and/or value graph, but there are non-obvious compile time vs quality
1804  // tradeoffs.
1805  if (CxtI) {
1806  BasicBlock *BB = CxtI->getParent();
1807 
1808  // Function entry or an unreachable block. Bail to avoid confusing
1809  // analysis below.
1810  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1811  if (PI == PE)
1812  return Unknown;
1813 
1814  // If V is a PHI node in the same block as the context, we need to ask
1815  // questions about the predicate as applied to the incoming value along
1816  // each edge. This is useful for eliminating cases where the predicate is
1817  // known along all incoming edges.
1818  if (auto *PHI = dyn_cast<PHINode>(V))
1819  if (PHI->getParent() == BB) {
1820  Tristate Baseline = Unknown;
1821  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1822  Value *Incoming = PHI->getIncomingValue(i);
1823  BasicBlock *PredBB = PHI->getIncomingBlock(i);
1824  // Note that PredBB may be BB itself.
1825  Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1826  CxtI);
1827 
1828  // Keep going as long as we've seen a consistent known result for
1829  // all inputs.
1830  Baseline = (i == 0) ? Result /* First iteration */
1831  : (Baseline == Result ? Baseline : Unknown); /* All others */
1832  if (Baseline == Unknown)
1833  break;
1834  }
1835  if (Baseline != Unknown)
1836  return Baseline;
1837  }
1838 
1839  // For a comparison where the V is outside this block, it's possible
1840  // that we've branched on it before. Look to see if the value is known
1841  // on all incoming edges.
1842  if (!isa<Instruction>(V) ||
1843  cast<Instruction>(V)->getParent() != BB) {
1844  // For predecessor edge, determine if the comparison is true or false
1845  // on that edge. If they're all true or all false, we can conclude
1846  // the value of the comparison in this block.
1847  Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1848  if (Baseline != Unknown) {
1849  // Check that all remaining incoming values match the first one.
1850  while (++PI != PE) {
1851  Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1852  if (Ret != Baseline) break;
1853  }
1854  // If we terminated early, then one of the values didn't match.
1855  if (PI == PE) {
1856  return Baseline;
1857  }
1858  }
1859  }
1860  }
1861  return Unknown;
1862 }
1863 
1865  BasicBlock *NewSucc) {
1866  if (PImpl) {
1867  const DataLayout &DL = PredBB->getModule()->getDataLayout();
1868  getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1869  }
1870 }
1871 
1873  if (PImpl) {
1874  const DataLayout &DL = BB->getModule()->getDataLayout();
1875  getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1876  }
1877 }
1878 
1879 
1881  if (PImpl) {
1882  getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1883  }
1884 }
1885 
1886 // Print the LVI for the function arguments at the start of each basic block.
1887 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1888  const BasicBlock *BB, formatted_raw_ostream &OS) {
1889  // Find if there are latticevalues defined for arguments of the function.
1890  auto *F = BB->getParent();
1891  for (auto &Arg : F->args()) {
1892  LVILatticeVal Result = LVIImpl->getValueInBlock(
1893  const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1894  if (Result.isUndefined())
1895  continue;
1896  OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1897  }
1898 }
1899 
1900 // This function prints the LVI analysis for the instruction I at the beginning
1901 // of various basic blocks. It relies on calculated values that are stored in
1902 // the LazyValueInfoCache, and in the absence of cached values, recalculte the
1903 // LazyValueInfo for `I`, and print that info.
1904 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1905  const Instruction *I, formatted_raw_ostream &OS) {
1906 
1907  auto *ParentBB = I->getParent();
1908  SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1909  // We can generate (solve) LVI values only for blocks that are dominated by
1910  // the I's parent. However, to avoid generating LVI for all dominating blocks,
1911  // that contain redundant/uninteresting information, we print LVI for
1912  // blocks that may use this LVI information (such as immediate successor
1913  // blocks, and blocks that contain uses of `I`).
1914  auto printResult = [&](const BasicBlock *BB) {
1915  if (!BlocksContainingLVI.insert(BB).second)
1916  return;
1917  LVILatticeVal Result = LVIImpl->getValueInBlock(
1918  const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1919  OS << "; LatticeVal for: '" << *I << "' in BB: '";
1920  BB->printAsOperand(OS, false);
1921  OS << "' is: " << Result << "\n";
1922  };
1923 
1924  printResult(ParentBB);
1925  // Print the LVI analysis results for the the immediate successor blocks, that
1926  // are dominated by `ParentBB`.
1927  for (auto *BBSucc : successors(ParentBB))
1928  if (DT.dominates(ParentBB, BBSucc))
1929  printResult(BBSucc);
1930 
1931  // Print LVI in blocks where `I` is used.
1932  for (auto *U : I->users())
1933  if (auto *UseI = dyn_cast<Instruction>(U))
1934  if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1935  printResult(UseI->getParent());
1936 
1937 }
1938 
1939 namespace {
1940 // Printer class for LazyValueInfo results.
1941 class LazyValueInfoPrinter : public FunctionPass {
1942 public:
1943  static char ID; // Pass identification, replacement for typeid
1944  LazyValueInfoPrinter() : FunctionPass(ID) {
1946  }
1947 
1948  void getAnalysisUsage(AnalysisUsage &AU) const override {
1949  AU.setPreservesAll();
1952  }
1953 
1954  // Get the mandatory dominator tree analysis and pass this in to the
1955  // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
1956  bool runOnFunction(Function &F) override {
1957  dbgs() << "LVI for function '" << F.getName() << "':\n";
1958  auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1959  auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1960  LVI.printLVI(F, DTree, dbgs());
1961  return false;
1962  }
1963 };
1964 }
1965 
1966 char LazyValueInfoPrinter::ID = 0;
1967 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1968  "Lazy Value Info Printer Pass", false, false)
1970 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1971  "Lazy Value Info Printer Pass", false, false)
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t CallInst * C
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr)
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:577
static bool isConstant(const MachineInstr &MI)
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) INITIALIZE_PASS_END(LazyValueInfoWrapperPass
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr)
Return the ConstantRange constraint that is known to hold for the specified value at the end of the s...
ConstantRange unionWith(const ConstantRange &CR) const
Return the range that results from the union of this range with another range.
Unsigned minimum.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
Wrapper around LazyValueInfo.
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:262
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
An immutable pass that tracks lazily created AssumptionCache objects.
const Value * getTrueValue() const
A cache of .assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:697
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic, I, at the point in the control-flow identified by the context instruction, CxtI.
Metadata node.
Definition: Metadata.h:862
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:232
reverse_iterator rend()
Definition: BasicBlock.h:259
An instruction for reading from memory.
Definition: Instructions.h:164
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
print alias Alias Set Printer
static const unsigned MaxProcessedPerValue
Signed maximum.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest=true)
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Constant * getConstant(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant at the end of the specified block...
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:591
This class represents the LLVM &#39;select&#39; instruction.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:958
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, const LVILatticeVal &Val, const DataLayout &DL, TargetLibraryInfo *TLI)
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
lazy value Lazy Value Information Analysis
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Result run(Function &F, FunctionAnalysisManager &FAM)
static LVILatticeVal intersect(const LVILatticeVal &A, const LVILatticeVal &B)
Combine two sets of facts about the same value into a single set of facts.
DominatorTree & getDomTree()
Definition: Dominators.h:271
static bool isKnownNonConstant(Value *V)
Returns true if we can statically tell that this value will never be a "useful" constant.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:478
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:106
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:86
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:820
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, LVILatticeVal &Result)
Compute the value of Val on the edge BBFrom -> BBTo.
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the function to an output stream with an optional AssemblyAnnotationWriter. ...
Definition: AsmWriter.cpp:3365
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:190
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:121
An instruction for storing to memory.
Definition: Instructions.h:306
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
FunctionPass * createLazyValueInfoPass()
createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
static LVILatticeVal getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, DenseMap< Value *, LVILatticeVal > &Visited)
Value * getOperand(unsigned i) const
Definition: User.h:154
Class to represent pointers.
Definition: DerivedTypes.h:467
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:109
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
#define P(N)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1306
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static LVILatticeVal getFromRangeMetadata(Instruction *BBI)
Conditional or Unconditional Branch instruction.
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
#define A
Definition: LargeTest.cpp:12
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:372
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:116
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:358
Represent the analysis usage information of a pass.
static bool hasSingleValue(const LVILatticeVal &Val)
Returns true if this lattice value represents at most one possible value.
const Instruction & back() const
Definition: BasicBlock.h:266
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:860
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:119
self_iterator getIterator()
Definition: ilist_node.h:82
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type. ...
lazy value info
const Value * getCondition() const
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:527
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldCompareInstOperands - Attempt to constant fold a compare instruction (icmp/fcmp) with the...
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:3538
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:63
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
bool isEmptySet() const
Return true if this set contains no members.
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
A function analysis which provides an AssumptionCache.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
This is the common base class for memset/memcpy/memmove.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:423
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
SelectPatternFlavor Flavor
#define B
Definition: LargeTest.cpp:24
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:379
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Provides information about what library functions are available for the current target.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
This class represents a range of values.
Definition: ConstantRange.h:47
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
Natural Loop Information
Definition: LoopInfo.cpp:721
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:172
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
Class for arbitrary precision integers.
Definition: APInt.h:69
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:395
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:191
static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest)
const Value * getFalseValue() const
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
Basic Alias true
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:934
This class wraps the llvm.memcpy/memmove intrinsics.
bool isKnownNonNull(const Value *V)
Return true if this pointer couldn&#39;t possibly be null by its definition.
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:706
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:520
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
Signed minimum.
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseMap.h:150
bool isSingleElement() const
Return true if this set contains exactly one member.
Analysis pass providing the TargetLibraryInfo.
Multiway switch.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:32
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB)
Return true if the allocation associated with Val is ever dereferenced within the given basic block...
IRTranslator LLVM IR MI
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:389
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:974
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:261
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Print the Analysis.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
int * Ptr
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const DataLayout *DL, DominatorTree *DT=nullptr)
This lazily constructs the LazyValueInfoImpl.
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
void initializeLazyValueInfoPrinterPass(PassRegistry &)
Analysis to compute lazy value information.
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool InBlock(const Value *V, const BasicBlock *BB)
#define LLVM_ATTRIBUTE_USED
Definition: Compiler.h:117