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