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::AShr:
1006 case Instruction::And:
1007 case Instruction::Or:
1008 // continue into the code below
1011 // Unhandled instructions are overdefined.
1012 DEBUG(dbgs() << " compute BB '" << BB->getName()
1013 << "' - overdefined (unknown binary operator).\n");
1014 BBLV = ValueLatticeElement::getOverdefined();
1018 // Figure out the range of the LHS. If that fails, use a conservative range,
1019 // but apply the transfer rule anyways. This lets us pick up facts from
1020 // expressions like "and i32 (call i32 @foo()), 32"
1021 if (!hasBlockValue(BO->getOperand(0), BB))
1022 if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
1023 // More work to do before applying this transfer rule.
1026 const unsigned OperandBitWidth =
1027 DL.getTypeSizeInBits(BO->getOperand(0)->getType());
1028 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1029 if (hasBlockValue(BO->getOperand(0), BB)) {
1030 ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
1031 intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
1033 if (LHSVal.isConstantRange())
1034 LHSRange = LHSVal.getConstantRange();
1037 ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
1038 ConstantRange RHSRange = ConstantRange(RHS->getValue());
1040 // NOTE: We're currently limited by the set of operations that ConstantRange
1041 // can evaluate symbolically. Enhancing that set will allows us to analyze
1042 // more definitions.
1043 Instruction::BinaryOps BinOp = BO->getOpcode();
1044 BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1048 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1050 Value *LHS = ICI->getOperand(0);
1051 Value *RHS = ICI->getOperand(1);
1052 CmpInst::Predicate Predicate = ICI->getPredicate();
1054 if (isa<Constant>(RHS)) {
1055 if (ICI->isEquality() && LHS == Val) {
1056 // We know that V has the RHS constant if this is a true SETEQ or
1058 if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1059 return ValueLatticeElement::get(cast<Constant>(RHS));
1061 return ValueLatticeElement::getNot(cast<Constant>(RHS));
1065 if (!Val->getType()->isIntegerTy())
1066 return ValueLatticeElement::getOverdefined();
1068 // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1069 // range of Val guaranteed by the condition. Recognize comparisons in the from
1071 // icmp <pred> Val, ...
1072 // icmp <pred> (add Val, Offset), ...
1073 // The latter is the range checking idiom that InstCombine produces. Subtract
1074 // the offset from the allowed range for RHS in this case.
1076 // Val or (add Val, Offset) can be on either hand of the comparison
1077 if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1078 std::swap(LHS, RHS);
1079 Predicate = CmpInst::getSwappedPredicate(Predicate);
1082 ConstantInt *Offset = nullptr;
1084 match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1086 if (LHS == Val || Offset) {
1087 // Calculate the range of values that are allowed by the comparison
1088 ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1089 /*isFullSet=*/true);
1090 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1091 RHSRange = ConstantRange(CI->getValue());
1092 else if (Instruction *I = dyn_cast<Instruction>(RHS))
1093 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1094 RHSRange = getConstantRangeFromMetadata(*Ranges);
1096 // If we're interested in the false dest, invert the condition
1097 CmpInst::Predicate Pred =
1098 isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1099 ConstantRange TrueValues =
1100 ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1102 if (Offset) // Apply the offset from above.
1103 TrueValues = TrueValues.subtract(Offset->getValue());
1105 return ValueLatticeElement::getRange(std::move(TrueValues));
1108 return ValueLatticeElement::getOverdefined();
1111 static ValueLatticeElement
1112 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1113 DenseMap<Value*, ValueLatticeElement> &Visited);
1115 static ValueLatticeElement
1116 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1117 DenseMap<Value*, ValueLatticeElement> &Visited) {
1118 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1119 return getValueFromICmpCondition(Val, ICI, isTrueDest);
1121 // Handle conditions in the form of (cond1 && cond2), we know that on the
1122 // true dest path both of the conditions hold. Similarly for conditions of
1123 // the form (cond1 || cond2), we know that on the false dest path neither
1125 BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1126 if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
1127 (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
1128 return ValueLatticeElement::getOverdefined();
1130 auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
1131 auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
1132 return intersect(RHS, LHS);
1135 static ValueLatticeElement
1136 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1137 DenseMap<Value*, ValueLatticeElement> &Visited) {
1138 auto I = Visited.find(Cond);
1139 if (I != Visited.end())
1142 auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1143 Visited[Cond] = Result;
1147 ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
1149 assert(Cond && "precondition");
1150 DenseMap<Value*, ValueLatticeElement> Visited;
1151 return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1154 // Return true if Usr has Op as an operand, otherwise false.
1155 static bool usesOperand(User *Usr, Value *Op) {
1156 return find(Usr->operands(), Op) != Usr->op_end();
1159 // Return true if the instruction type of Val is supported by
1160 // constantFoldUser(). Currently CastInst and BinaryOperator only. Call this
1161 // before calling constantFoldUser() to find out if it's even worth attempting
1163 static bool isOperationFoldable(User *Usr) {
1164 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
1167 // Check if Usr can be simplified to an integer constant when the value of one
1168 // of its operands Op is an integer constant OpConstVal. If so, return it as an
1169 // lattice value range with a single element or otherwise return an overdefined
1171 static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1172 const APInt &OpConstVal,
1173 const DataLayout &DL) {
1174 assert(isOperationFoldable(Usr) && "Precondition");
1175 Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1176 // Check if Usr can be simplified to a constant.
1177 if (auto *CI = dyn_cast<CastInst>(Usr)) {
1178 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1179 if (auto *C = dyn_cast_or_null<ConstantInt>(
1180 SimplifyCastInst(CI->getOpcode(), OpConst,
1181 CI->getDestTy(), DL))) {
1182 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1184 } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1185 bool Op0Match = BO->getOperand(0) == Op;
1186 bool Op1Match = BO->getOperand(1) == Op;
1187 assert((Op0Match || Op1Match) &&
1188 "Operand 0 nor Operand 1 isn't a match");
1189 Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1190 Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1191 if (auto *C = dyn_cast_or_null<ConstantInt>(
1192 SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1193 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1196 return ValueLatticeElement::getOverdefined();
1199 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1200 /// Val is not constrained on the edge. Result is unspecified if return value
1202 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1203 BasicBlock *BBTo, ValueLatticeElement &Result) {
1204 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1205 // know that v != 0.
1206 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1207 // If this is a conditional branch and only one successor goes to BBTo, then
1208 // we may be able to infer something from the condition.
1209 if (BI->isConditional() &&
1210 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1211 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1212 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1213 "BBTo isn't a successor of BBFrom");
1214 Value *Condition = BI->getCondition();
1216 // If V is the condition of the branch itself, then we know exactly what
1218 if (Condition == Val) {
1219 Result = ValueLatticeElement::get(ConstantInt::get(
1220 Type::getInt1Ty(Val->getContext()), isTrueDest));
1224 // If the condition of the branch is an equality comparison, we may be
1225 // able to infer the value.
1226 Result = getValueFromCondition(Val, Condition, isTrueDest);
1227 if (!Result.isOverdefined())
1230 if (User *Usr = dyn_cast<User>(Val)) {
1231 assert(Result.isOverdefined() && "Result isn't overdefined");
1232 // Check with isOperationFoldable() first to avoid linearly iterating
1233 // over the operands unnecessarily which can be expensive for
1234 // instructions with many operands.
1235 if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1236 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1237 if (usesOperand(Usr, Condition)) {
1238 // If Val has Condition as an operand and Val can be folded into a
1239 // constant with either Condition == true or Condition == false,
1240 // propagate the constant.
1242 // ; %Val is true on the edge to %then.
1243 // %Val = and i1 %Condition, true.
1244 // br %Condition, label %then, label %else
1245 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1246 Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1248 // If one of Val's operand has an inferred value, we may be able to
1249 // infer the value of Val.
1251 // ; %Val is 94 on the edge to %then.
1252 // %Val = add i8 %Op, 1
1253 // %Condition = icmp eq i8 %Op, 93
1254 // br i1 %Condition, label %then, label %else
1255 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1256 Value *Op = Usr->getOperand(i);
1257 ValueLatticeElement OpLatticeVal =
1258 getValueFromCondition(Op, Condition, isTrueDest);
1259 if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
1260 Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
1267 if (!Result.isOverdefined())
1272 // If the edge was formed by a switch on the value, then we may know exactly
1274 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1275 Value *Condition = SI->getCondition();
1276 if (!isa<IntegerType>(Val->getType()))
1278 bool ValUsesConditionAndMayBeFoldable = false;
1279 if (Condition != Val) {
1280 // Check if Val has Condition as an operand.
1281 if (User *Usr = dyn_cast<User>(Val))
1282 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1283 usesOperand(Usr, Condition);
1284 if (!ValUsesConditionAndMayBeFoldable)
1287 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1288 "Condition != Val nor Val doesn't use Condition");
1290 bool DefaultCase = SI->getDefaultDest() == BBTo;
1291 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1292 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1294 for (auto Case : SI->cases()) {
1295 APInt CaseValue = Case.getCaseValue()->getValue();
1296 ConstantRange EdgeVal(CaseValue);
1297 if (ValUsesConditionAndMayBeFoldable) {
1298 User *Usr = cast<User>(Val);
1299 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1300 ValueLatticeElement EdgeLatticeVal =
1301 constantFoldUser(Usr, Condition, CaseValue, DL);
1302 if (EdgeLatticeVal.isOverdefined())
1304 EdgeVal = EdgeLatticeVal.getConstantRange();
1307 // It is possible that the default destination is the destination of
1308 // some cases. We cannot perform difference for those cases.
1309 // We know Condition != CaseValue in BBTo. In some cases we can use
1310 // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1311 // only do this when f is identity (i.e. Val == Condition), but we
1312 // should be able to do this for any injective f.
1313 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1314 EdgesVals = EdgesVals.difference(EdgeVal);
1315 } else if (Case.getCaseSuccessor() == BBTo)
1316 EdgesVals = EdgesVals.unionWith(EdgeVal);
1318 Result = ValueLatticeElement::getRange(std::move(EdgesVals));
1324 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1325 /// the basic block if the edge does not constrain Val.
1326 bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1328 ValueLatticeElement &Result,
1329 Instruction *CxtI) {
1330 // If already a constant, there is nothing to compute.
1331 if (Constant *VC = dyn_cast<Constant>(Val)) {
1332 Result = ValueLatticeElement::get(VC);
1336 ValueLatticeElement LocalResult;
1337 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1338 // If we couldn't constrain the value on the edge, LocalResult doesn't
1339 // provide any information.
1340 LocalResult = ValueLatticeElement::getOverdefined();
1342 if (hasSingleValue(LocalResult)) {
1343 // Can't get any more precise here
1344 Result = LocalResult;
1348 if (!hasBlockValue(Val, BBFrom)) {
1349 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1351 // No new information.
1352 Result = LocalResult;
1356 // Try to intersect ranges of the BB and the constraint on the edge.
1357 ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
1358 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1359 BBFrom->getTerminator());
1360 // We can use the context instruction (generically the ultimate instruction
1361 // the calling pass is trying to simplify) here, even though the result of
1362 // this function is generally cached when called from the solve* functions
1363 // (and that cached result might be used with queries using a different
1364 // context instruction), because when this function is called from the solve*
1365 // functions, the context instruction is not provided. When called from
1366 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1367 // but then the result is not cached.
1368 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1370 Result = intersect(LocalResult, InBlock);
1374 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1375 Instruction *CxtI) {
1376 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1377 << BB->getName() << "'\n");
1379 assert(BlockValueStack.empty() && BlockValueSet.empty());
1380 if (!hasBlockValue(V, BB)) {
1381 pushBlockValue(std::make_pair(BB, V));
1384 ValueLatticeElement Result = getBlockValue(V, BB);
1385 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1387 DEBUG(dbgs() << " Result = " << Result << "\n");
1391 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1392 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1393 << CxtI->getName() << "'\n");
1395 if (auto *C = dyn_cast<Constant>(V))
1396 return ValueLatticeElement::get(C);
1398 ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1399 if (auto *I = dyn_cast<Instruction>(V))
1400 Result = getFromRangeMetadata(I);
1401 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1403 DEBUG(dbgs() << " Result = " << Result << "\n");
1407 ValueLatticeElement LazyValueInfoImpl::
1408 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1409 Instruction *CxtI) {
1410 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1411 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1413 ValueLatticeElement Result;
1414 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1416 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1418 assert(WasFastQuery && "More work to do after problem solved?");
1421 DEBUG(dbgs() << " Result = " << Result << "\n");
1425 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1426 BasicBlock *NewSucc) {
1427 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1430 //===----------------------------------------------------------------------===//
1431 // LazyValueInfo Impl
1432 //===----------------------------------------------------------------------===//
1434 /// This lazily constructs the LazyValueInfoImpl.
1435 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1436 const DataLayout *DL,
1437 DominatorTree *DT = nullptr) {
1439 assert(DL && "getCache() called with a null DataLayout");
1440 PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1442 return *static_cast<LazyValueInfoImpl*>(PImpl);
1445 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1446 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1447 const DataLayout &DL = F.getParent()->getDataLayout();
1449 DominatorTreeWrapperPass *DTWP =
1450 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1451 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1452 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1455 getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1461 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1462 AU.setPreservesAll();
1463 AU.addRequired<AssumptionCacheTracker>();
1464 AU.addRequired<TargetLibraryInfoWrapperPass>();
1467 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1469 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1471 void LazyValueInfo::releaseMemory() {
1472 // If the cache was allocated, free it.
1474 delete &getImpl(PImpl, AC, nullptr);
1479 bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1480 FunctionAnalysisManager::Invalidator &Inv) {
1481 // We need to invalidate if we have either failed to preserve this analyses
1482 // result directly or if any of its dependencies have been invalidated.
1483 auto PAC = PA.getChecker<LazyValueAnalysis>();
1484 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1485 (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1491 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1493 LazyValueInfo LazyValueAnalysis::run(Function &F,
1494 FunctionAnalysisManager &FAM) {
1495 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1496 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1497 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1499 return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1502 /// Returns true if we can statically tell that this value will never be a
1503 /// "useful" constant. In practice, this means we've got something like an
1504 /// alloca or a malloc call for which a comparison against a constant can
1505 /// only be guarding dead code. Note that we are potentially giving up some
1506 /// precision in dead code (a constant result) in favour of avoiding a
1507 /// expensive search for a easily answered common query.
1508 static bool isKnownNonConstant(Value *V) {
1509 V = V->stripPointerCasts();
1510 // The return val of alloc cannot be a Constant.
1511 if (isa<AllocaInst>(V))
1516 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1517 Instruction *CxtI) {
1518 // Bail out early if V is known not to be a Constant.
1519 if (isKnownNonConstant(V))
1522 const DataLayout &DL = BB->getModule()->getDataLayout();
1523 ValueLatticeElement Result =
1524 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1526 if (Result.isConstant())
1527 return Result.getConstant();
1528 if (Result.isConstantRange()) {
1529 const ConstantRange &CR = Result.getConstantRange();
1530 if (const APInt *SingleVal = CR.getSingleElement())
1531 return ConstantInt::get(V->getContext(), *SingleVal);
1536 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1537 Instruction *CxtI) {
1538 assert(V->getType()->isIntegerTy());
1539 unsigned Width = V->getType()->getIntegerBitWidth();
1540 const DataLayout &DL = BB->getModule()->getDataLayout();
1541 ValueLatticeElement Result =
1542 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1543 if (Result.isUndefined())
1544 return ConstantRange(Width, /*isFullSet=*/false);
1545 if (Result.isConstantRange())
1546 return Result.getConstantRange();
1547 // We represent ConstantInt constants as constant ranges but other kinds
1548 // of integer constants, i.e. ConstantExpr will be tagged as constants
1549 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1550 "ConstantInt value must be represented as constantrange");
1551 return ConstantRange(Width, /*isFullSet=*/true);
1554 /// Determine whether the specified value is known to be a
1555 /// constant on the specified edge. Return null if not.
1556 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1558 Instruction *CxtI) {
1559 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1560 ValueLatticeElement Result =
1561 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1563 if (Result.isConstant())
1564 return Result.getConstant();
1565 if (Result.isConstantRange()) {
1566 const ConstantRange &CR = Result.getConstantRange();
1567 if (const APInt *SingleVal = CR.getSingleElement())
1568 return ConstantInt::get(V->getContext(), *SingleVal);
1573 ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
1576 Instruction *CxtI) {
1577 unsigned Width = V->getType()->getIntegerBitWidth();
1578 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1579 ValueLatticeElement Result =
1580 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1582 if (Result.isUndefined())
1583 return ConstantRange(Width, /*isFullSet=*/false);
1584 if (Result.isConstantRange())
1585 return Result.getConstantRange();
1586 // We represent ConstantInt constants as constant ranges but other kinds
1587 // of integer constants, i.e. ConstantExpr will be tagged as constants
1588 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1589 "ConstantInt value must be represented as constantrange");
1590 return ConstantRange(Width, /*isFullSet=*/true);
1593 static LazyValueInfo::Tristate
1594 getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1595 const DataLayout &DL, TargetLibraryInfo *TLI) {
1596 // If we know the value is a constant, evaluate the conditional.
1597 Constant *Res = nullptr;
1598 if (Val.isConstant()) {
1599 Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1600 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1601 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1602 return LazyValueInfo::Unknown;
1605 if (Val.isConstantRange()) {
1606 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1607 if (!CI) return LazyValueInfo::Unknown;
1609 const ConstantRange &CR = Val.getConstantRange();
1610 if (Pred == ICmpInst::ICMP_EQ) {
1611 if (!CR.contains(CI->getValue()))
1612 return LazyValueInfo::False;
1614 if (CR.isSingleElement())
1615 return LazyValueInfo::True;
1616 } else if (Pred == ICmpInst::ICMP_NE) {
1617 if (!CR.contains(CI->getValue()))
1618 return LazyValueInfo::True;
1620 if (CR.isSingleElement())
1621 return LazyValueInfo::False;
1623 // Handle more complex predicates.
1624 ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1625 (ICmpInst::Predicate)Pred, CI->getValue());
1626 if (TrueValues.contains(CR))
1627 return LazyValueInfo::True;
1628 if (TrueValues.inverse().contains(CR))
1629 return LazyValueInfo::False;
1631 return LazyValueInfo::Unknown;
1634 if (Val.isNotConstant()) {
1635 // If this is an equality comparison, we can try to fold it knowing that
1637 if (Pred == ICmpInst::ICMP_EQ) {
1638 // !C1 == C -> false iff C1 == C.
1639 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1640 Val.getNotConstant(), C, DL,
1642 if (Res->isNullValue())
1643 return LazyValueInfo::False;
1644 } else if (Pred == ICmpInst::ICMP_NE) {
1645 // !C1 != C -> true iff C1 == C.
1646 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1647 Val.getNotConstant(), C, DL,
1649 if (Res->isNullValue())
1650 return LazyValueInfo::True;
1652 return LazyValueInfo::Unknown;
1655 return LazyValueInfo::Unknown;
1658 /// Determine whether the specified value comparison with a constant is known to
1659 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1660 LazyValueInfo::Tristate
1661 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1662 BasicBlock *FromBB, BasicBlock *ToBB,
1663 Instruction *CxtI) {
1664 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1665 ValueLatticeElement Result =
1666 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1668 return getPredicateResult(Pred, C, Result, DL, TLI);
1671 LazyValueInfo::Tristate
1672 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1673 Instruction *CxtI) {
1674 // Is or is not NonNull are common predicates being queried. If
1675 // isKnownNonZero can tell us the result of the predicate, we can
1676 // return it quickly. But this is only a fastpath, and falling
1677 // through would still be correct.
1678 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1679 if (V->getType()->isPointerTy() && C->isNullValue() &&
1680 isKnownNonZero(V->stripPointerCasts(), DL)) {
1681 if (Pred == ICmpInst::ICMP_EQ)
1682 return LazyValueInfo::False;
1683 else if (Pred == ICmpInst::ICMP_NE)
1684 return LazyValueInfo::True;
1686 ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1687 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1691 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1692 // LVI as a whole tries to compute a lattice value which is conservatively
1693 // correct at a given location. In this case, we have a predicate which we
1694 // weren't able to prove about the merged result, and we're pushing that
1695 // predicate back along each incoming edge to see if we can prove it
1696 // separately for each input. As a motivating example, consider:
1698 // %v1 = ... ; constantrange<1, 5>
1701 // %v2 = ... ; constantrange<10, 20>
1704 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1705 // %pred = icmp eq i32 %phi, 8
1706 // We can't tell from the lattice value for '%phi' that '%pred' is false
1707 // along each path, but by checking the predicate over each input separately,
1709 // We limit the search to one step backwards from the current BB and value.
1710 // We could consider extending this to search further backwards through the
1711 // CFG and/or value graph, but there are non-obvious compile time vs quality
1714 BasicBlock *BB = CxtI->getParent();
1716 // Function entry or an unreachable block. Bail to avoid confusing
1718 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1722 // If V is a PHI node in the same block as the context, we need to ask
1723 // questions about the predicate as applied to the incoming value along
1724 // each edge. This is useful for eliminating cases where the predicate is
1725 // known along all incoming edges.
1726 if (auto *PHI = dyn_cast<PHINode>(V))
1727 if (PHI->getParent() == BB) {
1728 Tristate Baseline = Unknown;
1729 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1730 Value *Incoming = PHI->getIncomingValue(i);
1731 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1732 // Note that PredBB may be BB itself.
1733 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1736 // Keep going as long as we've seen a consistent known result for
1738 Baseline = (i == 0) ? Result /* First iteration */
1739 : (Baseline == Result ? Baseline : Unknown); /* All others */
1740 if (Baseline == Unknown)
1743 if (Baseline != Unknown)
1747 // For a comparison where the V is outside this block, it's possible
1748 // that we've branched on it before. Look to see if the value is known
1749 // on all incoming edges.
1750 if (!isa<Instruction>(V) ||
1751 cast<Instruction>(V)->getParent() != BB) {
1752 // For predecessor edge, determine if the comparison is true or false
1753 // on that edge. If they're all true or all false, we can conclude
1754 // the value of the comparison in this block.
1755 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1756 if (Baseline != Unknown) {
1757 // Check that all remaining incoming values match the first one.
1758 while (++PI != PE) {
1759 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1760 if (Ret != Baseline) break;
1762 // If we terminated early, then one of the values didn't match.
1772 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1773 BasicBlock *NewSucc) {
1775 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1776 getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1780 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1782 const DataLayout &DL = BB->getModule()->getDataLayout();
1783 getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1788 void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
1790 getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1794 // Print the LVI for the function arguments at the start of each basic block.
1795 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1796 const BasicBlock *BB, formatted_raw_ostream &OS) {
1797 // Find if there are latticevalues defined for arguments of the function.
1798 auto *F = BB->getParent();
1799 for (auto &Arg : F->args()) {
1800 ValueLatticeElement Result = LVIImpl->getValueInBlock(
1801 const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1802 if (Result.isUndefined())
1804 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1808 // This function prints the LVI analysis for the instruction I at the beginning
1809 // of various basic blocks. It relies on calculated values that are stored in
1810 // the LazyValueInfoCache, and in the absence of cached values, recalculte the
1811 // LazyValueInfo for `I`, and print that info.
1812 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1813 const Instruction *I, formatted_raw_ostream &OS) {
1815 auto *ParentBB = I->getParent();
1816 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1817 // We can generate (solve) LVI values only for blocks that are dominated by
1818 // the I's parent. However, to avoid generating LVI for all dominating blocks,
1819 // that contain redundant/uninteresting information, we print LVI for
1820 // blocks that may use this LVI information (such as immediate successor
1821 // blocks, and blocks that contain uses of `I`).
1822 auto printResult = [&](const BasicBlock *BB) {
1823 if (!BlocksContainingLVI.insert(BB).second)
1825 ValueLatticeElement Result = LVIImpl->getValueInBlock(
1826 const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1827 OS << "; LatticeVal for: '" << *I << "' in BB: '";
1828 BB->printAsOperand(OS, false);
1829 OS << "' is: " << Result << "\n";
1832 printResult(ParentBB);
1833 // Print the LVI analysis results for the the immediate successor blocks, that
1834 // are dominated by `ParentBB`.
1835 for (auto *BBSucc : successors(ParentBB))
1836 if (DT.dominates(ParentBB, BBSucc))
1837 printResult(BBSucc);
1839 // Print LVI in blocks where `I` is used.
1840 for (auto *U : I->users())
1841 if (auto *UseI = dyn_cast<Instruction>(U))
1842 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1843 printResult(UseI->getParent());
1848 // Printer class for LazyValueInfo results.
1849 class LazyValueInfoPrinter : public FunctionPass {
1851 static char ID; // Pass identification, replacement for typeid
1852 LazyValueInfoPrinter() : FunctionPass(ID) {
1853 initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
1856 void getAnalysisUsage(AnalysisUsage &AU) const override {
1857 AU.setPreservesAll();
1858 AU.addRequired<LazyValueInfoWrapperPass>();
1859 AU.addRequired<DominatorTreeWrapperPass>();
1862 // Get the mandatory dominator tree analysis and pass this in to the
1863 // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
1864 bool runOnFunction(Function &F) override {
1865 dbgs() << "LVI for function '" << F.getName() << "':\n";
1866 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1867 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1868 LVI.printLVI(F, DTree, dbgs());
1874 char LazyValueInfoPrinter::ID = 0;
1875 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1876 "Lazy Value Info Printer Pass", false, false)
1877 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
1878 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1879 "Lazy Value Info Printer Pass", false, false)