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