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