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