LLVM  17.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/STLExtras.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/ConstantRange.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/Intrinsics.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/PatternMatch.h"
34 #include "llvm/IR/ValueHandle.h"
35 #include "llvm/InitializePasses.h"
36 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/KnownBits.h"
40 #include <optional>
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  std::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  std::optional<ValueLatticeElement>
214  getCachedValueInfo(Value *V, BasicBlock *BB) const {
215  const BlockCacheEntry *Entry = getBlockEntry(BB);
216  if (!Entry)
217  return std::nullopt;
218 
219  if (Entry->OverDefined.count(V))
221 
222  auto LatticeIt = Entry->LatticeElements.find_as(V);
223  if (LatticeIt == Entry->LatticeElements.end())
224  return std::nullopt;
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  std::optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB,
398  Instruction *CxtI);
399  std::optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
400  BasicBlock *T,
401  Instruction *CxtI = nullptr);
402 
403  // These methods process one work item and may add more. A false value
404  // returned means that the work item was not completely processed and must
405  // be revisited after going through the new items.
406  bool solveBlockValue(Value *Val, BasicBlock *BB);
407  std::optional<ValueLatticeElement> solveBlockValueImpl(Value *Val,
408  BasicBlock *BB);
409  std::optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
410  BasicBlock *BB);
411  std::optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,
412  BasicBlock *BB);
413  std::optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,
414  BasicBlock *BB);
415  std::optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI,
416  BasicBlock *BB);
417  std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
420  OpFn);
421  std::optional<ValueLatticeElement>
422  solveBlockValueBinaryOp(BinaryOperator *BBI, BasicBlock *BB);
423  std::optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI,
424  BasicBlock *BB);
425  std::optional<ValueLatticeElement>
426  solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB);
427  std::optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
428  BasicBlock *BB);
429  std::optional<ValueLatticeElement>
430  solveBlockValueExtractValue(ExtractValueInst *EVI, BasicBlock *BB);
431  bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB);
432  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
433  ValueLatticeElement &BBLV,
434  Instruction *BBI);
435 
436  void solve();
437 
438 public:
439  /// This is the query interface to determine the lattice value for the
440  /// specified Value* at the context instruction (if specified) or at the
441  /// start of the block.
442  ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
443  Instruction *CxtI = nullptr);
444 
445  /// This is the query interface to determine the lattice value for the
446  /// specified Value* at the specified instruction using only information
447  /// from assumes/guards and range metadata. Unlike getValueInBlock(), no
448  /// recursive query is performed.
449  ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
450 
451  /// This is the query interface to determine the lattice
452  /// value for the specified Value* that is true on the specified edge.
454  BasicBlock *ToBB,
455  Instruction *CxtI = nullptr);
456 
457  /// Complete flush all previously computed values
458  void clear() {
459  TheCache.clear();
460  }
461 
462  /// Printing the LazyValueInfo Analysis.
463  void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
464  LazyValueInfoAnnotatedWriter Writer(this, DTree);
465  F.print(OS, &Writer);
466  }
467 
468  /// This is part of the update interface to inform the cache
469  /// that a block has been deleted.
470  void eraseBlock(BasicBlock *BB) {
471  TheCache.eraseBlock(BB);
472  }
473 
474  /// This is the update interface to inform the cache that an edge from
475  /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
476  void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
477 
478  LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
479  Function *GuardDecl)
480  : AC(AC), DL(DL), GuardDecl(GuardDecl) {}
481 };
482 } // end anonymous namespace
483 
484 
487  BlockValueStack.begin(), BlockValueStack.end());
488 
489  unsigned processedCount = 0;
490  while (!BlockValueStack.empty()) {
491  processedCount++;
492  // Abort if we have to process too many values to get a result for this one.
493  // Because of the design of the overdefined cache currently being per-block
494  // to avoid naming-related issues (IE it wants to try to give different
495  // results for the same name in different blocks), overdefined results don't
496  // get cached globally, which in turn means we will often try to rediscover
497  // the same overdefined result again and again. Once something like
498  // PredicateInfo is used in LVI or CVP, we should be able to make the
499  // overdefined cache global, and remove this throttle.
500  if (processedCount > MaxProcessedPerValue) {
501  LLVM_DEBUG(
502  dbgs() << "Giving up on stack because we are getting too deep\n");
503  // Fill in the original values
504  while (!StartingStack.empty()) {
505  std::pair<BasicBlock *, Value *> &e = StartingStack.back();
506  TheCache.insertResult(e.second, e.first,
508  StartingStack.pop_back();
509  }
510  BlockValueSet.clear();
511  BlockValueStack.clear();
512  return;
513  }
514  std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
515  assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
516 
517  if (solveBlockValue(e.second, e.first)) {
518  // The work item was completely processed.
519  assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
520 #ifndef NDEBUG
521  std::optional<ValueLatticeElement> BBLV =
522  TheCache.getCachedValueInfo(e.second, e.first);
523  assert(BBLV && "Result should be in cache!");
524  LLVM_DEBUG(
525  dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
526  << *BBLV << "\n");
527 #endif
528 
529  BlockValueStack.pop_back();
530  BlockValueSet.erase(e);
531  } else {
532  // More work needs to be done before revisiting.
533  assert(BlockValueStack.back() != e && "Stack should have been pushed!");
534  }
535  }
536 }
537 
538 std::optional<ValueLatticeElement>
539 LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,
540  Instruction *CxtI) {
541  // If already a constant, there is nothing to compute.
542  if (Constant *VC = dyn_cast<Constant>(Val))
544 
545  if (std::optional<ValueLatticeElement> OptLatticeVal =
546  TheCache.getCachedValueInfo(Val, BB)) {
547  intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
548  return OptLatticeVal;
549  }
550 
551  // We have hit a cycle, assume overdefined.
552  if (!pushBlockValue({ BB, Val }))
554 
555  // Yet to be resolved.
556  return std::nullopt;
557 }
558 
560  switch (BBI->getOpcode()) {
561  default: break;
562  case Instruction::Load:
563  case Instruction::Call:
564  case Instruction::Invoke:
565  if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
566  if (isa<IntegerType>(BBI->getType())) {
569  }
570  break;
571  };
572  // Nothing known - will be intersected with other facts
574 }
575 
576 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
577  assert(!isa<Constant>(Val) && "Value should not be constant");
578  assert(!TheCache.getCachedValueInfo(Val, BB) &&
579  "Value should not be in cache");
580 
581  // Hold off inserting this value into the Cache in case we have to return
582  // false and come back later.
583  std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
584  if (!Res)
585  // Work pushed, will revisit
586  return false;
587 
588  TheCache.insertResult(Val, BB, *Res);
589  return true;
590 }
591 
592 std::optional<ValueLatticeElement>
593 LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) {
594  Instruction *BBI = dyn_cast<Instruction>(Val);
595  if (!BBI || BBI->getParent() != BB)
596  return solveBlockValueNonLocal(Val, BB);
597 
598  if (PHINode *PN = dyn_cast<PHINode>(BBI))
599  return solveBlockValuePHINode(PN, BB);
600 
601  if (auto *SI = dyn_cast<SelectInst>(BBI))
602  return solveBlockValueSelect(SI, BB);
603 
604  // If this value is a nonnull pointer, record it's range and bailout. Note
605  // that for all other pointer typed values, we terminate the search at the
606  // definition. We could easily extend this to look through geps, bitcasts,
607  // and the like to prove non-nullness, but it's not clear that's worth it
608  // compile time wise. The context-insensitive value walk done inside
609  // isKnownNonZero gets most of the profitable cases at much less expense.
610  // This does mean that we have a sensitivity to where the defining
611  // instruction is placed, even if it could legally be hoisted much higher.
612  // That is unfortunate.
613  PointerType *PT = dyn_cast<PointerType>(BBI->getType());
614  if (PT && isKnownNonZero(BBI, DL))
616 
617  if (BBI->getType()->isIntegerTy()) {
618  if (auto *CI = dyn_cast<CastInst>(BBI))
619  return solveBlockValueCast(CI, BB);
620 
621  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
622  return solveBlockValueBinaryOp(BO, BB);
623 
624  if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
625  return solveBlockValueExtractValue(EVI, BB);
626 
627  if (auto *II = dyn_cast<IntrinsicInst>(BBI))
628  return solveBlockValueIntrinsic(II, BB);
629  }
630 
631  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
632  << "' - unknown inst def found.\n");
633  return getFromRangeMetadata(BBI);
634 }
635 
636 static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) {
637  // TODO: Use NullPointerIsDefined instead.
638  if (Ptr->getType()->getPointerAddressSpace() == 0)
639  PtrSet.insert(getUnderlyingObject(Ptr));
640 }
641 
643  Instruction *I, NonNullPointerSet &PtrSet) {
644  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
645  AddNonNullPointer(L->getPointerOperand(), PtrSet);
646  } else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
647  AddNonNullPointer(S->getPointerOperand(), PtrSet);
648  } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
649  if (MI->isVolatile()) return;
650 
651  // FIXME: check whether it has a valuerange that excludes zero?
652  ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
653  if (!Len || Len->isZero()) return;
654 
655  AddNonNullPointer(MI->getRawDest(), PtrSet);
656  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
657  AddNonNullPointer(MTI->getRawSource(), PtrSet);
658  }
659 }
660 
661 bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
662  if (NullPointerIsDefined(BB->getParent(),
663  Val->getType()->getPointerAddressSpace()))
664  return false;
665 
666  Val = Val->stripInBoundsOffsets();
667  return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
668  NonNullPointerSet NonNullPointers;
669  for (Instruction &I : *BB)
670  AddNonNullPointersByInstruction(&I, NonNullPointers);
671  return NonNullPointers;
672  });
673 }
674 
675 std::optional<ValueLatticeElement>
676 LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {
677  ValueLatticeElement Result; // Start Undefined.
678 
679  // If this is the entry block, we must be asking about an argument. The
680  // value is overdefined.
681  if (BB->isEntryBlock()) {
682  assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
684  }
685 
686  // Loop over all of our predecessors, merging what we know from them into
687  // result. If we encounter an unexplored predecessor, we eagerly explore it
688  // in a depth first manner. In practice, this has the effect of discovering
689  // paths we can't analyze eagerly without spending compile times analyzing
690  // other paths. This heuristic benefits from the fact that predecessors are
691  // frequently arranged such that dominating ones come first and we quickly
692  // find a path to function entry. TODO: We should consider explicitly
693  // canonicalizing to make this true rather than relying on this happy
694  // accident.
695  for (BasicBlock *Pred : predecessors(BB)) {
696  std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
697  if (!EdgeResult)
698  // Explore that input, then return here
699  return std::nullopt;
700 
701  Result.mergeIn(*EdgeResult);
702 
703  // If we hit overdefined, exit early. The BlockVals entry is already set
704  // to overdefined.
705  if (Result.isOverdefined()) {
706  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
707  << "' - overdefined because of pred '"
708  << Pred->getName() << "' (non local).\n");
709  return Result;
710  }
711  }
712 
713  // Return the merged value, which is more precise than 'overdefined'.
714  assert(!Result.isOverdefined());
715  return Result;
716 }
717 
718 std::optional<ValueLatticeElement>
719 LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {
720  ValueLatticeElement Result; // Start Undefined.
721 
722  // Loop over all of our predecessors, merging what we know from them into
723  // result. See the comment about the chosen traversal order in
724  // solveBlockValueNonLocal; the same reasoning applies here.
725  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
726  BasicBlock *PhiBB = PN->getIncomingBlock(i);
727  Value *PhiVal = PN->getIncomingValue(i);
728  // Note that we can provide PN as the context value to getEdgeValue, even
729  // though the results will be cached, because PN is the value being used as
730  // the cache key in the caller.
731  std::optional<ValueLatticeElement> EdgeResult =
732  getEdgeValue(PhiVal, PhiBB, BB, PN);
733  if (!EdgeResult)
734  // Explore that input, then return here
735  return std::nullopt;
736 
737  Result.mergeIn(*EdgeResult);
738 
739  // If we hit overdefined, exit early. The BlockVals entry is already set
740  // to overdefined.
741  if (Result.isOverdefined()) {
742  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
743  << "' - overdefined because of pred (local).\n");
744 
745  return Result;
746  }
747  }
748 
749  // Return the merged value, which is more precise than 'overdefined'.
750  assert(!Result.isOverdefined() && "Possible PHI in entry block?");
751  return Result;
752 }
753 
755  bool isTrueDest = true);
756 
757 // If we can determine a constraint on the value given conditions assumed by
758 // the program, intersect those constraints with BBLV
759 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
760  Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
761  BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
762  if (!BBI)
763  return;
764 
765  BasicBlock *BB = BBI->getParent();
766  for (auto &AssumeVH : AC->assumptionsFor(Val)) {
767  if (!AssumeVH)
768  continue;
769 
770  // Only check assumes in the block of the context instruction. Other
771  // assumes will have already been taken into account when the value was
772  // propagated from predecessor blocks.
773  auto *I = cast<CallInst>(AssumeVH);
774  if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
775  continue;
776 
777  BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
778  }
779 
780  // If guards are not used in the module, don't spend time looking for them
781  if (GuardDecl && !GuardDecl->use_empty() &&
782  BBI->getIterator() != BB->begin()) {
783  for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
784  BB->rend())) {
785  Value *Cond = nullptr;
786  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
787  BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
788  }
789  }
790 
791  if (BBLV.isOverdefined()) {
792  // Check whether we're checking at the terminator, and the pointer has
793  // been dereferenced in this block.
794  PointerType *PTy = dyn_cast<PointerType>(Val->getType());
795  if (PTy && BB->getTerminator() == BBI &&
796  isNonNullAtEndOfBlock(Val, BB))
798  }
799 }
800 
802  Type *Ty, const DataLayout &DL) {
803  if (Val.isConstantRange())
804  return Val.getConstantRange();
805  return ConstantRange::getFull(DL.getTypeSizeInBits(Ty));
806 }
807 
808 std::optional<ValueLatticeElement>
809 LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) {
810  // Recurse on our inputs if needed
811  std::optional<ValueLatticeElement> OptTrueVal =
812  getBlockValue(SI->getTrueValue(), BB, SI);
813  if (!OptTrueVal)
814  return std::nullopt;
815  ValueLatticeElement &TrueVal = *OptTrueVal;
816 
817  std::optional<ValueLatticeElement> OptFalseVal =
818  getBlockValue(SI->getFalseValue(), BB, SI);
819  if (!OptFalseVal)
820  return std::nullopt;
821  ValueLatticeElement &FalseVal = *OptFalseVal;
822 
823  if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
824  const ConstantRange &TrueCR =
825  getConstantRangeOrFull(TrueVal, SI->getType(), DL);
826  const ConstantRange &FalseCR =
827  getConstantRangeOrFull(FalseVal, SI->getType(), DL);
828  Value *LHS = nullptr;
829  Value *RHS = nullptr;
831  // Is this a min specifically of our two inputs? (Avoid the risk of
832  // ValueTracking getting smarter looking back past our immediate inputs.)
834  ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
835  (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
836  ConstantRange ResultCR = [&]() {
837  switch (SPR.Flavor) {
838  default:
839  llvm_unreachable("unexpected minmax type!");
840  case SPF_SMIN: /// Signed minimum
841  return TrueCR.smin(FalseCR);
842  case SPF_UMIN: /// Unsigned minimum
843  return TrueCR.umin(FalseCR);
844  case SPF_SMAX: /// Signed maximum
845  return TrueCR.smax(FalseCR);
846  case SPF_UMAX: /// Unsigned maximum
847  return TrueCR.umax(FalseCR);
848  };
849  }();
851  ResultCR, TrueVal.isConstantRangeIncludingUndef() ||
852  FalseVal.isConstantRangeIncludingUndef());
853  }
854 
855  if (SPR.Flavor == SPF_ABS) {
856  if (LHS == SI->getTrueValue())
858  TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
859  if (LHS == SI->getFalseValue())
861  FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
862  }
863 
864  if (SPR.Flavor == SPF_NABS) {
866  if (LHS == SI->getTrueValue())
868  Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
869  if (LHS == SI->getFalseValue())
871  Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
872  }
873  }
874 
875  // Can we constrain the facts about the true and false values by using the
876  // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
877  // TODO: We could potentially refine an overdefined true value above.
878  Value *Cond = SI->getCondition();
880  getValueFromCondition(SI->getTrueValue(), Cond, true));
882  getValueFromCondition(SI->getFalseValue(), Cond, false));
883 
885  Result.mergeIn(FalseVal);
886  return Result;
887 }
888 
889 std::optional<ConstantRange>
890 LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) {
891  std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
892  if (!OptVal)
893  return std::nullopt;
894  return getConstantRangeOrFull(*OptVal, V->getType(), DL);
895 }
896 
897 std::optional<ValueLatticeElement>
898 LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {
899  // Without knowing how wide the input is, we can't analyze it in any useful
900  // way.
901  if (!CI->getOperand(0)->getType()->isSized())
903 
904  // Filter out casts we don't know how to reason about before attempting to
905  // recurse on our operand. This can cut a long search short if we know we're
906  // not going to be able to get any useful information anways.
907  switch (CI->getOpcode()) {
908  case Instruction::Trunc:
909  case Instruction::SExt:
910  case Instruction::ZExt:
911  case Instruction::BitCast:
912  break;
913  default:
914  // Unhandled instructions are overdefined.
915  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
916  << "' - overdefined (unknown cast).\n");
918  }
919 
920  // Figure out the range of the LHS. If that fails, we still apply the
921  // transfer rule on the full set since we may be able to locally infer
922  // interesting facts.
923  std::optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB);
924  if (!LHSRes)
925  // More work to do before applying this transfer rule.
926  return std::nullopt;
927  const ConstantRange &LHSRange = *LHSRes;
928 
929  const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
930 
931  // NOTE: We're currently limited by the set of operations that ConstantRange
932  // can evaluate symbolically. Enhancing that set will allows us to analyze
933  // more definitions.
934  return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
935  ResultBitWidth));
936 }
937 
938 std::optional<ValueLatticeElement>
939 LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
942  OpFn) {
943  // Figure out the ranges of the operands. If that fails, use a
944  // conservative range, but apply the transfer rule anyways. This
945  // lets us pick up facts from expressions like "and i32 (call i32
946  // @foo()), 32"
947  std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB);
948  std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB);
949  if (!LHSRes || !RHSRes)
950  // More work to do before applying this transfer rule.
951  return std::nullopt;
952 
953  const ConstantRange &LHSRange = *LHSRes;
954  const ConstantRange &RHSRange = *RHSRes;
955  return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
956 }
957 
958 std::optional<ValueLatticeElement>
959 LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) {
960  assert(BO->getOperand(0)->getType()->isSized() &&
961  "all operands to binary operators are sized");
962  if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
963  unsigned NoWrapKind = 0;
964  if (OBO->hasNoUnsignedWrap())
966  if (OBO->hasNoSignedWrap())
968 
969  return solveBlockValueBinaryOpImpl(
970  BO, BB,
971  [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
972  return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
973  });
974  }
975 
976  return solveBlockValueBinaryOpImpl(
977  BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
978  return CR1.binaryOp(BO->getOpcode(), CR2);
979  });
980 }
981 
982 std::optional<ValueLatticeElement>
983 LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
984  BasicBlock *BB) {
985  return solveBlockValueBinaryOpImpl(
986  WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
987  return CR1.binaryOp(WO->getBinaryOp(), CR2);
988  });
989 }
990 
991 std::optional<ValueLatticeElement>
992 LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) {
993  ValueLatticeElement MetadataVal = getFromRangeMetadata(II);
995  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
996  << "' - unknown intrinsic.\n");
997  return MetadataVal;
998  }
999 
1001  for (Value *Op : II->args()) {
1002  std::optional<ConstantRange> Range = getRangeFor(Op, II, BB);
1003  if (!Range)
1004  return std::nullopt;
1005  OpRanges.push_back(*Range);
1006  }
1007 
1009  II->getIntrinsicID(), OpRanges)),
1010  MetadataVal);
1011 }
1012 
1013 std::optional<ValueLatticeElement>
1014 LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
1015  BasicBlock *BB) {
1016  if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1017  if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
1018  return solveBlockValueOverflowIntrinsic(WO, BB);
1019 
1020  // Handle extractvalue of insertvalue to allow further simplification
1021  // based on replaced with.overflow intrinsics.
1023  EVI->getAggregateOperand(), EVI->getIndices(),
1024  EVI->getModule()->getDataLayout()))
1025  return getBlockValue(V, BB, EVI);
1026 
1027  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1028  << "' - overdefined (unknown extractvalue).\n");
1030 }
1031 
1033  ICmpInst::Predicate Pred) {
1034  if (LHS == Val)
1035  return true;
1036 
1037  // Handle range checking idiom produced by InstCombine. We will subtract the
1038  // offset from the allowed range for RHS in this case.
1039  const APInt *C;
1040  if (match(LHS, m_Add(m_Specific(Val), m_APInt(C)))) {
1041  Offset = *C;
1042  return true;
1043  }
1044 
1045  // Handle the symmetric case. This appears in saturation patterns like
1046  // (x == 16) ? 16 : (x + 1).
1047  if (match(Val, m_Add(m_Specific(LHS), m_APInt(C)))) {
1048  Offset = -*C;
1049  return true;
1050  }
1051 
1052  // If (x | y) < C, then (x < C) && (y < C).
1053  if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
1054  (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
1055  return true;
1056 
1057  // If (x & y) > C, then (x > C) && (y > C).
1058  if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
1059  (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
1060  return true;
1061 
1062  return false;
1063 }
1064 
1065 /// Get value range for a "(Val + Offset) Pred RHS" condition.
1067  CmpInst::Predicate Pred, Value *RHS, const APInt &Offset) {
1069  /*isFullSet=*/true);
1070  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1071  RHSRange = ConstantRange(CI->getValue());
1072  else if (Instruction *I = dyn_cast<Instruction>(RHS))
1073  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1074  RHSRange = getConstantRangeFromMetadata(*Ranges);
1075 
1076  ConstantRange TrueValues =
1077  ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1078  return ValueLatticeElement::getRange(TrueValues.subtract(Offset));
1079 }
1080 
1082  bool isTrueDest) {
1083  Value *LHS = ICI->getOperand(0);
1084  Value *RHS = ICI->getOperand(1);
1085 
1086  // Get the predicate that must hold along the considered edge.
1087  CmpInst::Predicate EdgePred =
1088  isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
1089 
1090  if (isa<Constant>(RHS)) {
1091  if (ICI->isEquality() && LHS == Val) {
1092  if (EdgePred == ICmpInst::ICMP_EQ)
1093  return ValueLatticeElement::get(cast<Constant>(RHS));
1094  else if (!isa<UndefValue>(RHS))
1095  return ValueLatticeElement::getNot(cast<Constant>(RHS));
1096  }
1097  }
1098 
1099  Type *Ty = Val->getType();
1100  if (!Ty->isIntegerTy())
1102 
1103  unsigned BitWidth = Ty->getScalarSizeInBits();
1104  APInt Offset(BitWidth, 0);
1105  if (matchICmpOperand(Offset, LHS, Val, EdgePred))
1106  return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset);
1107 
1108  CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred);
1109  if (matchICmpOperand(Offset, RHS, Val, SwappedPred))
1110  return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset);
1111 
1112  const APInt *Mask, *C;
1113  if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) &&
1114  match(RHS, m_APInt(C))) {
1115  // If (Val & Mask) == C then all the masked bits are known and we can
1116  // compute a value range based on that.
1117  if (EdgePred == ICmpInst::ICMP_EQ) {
1118  KnownBits Known;
1119  Known.Zero = ~*C & *Mask;
1120  Known.One = *C & *Mask;
1122  ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
1123  }
1124  // If (Val & Mask) != 0 then the value must be larger than the lowest set
1125  // bit of Mask.
1126  if (EdgePred == ICmpInst::ICMP_NE && !Mask->isZero() && C->isZero()) {
1128  APInt::getOneBitSet(BitWidth, Mask->countTrailingZeros()),
1130  }
1131  }
1132 
1133  // If (X urem Modulus) >= C, then X >= C.
1134  // If trunc X >= C, then X >= C.
1135  // TODO: An upper bound could be computed as well.
1136  if (match(LHS, m_CombineOr(m_URem(m_Specific(Val), m_Value()),
1137  m_Trunc(m_Specific(Val)))) &&
1138  match(RHS, m_APInt(C))) {
1139  // Use the icmp region so we don't have to deal with different predicates.
1141  if (!CR.isEmptySet())
1143  CR.getUnsignedMin().zext(BitWidth), APInt(BitWidth, 0)));
1144  }
1145 
1147 }
1148 
1149 // Handle conditions of the form
1150 // extractvalue(op.with.overflow(%x, C), 1).
1152  Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1153  // TODO: This only works with a constant RHS for now. We could also compute
1154  // the range of the RHS, but this doesn't fit into the current structure of
1155  // the edge value calculation.
1156  const APInt *C;
1157  if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
1159 
1160  // Calculate the possible values of %x for which no overflow occurs.
1162  WO->getBinaryOp(), *C, WO->getNoWrapKind());
1163 
1164  // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1165  // constrained to it's inverse (all values that might cause overflow).
1166  if (IsTrueDest)
1167  NWR = NWR.inverse();
1168  return ValueLatticeElement::getRange(NWR);
1169 }
1170 
1171 // Tracks a Value * condition and whether we're interested in it or its inverse
1173 
1174 static std::optional<ValueLatticeElement> getValueFromConditionImpl(
1175  Value *Val, CondValue CondVal, bool isRevisit,
1177  SmallVectorImpl<CondValue> &Worklist) {
1178 
1179  Value *Cond = CondVal.getPointer();
1180  bool isTrueDest = CondVal.getInt();
1181  if (!isRevisit) {
1182  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1183  return getValueFromICmpCondition(Val, ICI, isTrueDest);
1184 
1185  if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
1186  if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1187  if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1188  return getValueFromOverflowCondition(Val, WO, isTrueDest);
1189  }
1190 
1191  Value *N;
1192  if (match(Cond, m_Not(m_Value(N)))) {
1193  CondValue NKey(N, !isTrueDest);
1194  auto NV = Visited.find(NKey);
1195  if (NV == Visited.end()) {
1196  Worklist.push_back(NKey);
1197  return std::nullopt;
1198  }
1199  return NV->second;
1200  }
1201 
1202  Value *L, *R;
1203  bool IsAnd;
1204  if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))))
1205  IsAnd = true;
1206  else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
1207  IsAnd = false;
1208  else
1210 
1211  auto LV = Visited.find(CondValue(L, isTrueDest));
1212  auto RV = Visited.find(CondValue(R, isTrueDest));
1213 
1214  // if (L && R) -> intersect L and R
1215  // if (!(L || R)) -> intersect !L and !R
1216  // if (L || R) -> union L and R
1217  // if (!(L && R)) -> union !L and !R
1218  if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) {
1219  ValueLatticeElement V = LV->second;
1220  if (V.isOverdefined())
1221  return V;
1222  if (RV != Visited.end()) {
1223  V.mergeIn(RV->second);
1224  return V;
1225  }
1226  }
1227 
1228  if (LV == Visited.end() || RV == Visited.end()) {
1229  assert(!isRevisit);
1230  if (LV == Visited.end())
1231  Worklist.push_back(CondValue(L, isTrueDest));
1232  if (RV == Visited.end())
1233  Worklist.push_back(CondValue(R, isTrueDest));
1234  return std::nullopt;
1235  }
1236 
1237  return intersect(LV->second, RV->second);
1238 }
1239 
1241  bool isTrueDest) {
1242  assert(Cond && "precondition");
1244  SmallVector<CondValue> Worklist;
1245 
1246  CondValue CondKey(Cond, isTrueDest);
1247  Worklist.push_back(CondKey);
1248  do {
1249  CondValue CurrentCond = Worklist.back();
1250  // Insert an Overdefined placeholder into the set to prevent
1251  // infinite recursion if there exists IRs that use not
1252  // dominated by its def as in this example:
1253  // "%tmp3 = or i1 undef, %tmp4"
1254  // "%tmp4 = or i1 undef, %tmp3"
1255  auto Iter =
1256  Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined());
1257  bool isRevisit = !Iter.second;
1258  std::optional<ValueLatticeElement> Result = getValueFromConditionImpl(
1259  Val, CurrentCond, isRevisit, Visited, Worklist);
1260  if (Result) {
1261  Visited[CurrentCond] = *Result;
1262  Worklist.pop_back();
1263  }
1264  } while (!Worklist.empty());
1265 
1266  auto Result = Visited.find(CondKey);
1267  assert(Result != Visited.end());
1268  return Result->second;
1269 }
1270 
1271 // Return true if Usr has Op as an operand, otherwise false.
1272 static bool usesOperand(User *Usr, Value *Op) {
1273  return is_contained(Usr->operands(), Op);
1274 }
1275 
1276 // Return true if the instruction type of Val is supported by
1277 // constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
1278 // Call this before calling constantFoldUser() to find out if it's even worth
1279 // attempting to call it.
1280 static bool isOperationFoldable(User *Usr) {
1281  return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1282 }
1283 
1284 // Check if Usr can be simplified to an integer constant when the value of one
1285 // of its operands Op is an integer constant OpConstVal. If so, return it as an
1286 // lattice value range with a single element or otherwise return an overdefined
1287 // lattice value.
1289  const APInt &OpConstVal,
1290  const DataLayout &DL) {
1291  assert(isOperationFoldable(Usr) && "Precondition");
1292  Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1293  // Check if Usr can be simplified to a constant.
1294  if (auto *CI = dyn_cast<CastInst>(Usr)) {
1295  assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1296  if (auto *C = dyn_cast_or_null<ConstantInt>(
1297  simplifyCastInst(CI->getOpcode(), OpConst,
1298  CI->getDestTy(), DL))) {
1299  return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1300  }
1301  } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1302  bool Op0Match = BO->getOperand(0) == Op;
1303  bool Op1Match = BO->getOperand(1) == Op;
1304  assert((Op0Match || Op1Match) &&
1305  "Operand 0 nor Operand 1 isn't a match");
1306  Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1307  Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1308  if (auto *C = dyn_cast_or_null<ConstantInt>(
1309  simplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1310  return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1311  }
1312  } else if (isa<FreezeInst>(Usr)) {
1313  assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
1314  return ValueLatticeElement::getRange(ConstantRange(OpConstVal));
1315  }
1317 }
1318 
1319 /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1320 /// Val is not constrained on the edge. Result is unspecified if return value
1321 /// is false.
1322 static std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
1323  BasicBlock *BBFrom,
1324  BasicBlock *BBTo) {
1325  // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1326  // know that v != 0.
1327  if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1328  // If this is a conditional branch and only one successor goes to BBTo, then
1329  // we may be able to infer something from the condition.
1330  if (BI->isConditional() &&
1331  BI->getSuccessor(0) != BI->getSuccessor(1)) {
1332  bool isTrueDest = BI->getSuccessor(0) == BBTo;
1333  assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1334  "BBTo isn't a successor of BBFrom");
1335  Value *Condition = BI->getCondition();
1336 
1337  // If V is the condition of the branch itself, then we know exactly what
1338  // it is.
1339  if (Condition == Val)
1341  Type::getInt1Ty(Val->getContext()), isTrueDest));
1342 
1343  // If the condition of the branch is an equality comparison, we may be
1344  // able to infer the value.
1345  ValueLatticeElement Result = getValueFromCondition(Val, Condition,
1346  isTrueDest);
1347  if (!Result.isOverdefined())
1348  return Result;
1349 
1350  if (User *Usr = dyn_cast<User>(Val)) {
1351  assert(Result.isOverdefined() && "Result isn't overdefined");
1352  // Check with isOperationFoldable() first to avoid linearly iterating
1353  // over the operands unnecessarily which can be expensive for
1354  // instructions with many operands.
1355  if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1356  const DataLayout &DL = BBTo->getModule()->getDataLayout();
1357  if (usesOperand(Usr, Condition)) {
1358  // If Val has Condition as an operand and Val can be folded into a
1359  // constant with either Condition == true or Condition == false,
1360  // propagate the constant.
1361  // eg.
1362  // ; %Val is true on the edge to %then.
1363  // %Val = and i1 %Condition, true.
1364  // br %Condition, label %then, label %else
1365  APInt ConditionVal(1, isTrueDest ? 1 : 0);
1366  Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1367  } else {
1368  // If one of Val's operand has an inferred value, we may be able to
1369  // infer the value of Val.
1370  // eg.
1371  // ; %Val is 94 on the edge to %then.
1372  // %Val = add i8 %Op, 1
1373  // %Condition = icmp eq i8 %Op, 93
1374  // br i1 %Condition, label %then, label %else
1375  for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1376  Value *Op = Usr->getOperand(i);
1377  ValueLatticeElement OpLatticeVal =
1378  getValueFromCondition(Op, Condition, isTrueDest);
1379  if (std::optional<APInt> OpConst =
1380  OpLatticeVal.asConstantInteger()) {
1381  Result = constantFoldUser(Usr, Op, *OpConst, DL);
1382  break;
1383  }
1384  }
1385  }
1386  }
1387  }
1388  if (!Result.isOverdefined())
1389  return Result;
1390  }
1391  }
1392 
1393  // If the edge was formed by a switch on the value, then we may know exactly
1394  // what it is.
1395  if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1396  Value *Condition = SI->getCondition();
1397  if (!isa<IntegerType>(Val->getType()))
1398  return std::nullopt;
1399  bool ValUsesConditionAndMayBeFoldable = false;
1400  if (Condition != Val) {
1401  // Check if Val has Condition as an operand.
1402  if (User *Usr = dyn_cast<User>(Val))
1403  ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1404  usesOperand(Usr, Condition);
1405  if (!ValUsesConditionAndMayBeFoldable)
1406  return std::nullopt;
1407  }
1408  assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1409  "Condition != Val nor Val doesn't use Condition");
1410 
1411  bool DefaultCase = SI->getDefaultDest() == BBTo;
1412  unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1413  ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1414 
1415  for (auto Case : SI->cases()) {
1416  APInt CaseValue = Case.getCaseValue()->getValue();
1417  ConstantRange EdgeVal(CaseValue);
1418  if (ValUsesConditionAndMayBeFoldable) {
1419  User *Usr = cast<User>(Val);
1420  const DataLayout &DL = BBTo->getModule()->getDataLayout();
1421  ValueLatticeElement EdgeLatticeVal =
1422  constantFoldUser(Usr, Condition, CaseValue, DL);
1423  if (EdgeLatticeVal.isOverdefined())
1424  return std::nullopt;
1425  EdgeVal = EdgeLatticeVal.getConstantRange();
1426  }
1427  if (DefaultCase) {
1428  // It is possible that the default destination is the destination of
1429  // some cases. We cannot perform difference for those cases.
1430  // We know Condition != CaseValue in BBTo. In some cases we can use
1431  // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1432  // only do this when f is identity (i.e. Val == Condition), but we
1433  // should be able to do this for any injective f.
1434  if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1435  EdgesVals = EdgesVals.difference(EdgeVal);
1436  } else if (Case.getCaseSuccessor() == BBTo)
1437  EdgesVals = EdgesVals.unionWith(EdgeVal);
1438  }
1439  return ValueLatticeElement::getRange(std::move(EdgesVals));
1440  }
1441  return std::nullopt;
1442 }
1443 
1444 /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1445 /// the basic block if the edge does not constrain Val.
1446 std::optional<ValueLatticeElement>
1447 LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1448  BasicBlock *BBTo, Instruction *CxtI) {
1449  // If already a constant, there is nothing to compute.
1450  if (Constant *VC = dyn_cast<Constant>(Val))
1451  return ValueLatticeElement::get(VC);
1452 
1453  ValueLatticeElement LocalResult =
1454  getEdgeValueLocal(Val, BBFrom, BBTo)
1456  if (hasSingleValue(LocalResult))
1457  // Can't get any more precise here
1458  return LocalResult;
1459 
1460  std::optional<ValueLatticeElement> OptInBlock =
1461  getBlockValue(Val, BBFrom, BBFrom->getTerminator());
1462  if (!OptInBlock)
1463  return std::nullopt;
1464  ValueLatticeElement &InBlock = *OptInBlock;
1465 
1466  // We can use the context instruction (generically the ultimate instruction
1467  // the calling pass is trying to simplify) here, even though the result of
1468  // this function is generally cached when called from the solve* functions
1469  // (and that cached result might be used with queries using a different
1470  // context instruction), because when this function is called from the solve*
1471  // functions, the context instruction is not provided. When called from
1472  // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1473  // but then the result is not cached.
1474  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1475 
1476  return intersect(LocalResult, InBlock);
1477 }
1478 
1479 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1480  Instruction *CxtI) {
1481  LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1482  << BB->getName() << "'\n");
1483 
1484  assert(BlockValueStack.empty() && BlockValueSet.empty());
1485  std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
1486  if (!OptResult) {
1487  solve();
1488  OptResult = getBlockValue(V, BB, CxtI);
1489  assert(OptResult && "Value not available after solving");
1490  }
1491 
1492  ValueLatticeElement Result = *OptResult;
1493  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1494  return Result;
1495 }
1496 
1497 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1498  LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1499  << "'\n");
1500 
1501  if (auto *C = dyn_cast<Constant>(V))
1502  return ValueLatticeElement::get(C);
1503 
1505  if (auto *I = dyn_cast<Instruction>(V))
1507  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1508 
1509  LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1510  return Result;
1511 }
1512 
1514 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1515  Instruction *CxtI) {
1516  LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1517  << FromBB->getName() << "' to '" << ToBB->getName()
1518  << "'\n");
1519 
1520  std::optional<ValueLatticeElement> Result =
1521  getEdgeValue(V, FromBB, ToBB, CxtI);
1522  if (!Result) {
1523  solve();
1524  Result = getEdgeValue(V, FromBB, ToBB, CxtI);
1525  assert(Result && "More work to do after problem solved?");
1526  }
1527 
1528  LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");
1529  return *Result;
1530 }
1531 
1532 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1533  BasicBlock *NewSucc) {
1534  TheCache.threadEdgeImpl(OldSucc, NewSucc);
1535 }
1536 
1537 //===----------------------------------------------------------------------===//
1538 // LazyValueInfo Impl
1539 //===----------------------------------------------------------------------===//
1540 
1541 /// This lazily constructs the LazyValueInfoImpl.
1542 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1543  const Module *M) {
1544  if (!PImpl) {
1545  assert(M && "getCache() called with a null Module");
1546  const DataLayout &DL = M->getDataLayout();
1547  Function *GuardDecl = M->getFunction(
1548  Intrinsic::getName(Intrinsic::experimental_guard));
1549  PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl);
1550  }
1551  return *static_cast<LazyValueInfoImpl*>(PImpl);
1552 }
1553 
1555  Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1556  Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1557 
1558  if (Info.PImpl)
1559  getImpl(Info.PImpl, Info.AC, F.getParent()).clear();
1560 
1561  // Fully lazy.
1562  return false;
1563 }
1564 
1566  AU.setPreservesAll();
1569 }
1570 
1572 
1574 
1576  // If the cache was allocated, free it.
1577  if (PImpl) {
1578  delete &getImpl(PImpl, AC, nullptr);
1579  PImpl = nullptr;
1580  }
1581 }
1582 
1585  // We need to invalidate if we have either failed to preserve this analyses
1586  // result directly or if any of its dependencies have been invalidated.
1587  auto PAC = PA.getChecker<LazyValueAnalysis>();
1588  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
1589  return true;
1590 
1591  return false;
1592 }
1593 
1595 
1598  auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1599  auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1600 
1601  return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI);
1602 }
1603 
1604 /// Returns true if we can statically tell that this value will never be a
1605 /// "useful" constant. In practice, this means we've got something like an
1606 /// alloca or a malloc call for which a comparison against a constant can
1607 /// only be guarding dead code. Note that we are potentially giving up some
1608 /// precision in dead code (a constant result) in favour of avoiding a
1609 /// expensive search for a easily answered common query.
1610 static bool isKnownNonConstant(Value *V) {
1611  V = V->stripPointerCasts();
1612  // The return val of alloc cannot be a Constant.
1613  if (isa<AllocaInst>(V))
1614  return true;
1615  return false;
1616 }
1617 
1619  // Bail out early if V is known not to be a Constant.
1620  if (isKnownNonConstant(V))
1621  return nullptr;
1622 
1623  BasicBlock *BB = CxtI->getParent();
1624  ValueLatticeElement Result =
1625  getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI);
1626 
1627  if (Result.isConstant())
1628  return Result.getConstant();
1629  if (Result.isConstantRange()) {
1630  const ConstantRange &CR = Result.getConstantRange();
1631  if (const APInt *SingleVal = CR.getSingleElement())
1632  return ConstantInt::get(V->getContext(), *SingleVal);
1633  }
1634  return nullptr;
1635 }
1636 
1638  bool UndefAllowed) {
1639  assert(V->getType()->isIntegerTy());
1640  unsigned Width = V->getType()->getIntegerBitWidth();
1641  BasicBlock *BB = CxtI->getParent();
1642  ValueLatticeElement Result =
1643  getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI);
1644  if (Result.isUnknown())
1645  return ConstantRange::getEmpty(Width);
1646  if (Result.isConstantRange(UndefAllowed))
1647  return Result.getConstantRange(UndefAllowed);
1648  // We represent ConstantInt constants as constant ranges but other kinds
1649  // of integer constants, i.e. ConstantExpr will be tagged as constants
1650  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1651  "ConstantInt value must be represented as constantrange");
1652  return ConstantRange::getFull(Width);
1653 }
1654 
1656  bool UndefAllowed) {
1657  Value *V = U.get();
1658  ConstantRange CR =
1659  getConstantRange(V, cast<Instruction>(U.getUser()), UndefAllowed);
1660 
1661  // Check whether the only (possibly transitive) use of the value is in a
1662  // position where V can be constrained by a select or branch condition.
1663  const Use *CurrU = &U;
1664  // TODO: Increase limit?
1665  const unsigned MaxUsesToInspect = 3;
1666  for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
1667  std::optional<ValueLatticeElement> CondVal;
1668  auto *CurrI = cast<Instruction>(CurrU->getUser());
1669  if (auto *SI = dyn_cast<SelectInst>(CurrI)) {
1670  if (CurrU->getOperandNo() == 1)
1671  CondVal = getValueFromCondition(V, SI->getCondition(), true);
1672  else if (CurrU->getOperandNo() == 2)
1673  CondVal = getValueFromCondition(V, SI->getCondition(), false);
1674  } else if (auto *PHI = dyn_cast<PHINode>(CurrI)) {
1675  // TODO: Use non-local query?
1676  CondVal =
1677  getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU), PHI->getParent());
1678  } else if (!isSafeToSpeculativelyExecute(CurrI)) {
1679  // Stop walking if we hit a non-speculatable instruction. Even if the
1680  // result is only used under a specific condition, executing the
1681  // instruction itself may cause side effects or UB already.
1682  break;
1683  }
1684  if (CondVal && CondVal->isConstantRange())
1685  CR = CR.intersectWith(CondVal->getConstantRange());
1686 
1687  // Only follow one-use chain, to allow direct intersection of conditions.
1688  // If there are multiple uses, we would have to intersect with the union of
1689  // all conditions at different uses.
1690  if (!CurrI->hasOneUse())
1691  break;
1692  CurrU = &*CurrI->use_begin();
1693  }
1694  return CR;
1695 }
1696 
1697 /// Determine whether the specified value is known to be a
1698 /// constant on the specified edge. Return null if not.
1700  BasicBlock *ToBB,
1701  Instruction *CxtI) {
1702  Module *M = FromBB->getModule();
1703  ValueLatticeElement Result =
1704  getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1705 
1706  if (Result.isConstant())
1707  return Result.getConstant();
1708  if (Result.isConstantRange()) {
1709  const ConstantRange &CR = Result.getConstantRange();
1710  if (const APInt *SingleVal = CR.getSingleElement())
1711  return ConstantInt::get(V->getContext(), *SingleVal);
1712  }
1713  return nullptr;
1714 }
1715 
1717  BasicBlock *FromBB,
1718  BasicBlock *ToBB,
1719  Instruction *CxtI) {
1720  unsigned Width = V->getType()->getIntegerBitWidth();
1721  Module *M = FromBB->getModule();
1722  ValueLatticeElement Result =
1723  getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1724 
1725  if (Result.isUnknown())
1726  return ConstantRange::getEmpty(Width);
1727  if (Result.isConstantRange())
1728  return Result.getConstantRange();
1729  // We represent ConstantInt constants as constant ranges but other kinds
1730  // of integer constants, i.e. ConstantExpr will be tagged as constants
1731  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1732  "ConstantInt value must be represented as constantrange");
1733  return ConstantRange::getFull(Width);
1734 }
1735 
1737 getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1738  const DataLayout &DL, TargetLibraryInfo *TLI) {
1739  // If we know the value is a constant, evaluate the conditional.
1740  Constant *Res = nullptr;
1741  if (Val.isConstant()) {
1742  Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1743  if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1744  return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1745  return LazyValueInfo::Unknown;
1746  }
1747 
1748  if (Val.isConstantRange()) {
1749  ConstantInt *CI = dyn_cast<ConstantInt>(C);
1750  if (!CI) return LazyValueInfo::Unknown;
1751 
1752  const ConstantRange &CR = Val.getConstantRange();
1753  if (Pred == ICmpInst::ICMP_EQ) {
1754  if (!CR.contains(CI->getValue()))
1755  return LazyValueInfo::False;
1756 
1757  if (CR.isSingleElement())
1758  return LazyValueInfo::True;
1759  } else if (Pred == ICmpInst::ICMP_NE) {
1760  if (!CR.contains(CI->getValue()))
1761  return LazyValueInfo::True;
1762 
1763  if (CR.isSingleElement())
1764  return LazyValueInfo::False;
1765  } else {
1766  // Handle more complex predicates.
1768  (ICmpInst::Predicate)Pred, CI->getValue());
1769  if (TrueValues.contains(CR))
1770  return LazyValueInfo::True;
1771  if (TrueValues.inverse().contains(CR))
1772  return LazyValueInfo::False;
1773  }
1774  return LazyValueInfo::Unknown;
1775  }
1776 
1777  if (Val.isNotConstant()) {
1778  // If this is an equality comparison, we can try to fold it knowing that
1779  // "V != C1".
1780  if (Pred == ICmpInst::ICMP_EQ) {
1781  // !C1 == C -> false iff C1 == C.
1783  Val.getNotConstant(), C, DL,
1784  TLI);
1785  if (Res->isNullValue())
1786  return LazyValueInfo::False;
1787  } else if (Pred == ICmpInst::ICMP_NE) {
1788  // !C1 != C -> true iff C1 == C.
1790  Val.getNotConstant(), C, DL,
1791  TLI);
1792  if (Res->isNullValue())
1793  return LazyValueInfo::True;
1794  }
1795  return LazyValueInfo::Unknown;
1796  }
1797 
1798  return LazyValueInfo::Unknown;
1799 }
1800 
1801 /// Determine whether the specified value comparison with a constant is known to
1802 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1805  BasicBlock *FromBB, BasicBlock *ToBB,
1806  Instruction *CxtI) {
1807  Module *M = FromBB->getModule();
1808  ValueLatticeElement Result =
1809  getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1810 
1811  return getPredicateResult(Pred, C, Result, M->getDataLayout(), TLI);
1812 }
1813 
1816  Instruction *CxtI, bool UseBlockValue) {
1817  // Is or is not NonNull are common predicates being queried. If
1818  // isKnownNonZero can tell us the result of the predicate, we can
1819  // return it quickly. But this is only a fastpath, and falling
1820  // through would still be correct.
1821  Module *M = CxtI->getModule();
1822  const DataLayout &DL = M->getDataLayout();
1823  if (V->getType()->isPointerTy() && C->isNullValue() &&
1825  if (Pred == ICmpInst::ICMP_EQ)
1826  return LazyValueInfo::False;
1827  else if (Pred == ICmpInst::ICMP_NE)
1828  return LazyValueInfo::True;
1829  }
1830 
1831  ValueLatticeElement Result = UseBlockValue
1832  ? getImpl(PImpl, AC, M).getValueInBlock(V, CxtI->getParent(), CxtI)
1833  : getImpl(PImpl, AC, M).getValueAt(V, CxtI);
1834  Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1835  if (Ret != Unknown)
1836  return Ret;
1837 
1838  // Note: The following bit of code is somewhat distinct from the rest of LVI;
1839  // LVI as a whole tries to compute a lattice value which is conservatively
1840  // correct at a given location. In this case, we have a predicate which we
1841  // weren't able to prove about the merged result, and we're pushing that
1842  // predicate back along each incoming edge to see if we can prove it
1843  // separately for each input. As a motivating example, consider:
1844  // bb1:
1845  // %v1 = ... ; constantrange<1, 5>
1846  // br label %merge
1847  // bb2:
1848  // %v2 = ... ; constantrange<10, 20>
1849  // br label %merge
1850  // merge:
1851  // %phi = phi [%v1, %v2] ; constantrange<1,20>
1852  // %pred = icmp eq i32 %phi, 8
1853  // We can't tell from the lattice value for '%phi' that '%pred' is false
1854  // along each path, but by checking the predicate over each input separately,
1855  // we can.
1856  // We limit the search to one step backwards from the current BB and value.
1857  // We could consider extending this to search further backwards through the
1858  // CFG and/or value graph, but there are non-obvious compile time vs quality
1859  // tradeoffs.
1860  BasicBlock *BB = CxtI->getParent();
1861 
1862  // Function entry or an unreachable block. Bail to avoid confusing
1863  // analysis below.
1864  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1865  if (PI == PE)
1866  return Unknown;
1867 
1868  // If V is a PHI node in the same block as the context, we need to ask
1869  // questions about the predicate as applied to the incoming value along
1870  // each edge. This is useful for eliminating cases where the predicate is
1871  // known along all incoming edges.
1872  if (auto *PHI = dyn_cast<PHINode>(V))
1873  if (PHI->getParent() == BB) {
1874  Tristate Baseline = Unknown;
1875  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1876  Value *Incoming = PHI->getIncomingValue(i);
1877  BasicBlock *PredBB = PHI->getIncomingBlock(i);
1878  // Note that PredBB may be BB itself.
1879  Tristate Result =
1880  getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI);
1881 
1882  // Keep going as long as we've seen a consistent known result for
1883  // all inputs.
1884  Baseline = (i == 0) ? Result /* First iteration */
1885  : (Baseline == Result ? Baseline
1886  : Unknown); /* All others */
1887  if (Baseline == Unknown)
1888  break;
1889  }
1890  if (Baseline != Unknown)
1891  return Baseline;
1892  }
1893 
1894  // For a comparison where the V is outside this block, it's possible
1895  // that we've branched on it before. Look to see if the value is known
1896  // on all incoming edges.
1897  if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
1898  // For predecessor edge, determine if the comparison is true or false
1899  // on that edge. If they're all true or all false, we can conclude
1900  // the value of the comparison in this block.
1901  Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1902  if (Baseline != Unknown) {
1903  // Check that all remaining incoming values match the first one.
1904  while (++PI != PE) {
1905  Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1906  if (Ret != Baseline)
1907  break;
1908  }
1909  // If we terminated early, then one of the values didn't match.
1910  if (PI == PE) {
1911  return Baseline;
1912  }
1913  }
1914  }
1915 
1916  return Unknown;
1917 }
1918 
1920  Value *RHS,
1921  Instruction *CxtI,
1922  bool UseBlockValue) {
1924 
1925  if (auto *C = dyn_cast<Constant>(RHS))
1926  return getPredicateAt(P, LHS, C, CxtI, UseBlockValue);
1927  if (auto *C = dyn_cast<Constant>(LHS))
1928  return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI,
1929  UseBlockValue);
1930 
1931  // Got two non-Constant values. Try to determine the comparison results based
1932  // on the block values of the two operands, e.g. because they have
1933  // non-overlapping ranges.
1934  if (UseBlockValue) {
1935  Module *M = CxtI->getModule();
1937  getImpl(PImpl, AC, M).getValueInBlock(LHS, CxtI->getParent(), CxtI);
1938  if (L.isOverdefined())
1939  return LazyValueInfo::Unknown;
1940 
1942  getImpl(PImpl, AC, M).getValueInBlock(RHS, CxtI->getParent(), CxtI);
1944  if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R,
1945  M->getDataLayout())) {
1946  if (Res->isNullValue())
1947  return LazyValueInfo::False;
1948  if (Res->isOneValue())
1949  return LazyValueInfo::True;
1950  }
1951  }
1952  return LazyValueInfo::Unknown;
1953 }
1954 
1956  BasicBlock *NewSucc) {
1957  if (PImpl) {
1958  getImpl(PImpl, AC, PredBB->getModule())
1959  .threadEdge(PredBB, OldSucc, NewSucc);
1960  }
1961 }
1962 
1964  if (PImpl) {
1965  getImpl(PImpl, AC, BB->getModule()).eraseBlock(BB);
1966  }
1967 }
1968 
1970  if (PImpl) {
1971  getImpl(PImpl, AC, M).clear();
1972  }
1973 }
1974 
1976  if (PImpl) {
1977  getImpl(PImpl, AC, F.getParent()).printLVI(F, DTree, OS);
1978  }
1979 }
1980 
1981 // Print the LVI for the function arguments at the start of each basic block.
1982 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1983  const BasicBlock *BB, formatted_raw_ostream &OS) {
1984  // Find if there are latticevalues defined for arguments of the function.
1985  auto *F = BB->getParent();
1986  for (const auto &Arg : F->args()) {
1987  ValueLatticeElement Result = LVIImpl->getValueInBlock(
1988  const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1989  if (Result.isUnknown())
1990  continue;
1991  OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1992  }
1993 }
1994 
1995 // This function prints the LVI analysis for the instruction I at the beginning
1996 // of various basic blocks. It relies on calculated values that are stored in
1997 // the LazyValueInfoCache, and in the absence of cached values, recalculate the
1998 // LazyValueInfo for `I`, and print that info.
1999 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2000  const Instruction *I, formatted_raw_ostream &OS) {
2001 
2002  auto *ParentBB = I->getParent();
2003  SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
2004  // We can generate (solve) LVI values only for blocks that are dominated by
2005  // the I's parent. However, to avoid generating LVI for all dominating blocks,
2006  // that contain redundant/uninteresting information, we print LVI for
2007  // blocks that may use this LVI information (such as immediate successor
2008  // blocks, and blocks that contain uses of `I`).
2009  auto printResult = [&](const BasicBlock *BB) {
2010  if (!BlocksContainingLVI.insert(BB).second)
2011  return;
2012  ValueLatticeElement Result = LVIImpl->getValueInBlock(
2013  const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
2014  OS << "; LatticeVal for: '" << *I << "' in BB: '";
2015  BB->printAsOperand(OS, false);
2016  OS << "' is: " << Result << "\n";
2017  };
2018 
2019  printResult(ParentBB);
2020  // Print the LVI analysis results for the immediate successor blocks, that
2021  // are dominated by `ParentBB`.
2022  for (const auto *BBSucc : successors(ParentBB))
2023  if (DT.dominates(ParentBB, BBSucc))
2024  printResult(BBSucc);
2025 
2026  // Print LVI in blocks where `I` is used.
2027  for (const auto *U : I->users())
2028  if (auto *UseI = dyn_cast<Instruction>(U))
2029  if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
2030  printResult(UseI->getParent());
2031 
2032 }
2033 
2034 namespace {
2035 // Printer class for LazyValueInfo results.
2036 class LazyValueInfoPrinter : public FunctionPass {
2037 public:
2038  static char ID; // Pass identification, replacement for typeid
2039  LazyValueInfoPrinter() : FunctionPass(ID) {
2041  }
2042 
2043  void getAnalysisUsage(AnalysisUsage &AU) const override {
2044  AU.setPreservesAll();
2047  }
2048 
2049  // Get the mandatory dominator tree analysis and pass this in to the
2050  // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
2051  bool runOnFunction(Function &F) override {
2052  dbgs() << "LVI for function '" << F.getName() << "':\n";
2053  auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
2054  auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2055  LVI.printLVI(F, DTree, dbgs());
2056  return false;
2057  }
2058 };
2059 }
2060 
2061 char LazyValueInfoPrinter::ID = 0;
2062 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
2063  "Lazy Value Info Printer Pass", false, false)
2065 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:1699
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
getEdgeValueLocal
static std::optional< ValueLatticeElement > getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo)
Compute the value of Val on the edge BBFrom -> BBTo.
Definition: LazyValueInfo.cpp:1322
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:752
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:295
llvm::SPF_SMAX
@ SPF_SMAX
Unsigned minimum.
Definition: ValueTracking.h:694
llvm::LazyValueInfo::~LazyValueInfo
~LazyValueInfo()
Definition: LazyValueInfo.cpp:1573
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:109
getValueFromCondition
static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest=true)
Definition: LazyValueInfo.cpp:1240
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:859
llvm::ValueLatticeElement::isConstant
bool isConstant() const
Definition: ValueLattice.h:243
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:238
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:70
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
isOperationFoldable
static bool isOperationFoldable(User *Usr)
Definition: LazyValueInfo.cpp:1280
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
llvm::User::operands
op_range operands()
Definition: User.h:242
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:249
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:1610
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:774
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:1804
getValueFromICmpCondition
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest)
Definition: LazyValueInfo.cpp:1081
T
llvm::MemTransferInst
This class wraps the llvm.memcpy/memmove intrinsics.
Definition: IntrinsicInst.h:1113
llvm::ValueLatticeElement::getConstant
Constant * getConstant() const
Definition: ValueLattice.h:258
llvm::Function
Definition: Function.h:59
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) INITIALIZE_PASS_END(LazyValueInfoWrapperPass
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:54
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:714
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:132
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:757
llvm::successors
auto successors(const MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::LazyValueAnalysis
Analysis to compute lazy value information.
Definition: LazyValueInfo.h:138
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
getImpl
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const Module *M)
This lazily constructs the LazyValueInfoImpl.
Definition: LazyValueInfo.cpp:1542
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:1716
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:756
llvm::ValueLatticeElement::getNotConstant
Constant * getNotConstant() const
Definition: ValueLattice.h:263
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1054
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:218
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:975
llvm::Use::get
Value * get() const
Definition: Use.h:66
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:880
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:832
CondValue
PointerIntPair< Value *, 1, bool > CondValue
Definition: LazyValueInfo.cpp:1172
ValueTracking.h
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:313
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:1618
Information
Natural Loop Information
Definition: LoopInfo.cpp:1177
AddNonNullPointersByInstruction
static void AddNonNullPointersByInstruction(Instruction *I, NonNullPointerSet &PtrSet)
Definition: LazyValueInfo.cpp:642
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:695
getFromRangeMetadata
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)
Definition: LazyValueInfo.cpp:559
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:1048
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
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:6539
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:2262
llvm::getConstantRangeFromMetadata
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Definition: ConstantRange.cpp:1797
llvm::ValueLatticeElement::getCompare
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
Definition: ValueLattice.cpp:14
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:97
llvm::ConstantRange::isIntrinsicSupported
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
Definition: ConstantRange.cpp:937
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:682
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LazyValueAnalysis::run
Result run(Function &F, FunctionAnalysisManager &FAM)
Definition: LazyValueInfo.cpp:1596
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:875
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:4966
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
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
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:278
llvm::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:699
FormattedStream.h
usesOperand
static bool usesOperand(User *Usr, Value *Op)
Definition: LazyValueInfo.cpp:1272
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
getConstantRangeOrFull
static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val, Type *Ty, const DataLayout &DL)
Definition: LazyValueInfo.cpp:801
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
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:534
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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:2794
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:428
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:744
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:722
llvm::KnownBits::One
APInt One
Definition: KnownBits.h:25
llvm::LazyValueInfoWrapperPass::ID
static char ID
Definition: LazyValueInfo.h:153
llvm::ExtractValueInst::getNumIndices
unsigned getNumIndices() const
Definition: Instructions.h:2524
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:261
SI
@ SI
Definition: SIInstrInfo.cpp:7993
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:1628
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
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:5797
getPredicateResult
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL, TargetLibraryInfo *TLI)
Definition: LazyValueInfo.cpp:1737
TargetLibraryInfo.h
llvm::BinaryOpIntrinsic::getNoWrapKind
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Definition: IntrinsicInst.cpp:785
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:391
llvm::Instruction
Definition: Instruction.h:41
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:188
matchICmpOperand
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
Definition: LazyValueInfo.cpp:1032
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:2269
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
llvm::LazyValueInfo::printLVI
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Print the \LazyValueInfo Analysis.
Definition: LazyValueInfo.cpp:1975
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:626
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
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:887
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
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:4570
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:146
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:1565
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::PatternMatch::m_URem
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1075
PatternMatch.h
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:156
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2790
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:692
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:1554
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:275
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
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:954
llvm::predecessors
auto predecessors(const MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
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:920
AssemblyAnnotationWriter.h
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:222
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:693
llvm::SelectPatternResult
Definition: ValueTracking.h:713
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:60
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:717
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:1583
InBlock
static bool InBlock(const Value *V, const BasicBlock *BB)
Definition: SelectionDAGBuilder.cpp:2200
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:301
llvm::ConstantRange::inverse
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
Definition: ConstantRange.cpp:1620
llvm::OverflowingBinaryOperator::NoUnsignedWrap
@ NoUnsignedWrap
Definition: Operator.h:79
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:110
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1197
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:565
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:2574
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:1637
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find_as
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
Definition: DenseMap.h:175
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::LazyValueInfoWrapperPass
Wrapper around LazyValueInfo.
Definition: LazyValueInfo.h:149
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:1066
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:1707
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:31
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1804
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2504
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::PointerIntPair::getInt
IntType getInt() const
Definition: PointerIntPair.h:62
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:1093
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:1869
llvm::ICmpInst::isEquality
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1286
llvm::ConstantFoldCompareInstOperands
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
Definition: ConstantFolding.cpp:1219
getValueOnEdge
static Value * getValueOnEdge(LazyValueInfo *LVI, Value *Incoming, BasicBlock *From, BasicBlock *To, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:218
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::formatted_raw_ostream
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
Definition: FormattedStream.h:30
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SPF_ABS
@ SPF_ABS
Floating point maxnum.
Definition: ValueTracking.h:698
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:742
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:62
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1746
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:360
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:943
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:1156
llvm::LazyValueInfo::releaseMemory
void releaseMemory()
Definition: LazyValueInfo.cpp:1575
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
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
constantFoldUser
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)
Definition: LazyValueInfo.cpp:1288
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::LazyValueInfo::getConstantRangeAtUse
ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
Definition: LazyValueInfo.cpp:1655
llvm::BinaryOperator
Definition: InstrTypes.h:187
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:5097
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::logicalview::LVAttributeKind::Range
@ Range
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
Printer
Memory true print Memory SSA Printer
Definition: MemorySSA.cpp:78
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
llvm::logicalview::LVAttributeKind::Zero
@ Zero
llvm::Offset
@ Offset
Definition: DWP.cpp:406
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
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::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
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:1170
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::ValueLatticeElement::asConstantInteger
std::optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:278
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:428
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:770
llvm::PredIterator
Definition: CFG.h:42
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:177
ValueHandle.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::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:685
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:777
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
llvm::PBQP::RegAlloc::solve
Solution solve(PBQPRAGraph &G)
Definition: RegAllocPBQP.h:522
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
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:496
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:1184
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:354
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:1594
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:2455
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:1969
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:234
llvm::ValueLatticeElement::isNotConstant
bool isNotConstant() const
Definition: ValueLattice.h:244
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2510
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:446
llvm::LazyValueInfoWrapperPass::getLVI
LazyValueInfo & getLVI()
Definition: LazyValueInfo.cpp:1571
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:439
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:47
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::OverflowingBinaryOperator::NoSignedWrap
@ NoSignedWrap
Definition: Operator.h:80
llvm::initializeLazyValueInfoPrinterPass
void initializeLazyValueInfoPrinterPass(PassRegistry &)
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:328
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::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:386
llvm::ValueLatticeElement::get
static ValueLatticeElement get(Constant *C)
Definition: ValueLattice.h:203
llvm::PointerIntPair< Value *, 1, bool >
llvm::ConstantRange::intersectWith
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
Definition: ConstantRange.cpp:520
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
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
getValueFromConditionImpl
static std::optional< ValueLatticeElement > getValueFromConditionImpl(Value *Val, CondValue CondVal, bool isRevisit, SmallDenseMap< CondValue, ValueLatticeElement > &Visited, SmallVectorImpl< CondValue > &Worklist)
Definition: LazyValueInfo.cpp:1174
llvm::ConstantRange::fromKnownBits
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
Definition: ConstantRange.cpp:59
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:741
Dominators.h
N
#define N
llvm::CastInst::getOpcode
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:675
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:222
llvm::SPF_UMIN
@ SPF_UMIN
Signed minimum.
Definition: ValueTracking.h:693
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:90
InstructionSimplify.h
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:808
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2814
llvm::PHINode
Definition: Instructions.h:2708
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:127
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
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
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:157
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:488
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::MIPatternMatch::m_Not
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
Definition: MIPatternMatch.h:774
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3283
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:367
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3139
raw_ostream.h
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1611
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:2136
llvm::LazyValueInfo::eraseBlock
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
Definition: LazyValueInfo.cpp:1963
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:1815
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
AddNonNullPointer
static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet)
Definition: LazyValueInfo.cpp:636
InitializePasses.h
ValueLattice.h
llvm::ExtractValueInst::getIndices
ArrayRef< unsigned > getIndices() const
Definition: Instructions.h:2520
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4802
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:540
getValueFromOverflowCondition
static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
Definition: LazyValueInfo.cpp:1151
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:1955
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:1198
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:2556
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1342
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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::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:355
llvm::AssumptionCache::assumptionsFor
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
Definition: AssumptionCache.h:157