LLVM  8.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  LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
396  << BV.first->getName() << "\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  DominatorTree *DisabledDT; ///< Stores DT if it's disabled.
405 
406  ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
407  bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
408  ValueLatticeElement &Result, Instruction *CxtI = nullptr);
409  bool hasBlockValue(Value *Val, BasicBlock *BB);
410 
411  // These methods process one work item and may add more. A false value
412  // returned means that the work item was not completely processed and must
413  // be revisited after going through the new items.
414  bool solveBlockValue(Value *Val, BasicBlock *BB);
415  bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
416  BasicBlock *BB);
417  bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
418  BasicBlock *BB);
419  bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
420  BasicBlock *BB);
421  bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
422  BasicBlock *BB);
423  bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
424  BasicBlock *BB);
425  bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
426  BasicBlock *BB);
427  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
428  ValueLatticeElement &BBLV,
429  Instruction *BBI);
430 
431  void solve();
432 
433  public:
434  /// This is the query interface to determine the lattice
435  /// value for the specified Value* at the end of the specified block.
436  ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
437  Instruction *CxtI = nullptr);
438 
439  /// This is the query interface to determine the lattice
440  /// value for the specified Value* at the specified instruction (generally
441  /// from an assume intrinsic).
442  ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
443 
444  /// This is the query interface to determine the lattice
445  /// value for the specified Value* that is true on the specified edge.
446  ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
447  BasicBlock *ToBB,
448  Instruction *CxtI = nullptr);
449 
450  /// Complete flush all previously computed values
451  void clear() {
452  TheCache.clear();
453  }
454 
455  /// Printing the LazyValueInfo Analysis.
456  void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
457  LazyValueInfoAnnotatedWriter Writer(this, DTree);
458  F.print(OS, &Writer);
459  }
460 
461  /// This is part of the update interface to inform the cache
462  /// that a block has been deleted.
463  void eraseBlock(BasicBlock *BB) {
464  TheCache.eraseBlock(BB);
465  }
466 
467  /// Disables use of the DominatorTree within LVI.
468  void disableDT() {
469  if (DT) {
470  assert(!DisabledDT && "Both DT and DisabledDT are not nullptr!");
471  std::swap(DT, DisabledDT);
472  }
473  }
474 
475  /// Enables use of the DominatorTree within LVI. Does nothing if the class
476  /// instance was initialized without a DT pointer.
477  void enableDT() {
478  if (DisabledDT) {
479  assert(!DT && "Both DT and DisabledDT are not nullptr!");
480  std::swap(DT, DisabledDT);
481  }
482  }
483 
484  /// This is the update interface to inform the cache that an edge from
485  /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
486  void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
487 
488  LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
489  DominatorTree *DT = nullptr)
490  : AC(AC), DL(DL), DT(DT), DisabledDT(nullptr) {}
491  };
492 } // end anonymous namespace
493 
494 
497  BlockValueStack.begin(), BlockValueStack.end());
498 
499  unsigned processedCount = 0;
500  while (!BlockValueStack.empty()) {
501  processedCount++;
502  // Abort if we have to process too many values to get a result for this one.
503  // Because of the design of the overdefined cache currently being per-block
504  // to avoid naming-related issues (IE it wants to try to give different
505  // results for the same name in different blocks), overdefined results don't
506  // get cached globally, which in turn means we will often try to rediscover
507  // the same overdefined result again and again. Once something like
508  // PredicateInfo is used in LVI or CVP, we should be able to make the
509  // overdefined cache global, and remove this throttle.
510  if (processedCount > MaxProcessedPerValue) {
511  LLVM_DEBUG(
512  dbgs() << "Giving up on stack because we are getting too deep\n");
513  // Fill in the original values
514  while (!StartingStack.empty()) {
515  std::pair<BasicBlock *, Value *> &e = StartingStack.back();
516  TheCache.insertResult(e.second, e.first,
518  StartingStack.pop_back();
519  }
520  BlockValueSet.clear();
521  BlockValueStack.clear();
522  return;
523  }
524  std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
525  assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
526 
527  if (solveBlockValue(e.second, e.first)) {
528  // The work item was completely processed.
529  assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
530  assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
531  "Result should be in cache!");
532 
533  LLVM_DEBUG(
534  dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
535  << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
536 
537  BlockValueStack.pop_back();
538  BlockValueSet.erase(e);
539  } else {
540  // More work needs to be done before revisiting.
541  assert(BlockValueStack.back() != e && "Stack should have been pushed!");
542  }
543  }
544 }
545 
546 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
547  // If already a constant, there is nothing to compute.
548  if (isa<Constant>(Val))
549  return true;
550 
551  return TheCache.hasCachedValueInfo(Val, BB);
552 }
553 
554 ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
555  BasicBlock *BB) {
556  // If already a constant, there is nothing to compute.
557  if (Constant *VC = dyn_cast<Constant>(Val))
559 
560  return TheCache.getCachedValueInfo(Val, BB);
561 }
562 
564  switch (BBI->getOpcode()) {
565  default: break;
566  case Instruction::Load:
567  case Instruction::Call:
568  case Instruction::Invoke:
569  if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
570  if (isa<IntegerType>(BBI->getType())) {
573  }
574  break;
575  };
576  // Nothing known - will be intersected with other facts
578 }
579 
580 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
581  if (isa<Constant>(Val))
582  return true;
583 
584  if (TheCache.hasCachedValueInfo(Val, BB)) {
585  // If we have a cached value, use that.
586  LLVM_DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val="
587  << TheCache.getCachedValueInfo(Val, BB) << '\n');
588 
589  // Since we're reusing a cached value, we don't need to update the
590  // OverDefinedCache. The cache will have been properly updated whenever the
591  // cached value was inserted.
592  return true;
593  }
594 
595  // Hold off inserting this value into the Cache in case we have to return
596  // false and come back later.
598  if (!solveBlockValueImpl(Res, Val, BB))
599  // Work pushed, will revisit
600  return false;
601 
602  TheCache.insertResult(Val, BB, Res);
603  return true;
604 }
605 
606 bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
607  Value *Val, BasicBlock *BB) {
608 
609  Instruction *BBI = dyn_cast<Instruction>(Val);
610  if (!BBI || BBI->getParent() != BB)
611  return solveBlockValueNonLocal(Res, Val, BB);
612 
613  if (PHINode *PN = dyn_cast<PHINode>(BBI))
614  return solveBlockValuePHINode(Res, PN, BB);
615 
616  if (auto *SI = dyn_cast<SelectInst>(BBI))
617  return solveBlockValueSelect(Res, SI, BB);
618 
619  // If this value is a nonnull pointer, record it's range and bailout. Note
620  // that for all other pointer typed values, we terminate the search at the
621  // definition. We could easily extend this to look through geps, bitcasts,
622  // and the like to prove non-nullness, but it's not clear that's worth it
623  // compile time wise. The context-insensitive value walk done inside
624  // isKnownNonZero gets most of the profitable cases at much less expense.
625  // This does mean that we have a sensativity to where the defining
626  // instruction is placed, even if it could legally be hoisted much higher.
627  // That is unfortunate.
628  PointerType *PT = dyn_cast<PointerType>(BBI->getType());
629  if (PT && isKnownNonZero(BBI, DL)) {
631  return true;
632  }
633  if (BBI->getType()->isIntegerTy()) {
634  if (auto *CI = dyn_cast<CastInst>(BBI))
635  return solveBlockValueCast(Res, CI, BB);
636 
638  if (BO && isa<ConstantInt>(BO->getOperand(1)))
639  return solveBlockValueBinaryOp(Res, BO, BB);
640  }
641 
642  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
643  << "' - unknown inst def found.\n");
644  Res = getFromRangeMetadata(BBI);
645  return true;
646 }
647 
649  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
650  return L->getPointerAddressSpace() == 0 &&
651  GetUnderlyingObject(L->getPointerOperand(),
652  L->getModule()->getDataLayout()) == Ptr;
653  }
654  if (StoreInst *S = dyn_cast<StoreInst>(I)) {
655  return S->getPointerAddressSpace() == 0 &&
656  GetUnderlyingObject(S->getPointerOperand(),
657  S->getModule()->getDataLayout()) == Ptr;
658  }
659  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
660  if (MI->isVolatile()) return false;
661 
662  // FIXME: check whether it has a valuerange that excludes zero?
663  ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
664  if (!Len || Len->isZero()) return false;
665 
666  if (MI->getDestAddressSpace() == 0)
667  if (GetUnderlyingObject(MI->getRawDest(),
668  MI->getModule()->getDataLayout()) == Ptr)
669  return true;
670  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
671  if (MTI->getSourceAddressSpace() == 0)
672  if (GetUnderlyingObject(MTI->getRawSource(),
673  MTI->getModule()->getDataLayout()) == Ptr)
674  return true;
675  }
676  return false;
677 }
678 
679 /// Return true if the allocation associated with Val is ever dereferenced
680 /// within the given basic block. This establishes the fact Val is not null,
681 /// but does not imply that the memory at Val is dereferenceable. (Val may
682 /// point off the end of the dereferenceable part of the object.)
684  assert(Val->getType()->isPointerTy());
685 
686  const DataLayout &DL = BB->getModule()->getDataLayout();
687  Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
688  // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
689  // inside InstructionDereferencesPointer either.
690  if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
691  for (Instruction &I : *BB)
692  if (InstructionDereferencesPointer(&I, UnderlyingVal))
693  return true;
694  return false;
695 }
696 
697 bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
698  Value *Val, BasicBlock *BB) {
699  ValueLatticeElement Result; // Start Undefined.
700 
701  // If this is the entry block, we must be asking about an argument. The
702  // value is overdefined.
703  if (BB == &BB->getParent()->getEntryBlock()) {
704  assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
705  // Before giving up, see if we can prove the pointer non-null local to
706  // this particular block.
707  PointerType *PTy = dyn_cast<PointerType>(Val->getType());
708  if (PTy &&
709  (isKnownNonZero(Val, DL) ||
710  (isObjectDereferencedInBlock(Val, BB) &&
711  !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) {
713  } else {
715  }
716  BBLV = Result;
717  return true;
718  }
719 
720  // Loop over all of our predecessors, merging what we know from them into
721  // result. If we encounter an unexplored predecessor, we eagerly explore it
722  // in a depth first manner. In practice, this has the effect of discovering
723  // paths we can't analyze eagerly without spending compile times analyzing
724  // other paths. This heuristic benefits from the fact that predecessors are
725  // frequently arranged such that dominating ones come first and we quickly
726  // find a path to function entry. TODO: We should consider explicitly
727  // canonicalizing to make this true rather than relying on this happy
728  // accident.
729  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
730  ValueLatticeElement EdgeResult;
731  if (!getEdgeValue(Val, *PI, BB, EdgeResult))
732  // Explore that input, then return here
733  return false;
734 
735  Result.mergeIn(EdgeResult, DL);
736 
737  // If we hit overdefined, exit early. The BlockVals entry is already set
738  // to overdefined.
739  if (Result.isOverdefined()) {
740  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
741  << "' - overdefined because of pred (non local).\n");
742  // Before giving up, see if we can prove the pointer non-null local to
743  // this particular block.
744  PointerType *PTy = dyn_cast<PointerType>(Val->getType());
745  if (PTy && isObjectDereferencedInBlock(Val, BB) &&
748  }
749 
750  BBLV = Result;
751  return true;
752  }
753  }
754 
755  // Return the merged value, which is more precise than 'overdefined'.
756  assert(!Result.isOverdefined());
757  BBLV = Result;
758  return true;
759 }
760 
761 bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV,
762  PHINode *PN, BasicBlock *BB) {
763  ValueLatticeElement Result; // Start Undefined.
764 
765  // Loop over all of our predecessors, merging what we know from them into
766  // result. See the comment about the chosen traversal order in
767  // solveBlockValueNonLocal; the same reasoning applies here.
768  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
769  BasicBlock *PhiBB = PN->getIncomingBlock(i);
770  Value *PhiVal = PN->getIncomingValue(i);
771  ValueLatticeElement EdgeResult;
772  // Note that we can provide PN as the context value to getEdgeValue, even
773  // though the results will be cached, because PN is the value being used as
774  // the cache key in the caller.
775  if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
776  // Explore that input, then return here
777  return false;
778 
779  Result.mergeIn(EdgeResult, DL);
780 
781  // If we hit overdefined, exit early. The BlockVals entry is already set
782  // to overdefined.
783  if (Result.isOverdefined()) {
784  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
785  << "' - overdefined because of pred (local).\n");
786 
787  BBLV = Result;
788  return true;
789  }
790  }
791 
792  // Return the merged value, which is more precise than 'overdefined'.
793  assert(!Result.isOverdefined() && "Possible PHI in entry block?");
794  BBLV = Result;
795  return true;
796 }
797 
799  bool isTrueDest = true);
800 
801 // If we can determine a constraint on the value given conditions assumed by
802 // the program, intersect those constraints with BBLV
803 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
804  Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
805  BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
806  if (!BBI)
807  return;
808 
809  for (auto &AssumeVH : AC->assumptionsFor(Val)) {
810  if (!AssumeVH)
811  continue;
812  auto *I = cast<CallInst>(AssumeVH);
813  if (!isValidAssumeForContext(I, BBI, DT))
814  continue;
815 
816  BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
817  }
818 
819  // If guards are not used in the module, don't spend time looking for them
820  auto *GuardDecl = BBI->getModule()->getFunction(
821  Intrinsic::getName(Intrinsic::experimental_guard));
822  if (!GuardDecl || GuardDecl->use_empty())
823  return;
824 
825  for (Instruction &I : make_range(BBI->getIterator().getReverse(),
826  BBI->getParent()->rend())) {
827  Value *Cond = nullptr;
828  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
829  BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
830  }
831 }
832 
833 bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
834  SelectInst *SI, BasicBlock *BB) {
835 
836  // Recurse on our inputs if needed
837  if (!hasBlockValue(SI->getTrueValue(), BB)) {
838  if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
839  return false;
841  return true;
842  }
843  ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
844  // If we hit overdefined, don't ask more queries. We want to avoid poisoning
845  // extra slots in the table if we can.
846  if (TrueVal.isOverdefined()) {
848  return true;
849  }
850 
851  if (!hasBlockValue(SI->getFalseValue(), BB)) {
852  if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
853  return false;
855  return true;
856  }
857  ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
858  // If we hit overdefined, don't ask more queries. We want to avoid poisoning
859  // extra slots in the table if we can.
860  if (FalseVal.isOverdefined()) {
862  return true;
863  }
864 
865  if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
866  const ConstantRange &TrueCR = TrueVal.getConstantRange();
867  const ConstantRange &FalseCR = FalseVal.getConstantRange();
868  Value *LHS = nullptr;
869  Value *RHS = nullptr;
870  SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
871  // Is this a min specifically of our two inputs? (Avoid the risk of
872  // ValueTracking getting smarter looking back past our immediate inputs.)
874  LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
875  ConstantRange ResultCR = [&]() {
876  switch (SPR.Flavor) {
877  default:
878  llvm_unreachable("unexpected minmax type!");
879  case SPF_SMIN: /// Signed minimum
880  return TrueCR.smin(FalseCR);
881  case SPF_UMIN: /// Unsigned minimum
882  return TrueCR.umin(FalseCR);
883  case SPF_SMAX: /// Signed maximum
884  return TrueCR.smax(FalseCR);
885  case SPF_UMAX: /// Unsigned maximum
886  return TrueCR.umax(FalseCR);
887  };
888  }();
889  BBLV = ValueLatticeElement::getRange(ResultCR);
890  return true;
891  }
892 
893  // TODO: ABS, NABS from the SelectPatternResult
894  }
895 
896  // Can we constrain the facts about the true and false values by using the
897  // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
898  // TODO: We could potentially refine an overdefined true value above.
899  Value *Cond = SI->getCondition();
900  TrueVal = intersect(TrueVal,
901  getValueFromCondition(SI->getTrueValue(), Cond, true));
902  FalseVal = intersect(FalseVal,
903  getValueFromCondition(SI->getFalseValue(), Cond, false));
904 
905  // Handle clamp idioms such as:
906  // %24 = constantrange<0, 17>
907  // %39 = icmp eq i32 %24, 0
908  // %40 = add i32 %24, -1
909  // %siv.next = select i1 %39, i32 16, i32 %40
910  // %siv.next = constantrange<0, 17> not <-1, 17>
911  // In general, this can handle any clamp idiom which tests the edge
912  // condition via an equality or inequality.
913  if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
914  ICmpInst::Predicate Pred = ICI->getPredicate();
915  Value *A = ICI->getOperand(0);
916  if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
917  auto addConstants = [](ConstantInt *A, ConstantInt *B) {
918  assert(A->getType() == B->getType());
919  return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
920  };
921  // See if either input is A + C2, subject to the constraint from the
922  // condition that A != C when that input is used. We can assume that
923  // that input doesn't include C + C2.
924  ConstantInt *CIAdded;
925  switch (Pred) {
926  default: break;
927  case ICmpInst::ICMP_EQ:
928  if (match(SI->getFalseValue(), m_Add(m_Specific(A),
929  m_ConstantInt(CIAdded)))) {
930  auto ResNot = addConstants(CIBase, CIAdded);
931  FalseVal = intersect(FalseVal,
933  }
934  break;
935  case ICmpInst::ICMP_NE:
936  if (match(SI->getTrueValue(), m_Add(m_Specific(A),
937  m_ConstantInt(CIAdded)))) {
938  auto ResNot = addConstants(CIBase, CIAdded);
939  TrueVal = intersect(TrueVal,
941  }
942  break;
943  };
944  }
945  }
946 
947  ValueLatticeElement Result; // Start Undefined.
948  Result.mergeIn(TrueVal, DL);
949  Result.mergeIn(FalseVal, DL);
950  BBLV = Result;
951  return true;
952 }
953 
954 bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
955  CastInst *CI,
956  BasicBlock *BB) {
957  if (!CI->getOperand(0)->getType()->isSized()) {
958  // Without knowing how wide the input is, we can't analyze it in any useful
959  // way.
961  return true;
962  }
963 
964  // Filter out casts we don't know how to reason about before attempting to
965  // recurse on our operand. This can cut a long search short if we know we're
966  // not going to be able to get any useful information anways.
967  switch (CI->getOpcode()) {
968  case Instruction::Trunc:
969  case Instruction::SExt:
970  case Instruction::ZExt:
971  case Instruction::BitCast:
972  break;
973  default:
974  // Unhandled instructions are overdefined.
975  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
976  << "' - overdefined (unknown cast).\n");
978  return true;
979  }
980 
981  // Figure out the range of the LHS. If that fails, we still apply the
982  // transfer rule on the full set since we may be able to locally infer
983  // interesting facts.
984  if (!hasBlockValue(CI->getOperand(0), BB))
985  if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
986  // More work to do before applying this transfer rule.
987  return false;
988 
989  const unsigned OperandBitWidth =
990  DL.getTypeSizeInBits(CI->getOperand(0)->getType());
991  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
992  if (hasBlockValue(CI->getOperand(0), BB)) {
993  ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB);
994  intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
995  CI);
996  if (LHSVal.isConstantRange())
997  LHSRange = LHSVal.getConstantRange();
998  }
999 
1000  const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
1001 
1002  // NOTE: We're currently limited by the set of operations that ConstantRange
1003  // can evaluate symbolically. Enhancing that set will allows us to analyze
1004  // more definitions.
1005  BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
1006  ResultBitWidth));
1007  return true;
1008 }
1009 
1010 bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
1011  BinaryOperator *BO,
1012  BasicBlock *BB) {
1013 
1014  assert(BO->getOperand(0)->getType()->isSized() &&
1015  "all operands to binary operators are sized");
1016 
1017  // Filter out operators we don't know how to reason about before attempting to
1018  // recurse on our operand(s). This can cut a long search short if we know
1019  // we're not going to be able to get any useful information anyways.
1020  switch (BO->getOpcode()) {
1021  case Instruction::Add:
1022  case Instruction::Sub:
1023  case Instruction::Mul:
1024  case Instruction::UDiv:
1025  case Instruction::Shl:
1026  case Instruction::LShr:
1027  case Instruction::AShr:
1028  case Instruction::And:
1029  case Instruction::Or:
1030  // continue into the code below
1031  break;
1032  default:
1033  // Unhandled instructions are overdefined.
1034  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1035  << "' - overdefined (unknown binary operator).\n");
1037  return true;
1038  };
1039 
1040  // Figure out the range of the LHS. If that fails, use a conservative range,
1041  // but apply the transfer rule anyways. This lets us pick up facts from
1042  // expressions like "and i32 (call i32 @foo()), 32"
1043  if (!hasBlockValue(BO->getOperand(0), BB))
1044  if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
1045  // More work to do before applying this transfer rule.
1046  return false;
1047 
1048  const unsigned OperandBitWidth =
1049  DL.getTypeSizeInBits(BO->getOperand(0)->getType());
1050  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1051  if (hasBlockValue(BO->getOperand(0), BB)) {
1052  ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
1053  intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
1054  BO);
1055  if (LHSVal.isConstantRange())
1056  LHSRange = LHSVal.getConstantRange();
1057  }
1058 
1059  ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
1060  ConstantRange RHSRange = ConstantRange(RHS->getValue());
1061 
1062  // NOTE: We're currently limited by the set of operations that ConstantRange
1063  // can evaluate symbolically. Enhancing that set will allows us to analyze
1064  // more definitions.
1065  Instruction::BinaryOps BinOp = BO->getOpcode();
1066  BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1067  return true;
1068 }
1069 
1071  bool isTrueDest) {
1072  Value *LHS = ICI->getOperand(0);
1073  Value *RHS = ICI->getOperand(1);
1075 
1076  if (isa<Constant>(RHS)) {
1077  if (ICI->isEquality() && LHS == Val) {
1078  // We know that V has the RHS constant if this is a true SETEQ or
1079  // false SETNE.
1080  if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1081  return ValueLatticeElement::get(cast<Constant>(RHS));
1082  else
1083  return ValueLatticeElement::getNot(cast<Constant>(RHS));
1084  }
1085  }
1086 
1087  if (!Val->getType()->isIntegerTy())
1089 
1090  // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1091  // range of Val guaranteed by the condition. Recognize comparisons in the from
1092  // of:
1093  // icmp <pred> Val, ...
1094  // icmp <pred> (add Val, Offset), ...
1095  // The latter is the range checking idiom that InstCombine produces. Subtract
1096  // the offset from the allowed range for RHS in this case.
1097 
1098  // Val or (add Val, Offset) can be on either hand of the comparison
1099  if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1100  std::swap(LHS, RHS);
1101  Predicate = CmpInst::getSwappedPredicate(Predicate);
1102  }
1103 
1104  ConstantInt *Offset = nullptr;
1105  if (LHS != Val)
1106  match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1107 
1108  if (LHS == Val || Offset) {
1109  // Calculate the range of values that are allowed by the comparison
1110  ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1111  /*isFullSet=*/true);
1112  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1113  RHSRange = ConstantRange(CI->getValue());
1114  else if (Instruction *I = dyn_cast<Instruction>(RHS))
1115  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1116  RHSRange = getConstantRangeFromMetadata(*Ranges);
1117 
1118  // If we're interested in the false dest, invert the condition
1119  CmpInst::Predicate Pred =
1120  isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1121  ConstantRange TrueValues =
1122  ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1123 
1124  if (Offset) // Apply the offset from above.
1125  TrueValues = TrueValues.subtract(Offset->getValue());
1126 
1127  return ValueLatticeElement::getRange(std::move(TrueValues));
1128  }
1129 
1131 }
1132 
1133 static ValueLatticeElement
1134 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1136 
1137 static ValueLatticeElement
1138 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1140  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1141  return getValueFromICmpCondition(Val, ICI, isTrueDest);
1142 
1143  // Handle conditions in the form of (cond1 && cond2), we know that on the
1144  // true dest path both of the conditions hold. Similarly for conditions of
1145  // the form (cond1 || cond2), we know that on the false dest path neither
1146  // condition holds.
1147  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1148  if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
1149  (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
1151 
1152  // Prevent infinite recursion if Cond references itself as in this example:
1153  // Cond: "%tmp4 = and i1 %tmp4, undef"
1154  // BL: "%tmp4 = and i1 %tmp4, undef"
1155  // BR: "i1 undef"
1156  Value *BL = BO->getOperand(0);
1157  Value *BR = BO->getOperand(1);
1158  if (BL == Cond || BR == Cond)
1160 
1161  return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
1162  getValueFromCondition(Val, BR, isTrueDest, Visited));
1163 }
1164 
1165 static ValueLatticeElement
1166 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1168  auto I = Visited.find(Cond);
1169  if (I != Visited.end())
1170  return I->second;
1171 
1172  auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1173  Visited[Cond] = Result;
1174  return Result;
1175 }
1176 
1178  bool isTrueDest) {
1179  assert(Cond && "precondition");
1181  return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1182 }
1183 
1184 // Return true if Usr has Op as an operand, otherwise false.
1185 static bool usesOperand(User *Usr, Value *Op) {
1186  return find(Usr->operands(), Op) != Usr->op_end();
1187 }
1188 
1189 // Return true if the instruction type of Val is supported by
1190 // constantFoldUser(). Currently CastInst and BinaryOperator only. Call this
1191 // before calling constantFoldUser() to find out if it's even worth attempting
1192 // to call it.
1193 static bool isOperationFoldable(User *Usr) {
1194  return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
1195 }
1196 
1197 // Check if Usr can be simplified to an integer constant when the value of one
1198 // of its operands Op is an integer constant OpConstVal. If so, return it as an
1199 // lattice value range with a single element or otherwise return an overdefined
1200 // lattice value.
1202  const APInt &OpConstVal,
1203  const DataLayout &DL) {
1204  assert(isOperationFoldable(Usr) && "Precondition");
1205  Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1206  // Check if Usr can be simplified to a constant.
1207  if (auto *CI = dyn_cast<CastInst>(Usr)) {
1208  assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1209  if (auto *C = dyn_cast_or_null<ConstantInt>(
1210  SimplifyCastInst(CI->getOpcode(), OpConst,
1211  CI->getDestTy(), DL))) {
1212  return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1213  }
1214  } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1215  bool Op0Match = BO->getOperand(0) == Op;
1216  bool Op1Match = BO->getOperand(1) == Op;
1217  assert((Op0Match || Op1Match) &&
1218  "Operand 0 nor Operand 1 isn't a match");
1219  Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1220  Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1221  if (auto *C = dyn_cast_or_null<ConstantInt>(
1222  SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1223  return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1224  }
1225  }
1227 }
1228 
1229 /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1230 /// Val is not constrained on the edge. Result is unspecified if return value
1231 /// is false.
1232 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1233  BasicBlock *BBTo, ValueLatticeElement &Result) {
1234  // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1235  // know that v != 0.
1236  if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1237  // If this is a conditional branch and only one successor goes to BBTo, then
1238  // we may be able to infer something from the condition.
1239  if (BI->isConditional() &&
1240  BI->getSuccessor(0) != BI->getSuccessor(1)) {
1241  bool isTrueDest = BI->getSuccessor(0) == BBTo;
1242  assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1243  "BBTo isn't a successor of BBFrom");
1244  Value *Condition = BI->getCondition();
1245 
1246  // If V is the condition of the branch itself, then we know exactly what
1247  // it is.
1248  if (Condition == Val) {
1250  Type::getInt1Ty(Val->getContext()), isTrueDest));
1251  return true;
1252  }
1253 
1254  // If the condition of the branch is an equality comparison, we may be
1255  // able to infer the value.
1256  Result = getValueFromCondition(Val, Condition, isTrueDest);
1257  if (!Result.isOverdefined())
1258  return true;
1259 
1260  if (User *Usr = dyn_cast<User>(Val)) {
1261  assert(Result.isOverdefined() && "Result isn't overdefined");
1262  // Check with isOperationFoldable() first to avoid linearly iterating
1263  // over the operands unnecessarily which can be expensive for
1264  // instructions with many operands.
1265  if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1266  const DataLayout &DL = BBTo->getModule()->getDataLayout();
1267  if (usesOperand(Usr, Condition)) {
1268  // If Val has Condition as an operand and Val can be folded into a
1269  // constant with either Condition == true or Condition == false,
1270  // propagate the constant.
1271  // eg.
1272  // ; %Val is true on the edge to %then.
1273  // %Val = and i1 %Condition, true.
1274  // br %Condition, label %then, label %else
1275  APInt ConditionVal(1, isTrueDest ? 1 : 0);
1276  Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1277  } else {
1278  // If one of Val's operand has an inferred value, we may be able to
1279  // infer the value of Val.
1280  // eg.
1281  // ; %Val is 94 on the edge to %then.
1282  // %Val = add i8 %Op, 1
1283  // %Condition = icmp eq i8 %Op, 93
1284  // br i1 %Condition, label %then, label %else
1285  for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1286  Value *Op = Usr->getOperand(i);
1287  ValueLatticeElement OpLatticeVal =
1288  getValueFromCondition(Op, Condition, isTrueDest);
1289  if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
1290  Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
1291  break;
1292  }
1293  }
1294  }
1295  }
1296  }
1297  if (!Result.isOverdefined())
1298  return true;
1299  }
1300  }
1301 
1302  // If the edge was formed by a switch on the value, then we may know exactly
1303  // what it is.
1304  if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1305  Value *Condition = SI->getCondition();
1306  if (!isa<IntegerType>(Val->getType()))
1307  return false;
1308  bool ValUsesConditionAndMayBeFoldable = false;
1309  if (Condition != Val) {
1310  // Check if Val has Condition as an operand.
1311  if (User *Usr = dyn_cast<User>(Val))
1312  ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1313  usesOperand(Usr, Condition);
1314  if (!ValUsesConditionAndMayBeFoldable)
1315  return false;
1316  }
1317  assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1318  "Condition != Val nor Val doesn't use Condition");
1319 
1320  bool DefaultCase = SI->getDefaultDest() == BBTo;
1321  unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1322  ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1323 
1324  for (auto Case : SI->cases()) {
1325  APInt CaseValue = Case.getCaseValue()->getValue();
1326  ConstantRange EdgeVal(CaseValue);
1327  if (ValUsesConditionAndMayBeFoldable) {
1328  User *Usr = cast<User>(Val);
1329  const DataLayout &DL = BBTo->getModule()->getDataLayout();
1330  ValueLatticeElement EdgeLatticeVal =
1331  constantFoldUser(Usr, Condition, CaseValue, DL);
1332  if (EdgeLatticeVal.isOverdefined())
1333  return false;
1334  EdgeVal = EdgeLatticeVal.getConstantRange();
1335  }
1336  if (DefaultCase) {
1337  // It is possible that the default destination is the destination of
1338  // some cases. We cannot perform difference for those cases.
1339  // We know Condition != CaseValue in BBTo. In some cases we can use
1340  // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1341  // only do this when f is identity (i.e. Val == Condition), but we
1342  // should be able to do this for any injective f.
1343  if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1344  EdgesVals = EdgesVals.difference(EdgeVal);
1345  } else if (Case.getCaseSuccessor() == BBTo)
1346  EdgesVals = EdgesVals.unionWith(EdgeVal);
1347  }
1348  Result = ValueLatticeElement::getRange(std::move(EdgesVals));
1349  return true;
1350  }
1351  return false;
1352 }
1353 
1354 /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1355 /// the basic block if the edge does not constrain Val.
1356 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1357  BasicBlock *BBTo,
1359  Instruction *CxtI) {
1360  // If already a constant, there is nothing to compute.
1361  if (Constant *VC = dyn_cast<Constant>(Val)) {
1362  Result = ValueLatticeElement::get(VC);
1363  return true;
1364  }
1365 
1366  ValueLatticeElement LocalResult;
1367  if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1368  // If we couldn't constrain the value on the edge, LocalResult doesn't
1369  // provide any information.
1370  LocalResult = ValueLatticeElement::getOverdefined();
1371 
1372  if (hasSingleValue(LocalResult)) {
1373  // Can't get any more precise here
1374  Result = LocalResult;
1375  return true;
1376  }
1377 
1378  if (!hasBlockValue(Val, BBFrom)) {
1379  if (pushBlockValue(std::make_pair(BBFrom, Val)))
1380  return false;
1381  // No new information.
1382  Result = LocalResult;
1383  return true;
1384  }
1385 
1386  // Try to intersect ranges of the BB and the constraint on the edge.
1387  ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
1388  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1389  BBFrom->getTerminator());
1390  // We can use the context instruction (generically the ultimate instruction
1391  // the calling pass is trying to simplify) here, even though the result of
1392  // this function is generally cached when called from the solve* functions
1393  // (and that cached result might be used with queries using a different
1394  // context instruction), because when this function is called from the solve*
1395  // functions, the context instruction is not provided. When called from
1396  // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1397  // but then the result is not cached.
1398  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1399 
1400  Result = intersect(LocalResult, InBlock);
1401  return true;
1402 }
1403 
1404 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1405  Instruction *CxtI) {
1406  LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1407  << BB->getName() << "'\n");
1408 
1409  assert(BlockValueStack.empty() && BlockValueSet.empty());
1410  if (!hasBlockValue(V, BB)) {
1411  pushBlockValue(std::make_pair(BB, V));
1412  solve();
1413  }
1414  ValueLatticeElement Result = getBlockValue(V, BB);
1415  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1416 
1417  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1418  return Result;
1419 }
1420 
1421 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1422  LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1423  << "'\n");
1424 
1425  if (auto *C = dyn_cast<Constant>(V))
1426  return ValueLatticeElement::get(C);
1427 
1429  if (auto *I = dyn_cast<Instruction>(V))
1430  Result = getFromRangeMetadata(I);
1431  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1432 
1433  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1434  return Result;
1435 }
1436 
1437 ValueLatticeElement LazyValueInfoImpl::
1438 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1439  Instruction *CxtI) {
1440  LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1441  << FromBB->getName() << "' to '" << ToBB->getName()
1442  << "'\n");
1443 
1444  ValueLatticeElement Result;
1445  if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1446  solve();
1447  bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1448  (void)WasFastQuery;
1449  assert(WasFastQuery && "More work to do after problem solved?");
1450  }
1451 
1452  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1453  return Result;
1454 }
1455 
1456 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1457  BasicBlock *NewSucc) {
1458  TheCache.threadEdgeImpl(OldSucc, NewSucc);
1459 }
1460 
1461 //===----------------------------------------------------------------------===//
1462 // LazyValueInfo Impl
1463 //===----------------------------------------------------------------------===//
1464 
1465 /// This lazily constructs the LazyValueInfoImpl.
1466 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1467  const DataLayout *DL,
1468  DominatorTree *DT = nullptr) {
1469  if (!PImpl) {
1470  assert(DL && "getCache() called with a null DataLayout");
1471  PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1472  }
1473  return *static_cast<LazyValueInfoImpl*>(PImpl);
1474 }
1475 
1477  Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1478  const DataLayout &DL = F.getParent()->getDataLayout();
1479 
1480  DominatorTreeWrapperPass *DTWP =
1481  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1482  Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1483  Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1484 
1485  if (Info.PImpl)
1486  getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1487 
1488  // Fully lazy.
1489  return false;
1490 }
1491 
1493  AU.setPreservesAll();
1496 }
1497 
1499 
1500 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1501 
1503  // If the cache was allocated, free it.
1504  if (PImpl) {
1505  delete &getImpl(PImpl, AC, nullptr);
1506  PImpl = nullptr;
1507  }
1508 }
1509 
1512  // We need to invalidate if we have either failed to preserve this analyses
1513  // result directly or if any of its dependencies have been invalidated.
1514  auto PAC = PA.getChecker<LazyValueAnalysis>();
1515  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1516  (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1517  return true;
1518 
1519  return false;
1520 }
1521 
1522 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1523 
1525  FunctionAnalysisManager &FAM) {
1526  auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1527  auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1528  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1529 
1530  return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1531 }
1532 
1533 /// Returns true if we can statically tell that this value will never be a
1534 /// "useful" constant. In practice, this means we've got something like an
1535 /// alloca or a malloc call for which a comparison against a constant can
1536 /// only be guarding dead code. Note that we are potentially giving up some
1537 /// precision in dead code (a constant result) in favour of avoiding a
1538 /// expensive search for a easily answered common query.
1539 static bool isKnownNonConstant(Value *V) {
1540  V = V->stripPointerCasts();
1541  // The return val of alloc cannot be a Constant.
1542  if (isa<AllocaInst>(V))
1543  return true;
1544  return false;
1545 }
1546 
1548  Instruction *CxtI) {
1549  // Bail out early if V is known not to be a Constant.
1550  if (isKnownNonConstant(V))
1551  return nullptr;
1552 
1553  const DataLayout &DL = BB->getModule()->getDataLayout();
1554  ValueLatticeElement Result =
1555  getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1556 
1557  if (Result.isConstant())
1558  return Result.getConstant();
1559  if (Result.isConstantRange()) {
1560  const ConstantRange &CR = Result.getConstantRange();
1561  if (const APInt *SingleVal = CR.getSingleElement())
1562  return ConstantInt::get(V->getContext(), *SingleVal);
1563  }
1564  return nullptr;
1565 }
1566 
1568  Instruction *CxtI) {
1569  assert(V->getType()->isIntegerTy());
1570  unsigned Width = V->getType()->getIntegerBitWidth();
1571  const DataLayout &DL = BB->getModule()->getDataLayout();
1572  ValueLatticeElement Result =
1573  getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1574  if (Result.isUndefined())
1575  return ConstantRange(Width, /*isFullSet=*/false);
1576  if (Result.isConstantRange())
1577  return Result.getConstantRange();
1578  // We represent ConstantInt constants as constant ranges but other kinds
1579  // of integer constants, i.e. ConstantExpr will be tagged as constants
1580  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1581  "ConstantInt value must be represented as constantrange");
1582  return ConstantRange(Width, /*isFullSet=*/true);
1583 }
1584 
1585 /// Determine whether the specified value is known to be a
1586 /// constant on the specified edge. Return null if not.
1588  BasicBlock *ToBB,
1589  Instruction *CxtI) {
1590  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1591  ValueLatticeElement Result =
1592  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1593 
1594  if (Result.isConstant())
1595  return Result.getConstant();
1596  if (Result.isConstantRange()) {
1597  const ConstantRange &CR = Result.getConstantRange();
1598  if (const APInt *SingleVal = CR.getSingleElement())
1599  return ConstantInt::get(V->getContext(), *SingleVal);
1600  }
1601  return nullptr;
1602 }
1603 
1605  BasicBlock *FromBB,
1606  BasicBlock *ToBB,
1607  Instruction *CxtI) {
1608  unsigned Width = V->getType()->getIntegerBitWidth();
1609  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1610  ValueLatticeElement Result =
1611  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1612 
1613  if (Result.isUndefined())
1614  return ConstantRange(Width, /*isFullSet=*/false);
1615  if (Result.isConstantRange())
1616  return Result.getConstantRange();
1617  // We represent ConstantInt constants as constant ranges but other kinds
1618  // of integer constants, i.e. ConstantExpr will be tagged as constants
1619  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1620  "ConstantInt value must be represented as constantrange");
1621  return ConstantRange(Width, /*isFullSet=*/true);
1622 }
1623 
1625 getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1626  const DataLayout &DL, TargetLibraryInfo *TLI) {
1627  // If we know the value is a constant, evaluate the conditional.
1628  Constant *Res = nullptr;
1629  if (Val.isConstant()) {
1630  Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1631  if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1632  return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1633  return LazyValueInfo::Unknown;
1634  }
1635 
1636  if (Val.isConstantRange()) {
1638  if (!CI) return LazyValueInfo::Unknown;
1639 
1640  const ConstantRange &CR = Val.getConstantRange();
1641  if (Pred == ICmpInst::ICMP_EQ) {
1642  if (!CR.contains(CI->getValue()))
1643  return LazyValueInfo::False;
1644 
1645  if (CR.isSingleElement())
1646  return LazyValueInfo::True;
1647  } else if (Pred == ICmpInst::ICMP_NE) {
1648  if (!CR.contains(CI->getValue()))
1649  return LazyValueInfo::True;
1650 
1651  if (CR.isSingleElement())
1652  return LazyValueInfo::False;
1653  } else {
1654  // Handle more complex predicates.
1656  (ICmpInst::Predicate)Pred, CI->getValue());
1657  if (TrueValues.contains(CR))
1658  return LazyValueInfo::True;
1659  if (TrueValues.inverse().contains(CR))
1660  return LazyValueInfo::False;
1661  }
1662  return LazyValueInfo::Unknown;
1663  }
1664 
1665  if (Val.isNotConstant()) {
1666  // If this is an equality comparison, we can try to fold it knowing that
1667  // "V != C1".
1668  if (Pred == ICmpInst::ICMP_EQ) {
1669  // !C1 == C -> false iff C1 == C.
1671  Val.getNotConstant(), C, DL,
1672  TLI);
1673  if (Res->isNullValue())
1674  return LazyValueInfo::False;
1675  } else if (Pred == ICmpInst::ICMP_NE) {
1676  // !C1 != C -> true iff C1 == C.
1678  Val.getNotConstant(), C, DL,
1679  TLI);
1680  if (Res->isNullValue())
1681  return LazyValueInfo::True;
1682  }
1683  return LazyValueInfo::Unknown;
1684  }
1685 
1686  return LazyValueInfo::Unknown;
1687 }
1688 
1689 /// Determine whether the specified value comparison with a constant is known to
1690 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1693  BasicBlock *FromBB, BasicBlock *ToBB,
1694  Instruction *CxtI) {
1695  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1696  ValueLatticeElement Result =
1697  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1698 
1699  return getPredicateResult(Pred, C, Result, DL, TLI);
1700 }
1701 
1704  Instruction *CxtI) {
1705  // Is or is not NonNull are common predicates being queried. If
1706  // isKnownNonZero can tell us the result of the predicate, we can
1707  // return it quickly. But this is only a fastpath, and falling
1708  // through would still be correct.
1709  const DataLayout &DL = CxtI->getModule()->getDataLayout();
1710  if (V->getType()->isPointerTy() && C->isNullValue() &&
1711  isKnownNonZero(V->stripPointerCasts(), DL)) {
1712  if (Pred == ICmpInst::ICMP_EQ)
1713  return LazyValueInfo::False;
1714  else if (Pred == ICmpInst::ICMP_NE)
1715  return LazyValueInfo::True;
1716  }
1717  ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1718  Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1719  if (Ret != Unknown)
1720  return Ret;
1721 
1722  // Note: The following bit of code is somewhat distinct from the rest of LVI;
1723  // LVI as a whole tries to compute a lattice value which is conservatively
1724  // correct at a given location. In this case, we have a predicate which we
1725  // weren't able to prove about the merged result, and we're pushing that
1726  // predicate back along each incoming edge to see if we can prove it
1727  // separately for each input. As a motivating example, consider:
1728  // bb1:
1729  // %v1 = ... ; constantrange<1, 5>
1730  // br label %merge
1731  // bb2:
1732  // %v2 = ... ; constantrange<10, 20>
1733  // br label %merge
1734  // merge:
1735  // %phi = phi [%v1, %v2] ; constantrange<1,20>
1736  // %pred = icmp eq i32 %phi, 8
1737  // We can't tell from the lattice value for '%phi' that '%pred' is false
1738  // along each path, but by checking the predicate over each input separately,
1739  // we can.
1740  // We limit the search to one step backwards from the current BB and value.
1741  // We could consider extending this to search further backwards through the
1742  // CFG and/or value graph, but there are non-obvious compile time vs quality
1743  // tradeoffs.
1744  if (CxtI) {
1745  BasicBlock *BB = CxtI->getParent();
1746 
1747  // Function entry or an unreachable block. Bail to avoid confusing
1748  // analysis below.
1749  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1750  if (PI == PE)
1751  return Unknown;
1752 
1753  // If V is a PHI node in the same block as the context, we need to ask
1754  // questions about the predicate as applied to the incoming value along
1755  // each edge. This is useful for eliminating cases where the predicate is
1756  // known along all incoming edges.
1757  if (auto *PHI = dyn_cast<PHINode>(V))
1758  if (PHI->getParent() == BB) {
1759  Tristate Baseline = Unknown;
1760  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1761  Value *Incoming = PHI->getIncomingValue(i);
1762  BasicBlock *PredBB = PHI->getIncomingBlock(i);
1763  // Note that PredBB may be BB itself.
1764  Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1765  CxtI);
1766 
1767  // Keep going as long as we've seen a consistent known result for
1768  // all inputs.
1769  Baseline = (i == 0) ? Result /* First iteration */
1770  : (Baseline == Result ? Baseline : Unknown); /* All others */
1771  if (Baseline == Unknown)
1772  break;
1773  }
1774  if (Baseline != Unknown)
1775  return Baseline;
1776  }
1777 
1778  // For a comparison where the V is outside this block, it's possible
1779  // that we've branched on it before. Look to see if the value is known
1780  // on all incoming edges.
1781  if (!isa<Instruction>(V) ||
1782  cast<Instruction>(V)->getParent() != BB) {
1783  // For predecessor edge, determine if the comparison is true or false
1784  // on that edge. If they're all true or all false, we can conclude
1785  // the value of the comparison in this block.
1786  Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1787  if (Baseline != Unknown) {
1788  // Check that all remaining incoming values match the first one.
1789  while (++PI != PE) {
1790  Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1791  if (Ret != Baseline) break;
1792  }
1793  // If we terminated early, then one of the values didn't match.
1794  if (PI == PE) {
1795  return Baseline;
1796  }
1797  }
1798  }
1799  }
1800  return Unknown;
1801 }
1802 
1804  BasicBlock *NewSucc) {
1805  if (PImpl) {
1806  const DataLayout &DL = PredBB->getModule()->getDataLayout();
1807  getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1808  }
1809 }
1810 
1812  if (PImpl) {
1813  const DataLayout &DL = BB->getModule()->getDataLayout();
1814  getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1815  }
1816 }
1817 
1818 
1820  if (PImpl) {
1821  getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1822  }
1823 }
1824 
1826  if (PImpl)
1827  getImpl(PImpl, AC, DL, DT).disableDT();
1828 }
1829 
1831  if (PImpl)
1832  getImpl(PImpl, AC, DL, DT).enableDT();
1833 }
1834 
1835 // Print the LVI for the function arguments at the start of each basic block.
1836 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1837  const BasicBlock *BB, formatted_raw_ostream &OS) {
1838  // Find if there are latticevalues defined for arguments of the function.
1839  auto *F = BB->getParent();
1840  for (auto &Arg : F->args()) {
1841  ValueLatticeElement Result = LVIImpl->getValueInBlock(
1842  const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1843  if (Result.isUndefined())
1844  continue;
1845  OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1846  }
1847 }
1848 
1849 // This function prints the LVI analysis for the instruction I at the beginning
1850 // of various basic blocks. It relies on calculated values that are stored in
1851 // the LazyValueInfoCache, and in the absence of cached values, recalculate the
1852 // LazyValueInfo for `I`, and print that info.
1853 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1854  const Instruction *I, formatted_raw_ostream &OS) {
1855 
1856  auto *ParentBB = I->getParent();
1857  SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1858  // We can generate (solve) LVI values only for blocks that are dominated by
1859  // the I's parent. However, to avoid generating LVI for all dominating blocks,
1860  // that contain redundant/uninteresting information, we print LVI for
1861  // blocks that may use this LVI information (such as immediate successor
1862  // blocks, and blocks that contain uses of `I`).
1863  auto printResult = [&](const BasicBlock *BB) {
1864  if (!BlocksContainingLVI.insert(BB).second)
1865  return;
1866  ValueLatticeElement Result = LVIImpl->getValueInBlock(
1867  const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1868  OS << "; LatticeVal for: '" << *I << "' in BB: '";
1869  BB->printAsOperand(OS, false);
1870  OS << "' is: " << Result << "\n";
1871  };
1872 
1873  printResult(ParentBB);
1874  // Print the LVI analysis results for the immediate successor blocks, that
1875  // are dominated by `ParentBB`.
1876  for (auto *BBSucc : successors(ParentBB))
1877  if (DT.dominates(ParentBB, BBSucc))
1878  printResult(BBSucc);
1879 
1880  // Print LVI in blocks where `I` is used.
1881  for (auto *U : I->users())
1882  if (auto *UseI = dyn_cast<Instruction>(U))
1883  if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1884  printResult(UseI->getParent());
1885 
1886 }
1887 
1888 namespace {
1889 // Printer class for LazyValueInfo results.
1890 class LazyValueInfoPrinter : public FunctionPass {
1891 public:
1892  static char ID; // Pass identification, replacement for typeid
1893  LazyValueInfoPrinter() : FunctionPass(ID) {
1895  }
1896 
1897  void getAnalysisUsage(AnalysisUsage &AU) const override {
1898  AU.setPreservesAll();
1901  }
1902 
1903  // Get the mandatory dominator tree analysis and pass this in to the
1904  // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
1905  bool runOnFunction(Function &F) override {
1906  dbgs() << "LVI for function '" << F.getName() << "':\n";
1907  auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1908  auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1909  LVI.printLVI(F, DTree, dbgs());
1910  return false;
1911  }
1912 };
1913 }
1914 
1915 char LazyValueInfoPrinter::ID = 0;
1916 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1917  "Lazy Value Info Printer Pass", false, false)
1919 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1920  "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:165
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
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:660
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:770
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:355
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:265
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:120
An immutable pass that tracks lazily created AssumptionCache objects.
const Value * getTrueValue() const
A cache of @llvm.assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
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:864
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:271
block Block Frequency true
An instruction for reading from memory.
Definition: Instructions.h:168
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:305
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 if the function does no...
Definition: BasicBlock.cpp:134
#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:627
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:783
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:392
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:270
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:126
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:639
const ConstantRange & getConstantRange() const
Definition: ValueLattice.h:159
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:645
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:4001
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:217
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:310
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
FunctionPass * createLazyValueInfoPass()
createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
Value * getOperand(unsigned i) const
Definition: User.h:170
Class to represent pointers.
Definition: DerivedTypes.h:467
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:589
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:154
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1378
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:224
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:499
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:232
const Instruction & back() const
Definition: BasicBlock.h:278
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.
unsigned getAddressSpace() const
Definition: Globals.cpp:111
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:685
bool isConstantRange() const
Definition: ValueLattice.h:146
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:238
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:495
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:539
static ValueLatticeElement getRange(ConstantRange CR)
Definition: ValueLattice.h:132
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:1063
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:149
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:4172
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:305
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:154
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.
void enableDT()
Enables use of the DominatorTree within LVI.
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:847
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:621
Natural Loop Information
Definition: LoopInfo.cpp:708
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:652
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:1440
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:175
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
Class for arbitrary precision integers.
Definition: APInt.h:70
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:400
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:212
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...
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:759
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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:789
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:241
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:642
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:92
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
LLVM Value Representation.
Definition: Value.h:73
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
succ_range successors(Instruction *I)
Definition: CFG.h:262
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:46
static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB)
Return true if the allocation associated with Val is ever dereferenced within the given basic block...
IRTranslator LLVM IR MI
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:389
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:137
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:799
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
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:138
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const DataLayout *DL, DominatorTree *DT=nullptr)
This lazily constructs the LazyValueInfoImpl.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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:71
void initializeLazyValueInfoPrinterPass(PassRegistry &)
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest)
void disableDT()
Disables use of the DominatorTree within LVI.
Analysis to compute lazy value information.
const BasicBlock * getParent() const
Definition: Instruction.h:67
static bool InBlock(const Value *V, const BasicBlock *BB)