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