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