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