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)
55  "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  if (SPR.Flavor == SPF_ABS) {
897  if (LHS == SI->getTrueValue()) {
898  BBLV = ValueLatticeElement::getRange(TrueCR.abs());
899  return true;
900  }
901  if (LHS == SI->getFalseValue()) {
902  BBLV = ValueLatticeElement::getRange(FalseCR.abs());
903  return true;
904  }
905  }
906 
907  if (SPR.Flavor == SPF_NABS) {
909  if (LHS == SI->getTrueValue()) {
910  BBLV = ValueLatticeElement::getRange(Zero.sub(TrueCR.abs()));
911  return true;
912  }
913  if (LHS == SI->getFalseValue()) {
914  BBLV = ValueLatticeElement::getRange(Zero.sub(FalseCR.abs()));
915  return true;
916  }
917  }
918  }
919 
920  // Can we constrain the facts about the true and false values by using the
921  // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
922  // TODO: We could potentially refine an overdefined true value above.
923  Value *Cond = SI->getCondition();
924  TrueVal = intersect(TrueVal,
925  getValueFromCondition(SI->getTrueValue(), Cond, true));
926  FalseVal = intersect(FalseVal,
927  getValueFromCondition(SI->getFalseValue(), Cond, false));
928 
929  // Handle clamp idioms such as:
930  // %24 = constantrange<0, 17>
931  // %39 = icmp eq i32 %24, 0
932  // %40 = add i32 %24, -1
933  // %siv.next = select i1 %39, i32 16, i32 %40
934  // %siv.next = constantrange<0, 17> not <-1, 17>
935  // In general, this can handle any clamp idiom which tests the edge
936  // condition via an equality or inequality.
937  if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
938  ICmpInst::Predicate Pred = ICI->getPredicate();
939  Value *A = ICI->getOperand(0);
940  if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
941  auto addConstants = [](ConstantInt *A, ConstantInt *B) {
942  assert(A->getType() == B->getType());
943  return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
944  };
945  // See if either input is A + C2, subject to the constraint from the
946  // condition that A != C when that input is used. We can assume that
947  // that input doesn't include C + C2.
948  ConstantInt *CIAdded;
949  switch (Pred) {
950  default: break;
951  case ICmpInst::ICMP_EQ:
952  if (match(SI->getFalseValue(), m_Add(m_Specific(A),
953  m_ConstantInt(CIAdded)))) {
954  auto ResNot = addConstants(CIBase, CIAdded);
955  FalseVal = intersect(FalseVal,
957  }
958  break;
959  case ICmpInst::ICMP_NE:
960  if (match(SI->getTrueValue(), m_Add(m_Specific(A),
961  m_ConstantInt(CIAdded)))) {
962  auto ResNot = addConstants(CIBase, CIAdded);
963  TrueVal = intersect(TrueVal,
965  }
966  break;
967  };
968  }
969  }
970 
971  ValueLatticeElement Result; // Start Undefined.
972  Result.mergeIn(TrueVal, DL);
973  Result.mergeIn(FalseVal, DL);
974  BBLV = Result;
975  return true;
976 }
977 
978 Optional<ConstantRange> LazyValueInfoImpl::getRangeForOperand(unsigned Op,
979  Instruction *I,
980  BasicBlock *BB) {
981  if (!hasBlockValue(I->getOperand(Op), BB))
982  if (pushBlockValue(std::make_pair(BB, I->getOperand(Op))))
983  return None;
984 
985  const unsigned OperandBitWidth =
986  DL.getTypeSizeInBits(I->getOperand(Op)->getType());
987  ConstantRange Range = ConstantRange::getFull(OperandBitWidth);
988  if (hasBlockValue(I->getOperand(Op), BB)) {
989  ValueLatticeElement Val = getBlockValue(I->getOperand(Op), BB);
990  intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I);
991  if (Val.isConstantRange())
992  Range = Val.getConstantRange();
993  }
994  return Range;
995 }
996 
997 bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
998  CastInst *CI,
999  BasicBlock *BB) {
1000  if (!CI->getOperand(0)->getType()->isSized()) {
1001  // Without knowing how wide the input is, we can't analyze it in any useful
1002  // way.
1004  return true;
1005  }
1006 
1007  // Filter out casts we don't know how to reason about before attempting to
1008  // recurse on our operand. This can cut a long search short if we know we're
1009  // not going to be able to get any useful information anways.
1010  switch (CI->getOpcode()) {
1011  case Instruction::Trunc:
1012  case Instruction::SExt:
1013  case Instruction::ZExt:
1014  case Instruction::BitCast:
1015  break;
1016  default:
1017  // Unhandled instructions are overdefined.
1018  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1019  << "' - overdefined (unknown cast).\n");
1021  return true;
1022  }
1023 
1024  // Figure out the range of the LHS. If that fails, we still apply the
1025  // transfer rule on the full set since we may be able to locally infer
1026  // interesting facts.
1027  Optional<ConstantRange> LHSRes = getRangeForOperand(0, CI, BB);
1028  if (!LHSRes.hasValue())
1029  // More work to do before applying this transfer rule.
1030  return false;
1031  ConstantRange LHSRange = LHSRes.getValue();
1032 
1033  const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
1034 
1035  // NOTE: We're currently limited by the set of operations that ConstantRange
1036  // can evaluate symbolically. Enhancing that set will allows us to analyze
1037  // more definitions.
1038  BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
1039  ResultBitWidth));
1040  return true;
1041 }
1042 
1043 bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
1044  BinaryOperator *BO,
1045  BasicBlock *BB) {
1046 
1047  assert(BO->getOperand(0)->getType()->isSized() &&
1048  "all operands to binary operators are sized");
1049 
1050  // Filter out operators we don't know how to reason about before attempting to
1051  // recurse on our operand(s). This can cut a long search short if we know
1052  // we're not going to be able to get any useful information anyways.
1053  switch (BO->getOpcode()) {
1054  case Instruction::Add:
1055  case Instruction::Sub:
1056  case Instruction::Mul:
1057  case Instruction::UDiv:
1058  case Instruction::Shl:
1059  case Instruction::LShr:
1060  case Instruction::AShr:
1061  case Instruction::And:
1062  case Instruction::Or:
1063  // continue into the code below
1064  break;
1065  default:
1066  // Unhandled instructions are overdefined.
1067  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1068  << "' - overdefined (unknown binary operator).\n");
1070  return true;
1071  };
1072 
1073  // Figure out the ranges of the operands. If that fails, use a
1074  // conservative range, but apply the transfer rule anyways. This
1075  // lets us pick up facts from expressions like "and i32 (call i32
1076  // @foo()), 32"
1077  Optional<ConstantRange> LHSRes = getRangeForOperand(0, BO, BB);
1078  Optional<ConstantRange> RHSRes = getRangeForOperand(1, BO, BB);
1079 
1080  if (!LHSRes.hasValue() || !RHSRes.hasValue())
1081  // More work to do before applying this transfer rule.
1082  return false;
1083 
1084  ConstantRange LHSRange = LHSRes.getValue();
1085  ConstantRange RHSRange = RHSRes.getValue();
1086 
1087  // NOTE: We're currently limited by the set of operations that ConstantRange
1088  // can evaluate symbolically. Enhancing that set will allows us to analyze
1089  // more definitions.
1090  Instruction::BinaryOps BinOp = BO->getOpcode();
1091  BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1092  return true;
1093 }
1094 
1096  bool isTrueDest) {
1097  Value *LHS = ICI->getOperand(0);
1098  Value *RHS = ICI->getOperand(1);
1100 
1101  if (isa<Constant>(RHS)) {
1102  if (ICI->isEquality() && LHS == Val) {
1103  // We know that V has the RHS constant if this is a true SETEQ or
1104  // false SETNE.
1105  if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1106  return ValueLatticeElement::get(cast<Constant>(RHS));
1107  else
1108  return ValueLatticeElement::getNot(cast<Constant>(RHS));
1109  }
1110  }
1111 
1112  if (!Val->getType()->isIntegerTy())
1114 
1115  // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1116  // range of Val guaranteed by the condition. Recognize comparisons in the from
1117  // of:
1118  // icmp <pred> Val, ...
1119  // icmp <pred> (add Val, Offset), ...
1120  // The latter is the range checking idiom that InstCombine produces. Subtract
1121  // the offset from the allowed range for RHS in this case.
1122 
1123  // Val or (add Val, Offset) can be on either hand of the comparison
1124  if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1125  std::swap(LHS, RHS);
1126  Predicate = CmpInst::getSwappedPredicate(Predicate);
1127  }
1128 
1129  ConstantInt *Offset = nullptr;
1130  if (LHS != Val)
1131  match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1132 
1133  if (LHS == Val || Offset) {
1134  // Calculate the range of values that are allowed by the comparison
1135  ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1136  /*isFullSet=*/true);
1137  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1138  RHSRange = ConstantRange(CI->getValue());
1139  else if (Instruction *I = dyn_cast<Instruction>(RHS))
1140  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1141  RHSRange = getConstantRangeFromMetadata(*Ranges);
1142 
1143  // If we're interested in the false dest, invert the condition
1144  CmpInst::Predicate Pred =
1145  isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1146  ConstantRange TrueValues =
1147  ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1148 
1149  if (Offset) // Apply the offset from above.
1150  TrueValues = TrueValues.subtract(Offset->getValue());
1151 
1152  return ValueLatticeElement::getRange(std::move(TrueValues));
1153  }
1154 
1156 }
1157 
1158 // Handle conditions of the form
1159 // extractvalue(op.with.overflow(%x, C), 1).
1161  Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1162  // TODO: This only works with a constant RHS for now. We could also compute
1163  // the range of the RHS, but this doesn't fit into the current structure of
1164  // the edge value calculation.
1165  const APInt *C;
1166  if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
1168 
1169  // Calculate the possible values of %x for which no overflow occurs.
1171  WO->getBinaryOp(), *C, WO->getNoWrapKind());
1172 
1173  // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1174  // constrained to it's inverse (all values that might cause overflow).
1175  if (IsTrueDest)
1176  NWR = NWR.inverse();
1177  return ValueLatticeElement::getRange(NWR);
1178 }
1179 
1180 static ValueLatticeElement
1181 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1183 
1184 static ValueLatticeElement
1185 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1187  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1188  return getValueFromICmpCondition(Val, ICI, isTrueDest);
1189 
1190  if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
1191  if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1192  if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1193  return getValueFromOverflowCondition(Val, WO, isTrueDest);
1194 
1195  // Handle conditions in the form of (cond1 && cond2), we know that on the
1196  // true dest path both of the conditions hold. Similarly for conditions of
1197  // the form (cond1 || cond2), we know that on the false dest path neither
1198  // condition holds.
1199  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1200  if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
1201  (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
1203 
1204  // Prevent infinite recursion if Cond references itself as in this example:
1205  // Cond: "%tmp4 = and i1 %tmp4, undef"
1206  // BL: "%tmp4 = and i1 %tmp4, undef"
1207  // BR: "i1 undef"
1208  Value *BL = BO->getOperand(0);
1209  Value *BR = BO->getOperand(1);
1210  if (BL == Cond || BR == Cond)
1212 
1213  return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
1214  getValueFromCondition(Val, BR, isTrueDest, Visited));
1215 }
1216 
1217 static ValueLatticeElement
1218 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1220  auto I = Visited.find(Cond);
1221  if (I != Visited.end())
1222  return I->second;
1223 
1224  auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1225  Visited[Cond] = Result;
1226  return Result;
1227 }
1228 
1230  bool isTrueDest) {
1231  assert(Cond && "precondition");
1233  return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1234 }
1235 
1236 // Return true if Usr has Op as an operand, otherwise false.
1237 static bool usesOperand(User *Usr, Value *Op) {
1238  return find(Usr->operands(), Op) != Usr->op_end();
1239 }
1240 
1241 // Return true if the instruction type of Val is supported by
1242 // constantFoldUser(). Currently CastInst and BinaryOperator only. Call this
1243 // before calling constantFoldUser() to find out if it's even worth attempting
1244 // to call it.
1245 static bool isOperationFoldable(User *Usr) {
1246  return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
1247 }
1248 
1249 // Check if Usr can be simplified to an integer constant when the value of one
1250 // of its operands Op is an integer constant OpConstVal. If so, return it as an
1251 // lattice value range with a single element or otherwise return an overdefined
1252 // lattice value.
1254  const APInt &OpConstVal,
1255  const DataLayout &DL) {
1256  assert(isOperationFoldable(Usr) && "Precondition");
1257  Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1258  // Check if Usr can be simplified to a constant.
1259  if (auto *CI = dyn_cast<CastInst>(Usr)) {
1260  assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1261  if (auto *C = dyn_cast_or_null<ConstantInt>(
1262  SimplifyCastInst(CI->getOpcode(), OpConst,
1263  CI->getDestTy(), DL))) {
1264  return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1265  }
1266  } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1267  bool Op0Match = BO->getOperand(0) == Op;
1268  bool Op1Match = BO->getOperand(1) == Op;
1269  assert((Op0Match || Op1Match) &&
1270  "Operand 0 nor Operand 1 isn't a match");
1271  Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1272  Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1273  if (auto *C = dyn_cast_or_null<ConstantInt>(
1274  SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1275  return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1276  }
1277  }
1279 }
1280 
1281 /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1282 /// Val is not constrained on the edge. Result is unspecified if return value
1283 /// is false.
1284 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1285  BasicBlock *BBTo, ValueLatticeElement &Result) {
1286  // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1287  // know that v != 0.
1288  if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1289  // If this is a conditional branch and only one successor goes to BBTo, then
1290  // we may be able to infer something from the condition.
1291  if (BI->isConditional() &&
1292  BI->getSuccessor(0) != BI->getSuccessor(1)) {
1293  bool isTrueDest = BI->getSuccessor(0) == BBTo;
1294  assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1295  "BBTo isn't a successor of BBFrom");
1296  Value *Condition = BI->getCondition();
1297 
1298  // If V is the condition of the branch itself, then we know exactly what
1299  // it is.
1300  if (Condition == Val) {
1302  Type::getInt1Ty(Val->getContext()), isTrueDest));
1303  return true;
1304  }
1305 
1306  // If the condition of the branch is an equality comparison, we may be
1307  // able to infer the value.
1308  Result = getValueFromCondition(Val, Condition, isTrueDest);
1309  if (!Result.isOverdefined())
1310  return true;
1311 
1312  if (User *Usr = dyn_cast<User>(Val)) {
1313  assert(Result.isOverdefined() && "Result isn't overdefined");
1314  // Check with isOperationFoldable() first to avoid linearly iterating
1315  // over the operands unnecessarily which can be expensive for
1316  // instructions with many operands.
1317  if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1318  const DataLayout &DL = BBTo->getModule()->getDataLayout();
1319  if (usesOperand(Usr, Condition)) {
1320  // If Val has Condition as an operand and Val can be folded into a
1321  // constant with either Condition == true or Condition == false,
1322  // propagate the constant.
1323  // eg.
1324  // ; %Val is true on the edge to %then.
1325  // %Val = and i1 %Condition, true.
1326  // br %Condition, label %then, label %else
1327  APInt ConditionVal(1, isTrueDest ? 1 : 0);
1328  Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1329  } else {
1330  // If one of Val's operand has an inferred value, we may be able to
1331  // infer the value of Val.
1332  // eg.
1333  // ; %Val is 94 on the edge to %then.
1334  // %Val = add i8 %Op, 1
1335  // %Condition = icmp eq i8 %Op, 93
1336  // br i1 %Condition, label %then, label %else
1337  for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1338  Value *Op = Usr->getOperand(i);
1339  ValueLatticeElement OpLatticeVal =
1340  getValueFromCondition(Op, Condition, isTrueDest);
1341  if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
1342  Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
1343  break;
1344  }
1345  }
1346  }
1347  }
1348  }
1349  if (!Result.isOverdefined())
1350  return true;
1351  }
1352  }
1353 
1354  // If the edge was formed by a switch on the value, then we may know exactly
1355  // what it is.
1356  if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1357  Value *Condition = SI->getCondition();
1358  if (!isa<IntegerType>(Val->getType()))
1359  return false;
1360  bool ValUsesConditionAndMayBeFoldable = false;
1361  if (Condition != Val) {
1362  // Check if Val has Condition as an operand.
1363  if (User *Usr = dyn_cast<User>(Val))
1364  ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1365  usesOperand(Usr, Condition);
1366  if (!ValUsesConditionAndMayBeFoldable)
1367  return false;
1368  }
1369  assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1370  "Condition != Val nor Val doesn't use Condition");
1371 
1372  bool DefaultCase = SI->getDefaultDest() == BBTo;
1373  unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1374  ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1375 
1376  for (auto Case : SI->cases()) {
1377  APInt CaseValue = Case.getCaseValue()->getValue();
1378  ConstantRange EdgeVal(CaseValue);
1379  if (ValUsesConditionAndMayBeFoldable) {
1380  User *Usr = cast<User>(Val);
1381  const DataLayout &DL = BBTo->getModule()->getDataLayout();
1382  ValueLatticeElement EdgeLatticeVal =
1383  constantFoldUser(Usr, Condition, CaseValue, DL);
1384  if (EdgeLatticeVal.isOverdefined())
1385  return false;
1386  EdgeVal = EdgeLatticeVal.getConstantRange();
1387  }
1388  if (DefaultCase) {
1389  // It is possible that the default destination is the destination of
1390  // some cases. We cannot perform difference for those cases.
1391  // We know Condition != CaseValue in BBTo. In some cases we can use
1392  // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1393  // only do this when f is identity (i.e. Val == Condition), but we
1394  // should be able to do this for any injective f.
1395  if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1396  EdgesVals = EdgesVals.difference(EdgeVal);
1397  } else if (Case.getCaseSuccessor() == BBTo)
1398  EdgesVals = EdgesVals.unionWith(EdgeVal);
1399  }
1400  Result = ValueLatticeElement::getRange(std::move(EdgesVals));
1401  return true;
1402  }
1403  return false;
1404 }
1405 
1406 /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1407 /// the basic block if the edge does not constrain Val.
1408 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1409  BasicBlock *BBTo,
1410  ValueLatticeElement &Result,
1411  Instruction *CxtI) {
1412  // If already a constant, there is nothing to compute.
1413  if (Constant *VC = dyn_cast<Constant>(Val)) {
1414  Result = ValueLatticeElement::get(VC);
1415  return true;
1416  }
1417 
1418  ValueLatticeElement LocalResult;
1419  if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1420  // If we couldn't constrain the value on the edge, LocalResult doesn't
1421  // provide any information.
1422  LocalResult = ValueLatticeElement::getOverdefined();
1423 
1424  if (hasSingleValue(LocalResult)) {
1425  // Can't get any more precise here
1426  Result = LocalResult;
1427  return true;
1428  }
1429 
1430  if (!hasBlockValue(Val, BBFrom)) {
1431  if (pushBlockValue(std::make_pair(BBFrom, Val)))
1432  return false;
1433  // No new information.
1434  Result = LocalResult;
1435  return true;
1436  }
1437 
1438  // Try to intersect ranges of the BB and the constraint on the edge.
1439  ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
1440  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1441  BBFrom->getTerminator());
1442  // We can use the context instruction (generically the ultimate instruction
1443  // the calling pass is trying to simplify) here, even though the result of
1444  // this function is generally cached when called from the solve* functions
1445  // (and that cached result might be used with queries using a different
1446  // context instruction), because when this function is called from the solve*
1447  // functions, the context instruction is not provided. When called from
1448  // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1449  // but then the result is not cached.
1450  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1451 
1452  Result = intersect(LocalResult, InBlock);
1453  return true;
1454 }
1455 
1456 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1457  Instruction *CxtI) {
1458  LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1459  << BB->getName() << "'\n");
1460 
1461  assert(BlockValueStack.empty() && BlockValueSet.empty());
1462  if (!hasBlockValue(V, BB)) {
1463  pushBlockValue(std::make_pair(BB, V));
1464  solve();
1465  }
1466  ValueLatticeElement Result = getBlockValue(V, BB);
1467  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1468 
1469  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1470  return Result;
1471 }
1472 
1473 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1474  LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1475  << "'\n");
1476 
1477  if (auto *C = dyn_cast<Constant>(V))
1478  return ValueLatticeElement::get(C);
1479 
1481  if (auto *I = dyn_cast<Instruction>(V))
1482  Result = getFromRangeMetadata(I);
1483  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1484 
1485  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1486  return Result;
1487 }
1488 
1489 ValueLatticeElement LazyValueInfoImpl::
1490 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1491  Instruction *CxtI) {
1492  LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1493  << FromBB->getName() << "' to '" << ToBB->getName()
1494  << "'\n");
1495 
1496  ValueLatticeElement Result;
1497  if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1498  solve();
1499  bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1500  (void)WasFastQuery;
1501  assert(WasFastQuery && "More work to do after problem solved?");
1502  }
1503 
1504  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1505  return Result;
1506 }
1507 
1508 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1509  BasicBlock *NewSucc) {
1510  TheCache.threadEdgeImpl(OldSucc, NewSucc);
1511 }
1512 
1513 //===----------------------------------------------------------------------===//
1514 // LazyValueInfo Impl
1515 //===----------------------------------------------------------------------===//
1516 
1517 /// This lazily constructs the LazyValueInfoImpl.
1518 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1519  const DataLayout *DL,
1520  DominatorTree *DT = nullptr) {
1521  if (!PImpl) {
1522  assert(DL && "getCache() called with a null DataLayout");
1523  PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1524  }
1525  return *static_cast<LazyValueInfoImpl*>(PImpl);
1526 }
1527 
1529  Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1530  const DataLayout &DL = F.getParent()->getDataLayout();
1531 
1532  DominatorTreeWrapperPass *DTWP =
1533  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1534  Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1535  Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1536 
1537  if (Info.PImpl)
1538  getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1539 
1540  // Fully lazy.
1541  return false;
1542 }
1543 
1545  AU.setPreservesAll();
1548 }
1549 
1551 
1552 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1553 
1555  // If the cache was allocated, free it.
1556  if (PImpl) {
1557  delete &getImpl(PImpl, AC, nullptr);
1558  PImpl = nullptr;
1559  }
1560 }
1561 
1564  // We need to invalidate if we have either failed to preserve this analyses
1565  // result directly or if any of its dependencies have been invalidated.
1566  auto PAC = PA.getChecker<LazyValueAnalysis>();
1567  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1568  (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1569  return true;
1570 
1571  return false;
1572 }
1573 
1575 
1577  FunctionAnalysisManager &FAM) {
1578  auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1579  auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1580  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1581 
1582  return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1583 }
1584 
1585 /// Returns true if we can statically tell that this value will never be a
1586 /// "useful" constant. In practice, this means we've got something like an
1587 /// alloca or a malloc call for which a comparison against a constant can
1588 /// only be guarding dead code. Note that we are potentially giving up some
1589 /// precision in dead code (a constant result) in favour of avoiding a
1590 /// expensive search for a easily answered common query.
1591 static bool isKnownNonConstant(Value *V) {
1592  V = V->stripPointerCasts();
1593  // The return val of alloc cannot be a Constant.
1594  if (isa<AllocaInst>(V))
1595  return true;
1596  return false;
1597 }
1598 
1600  Instruction *CxtI) {
1601  // Bail out early if V is known not to be a Constant.
1602  if (isKnownNonConstant(V))
1603  return nullptr;
1604 
1605  const DataLayout &DL = BB->getModule()->getDataLayout();
1606  ValueLatticeElement Result =
1607  getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1608 
1609  if (Result.isConstant())
1610  return Result.getConstant();
1611  if (Result.isConstantRange()) {
1612  const ConstantRange &CR = Result.getConstantRange();
1613  if (const APInt *SingleVal = CR.getSingleElement())
1614  return ConstantInt::get(V->getContext(), *SingleVal);
1615  }
1616  return nullptr;
1617 }
1618 
1620  Instruction *CxtI) {
1621  assert(V->getType()->isIntegerTy());
1622  unsigned Width = V->getType()->getIntegerBitWidth();
1623  const DataLayout &DL = BB->getModule()->getDataLayout();
1624  ValueLatticeElement Result =
1625  getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1626  if (Result.isUndefined())
1627  return ConstantRange::getEmpty(Width);
1628  if (Result.isConstantRange())
1629  return Result.getConstantRange();
1630  // We represent ConstantInt constants as constant ranges but other kinds
1631  // of integer constants, i.e. ConstantExpr will be tagged as constants
1632  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1633  "ConstantInt value must be represented as constantrange");
1634  return ConstantRange::getFull(Width);
1635 }
1636 
1637 /// Determine whether the specified value is known to be a
1638 /// constant on the specified edge. Return null if not.
1640  BasicBlock *ToBB,
1641  Instruction *CxtI) {
1642  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1643  ValueLatticeElement Result =
1644  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1645 
1646  if (Result.isConstant())
1647  return Result.getConstant();
1648  if (Result.isConstantRange()) {
1649  const ConstantRange &CR = Result.getConstantRange();
1650  if (const APInt *SingleVal = CR.getSingleElement())
1651  return ConstantInt::get(V->getContext(), *SingleVal);
1652  }
1653  return nullptr;
1654 }
1655 
1657  BasicBlock *FromBB,
1658  BasicBlock *ToBB,
1659  Instruction *CxtI) {
1660  unsigned Width = V->getType()->getIntegerBitWidth();
1661  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1662  ValueLatticeElement Result =
1663  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1664 
1665  if (Result.isUndefined())
1666  return ConstantRange::getEmpty(Width);
1667  if (Result.isConstantRange())
1668  return Result.getConstantRange();
1669  // We represent ConstantInt constants as constant ranges but other kinds
1670  // of integer constants, i.e. ConstantExpr will be tagged as constants
1671  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1672  "ConstantInt value must be represented as constantrange");
1673  return ConstantRange::getFull(Width);
1674 }
1675 
1677 getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1678  const DataLayout &DL, TargetLibraryInfo *TLI) {
1679  // If we know the value is a constant, evaluate the conditional.
1680  Constant *Res = nullptr;
1681  if (Val.isConstant()) {
1682  Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1683  if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1684  return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1685  return LazyValueInfo::Unknown;
1686  }
1687 
1688  if (Val.isConstantRange()) {
1690  if (!CI) return LazyValueInfo::Unknown;
1691 
1692  const ConstantRange &CR = Val.getConstantRange();
1693  if (Pred == ICmpInst::ICMP_EQ) {
1694  if (!CR.contains(CI->getValue()))
1695  return LazyValueInfo::False;
1696 
1697  if (CR.isSingleElement())
1698  return LazyValueInfo::True;
1699  } else if (Pred == ICmpInst::ICMP_NE) {
1700  if (!CR.contains(CI->getValue()))
1701  return LazyValueInfo::True;
1702 
1703  if (CR.isSingleElement())
1704  return LazyValueInfo::False;
1705  } else {
1706  // Handle more complex predicates.
1708  (ICmpInst::Predicate)Pred, CI->getValue());
1709  if (TrueValues.contains(CR))
1710  return LazyValueInfo::True;
1711  if (TrueValues.inverse().contains(CR))
1712  return LazyValueInfo::False;
1713  }
1714  return LazyValueInfo::Unknown;
1715  }
1716 
1717  if (Val.isNotConstant()) {
1718  // If this is an equality comparison, we can try to fold it knowing that
1719  // "V != C1".
1720  if (Pred == ICmpInst::ICMP_EQ) {
1721  // !C1 == C -> false iff C1 == C.
1723  Val.getNotConstant(), C, DL,
1724  TLI);
1725  if (Res->isNullValue())
1726  return LazyValueInfo::False;
1727  } else if (Pred == ICmpInst::ICMP_NE) {
1728  // !C1 != C -> true iff C1 == C.
1730  Val.getNotConstant(), C, DL,
1731  TLI);
1732  if (Res->isNullValue())
1733  return LazyValueInfo::True;
1734  }
1735  return LazyValueInfo::Unknown;
1736  }
1737 
1738  return LazyValueInfo::Unknown;
1739 }
1740 
1741 /// Determine whether the specified value comparison with a constant is known to
1742 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1745  BasicBlock *FromBB, BasicBlock *ToBB,
1746  Instruction *CxtI) {
1747  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1748  ValueLatticeElement Result =
1749  getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1750 
1751  return getPredicateResult(Pred, C, Result, DL, TLI);
1752 }
1753 
1756  Instruction *CxtI) {
1757  // Is or is not NonNull are common predicates being queried. If
1758  // isKnownNonZero can tell us the result of the predicate, we can
1759  // return it quickly. But this is only a fastpath, and falling
1760  // through would still be correct.
1761  const DataLayout &DL = CxtI->getModule()->getDataLayout();
1762  if (V->getType()->isPointerTy() && C->isNullValue() &&
1763  isKnownNonZero(V->stripPointerCasts(), DL)) {
1764  if (Pred == ICmpInst::ICMP_EQ)
1765  return LazyValueInfo::False;
1766  else if (Pred == ICmpInst::ICMP_NE)
1767  return LazyValueInfo::True;
1768  }
1769  ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1770  Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1771  if (Ret != Unknown)
1772  return Ret;
1773 
1774  // Note: The following bit of code is somewhat distinct from the rest of LVI;
1775  // LVI as a whole tries to compute a lattice value which is conservatively
1776  // correct at a given location. In this case, we have a predicate which we
1777  // weren't able to prove about the merged result, and we're pushing that
1778  // predicate back along each incoming edge to see if we can prove it
1779  // separately for each input. As a motivating example, consider:
1780  // bb1:
1781  // %v1 = ... ; constantrange<1, 5>
1782  // br label %merge
1783  // bb2:
1784  // %v2 = ... ; constantrange<10, 20>
1785  // br label %merge
1786  // merge:
1787  // %phi = phi [%v1, %v2] ; constantrange<1,20>
1788  // %pred = icmp eq i32 %phi, 8
1789  // We can't tell from the lattice value for '%phi' that '%pred' is false
1790  // along each path, but by checking the predicate over each input separately,
1791  // we can.
1792  // We limit the search to one step backwards from the current BB and value.
1793  // We could consider extending this to search further backwards through the
1794  // CFG and/or value graph, but there are non-obvious compile time vs quality
1795  // tradeoffs.
1796  if (CxtI) {
1797  BasicBlock *BB = CxtI->getParent();
1798 
1799  // Function entry or an unreachable block. Bail to avoid confusing
1800  // analysis below.
1801  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1802  if (PI == PE)
1803  return Unknown;
1804 
1805  // If V is a PHI node in the same block as the context, we need to ask
1806  // questions about the predicate as applied to the incoming value along
1807  // each edge. This is useful for eliminating cases where the predicate is
1808  // known along all incoming edges.
1809  if (auto *PHI = dyn_cast<PHINode>(V))
1810  if (PHI->getParent() == BB) {
1811  Tristate Baseline = Unknown;
1812  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1813  Value *Incoming = PHI->getIncomingValue(i);
1814  BasicBlock *PredBB = PHI->getIncomingBlock(i);
1815  // Note that PredBB may be BB itself.
1816  Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1817  CxtI);
1818 
1819  // Keep going as long as we've seen a consistent known result for
1820  // all inputs.
1821  Baseline = (i == 0) ? Result /* First iteration */
1822  : (Baseline == Result ? Baseline : Unknown); /* All others */
1823  if (Baseline == Unknown)
1824  break;
1825  }
1826  if (Baseline != Unknown)
1827  return Baseline;
1828  }
1829 
1830  // For a comparison where the V is outside this block, it's possible
1831  // that we've branched on it before. Look to see if the value is known
1832  // on all incoming edges.
1833  if (!isa<Instruction>(V) ||
1834  cast<Instruction>(V)->getParent() != BB) {
1835  // For predecessor edge, determine if the comparison is true or false
1836  // on that edge. If they're all true or all false, we can conclude
1837  // the value of the comparison in this block.
1838  Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1839  if (Baseline != Unknown) {
1840  // Check that all remaining incoming values match the first one.
1841  while (++PI != PE) {
1842  Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1843  if (Ret != Baseline) break;
1844  }
1845  // If we terminated early, then one of the values didn't match.
1846  if (PI == PE) {
1847  return Baseline;
1848  }
1849  }
1850  }
1851  }
1852  return Unknown;
1853 }
1854 
1856  BasicBlock *NewSucc) {
1857  if (PImpl) {
1858  const DataLayout &DL = PredBB->getModule()->getDataLayout();
1859  getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1860  }
1861 }
1862 
1864  if (PImpl) {
1865  const DataLayout &DL = BB->getModule()->getDataLayout();
1866  getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1867  }
1868 }
1869 
1870 
1872  if (PImpl) {
1873  getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1874  }
1875 }
1876 
1878  if (PImpl)
1879  getImpl(PImpl, AC, DL, DT).disableDT();
1880 }
1881 
1883  if (PImpl)
1884  getImpl(PImpl, AC, DL, DT).enableDT();
1885 }
1886 
1887 // Print the LVI for the function arguments at the start of each basic block.
1888 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1889  const BasicBlock *BB, formatted_raw_ostream &OS) {
1890  // Find if there are latticevalues defined for arguments of the function.
1891  auto *F = BB->getParent();
1892  for (auto &Arg : F->args()) {
1893  ValueLatticeElement Result = LVIImpl->getValueInBlock(
1894  const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1895  if (Result.isUndefined())
1896  continue;
1897  OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1898  }
1899 }
1900 
1901 // This function prints the LVI analysis for the instruction I at the beginning
1902 // of various basic blocks. It relies on calculated values that are stored in
1903 // the LazyValueInfoCache, and in the absence of cached values, recalculate the
1904 // LazyValueInfo for `I`, and print that info.
1905 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1906  const Instruction *I, formatted_raw_ostream &OS) {
1907 
1908  auto *ParentBB = I->getParent();
1909  SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1910  // We can generate (solve) LVI values only for blocks that are dominated by
1911  // the I's parent. However, to avoid generating LVI for all dominating blocks,
1912  // that contain redundant/uninteresting information, we print LVI for
1913  // blocks that may use this LVI information (such as immediate successor
1914  // blocks, and blocks that contain uses of `I`).
1915  auto printResult = [&](const BasicBlock *BB) {
1916  if (!BlocksContainingLVI.insert(BB).second)
1917  return;
1918  ValueLatticeElement Result = LVIImpl->getValueInBlock(
1919  const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1920  OS << "; LatticeVal for: '" << *I << "' in BB: '";
1921  BB->printAsOperand(OS, false);
1922  OS << "' is: " << Result << "\n";
1923  };
1924 
1925  printResult(ParentBB);
1926  // Print the LVI analysis results for the immediate successor blocks, that
1927  // are dominated by `ParentBB`.
1928  for (auto *BBSucc : successors(ParentBB))
1929  if (DT.dominates(ParentBB, BBSucc))
1930  printResult(BBSucc);
1931 
1932  // Print LVI in blocks where `I` is used.
1933  for (auto *U : I->users())
1934  if (auto *UseI = dyn_cast<Instruction>(U))
1935  if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1936  printResult(UseI->getParent());
1937 
1938 }
1939 
1940 namespace {
1941 // Printer class for LazyValueInfo results.
1942 class LazyValueInfoPrinter : public FunctionPass {
1943 public:
1944  static char ID; // Pass identification, replacement for typeid
1945  LazyValueInfoPrinter() : FunctionPass(ID) {
1947  }
1948 
1949  void getAnalysisUsage(AnalysisUsage &AU) const override {
1950  AU.setPreservesAll();
1953  }
1954 
1955  // Get the mandatory dominator tree analysis and pass this in to the
1956  // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
1957  bool runOnFunction(Function &F) override {
1958  dbgs() << "LVI for function '" << F.getName() << "':\n";
1959  auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1960  auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1961  LVI.printLVI(F, DTree, dbgs());
1962  return false;
1963  }
1964 };
1965 }
1966 
1967 char LazyValueInfoPrinter::ID = 0;
1968 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1969  "Lazy Value Info Printer Pass", false, false)
1971 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1972  "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:666
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...
Value * getRHS() const
Unsigned minimum.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:379
Wrapper around LazyValueInfo.
This class represents a op.with.overflow intrinsic.
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
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
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
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:311
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
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:629
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:808
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Absolute value.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:416
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
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:669
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
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:4118
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:645
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:657
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
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:175
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:709
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
static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
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:4289
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 ...
Floating point maxnum.
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:802
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:676
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:1445
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:784
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
ConstantRange abs() const
Calculate absolute value range.
#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:795
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:332
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.
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:648
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
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
Value * getLHS() const
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:824
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 APInt getNullValue(unsigned numBits)
Get the &#39;0&#39; value.
Definition: APInt.h:568
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)