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