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