1 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the interface for lazy computation of value constraint
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Analysis/LazyValueInfo.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/Analysis/AssumptionCache.h"
19 #include "llvm/Analysis/ConstantFolding.h"
20 #include "llvm/Analysis/InstructionSimplify.h"
21 #include "llvm/Analysis/TargetLibraryInfo.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/Analysis/ValueLattice.h"
24 #include "llvm/IR/AssemblyAnnotationWriter.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/ConstantRange.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/Intrinsics.h"
33 #include "llvm/IR/LLVMContext.h"
34 #include "llvm/IR/PatternMatch.h"
35 #include "llvm/IR/ValueHandle.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/FormattedStream.h"
38 #include "llvm/Support/raw_ostream.h"
41 using namespace PatternMatch;
43 #define DEBUG_TYPE "lazy-value-info"
45 // This is the number of worklist items we will process to try to discover an
46 // answer for a given value.
47 static const unsigned MaxProcessedPerValue = 500;
49 char LazyValueInfoWrapperPass::ID = 0;
50 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
51 "Lazy Value Information Analysis", false, true)
52 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
53 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
54 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
55 "Lazy Value Information Analysis", false, true)
58 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
61 AnalysisKey LazyValueAnalysis::Key;
63 /// Returns true if this lattice value represents at most one possible value.
64 /// This is as precise as any lattice value can get while still representing
66 static bool hasSingleValue(const ValueLatticeElement &Val) {
67 if (Val.isConstantRange() &&
68 Val.getConstantRange().isSingleElement())
69 // Integer constants are single element ranges
72 // Non integer constants
77 /// Combine two sets of facts about the same value into a single set of
78 /// facts. Note that this method is not suitable for merging facts along
79 /// different paths in a CFG; that's what the mergeIn function is for. This
80 /// is for merging facts gathered about the same value at the same location
81 /// through two independent means.
83 /// * This method does not promise to return the most precise possible lattice
84 /// value implied by A and B. It is allowed to return any lattice element
85 /// which is at least as strong as *either* A or B (unless our facts
86 /// conflict, see below).
87 /// * Due to unreachable code, the intersection of two lattice values could be
88 /// contradictory. If this happens, we return some valid lattice value so as
89 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
90 /// we do not make this guarantee. TODO: This would be a useful enhancement.
91 static ValueLatticeElement intersect(const ValueLatticeElement &A,
92 const ValueLatticeElement &B) {
93 // Undefined is the strongest state. It means the value is known to be along
94 // an unreachable path.
100 // If we gave up for one, but got a useable fact from the other, use it.
101 if (A.isOverdefined())
103 if (B.isOverdefined())
106 // Can't get any more precise than constants.
107 if (hasSingleValue(A))
109 if (hasSingleValue(B))
112 // Could be either constant range or not constant here.
113 if (!A.isConstantRange() || !B.isConstantRange()) {
114 // TODO: Arbitrary choice, could be improved
118 // Intersect two constant ranges
119 ConstantRange Range =
120 A.getConstantRange().intersectWith(B.getConstantRange());
121 // Note: An empty range is implicitly converted to overdefined internally.
122 // TODO: We could instead use Undefined here since we've proven a conflict
123 // and thus know this path must be unreachable.
124 return ValueLatticeElement::getRange(std::move(Range));
127 //===----------------------------------------------------------------------===//
128 // LazyValueInfoCache Decl
129 //===----------------------------------------------------------------------===//
132 /// A callback value handle updates the cache when values are erased.
133 class LazyValueInfoCache;
134 struct LVIValueHandle final : public CallbackVH {
135 // Needs to access getValPtr(), which is protected.
136 friend struct DenseMapInfo<LVIValueHandle>;
138 LazyValueInfoCache *Parent;
140 LVIValueHandle(Value *V, LazyValueInfoCache *P)
141 : CallbackVH(V), Parent(P) { }
143 void deleted() override;
144 void allUsesReplacedWith(Value *V) override {
148 } // end anonymous namespace
151 /// This is the cache kept by LazyValueInfo which
152 /// maintains information about queries across the clients' queries.
153 class LazyValueInfoCache {
154 /// This is all of the cached block information for exactly one Value*.
155 /// The entries are sorted by the BasicBlock* of the
156 /// entries, allowing us to do a lookup with a binary search.
157 /// Over-defined lattice values are recorded in OverDefinedCache to reduce
159 struct ValueCacheEntryTy {
160 ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
161 LVIValueHandle Handle;
162 SmallDenseMap<PoisoningVH<BasicBlock>, ValueLatticeElement, 4> BlockVals;
165 /// This tracks, on a per-block basis, the set of values that are
166 /// over-defined at the end of that block.
167 typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
169 /// Keep track of all blocks that we have ever seen, so we
170 /// don't spend time removing unused blocks from our caches.
171 DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
173 /// This is all of the cached information for all values,
174 /// mapped from Value* to key information.
175 DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
176 OverDefinedCacheTy OverDefinedCache;
180 void insertResult(Value *Val, BasicBlock *BB,
181 const ValueLatticeElement &Result) {
182 SeenBlocks.insert(BB);
184 // Insert over-defined values into their own cache to reduce memory
186 if (Result.isOverdefined())
187 OverDefinedCache[BB].insert(Val);
189 auto It = ValueCache.find_as(Val);
190 if (It == ValueCache.end()) {
191 ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
192 It = ValueCache.find_as(Val);
193 assert(It != ValueCache.end() && "Val was just added to the map!");
195 It->second->BlockVals[BB] = Result;
199 bool isOverdefined(Value *V, BasicBlock *BB) const {
200 auto ODI = OverDefinedCache.find(BB);
202 if (ODI == OverDefinedCache.end())
205 return ODI->second.count(V);
208 bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
209 if (isOverdefined(V, BB))
212 auto I = ValueCache.find_as(V);
213 if (I == ValueCache.end())
216 return I->second->BlockVals.count(BB);
219 ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const {
220 if (isOverdefined(V, BB))
221 return ValueLatticeElement::getOverdefined();
223 auto I = ValueCache.find_as(V);
224 if (I == ValueCache.end())
225 return ValueLatticeElement();
226 auto BBI = I->second->BlockVals.find(BB);
227 if (BBI == I->second->BlockVals.end())
228 return ValueLatticeElement();
232 /// clear - Empty the cache.
236 OverDefinedCache.clear();
239 /// Inform the cache that a given value has been deleted.
240 void eraseValue(Value *V);
242 /// This is part of the update interface to inform the cache
243 /// that a block has been deleted.
244 void eraseBlock(BasicBlock *BB);
246 /// Updates the cache to remove any influence an overdefined value in
247 /// OldSucc might have (unless also overdefined in NewSucc). This just
248 /// flushes elements from the cache and does not add any.
249 void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
251 friend struct LVIValueHandle;
255 void LazyValueInfoCache::eraseValue(Value *V) {
256 for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
257 // Copy and increment the iterator immediately so we can erase behind
260 SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
262 if (ValueSet.empty())
263 OverDefinedCache.erase(Iter);
269 void LVIValueHandle::deleted() {
270 // This erasure deallocates *this, so it MUST happen after we're done
271 // using any and all members of *this.
272 Parent->eraseValue(*this);
275 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
276 // Shortcut if we have never seen this block.
277 DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
278 if (I == SeenBlocks.end())
282 auto ODI = OverDefinedCache.find(BB);
283 if (ODI != OverDefinedCache.end())
284 OverDefinedCache.erase(ODI);
286 for (auto &I : ValueCache)
287 I.second->BlockVals.erase(BB);
290 void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
291 BasicBlock *NewSucc) {
292 // When an edge in the graph has been threaded, values that we could not
293 // determine a value for before (i.e. were marked overdefined) may be
294 // possible to solve now. We do NOT try to proactively update these values.
295 // Instead, we clear their entries from the cache, and allow lazy updating to
296 // recompute them when needed.
298 // The updating process is fairly simple: we need to drop cached info
299 // for all values that were marked overdefined in OldSucc, and for those same
300 // values in any successor of OldSucc (except NewSucc) in which they were
301 // also marked overdefined.
302 std::vector<BasicBlock*> worklist;
303 worklist.push_back(OldSucc);
305 auto I = OverDefinedCache.find(OldSucc);
306 if (I == OverDefinedCache.end())
307 return; // Nothing to process here.
308 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
310 // Use a worklist to perform a depth-first search of OldSucc's successors.
311 // NOTE: We do not need a visited list since any blocks we have already
312 // visited will have had their overdefined markers cleared already, and we
313 // thus won't loop to their successors.
314 while (!worklist.empty()) {
315 BasicBlock *ToUpdate = worklist.back();
318 // Skip blocks only accessible through NewSucc.
319 if (ToUpdate == NewSucc) continue;
321 // If a value was marked overdefined in OldSucc, and is here too...
322 auto OI = OverDefinedCache.find(ToUpdate);
323 if (OI == OverDefinedCache.end())
325 SmallPtrSetImpl<Value *> &ValueSet = OI->second;
327 bool changed = false;
328 for (Value *V : ValsToClear) {
329 if (!ValueSet.erase(V))
332 // If we removed anything, then we potentially need to update
333 // blocks successors too.
336 if (ValueSet.empty()) {
337 OverDefinedCache.erase(OI);
342 if (!changed) continue;
344 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
350 /// An assembly annotator class to print LazyValueCache information in
352 class LazyValueInfoImpl;
353 class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
354 LazyValueInfoImpl *LVIImpl;
355 // While analyzing which blocks we can solve values for, we need the dominator
356 // information. Since this is an optional parameter in LVI, we require this
357 // DomTreeAnalysis pass in the printer pass, and pass the dominator
358 // tree to the LazyValueInfoAnnotatedWriter.
362 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
363 : LVIImpl(L), DT(DTree) {}
365 virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
366 formatted_raw_ostream &OS);
368 virtual void emitInstructionAnnot(const Instruction *I,
369 formatted_raw_ostream &OS);
373 // The actual implementation of the lazy analysis and update. Note that the
374 // inheritance from LazyValueInfoCache is intended to be temporary while
375 // splitting the code and then transitioning to a has-a relationship.
376 class LazyValueInfoImpl {
378 /// Cached results from previous queries
379 LazyValueInfoCache TheCache;
381 /// This stack holds the state of the value solver during a query.
382 /// It basically emulates the callstack of the naive
383 /// recursive value lookup process.
384 SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
386 /// Keeps track of which block-value pairs are in BlockValueStack.
387 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
389 /// Push BV onto BlockValueStack unless it's already in there.
390 /// Returns true on success.
391 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
392 if (!BlockValueSet.insert(BV).second)
393 return false; // It's already in the stack.
395 DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
397 BlockValueStack.push_back(BV);
401 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
402 const DataLayout &DL; ///< A mandatory DataLayout
403 DominatorTree *DT; ///< An optional DT pointer.
405 ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
406 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
407 ValueLatticeElement &Result, Instruction *CxtI = nullptr);
408 bool hasBlockValue(Value *Val, BasicBlock *BB);
410 // These methods process one work item and may add more. A false value
411 // returned means that the work item was not completely processed and must
412 // be revisited after going through the new items.
413 bool solveBlockValue(Value *Val, BasicBlock *BB);
414 bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
416 bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
418 bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
420 bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
422 bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
424 bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
426 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
427 ValueLatticeElement &BBLV,
433 /// This is the query interface to determine the lattice
434 /// value for the specified Value* at the end of the specified block.
435 ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
436 Instruction *CxtI = nullptr);
438 /// This is the query interface to determine the lattice
439 /// value for the specified Value* at the specified instruction (generally
440 /// from an assume intrinsic).
441 ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
443 /// This is the query interface to determine the lattice
444 /// value for the specified Value* that is true on the specified edge.
445 ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
447 Instruction *CxtI = nullptr);
449 /// Complete flush all previously computed values
454 /// Printing the LazyValueInfo Analysis.
455 void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
456 LazyValueInfoAnnotatedWriter Writer(this, DTree);
457 F.print(OS, &Writer);
460 /// This is part of the update interface to inform the cache
461 /// that a block has been deleted.
462 void eraseBlock(BasicBlock *BB) {
463 TheCache.eraseBlock(BB);
466 /// This is the update interface to inform the cache that an edge from
467 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
468 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
470 LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
471 DominatorTree *DT = nullptr)
472 : AC(AC), DL(DL), DT(DT) {}
474 } // end anonymous namespace
477 void LazyValueInfoImpl::solve() {
478 SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
479 BlockValueStack.begin(), BlockValueStack.end());
481 unsigned processedCount = 0;
482 while (!BlockValueStack.empty()) {
484 // Abort if we have to process too many values to get a result for this one.
485 // Because of the design of the overdefined cache currently being per-block
486 // to avoid naming-related issues (IE it wants to try to give different
487 // results for the same name in different blocks), overdefined results don't
488 // get cached globally, which in turn means we will often try to rediscover
489 // the same overdefined result again and again. Once something like
490 // PredicateInfo is used in LVI or CVP, we should be able to make the
491 // overdefined cache global, and remove this throttle.
492 if (processedCount > MaxProcessedPerValue) {
493 DEBUG(dbgs() << "Giving up on stack because we are getting too deep\n");
494 // Fill in the original values
495 while (!StartingStack.empty()) {
496 std::pair<BasicBlock *, Value *> &e = StartingStack.back();
497 TheCache.insertResult(e.second, e.first,
498 ValueLatticeElement::getOverdefined());
499 StartingStack.pop_back();
501 BlockValueSet.clear();
502 BlockValueStack.clear();
505 std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
506 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
508 if (solveBlockValue(e.second, e.first)) {
509 // The work item was completely processed.
510 assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
511 assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
512 "Result should be in cache!");
514 DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
515 << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
517 BlockValueStack.pop_back();
518 BlockValueSet.erase(e);
520 // More work needs to be done before revisiting.
521 assert(BlockValueStack.back() != e && "Stack should have been pushed!");
526 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
527 // If already a constant, there is nothing to compute.
528 if (isa<Constant>(Val))
531 return TheCache.hasCachedValueInfo(Val, BB);
534 ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
536 // If already a constant, there is nothing to compute.
537 if (Constant *VC = dyn_cast<Constant>(Val))
538 return ValueLatticeElement::get(VC);
540 return TheCache.getCachedValueInfo(Val, BB);
543 static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
544 switch (BBI->getOpcode()) {
546 case Instruction::Load:
547 case Instruction::Call:
548 case Instruction::Invoke:
549 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
550 if (isa<IntegerType>(BBI->getType())) {
551 return ValueLatticeElement::getRange(
552 getConstantRangeFromMetadata(*Ranges));
556 // Nothing known - will be intersected with other facts
557 return ValueLatticeElement::getOverdefined();
560 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
561 if (isa<Constant>(Val))
564 if (TheCache.hasCachedValueInfo(Val, BB)) {
565 // If we have a cached value, use that.
566 DEBUG(dbgs() << " reuse BB '" << BB->getName()
567 << "' val=" << TheCache.getCachedValueInfo(Val, BB) << '\n');
569 // Since we're reusing a cached value, we don't need to update the
570 // OverDefinedCache. The cache will have been properly updated whenever the
571 // cached value was inserted.
575 // Hold off inserting this value into the Cache in case we have to return
576 // false and come back later.
577 ValueLatticeElement Res;
578 if (!solveBlockValueImpl(Res, Val, BB))
579 // Work pushed, will revisit
582 TheCache.insertResult(Val, BB, Res);
586 bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
587 Value *Val, BasicBlock *BB) {
589 Instruction *BBI = dyn_cast<Instruction>(Val);
590 if (!BBI || BBI->getParent() != BB)
591 return solveBlockValueNonLocal(Res, Val, BB);
593 if (PHINode *PN = dyn_cast<PHINode>(BBI))
594 return solveBlockValuePHINode(Res, PN, BB);
596 if (auto *SI = dyn_cast<SelectInst>(BBI))
597 return solveBlockValueSelect(Res, SI, BB);
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 sensativity 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)) {
610 Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
613 if (BBI->getType()->isIntegerTy()) {
614 if (auto *CI = dyn_cast<CastInst>(BBI))
615 return solveBlockValueCast(Res, CI, BB);
617 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
618 if (BO && isa<ConstantInt>(BO->getOperand(1)))
619 return solveBlockValueBinaryOp(Res, BO, BB);
622 DEBUG(dbgs() << " compute BB '" << BB->getName()
623 << "' - unknown inst def found.\n");
624 Res = getFromRangeMetadata(BBI);
628 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
629 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
630 return L->getPointerAddressSpace() == 0 &&
631 GetUnderlyingObject(L->getPointerOperand(),
632 L->getModule()->getDataLayout()) == Ptr;
634 if (StoreInst *S = dyn_cast<StoreInst>(I)) {
635 return S->getPointerAddressSpace() == 0 &&
636 GetUnderlyingObject(S->getPointerOperand(),
637 S->getModule()->getDataLayout()) == Ptr;
639 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
640 if (MI->isVolatile()) return false;
642 // FIXME: check whether it has a valuerange that excludes zero?
643 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
644 if (!Len || Len->isZero()) return false;
646 if (MI->getDestAddressSpace() == 0)
647 if (GetUnderlyingObject(MI->getRawDest(),
648 MI->getModule()->getDataLayout()) == Ptr)
650 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
651 if (MTI->getSourceAddressSpace() == 0)
652 if (GetUnderlyingObject(MTI->getRawSource(),
653 MTI->getModule()->getDataLayout()) == Ptr)
659 /// Return true if the allocation associated with Val is ever dereferenced
660 /// within the given basic block. This establishes the fact Val is not null,
661 /// but does not imply that the memory at Val is dereferenceable. (Val may
662 /// point off the end of the dereferenceable part of the object.)
663 static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
664 assert(Val->getType()->isPointerTy());
666 const DataLayout &DL = BB->getModule()->getDataLayout();
667 Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
668 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
669 // inside InstructionDereferencesPointer either.
670 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
671 for (Instruction &I : *BB)
672 if (InstructionDereferencesPointer(&I, UnderlyingVal))
677 bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
678 Value *Val, BasicBlock *BB) {
679 ValueLatticeElement Result; // Start Undefined.
681 // If this is the entry block, we must be asking about an argument. The
682 // value is overdefined.
683 if (BB == &BB->getParent()->getEntryBlock()) {
684 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
685 // Before giving up, see if we can prove the pointer non-null local to
686 // this particular block.
687 if (Val->getType()->isPointerTy() &&
688 (isKnownNonZero(Val, DL) || isObjectDereferencedInBlock(Val, BB))) {
689 PointerType *PTy = cast<PointerType>(Val->getType());
690 Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
692 Result = ValueLatticeElement::getOverdefined();
698 // Loop over all of our predecessors, merging what we know from them into
699 // result. If we encounter an unexplored predecessor, we eagerly explore it
700 // in a depth first manner. In practice, this has the effect of discovering
701 // paths we can't analyze eagerly without spending compile times analyzing
702 // other paths. This heuristic benefits from the fact that predecessors are
703 // frequently arranged such that dominating ones come first and we quickly
704 // find a path to function entry. TODO: We should consider explicitly
705 // canonicalizing to make this true rather than relying on this happy
707 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
708 ValueLatticeElement EdgeResult;
709 if (!getEdgeValue(Val, *PI, BB, EdgeResult))
710 // Explore that input, then return here
713 Result.mergeIn(EdgeResult, DL);
715 // If we hit overdefined, exit early. The BlockVals entry is already set
717 if (Result.isOverdefined()) {
718 DEBUG(dbgs() << " compute BB '" << BB->getName()
719 << "' - overdefined because of pred (non local).\n");
720 // Before giving up, see if we can prove the pointer non-null local to
721 // this particular block.
722 if (Val->getType()->isPointerTy() &&
723 isObjectDereferencedInBlock(Val, BB)) {
724 PointerType *PTy = cast<PointerType>(Val->getType());
725 Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
733 // Return the merged value, which is more precise than 'overdefined'.
734 assert(!Result.isOverdefined());
739 bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV,
740 PHINode *PN, BasicBlock *BB) {
741 ValueLatticeElement Result; // Start Undefined.
743 // Loop over all of our predecessors, merging what we know from them into
744 // result. See the comment about the chosen traversal order in
745 // solveBlockValueNonLocal; the same reasoning applies here.
746 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
747 BasicBlock *PhiBB = PN->getIncomingBlock(i);
748 Value *PhiVal = PN->getIncomingValue(i);
749 ValueLatticeElement EdgeResult;
750 // Note that we can provide PN as the context value to getEdgeValue, even
751 // though the results will be cached, because PN is the value being used as
752 // the cache key in the caller.
753 if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
754 // Explore that input, then return here
757 Result.mergeIn(EdgeResult, DL);
759 // If we hit overdefined, exit early. The BlockVals entry is already set
761 if (Result.isOverdefined()) {
762 DEBUG(dbgs() << " compute BB '" << BB->getName()
763 << "' - overdefined because of pred (local).\n");
770 // Return the merged value, which is more precise than 'overdefined'.
771 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
776 static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
777 bool isTrueDest = true);
779 // If we can determine a constraint on the value given conditions assumed by
780 // the program, intersect those constraints with BBLV
781 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
782 Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
783 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
787 for (auto &AssumeVH : AC->assumptionsFor(Val)) {
790 auto *I = cast<CallInst>(AssumeVH);
791 if (!isValidAssumeForContext(I, BBI, DT))
794 BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
797 // If guards are not used in the module, don't spend time looking for them
798 auto *GuardDecl = BBI->getModule()->getFunction(
799 Intrinsic::getName(Intrinsic::experimental_guard));
800 if (!GuardDecl || GuardDecl->use_empty())
803 for (Instruction &I : make_range(BBI->getIterator().getReverse(),
804 BBI->getParent()->rend())) {
805 Value *Cond = nullptr;
806 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
807 BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
811 bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
812 SelectInst *SI, BasicBlock *BB) {
814 // Recurse on our inputs if needed
815 if (!hasBlockValue(SI->getTrueValue(), BB)) {
816 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
818 BBLV = ValueLatticeElement::getOverdefined();
821 ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
822 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
823 // extra slots in the table if we can.
824 if (TrueVal.isOverdefined()) {
825 BBLV = ValueLatticeElement::getOverdefined();
829 if (!hasBlockValue(SI->getFalseValue(), BB)) {
830 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
832 BBLV = ValueLatticeElement::getOverdefined();
835 ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
836 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
837 // extra slots in the table if we can.
838 if (FalseVal.isOverdefined()) {
839 BBLV = ValueLatticeElement::getOverdefined();
843 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
844 const ConstantRange &TrueCR = TrueVal.getConstantRange();
845 const ConstantRange &FalseCR = FalseVal.getConstantRange();
846 Value *LHS = nullptr;
847 Value *RHS = nullptr;
848 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
849 // Is this a min specifically of our two inputs? (Avoid the risk of
850 // ValueTracking getting smarter looking back past our immediate inputs.)
851 if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
852 LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
853 ConstantRange ResultCR = [&]() {
854 switch (SPR.Flavor) {
856 llvm_unreachable("unexpected minmax type!");
857 case SPF_SMIN: /// Signed minimum
858 return TrueCR.smin(FalseCR);
859 case SPF_UMIN: /// Unsigned minimum
860 return TrueCR.umin(FalseCR);
861 case SPF_SMAX: /// Signed maximum
862 return TrueCR.smax(FalseCR);
863 case SPF_UMAX: /// Unsigned maximum
864 return TrueCR.umax(FalseCR);
867 BBLV = ValueLatticeElement::getRange(ResultCR);
871 // TODO: ABS, NABS from the SelectPatternResult
874 // Can we constrain the facts about the true and false values by using the
875 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
876 // TODO: We could potentially refine an overdefined true value above.
877 Value *Cond = SI->getCondition();
878 TrueVal = intersect(TrueVal,
879 getValueFromCondition(SI->getTrueValue(), Cond, true));
880 FalseVal = intersect(FalseVal,
881 getValueFromCondition(SI->getFalseValue(), Cond, false));
883 // Handle clamp idioms such as:
884 // %24 = constantrange<0, 17>
885 // %39 = icmp eq i32 %24, 0
886 // %40 = add i32 %24, -1
887 // %siv.next = select i1 %39, i32 16, i32 %40
888 // %siv.next = constantrange<0, 17> not <-1, 17>
889 // In general, this can handle any clamp idiom which tests the edge
890 // condition via an equality or inequality.
891 if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
892 ICmpInst::Predicate Pred = ICI->getPredicate();
893 Value *A = ICI->getOperand(0);
894 if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
895 auto addConstants = [](ConstantInt *A, ConstantInt *B) {
896 assert(A->getType() == B->getType());
897 return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
899 // See if either input is A + C2, subject to the constraint from the
900 // condition that A != C when that input is used. We can assume that
901 // that input doesn't include C + C2.
902 ConstantInt *CIAdded;
905 case ICmpInst::ICMP_EQ:
906 if (match(SI->getFalseValue(), m_Add(m_Specific(A),
907 m_ConstantInt(CIAdded)))) {
908 auto ResNot = addConstants(CIBase, CIAdded);
909 FalseVal = intersect(FalseVal,
910 ValueLatticeElement::getNot(ResNot));
913 case ICmpInst::ICMP_NE:
914 if (match(SI->getTrueValue(), m_Add(m_Specific(A),
915 m_ConstantInt(CIAdded)))) {
916 auto ResNot = addConstants(CIBase, CIAdded);
917 TrueVal = intersect(TrueVal,
918 ValueLatticeElement::getNot(ResNot));
925 ValueLatticeElement Result; // Start Undefined.
926 Result.mergeIn(TrueVal, DL);
927 Result.mergeIn(FalseVal, DL);
932 bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
935 if (!CI->getOperand(0)->getType()->isSized()) {
936 // Without knowing how wide the input is, we can't analyze it in any useful
938 BBLV = ValueLatticeElement::getOverdefined();
942 // Filter out casts we don't know how to reason about before attempting to
943 // recurse on our operand. This can cut a long search short if we know we're
944 // not going to be able to get any useful information anways.
945 switch (CI->getOpcode()) {
946 case Instruction::Trunc:
947 case Instruction::SExt:
948 case Instruction::ZExt:
949 case Instruction::BitCast:
952 // Unhandled instructions are overdefined.
953 DEBUG(dbgs() << " compute BB '" << BB->getName()
954 << "' - overdefined (unknown cast).\n");
955 BBLV = ValueLatticeElement::getOverdefined();
959 // Figure out the range of the LHS. If that fails, we still apply the
960 // transfer rule on the full set since we may be able to locally infer
961 // interesting facts.
962 if (!hasBlockValue(CI->getOperand(0), BB))
963 if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
964 // More work to do before applying this transfer rule.
967 const unsigned OperandBitWidth =
968 DL.getTypeSizeInBits(CI->getOperand(0)->getType());
969 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
970 if (hasBlockValue(CI->getOperand(0), BB)) {
971 ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB);
972 intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
974 if (LHSVal.isConstantRange())
975 LHSRange = LHSVal.getConstantRange();
978 const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
980 // NOTE: We're currently limited by the set of operations that ConstantRange
981 // can evaluate symbolically. Enhancing that set will allows us to analyze
983 BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
988 bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
992 assert(BO->getOperand(0)->getType()->isSized() &&
993 "all operands to binary operators are sized");
995 // Filter out operators we don't know how to reason about before attempting to
996 // recurse on our operand(s). This can cut a long search short if we know
997 // we're not going to be able to get any useful information anyways.
998 switch (BO->getOpcode()) {
999 case Instruction::Add:
1000 case Instruction::Sub:
1001 case Instruction::Mul:
1002 case Instruction::UDiv:
1003 case Instruction::Shl:
1004 case Instruction::LShr:
1005 case Instruction::And:
1006 case Instruction::Or:
1007 // continue into the code below
1010 // Unhandled instructions are overdefined.
1011 DEBUG(dbgs() << " compute BB '" << BB->getName()
1012 << "' - overdefined (unknown binary operator).\n");
1013 BBLV = ValueLatticeElement::getOverdefined();
1017 // Figure out the range of the LHS. If that fails, use a conservative range,
1018 // but apply the transfer rule anyways. This lets us pick up facts from
1019 // expressions like "and i32 (call i32 @foo()), 32"
1020 if (!hasBlockValue(BO->getOperand(0), BB))
1021 if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
1022 // More work to do before applying this transfer rule.
1025 const unsigned OperandBitWidth =
1026 DL.getTypeSizeInBits(BO->getOperand(0)->getType());
1027 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1028 if (hasBlockValue(BO->getOperand(0), BB)) {
1029 ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
1030 intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
1032 if (LHSVal.isConstantRange())
1033 LHSRange = LHSVal.getConstantRange();
1036 ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
1037 ConstantRange RHSRange = ConstantRange(RHS->getValue());
1039 // NOTE: We're currently limited by the set of operations that ConstantRange
1040 // can evaluate symbolically. Enhancing that set will allows us to analyze
1041 // more definitions.
1042 Instruction::BinaryOps BinOp = BO->getOpcode();
1043 BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1047 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1049 Value *LHS = ICI->getOperand(0);
1050 Value *RHS = ICI->getOperand(1);
1051 CmpInst::Predicate Predicate = ICI->getPredicate();
1053 if (isa<Constant>(RHS)) {
1054 if (ICI->isEquality() && LHS == Val) {
1055 // We know that V has the RHS constant if this is a true SETEQ or
1057 if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1058 return ValueLatticeElement::get(cast<Constant>(RHS));
1060 return ValueLatticeElement::getNot(cast<Constant>(RHS));
1064 if (!Val->getType()->isIntegerTy())
1065 return ValueLatticeElement::getOverdefined();
1067 // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1068 // range of Val guaranteed by the condition. Recognize comparisons in the from
1070 // icmp <pred> Val, ...
1071 // icmp <pred> (add Val, Offset), ...
1072 // The latter is the range checking idiom that InstCombine produces. Subtract
1073 // the offset from the allowed range for RHS in this case.
1075 // Val or (add Val, Offset) can be on either hand of the comparison
1076 if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1077 std::swap(LHS, RHS);
1078 Predicate = CmpInst::getSwappedPredicate(Predicate);
1081 ConstantInt *Offset = nullptr;
1083 match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1085 if (LHS == Val || Offset) {
1086 // Calculate the range of values that are allowed by the comparison
1087 ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1088 /*isFullSet=*/true);
1089 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1090 RHSRange = ConstantRange(CI->getValue());
1091 else if (Instruction *I = dyn_cast<Instruction>(RHS))
1092 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1093 RHSRange = getConstantRangeFromMetadata(*Ranges);
1095 // If we're interested in the false dest, invert the condition
1096 CmpInst::Predicate Pred =
1097 isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1098 ConstantRange TrueValues =
1099 ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1101 if (Offset) // Apply the offset from above.
1102 TrueValues = TrueValues.subtract(Offset->getValue());
1104 return ValueLatticeElement::getRange(std::move(TrueValues));
1107 return ValueLatticeElement::getOverdefined();
1110 static ValueLatticeElement
1111 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1112 DenseMap<Value*, ValueLatticeElement> &Visited);
1114 static ValueLatticeElement
1115 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1116 DenseMap<Value*, ValueLatticeElement> &Visited) {
1117 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1118 return getValueFromICmpCondition(Val, ICI, isTrueDest);
1120 // Handle conditions in the form of (cond1 && cond2), we know that on the
1121 // true dest path both of the conditions hold. Similarly for conditions of
1122 // the form (cond1 || cond2), we know that on the false dest path neither
1124 BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1125 if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
1126 (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
1127 return ValueLatticeElement::getOverdefined();
1129 auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
1130 auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
1131 return intersect(RHS, LHS);
1134 static ValueLatticeElement
1135 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1136 DenseMap<Value*, ValueLatticeElement> &Visited) {
1137 auto I = Visited.find(Cond);
1138 if (I != Visited.end())
1141 auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1142 Visited[Cond] = Result;
1146 ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
1148 assert(Cond && "precondition");
1149 DenseMap<Value*, ValueLatticeElement> Visited;
1150 return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1153 // Return true if Usr has Op as an operand, otherwise false.
1154 static bool usesOperand(User *Usr, Value *Op) {
1155 return find(Usr->operands(), Op) != Usr->op_end();
1158 // Return true if the instruction type of Val is supported by
1159 // constantFoldUser(). Currently CastInst and BinaryOperator only. Call this
1160 // before calling constantFoldUser() to find out if it's even worth attempting
1162 static bool isOperationFoldable(User *Usr) {
1163 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
1166 // Check if Usr can be simplified to an integer constant when the value of one
1167 // of its operands Op is an integer constant OpConstVal. If so, return it as an
1168 // lattice value range with a single element or otherwise return an overdefined
1170 static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1171 const APInt &OpConstVal,
1172 const DataLayout &DL) {
1173 assert(isOperationFoldable(Usr) && "Precondition");
1174 Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1175 // Check if Usr can be simplified to a constant.
1176 if (auto *CI = dyn_cast<CastInst>(Usr)) {
1177 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1178 if (auto *C = dyn_cast_or_null<ConstantInt>(
1179 SimplifyCastInst(CI->getOpcode(), OpConst,
1180 CI->getDestTy(), DL))) {
1181 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1183 } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1184 bool Op0Match = BO->getOperand(0) == Op;
1185 bool Op1Match = BO->getOperand(1) == Op;
1186 assert((Op0Match || Op1Match) &&
1187 "Operand 0 nor Operand 1 isn't a match");
1188 Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1189 Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1190 if (auto *C = dyn_cast_or_null<ConstantInt>(
1191 SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1192 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1195 return ValueLatticeElement::getOverdefined();
1198 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1199 /// Val is not constrained on the edge. Result is unspecified if return value
1201 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1202 BasicBlock *BBTo, ValueLatticeElement &Result) {
1203 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1204 // know that v != 0.
1205 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1206 // If this is a conditional branch and only one successor goes to BBTo, then
1207 // we may be able to infer something from the condition.
1208 if (BI->isConditional() &&
1209 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1210 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1211 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1212 "BBTo isn't a successor of BBFrom");
1213 Value *Condition = BI->getCondition();
1215 // If V is the condition of the branch itself, then we know exactly what
1217 if (Condition == Val) {
1218 Result = ValueLatticeElement::get(ConstantInt::get(
1219 Type::getInt1Ty(Val->getContext()), isTrueDest));
1223 // If the condition of the branch is an equality comparison, we may be
1224 // able to infer the value.
1225 Result = getValueFromCondition(Val, Condition, isTrueDest);
1226 if (!Result.isOverdefined())
1229 if (User *Usr = dyn_cast<User>(Val)) {
1230 assert(Result.isOverdefined() && "Result isn't overdefined");
1231 // Check with isOperationFoldable() first to avoid linearly iterating
1232 // over the operands unnecessarily which can be expensive for
1233 // instructions with many operands.
1234 if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1235 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1236 if (usesOperand(Usr, Condition)) {
1237 // If Val has Condition as an operand and Val can be folded into a
1238 // constant with either Condition == true or Condition == false,
1239 // propagate the constant.
1241 // ; %Val is true on the edge to %then.
1242 // %Val = and i1 %Condition, true.
1243 // br %Condition, label %then, label %else
1244 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1245 Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1247 // If one of Val's operand has an inferred value, we may be able to
1248 // infer the value of Val.
1250 // ; %Val is 94 on the edge to %then.
1251 // %Val = add i8 %Op, 1
1252 // %Condition = icmp eq i8 %Op, 93
1253 // br i1 %Condition, label %then, label %else
1254 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1255 Value *Op = Usr->getOperand(i);
1256 ValueLatticeElement OpLatticeVal =
1257 getValueFromCondition(Op, Condition, isTrueDest);
1258 if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
1259 Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
1266 if (!Result.isOverdefined())
1271 // If the edge was formed by a switch on the value, then we may know exactly
1273 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1274 Value *Condition = SI->getCondition();
1275 if (!isa<IntegerType>(Val->getType()))
1277 bool ValUsesConditionAndMayBeFoldable = false;
1278 if (Condition != Val) {
1279 // Check if Val has Condition as an operand.
1280 if (User *Usr = dyn_cast<User>(Val))
1281 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1282 usesOperand(Usr, Condition);
1283 if (!ValUsesConditionAndMayBeFoldable)
1286 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1287 "Condition != Val nor Val doesn't use Condition");
1289 bool DefaultCase = SI->getDefaultDest() == BBTo;
1290 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1291 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1293 for (auto Case : SI->cases()) {
1294 APInt CaseValue = Case.getCaseValue()->getValue();
1295 ConstantRange EdgeVal(CaseValue);
1296 if (ValUsesConditionAndMayBeFoldable) {
1297 User *Usr = cast<User>(Val);
1298 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1299 ValueLatticeElement EdgeLatticeVal =
1300 constantFoldUser(Usr, Condition, CaseValue, DL);
1301 if (EdgeLatticeVal.isOverdefined())
1303 EdgeVal = EdgeLatticeVal.getConstantRange();
1306 // It is possible that the default destination is the destination of
1307 // some cases. We cannot perform difference for those cases.
1308 // We know Condition != CaseValue in BBTo. In some cases we can use
1309 // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1310 // only do this when f is identity (i.e. Val == Condition), but we
1311 // should be able to do this for any injective f.
1312 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1313 EdgesVals = EdgesVals.difference(EdgeVal);
1314 } else if (Case.getCaseSuccessor() == BBTo)
1315 EdgesVals = EdgesVals.unionWith(EdgeVal);
1317 Result = ValueLatticeElement::getRange(std::move(EdgesVals));
1323 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1324 /// the basic block if the edge does not constrain Val.
1325 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1327 ValueLatticeElement &Result,
1328 Instruction *CxtI) {
1329 // If already a constant, there is nothing to compute.
1330 if (Constant *VC = dyn_cast<Constant>(Val)) {
1331 Result = ValueLatticeElement::get(VC);
1335 ValueLatticeElement LocalResult;
1336 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1337 // If we couldn't constrain the value on the edge, LocalResult doesn't
1338 // provide any information.
1339 LocalResult = ValueLatticeElement::getOverdefined();
1341 if (hasSingleValue(LocalResult)) {
1342 // Can't get any more precise here
1343 Result = LocalResult;
1347 if (!hasBlockValue(Val, BBFrom)) {
1348 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1350 // No new information.
1351 Result = LocalResult;
1355 // Try to intersect ranges of the BB and the constraint on the edge.
1356 ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
1357 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1358 BBFrom->getTerminator());
1359 // We can use the context instruction (generically the ultimate instruction
1360 // the calling pass is trying to simplify) here, even though the result of
1361 // this function is generally cached when called from the solve* functions
1362 // (and that cached result might be used with queries using a different
1363 // context instruction), because when this function is called from the solve*
1364 // functions, the context instruction is not provided. When called from
1365 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1366 // but then the result is not cached.
1367 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1369 Result = intersect(LocalResult, InBlock);
1373 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1374 Instruction *CxtI) {
1375 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1376 << BB->getName() << "'\n");
1378 assert(BlockValueStack.empty() && BlockValueSet.empty());
1379 if (!hasBlockValue(V, BB)) {
1380 pushBlockValue(std::make_pair(BB, V));
1383 ValueLatticeElement Result = getBlockValue(V, BB);
1384 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1386 DEBUG(dbgs() << " Result = " << Result << "\n");
1390 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1391 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1392 << CxtI->getName() << "'\n");
1394 if (auto *C = dyn_cast<Constant>(V))
1395 return ValueLatticeElement::get(C);
1397 ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1398 if (auto *I = dyn_cast<Instruction>(V))
1399 Result = getFromRangeMetadata(I);
1400 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1402 DEBUG(dbgs() << " Result = " << Result << "\n");
1406 ValueLatticeElement LazyValueInfoImpl::
1407 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1408 Instruction *CxtI) {
1409 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1410 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1412 ValueLatticeElement Result;
1413 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1415 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1417 assert(WasFastQuery && "More work to do after problem solved?");
1420 DEBUG(dbgs() << " Result = " << Result << "\n");
1424 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1425 BasicBlock *NewSucc) {
1426 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1429 //===----------------------------------------------------------------------===//
1430 // LazyValueInfo Impl
1431 //===----------------------------------------------------------------------===//
1433 /// This lazily constructs the LazyValueInfoImpl.
1434 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1435 const DataLayout *DL,
1436 DominatorTree *DT = nullptr) {
1438 assert(DL && "getCache() called with a null DataLayout");
1439 PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1441 return *static_cast<LazyValueInfoImpl*>(PImpl);
1444 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1445 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1446 const DataLayout &DL = F.getParent()->getDataLayout();
1448 DominatorTreeWrapperPass *DTWP =
1449 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1450 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1451 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1454 getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1460 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1461 AU.setPreservesAll();
1462 AU.addRequired<AssumptionCacheTracker>();
1463 AU.addRequired<TargetLibraryInfoWrapperPass>();
1466 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1468 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1470 void LazyValueInfo::releaseMemory() {
1471 // If the cache was allocated, free it.
1473 delete &getImpl(PImpl, AC, nullptr);
1478 bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1479 FunctionAnalysisManager::Invalidator &Inv) {
1480 // We need to invalidate if we have either failed to preserve this analyses
1481 // result directly or if any of its dependencies have been invalidated.
1482 auto PAC = PA.getChecker<LazyValueAnalysis>();
1483 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1484 (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1490 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1492 LazyValueInfo LazyValueAnalysis::run(Function &F,
1493 FunctionAnalysisManager &FAM) {
1494 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1495 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1496 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1498 return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1501 /// Returns true if we can statically tell that this value will never be a
1502 /// "useful" constant. In practice, this means we've got something like an
1503 /// alloca or a malloc call for which a comparison against a constant can
1504 /// only be guarding dead code. Note that we are potentially giving up some
1505 /// precision in dead code (a constant result) in favour of avoiding a
1506 /// expensive search for a easily answered common query.
1507 static bool isKnownNonConstant(Value *V) {
1508 V = V->stripPointerCasts();
1509 // The return val of alloc cannot be a Constant.
1510 if (isa<AllocaInst>(V))
1515 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1516 Instruction *CxtI) {
1517 // Bail out early if V is known not to be a Constant.
1518 if (isKnownNonConstant(V))
1521 const DataLayout &DL = BB->getModule()->getDataLayout();
1522 ValueLatticeElement Result =
1523 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1525 if (Result.isConstant())
1526 return Result.getConstant();
1527 if (Result.isConstantRange()) {
1528 const ConstantRange &CR = Result.getConstantRange();
1529 if (const APInt *SingleVal = CR.getSingleElement())
1530 return ConstantInt::get(V->getContext(), *SingleVal);
1535 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1536 Instruction *CxtI) {
1537 assert(V->getType()->isIntegerTy());
1538 unsigned Width = V->getType()->getIntegerBitWidth();
1539 const DataLayout &DL = BB->getModule()->getDataLayout();
1540 ValueLatticeElement Result =
1541 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1542 if (Result.isUndefined())
1543 return ConstantRange(Width, /*isFullSet=*/false);
1544 if (Result.isConstantRange())
1545 return Result.getConstantRange();
1546 // We represent ConstantInt constants as constant ranges but other kinds
1547 // of integer constants, i.e. ConstantExpr will be tagged as constants
1548 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1549 "ConstantInt value must be represented as constantrange");
1550 return ConstantRange(Width, /*isFullSet=*/true);
1553 /// Determine whether the specified value is known to be a
1554 /// constant on the specified edge. Return null if not.
1555 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1557 Instruction *CxtI) {
1558 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1559 ValueLatticeElement Result =
1560 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1562 if (Result.isConstant())
1563 return Result.getConstant();
1564 if (Result.isConstantRange()) {
1565 const ConstantRange &CR = Result.getConstantRange();
1566 if (const APInt *SingleVal = CR.getSingleElement())
1567 return ConstantInt::get(V->getContext(), *SingleVal);
1572 ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
1575 Instruction *CxtI) {
1576 unsigned Width = V->getType()->getIntegerBitWidth();
1577 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1578 ValueLatticeElement Result =
1579 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1581 if (Result.isUndefined())
1582 return ConstantRange(Width, /*isFullSet=*/false);
1583 if (Result.isConstantRange())
1584 return Result.getConstantRange();
1585 // We represent ConstantInt constants as constant ranges but other kinds
1586 // of integer constants, i.e. ConstantExpr will be tagged as constants
1587 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1588 "ConstantInt value must be represented as constantrange");
1589 return ConstantRange(Width, /*isFullSet=*/true);
1592 static LazyValueInfo::Tristate
1593 getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1594 const DataLayout &DL, TargetLibraryInfo *TLI) {
1595 // If we know the value is a constant, evaluate the conditional.
1596 Constant *Res = nullptr;
1597 if (Val.isConstant()) {
1598 Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1599 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1600 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1601 return LazyValueInfo::Unknown;
1604 if (Val.isConstantRange()) {
1605 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1606 if (!CI) return LazyValueInfo::Unknown;
1608 const ConstantRange &CR = Val.getConstantRange();
1609 if (Pred == ICmpInst::ICMP_EQ) {
1610 if (!CR.contains(CI->getValue()))
1611 return LazyValueInfo::False;
1613 if (CR.isSingleElement())
1614 return LazyValueInfo::True;
1615 } else if (Pred == ICmpInst::ICMP_NE) {
1616 if (!CR.contains(CI->getValue()))
1617 return LazyValueInfo::True;
1619 if (CR.isSingleElement())
1620 return LazyValueInfo::False;
1622 // Handle more complex predicates.
1623 ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1624 (ICmpInst::Predicate)Pred, CI->getValue());
1625 if (TrueValues.contains(CR))
1626 return LazyValueInfo::True;
1627 if (TrueValues.inverse().contains(CR))
1628 return LazyValueInfo::False;
1630 return LazyValueInfo::Unknown;
1633 if (Val.isNotConstant()) {
1634 // If this is an equality comparison, we can try to fold it knowing that
1636 if (Pred == ICmpInst::ICMP_EQ) {
1637 // !C1 == C -> false iff C1 == C.
1638 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1639 Val.getNotConstant(), C, DL,
1641 if (Res->isNullValue())
1642 return LazyValueInfo::False;
1643 } else if (Pred == ICmpInst::ICMP_NE) {
1644 // !C1 != C -> true iff C1 == C.
1645 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1646 Val.getNotConstant(), C, DL,
1648 if (Res->isNullValue())
1649 return LazyValueInfo::True;
1651 return LazyValueInfo::Unknown;
1654 return LazyValueInfo::Unknown;
1657 /// Determine whether the specified value comparison with a constant is known to
1658 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1659 LazyValueInfo::Tristate
1660 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1661 BasicBlock *FromBB, BasicBlock *ToBB,
1662 Instruction *CxtI) {
1663 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1664 ValueLatticeElement Result =
1665 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1667 return getPredicateResult(Pred, C, Result, DL, TLI);
1670 LazyValueInfo::Tristate
1671 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1672 Instruction *CxtI) {
1673 // Is or is not NonNull are common predicates being queried. If
1674 // isKnownNonZero can tell us the result of the predicate, we can
1675 // return it quickly. But this is only a fastpath, and falling
1676 // through would still be correct.
1677 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1678 if (V->getType()->isPointerTy() && C->isNullValue() &&
1679 isKnownNonZero(V->stripPointerCasts(), DL)) {
1680 if (Pred == ICmpInst::ICMP_EQ)
1681 return LazyValueInfo::False;
1682 else if (Pred == ICmpInst::ICMP_NE)
1683 return LazyValueInfo::True;
1685 ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1686 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1690 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1691 // LVI as a whole tries to compute a lattice value which is conservatively
1692 // correct at a given location. In this case, we have a predicate which we
1693 // weren't able to prove about the merged result, and we're pushing that
1694 // predicate back along each incoming edge to see if we can prove it
1695 // separately for each input. As a motivating example, consider:
1697 // %v1 = ... ; constantrange<1, 5>
1700 // %v2 = ... ; constantrange<10, 20>
1703 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1704 // %pred = icmp eq i32 %phi, 8
1705 // We can't tell from the lattice value for '%phi' that '%pred' is false
1706 // along each path, but by checking the predicate over each input separately,
1708 // We limit the search to one step backwards from the current BB and value.
1709 // We could consider extending this to search further backwards through the
1710 // CFG and/or value graph, but there are non-obvious compile time vs quality
1713 BasicBlock *BB = CxtI->getParent();
1715 // Function entry or an unreachable block. Bail to avoid confusing
1717 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1721 // If V is a PHI node in the same block as the context, we need to ask
1722 // questions about the predicate as applied to the incoming value along
1723 // each edge. This is useful for eliminating cases where the predicate is
1724 // known along all incoming edges.
1725 if (auto *PHI = dyn_cast<PHINode>(V))
1726 if (PHI->getParent() == BB) {
1727 Tristate Baseline = Unknown;
1728 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1729 Value *Incoming = PHI->getIncomingValue(i);
1730 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1731 // Note that PredBB may be BB itself.
1732 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1735 // Keep going as long as we've seen a consistent known result for
1737 Baseline = (i == 0) ? Result /* First iteration */
1738 : (Baseline == Result ? Baseline : Unknown); /* All others */
1739 if (Baseline == Unknown)
1742 if (Baseline != Unknown)
1746 // For a comparison where the V is outside this block, it's possible
1747 // that we've branched on it before. Look to see if the value is known
1748 // on all incoming edges.
1749 if (!isa<Instruction>(V) ||
1750 cast<Instruction>(V)->getParent() != BB) {
1751 // For predecessor edge, determine if the comparison is true or false
1752 // on that edge. If they're all true or all false, we can conclude
1753 // the value of the comparison in this block.
1754 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1755 if (Baseline != Unknown) {
1756 // Check that all remaining incoming values match the first one.
1757 while (++PI != PE) {
1758 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1759 if (Ret != Baseline) break;
1761 // If we terminated early, then one of the values didn't match.
1771 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1772 BasicBlock *NewSucc) {
1774 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1775 getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1779 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1781 const DataLayout &DL = BB->getModule()->getDataLayout();
1782 getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1787 void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
1789 getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1793 // Print the LVI for the function arguments at the start of each basic block.
1794 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1795 const BasicBlock *BB, formatted_raw_ostream &OS) {
1796 // Find if there are latticevalues defined for arguments of the function.
1797 auto *F = BB->getParent();
1798 for (auto &Arg : F->args()) {
1799 ValueLatticeElement Result = LVIImpl->getValueInBlock(
1800 const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1801 if (Result.isUndefined())
1803 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1807 // This function prints the LVI analysis for the instruction I at the beginning
1808 // of various basic blocks. It relies on calculated values that are stored in
1809 // the LazyValueInfoCache, and in the absence of cached values, recalculte the
1810 // LazyValueInfo for `I`, and print that info.
1811 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1812 const Instruction *I, formatted_raw_ostream &OS) {
1814 auto *ParentBB = I->getParent();
1815 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1816 // We can generate (solve) LVI values only for blocks that are dominated by
1817 // the I's parent. However, to avoid generating LVI for all dominating blocks,
1818 // that contain redundant/uninteresting information, we print LVI for
1819 // blocks that may use this LVI information (such as immediate successor
1820 // blocks, and blocks that contain uses of `I`).
1821 auto printResult = [&](const BasicBlock *BB) {
1822 if (!BlocksContainingLVI.insert(BB).second)
1824 ValueLatticeElement Result = LVIImpl->getValueInBlock(
1825 const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1826 OS << "; LatticeVal for: '" << *I << "' in BB: '";
1827 BB->printAsOperand(OS, false);
1828 OS << "' is: " << Result << "\n";
1831 printResult(ParentBB);
1832 // Print the LVI analysis results for the the immediate successor blocks, that
1833 // are dominated by `ParentBB`.
1834 for (auto *BBSucc : successors(ParentBB))
1835 if (DT.dominates(ParentBB, BBSucc))
1836 printResult(BBSucc);
1838 // Print LVI in blocks where `I` is used.
1839 for (auto *U : I->users())
1840 if (auto *UseI = dyn_cast<Instruction>(U))
1841 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1842 printResult(UseI->getParent());
1847 // Printer class for LazyValueInfo results.
1848 class LazyValueInfoPrinter : public FunctionPass {
1850 static char ID; // Pass identification, replacement for typeid
1851 LazyValueInfoPrinter() : FunctionPass(ID) {
1852 initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
1855 void getAnalysisUsage(AnalysisUsage &AU) const override {
1856 AU.setPreservesAll();
1857 AU.addRequired<LazyValueInfoWrapperPass>();
1858 AU.addRequired<DominatorTreeWrapperPass>();
1861 // Get the mandatory dominator tree analysis and pass this in to the
1862 // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
1863 bool runOnFunction(Function &F) override {
1864 dbgs() << "LVI for function '" << F.getName() << "':\n";
1865 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1866 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1867 LVI.printLVI(F, DTree, dbgs());
1873 char LazyValueInfoPrinter::ID = 0;
1874 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1875 "Lazy Value Info Printer Pass", false, false)
1876 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
1877 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1878 "Lazy Value Info Printer Pass", false, false)