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