1 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file defines the interface for lazy computation of value constraint
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/LazyValueInfo.h"
15 #include "llvm/ADT/DenseSet.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/Analysis/AssumptionCache.h"
18 #include "llvm/Analysis/ConstantFolding.h"
19 #include "llvm/Analysis/InstructionSimplify.h"
20 #include "llvm/Analysis/TargetLibraryInfo.h"
21 #include "llvm/Analysis/ValueLattice.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/IR/AssemblyAnnotationWriter.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/ConstantRange.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/Intrinsics.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/PatternMatch.h"
34 #include "llvm/IR/ValueHandle.h"
35 #include "llvm/InitializePasses.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/FormattedStream.h"
38 #include "llvm/Support/KnownBits.h"
39 #include "llvm/Support/raw_ostream.h"
42 using namespace PatternMatch;
44 #define DEBUG_TYPE "lazy-value-info"
46 // This is the number of worklist items we will process to try to discover an
47 // answer for a given value.
48 static const unsigned MaxProcessedPerValue = 500;
50 char LazyValueInfoWrapperPass::ID = 0;
51 LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) {
52 initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry());
54 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
55 "Lazy Value Information Analysis", false, true)
56 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
57 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
58 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
59 "Lazy Value Information Analysis", false, true)
62 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
65 AnalysisKey LazyValueAnalysis::Key;
67 /// Returns true if this lattice value represents at most one possible value.
68 /// This is as precise as any lattice value can get while still representing
70 static bool hasSingleValue(const ValueLatticeElement &Val) {
71 if (Val.isConstantRange() &&
72 Val.getConstantRange().isSingleElement())
73 // Integer constants are single element ranges
76 // Non integer constants
81 /// Combine two sets of facts about the same value into a single set of
82 /// facts. Note that this method is not suitable for merging facts along
83 /// different paths in a CFG; that's what the mergeIn function is for. This
84 /// is for merging facts gathered about the same value at the same location
85 /// through two independent means.
87 /// * This method does not promise to return the most precise possible lattice
88 /// value implied by A and B. It is allowed to return any lattice element
89 /// which is at least as strong as *either* A or B (unless our facts
90 /// conflict, see below).
91 /// * Due to unreachable code, the intersection of two lattice values could be
92 /// contradictory. If this happens, we return some valid lattice value so as
93 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
94 /// we do not make this guarantee. TODO: This would be a useful enhancement.
95 static ValueLatticeElement intersect(const ValueLatticeElement &A,
96 const ValueLatticeElement &B) {
97 // Undefined is the strongest state. It means the value is known to be along
98 // an unreachable path.
104 // If we gave up for one, but got a useable fact from the other, use it.
105 if (A.isOverdefined())
107 if (B.isOverdefined())
110 // Can't get any more precise than constants.
111 if (hasSingleValue(A))
113 if (hasSingleValue(B))
116 // Could be either constant range or not constant here.
117 if (!A.isConstantRange() || !B.isConstantRange()) {
118 // TODO: Arbitrary choice, could be improved
122 // Intersect two constant ranges
123 ConstantRange Range =
124 A.getConstantRange().intersectWith(B.getConstantRange());
125 // Note: An empty range is implicitly converted to unknown or undef depending
126 // on MayIncludeUndef internally.
127 return ValueLatticeElement::getRange(
128 std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() ||
129 B.isConstantRangeIncludingUndef());
132 //===----------------------------------------------------------------------===//
133 // LazyValueInfoCache Decl
134 //===----------------------------------------------------------------------===//
137 /// A callback value handle updates the cache when values are erased.
138 class LazyValueInfoCache;
139 struct LVIValueHandle final : public CallbackVH {
140 LazyValueInfoCache *Parent;
142 LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr)
143 : CallbackVH(V), Parent(P) { }
145 void deleted() override;
146 void allUsesReplacedWith(Value *V) override {
150 } // end anonymous namespace
153 using NonNullPointerSet = SmallDenseSet<AssertingVH<Value>, 2>;
155 /// This is the cache kept by LazyValueInfo which
156 /// maintains information about queries across the clients' queries.
157 class LazyValueInfoCache {
158 /// This is all of the cached information for one basic block. It contains
159 /// the per-value lattice elements, as well as a separate set for
160 /// overdefined values to reduce memory usage. Additionally pointers
161 /// dereferenced in the block are cached for nullability queries.
162 struct BlockCacheEntry {
163 SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
164 SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
165 // std::nullopt indicates that the nonnull pointers for this basic block
166 // block have not been computed yet.
167 std::optional<NonNullPointerSet> NonNullPointers;
170 /// Cached information per basic block.
171 DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>>
173 /// Set of value handles used to erase values from the cache on deletion.
174 DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
176 const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const {
177 auto It = BlockCache.find_as(BB);
178 if (It == BlockCache.end())
180 return It->second.get();
183 BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {
184 auto It = BlockCache.find_as(BB);
185 if (It == BlockCache.end())
186 It = BlockCache.insert({ BB, std::make_unique<BlockCacheEntry>() })
189 return It->second.get();
192 void addValueHandle(Value *Val) {
193 auto HandleIt = ValueHandles.find_as(Val);
194 if (HandleIt == ValueHandles.end())
195 ValueHandles.insert({ Val, this });
199 void insertResult(Value *Val, BasicBlock *BB,
200 const ValueLatticeElement &Result) {
201 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
203 // Insert over-defined values into their own cache to reduce memory
205 if (Result.isOverdefined())
206 Entry->OverDefined.insert(Val);
208 Entry->LatticeElements.insert({ Val, Result });
213 std::optional<ValueLatticeElement>
214 getCachedValueInfo(Value *V, BasicBlock *BB) const {
215 const BlockCacheEntry *Entry = getBlockEntry(BB);
219 if (Entry->OverDefined.count(V))
220 return ValueLatticeElement::getOverdefined();
222 auto LatticeIt = Entry->LatticeElements.find_as(V);
223 if (LatticeIt == Entry->LatticeElements.end())
226 return LatticeIt->second;
229 bool isNonNullAtEndOfBlock(
230 Value *V, BasicBlock *BB,
231 function_ref<NonNullPointerSet(BasicBlock *)> InitFn) {
232 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
233 if (!Entry->NonNullPointers) {
234 Entry->NonNullPointers = InitFn(BB);
235 for (Value *V : *Entry->NonNullPointers)
239 return Entry->NonNullPointers->count(V);
242 /// clear - Empty the cache.
245 ValueHandles.clear();
248 /// Inform the cache that a given value has been deleted.
249 void eraseValue(Value *V);
251 /// This is part of the update interface to inform the cache
252 /// that a block has been deleted.
253 void eraseBlock(BasicBlock *BB);
255 /// Updates the cache to remove any influence an overdefined value in
256 /// OldSucc might have (unless also overdefined in NewSucc). This just
257 /// flushes elements from the cache and does not add any.
258 void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
262 void LazyValueInfoCache::eraseValue(Value *V) {
263 for (auto &Pair : BlockCache) {
264 Pair.second->LatticeElements.erase(V);
265 Pair.second->OverDefined.erase(V);
266 if (Pair.second->NonNullPointers)
267 Pair.second->NonNullPointers->erase(V);
270 auto HandleIt = ValueHandles.find_as(V);
271 if (HandleIt != ValueHandles.end())
272 ValueHandles.erase(HandleIt);
275 void LVIValueHandle::deleted() {
276 // This erasure deallocates *this, so it MUST happen after we're done
277 // using any and all members of *this.
278 Parent->eraseValue(*this);
281 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
282 BlockCache.erase(BB);
285 void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
286 BasicBlock *NewSucc) {
287 // When an edge in the graph has been threaded, values that we could not
288 // determine a value for before (i.e. were marked overdefined) may be
289 // possible to solve now. We do NOT try to proactively update these values.
290 // Instead, we clear their entries from the cache, and allow lazy updating to
291 // recompute them when needed.
293 // The updating process is fairly simple: we need to drop cached info
294 // for all values that were marked overdefined in OldSucc, and for those same
295 // values in any successor of OldSucc (except NewSucc) in which they were
296 // also marked overdefined.
297 std::vector<BasicBlock*> worklist;
298 worklist.push_back(OldSucc);
300 const BlockCacheEntry *Entry = getBlockEntry(OldSucc);
301 if (!Entry || Entry->OverDefined.empty())
302 return; // Nothing to process here.
303 SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),
304 Entry->OverDefined.end());
306 // Use a worklist to perform a depth-first search of OldSucc's successors.
307 // NOTE: We do not need a visited list since any blocks we have already
308 // visited will have had their overdefined markers cleared already, and we
309 // thus won't loop to their successors.
310 while (!worklist.empty()) {
311 BasicBlock *ToUpdate = worklist.back();
314 // Skip blocks only accessible through NewSucc.
315 if (ToUpdate == NewSucc) continue;
317 // If a value was marked overdefined in OldSucc, and is here too...
318 auto OI = BlockCache.find_as(ToUpdate);
319 if (OI == BlockCache.end() || OI->second->OverDefined.empty())
321 auto &ValueSet = OI->second->OverDefined;
323 bool changed = false;
324 for (Value *V : ValsToClear) {
325 if (!ValueSet.erase(V))
328 // If we removed anything, then we potentially need to update
329 // blocks successors too.
333 if (!changed) continue;
335 llvm::append_range(worklist, successors(ToUpdate));
341 /// An assembly annotator class to print LazyValueCache information in
343 class LazyValueInfoImpl;
344 class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
345 LazyValueInfoImpl *LVIImpl;
346 // While analyzing which blocks we can solve values for, we need the dominator
351 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
352 : LVIImpl(L), DT(DTree) {}
354 void emitBasicBlockStartAnnot(const BasicBlock *BB,
355 formatted_raw_ostream &OS) override;
357 void emitInstructionAnnot(const Instruction *I,
358 formatted_raw_ostream &OS) override;
362 // The actual implementation of the lazy analysis and update. Note that the
363 // inheritance from LazyValueInfoCache is intended to be temporary while
364 // splitting the code and then transitioning to a has-a relationship.
365 class LazyValueInfoImpl {
367 /// Cached results from previous queries
368 LazyValueInfoCache TheCache;
370 /// This stack holds the state of the value solver during a query.
371 /// It basically emulates the callstack of the naive
372 /// recursive value lookup process.
373 SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
375 /// Keeps track of which block-value pairs are in BlockValueStack.
376 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
378 /// Push BV onto BlockValueStack unless it's already in there.
379 /// Returns true on success.
380 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
381 if (!BlockValueSet.insert(BV).second)
382 return false; // It's already in the stack.
384 LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
385 << BV.first->getName() << "\n");
386 BlockValueStack.push_back(BV);
390 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
391 const DataLayout &DL; ///< A mandatory DataLayout
393 /// Declaration of the llvm.experimental.guard() intrinsic,
394 /// if it exists in the module.
397 std::optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB,
399 std::optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
401 Instruction *CxtI = nullptr);
403 // These methods process one work item and may add more. A false value
404 // returned means that the work item was not completely processed and must
405 // be revisited after going through the new items.
406 bool solveBlockValue(Value *Val, BasicBlock *BB);
407 std::optional<ValueLatticeElement> solveBlockValueImpl(Value *Val,
409 std::optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
411 std::optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,
413 std::optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,
415 std::optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI,
417 std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
418 Instruction *I, BasicBlock *BB,
419 std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
421 std::optional<ValueLatticeElement>
422 solveBlockValueBinaryOp(BinaryOperator *BBI, BasicBlock *BB);
423 std::optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI,
425 std::optional<ValueLatticeElement>
426 solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB);
427 std::optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
429 std::optional<ValueLatticeElement>
430 solveBlockValueExtractValue(ExtractValueInst *EVI, BasicBlock *BB);
431 bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB);
432 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
433 ValueLatticeElement &BBLV,
439 /// This is the query interface to determine the lattice value for the
440 /// specified Value* at the context instruction (if specified) or at the
441 /// start of the block.
442 ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
443 Instruction *CxtI = nullptr);
445 /// This is the query interface to determine the lattice value for the
446 /// specified Value* at the specified instruction using only information
447 /// from assumes/guards and range metadata. Unlike getValueInBlock(), no
448 /// recursive query is performed.
449 ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
451 /// This is the query interface to determine the lattice
452 /// value for the specified Value* that is true on the specified edge.
453 ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
455 Instruction *CxtI = nullptr);
457 /// Complete flush all previously computed values
462 /// Printing the LazyValueInfo Analysis.
463 void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
464 LazyValueInfoAnnotatedWriter Writer(this, DTree);
465 F.print(OS, &Writer);
468 /// This is part of the update interface to inform the cache
469 /// that a block has been deleted.
470 void eraseBlock(BasicBlock *BB) {
471 TheCache.eraseBlock(BB);
474 /// This is the update interface to inform the cache that an edge from
475 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
476 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
478 LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
480 : AC(AC), DL(DL), GuardDecl(GuardDecl) {}
482 } // end anonymous namespace
485 void LazyValueInfoImpl::solve() {
486 SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
487 BlockValueStack.begin(), BlockValueStack.end());
489 unsigned processedCount = 0;
490 while (!BlockValueStack.empty()) {
492 // Abort if we have to process too many values to get a result for this one.
493 // Because of the design of the overdefined cache currently being per-block
494 // to avoid naming-related issues (IE it wants to try to give different
495 // results for the same name in different blocks), overdefined results don't
496 // get cached globally, which in turn means we will often try to rediscover
497 // the same overdefined result again and again. Once something like
498 // PredicateInfo is used in LVI or CVP, we should be able to make the
499 // overdefined cache global, and remove this throttle.
500 if (processedCount > MaxProcessedPerValue) {
502 dbgs() << "Giving up on stack because we are getting too deep\n");
503 // Fill in the original values
504 while (!StartingStack.empty()) {
505 std::pair<BasicBlock *, Value *> &e = StartingStack.back();
506 TheCache.insertResult(e.second, e.first,
507 ValueLatticeElement::getOverdefined());
508 StartingStack.pop_back();
510 BlockValueSet.clear();
511 BlockValueStack.clear();
514 std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
515 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
517 if (solveBlockValue(e.second, e.first)) {
518 // The work item was completely processed.
519 assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
521 std::optional<ValueLatticeElement> BBLV =
522 TheCache.getCachedValueInfo(e.second, e.first);
523 assert(BBLV && "Result should be in cache!");
525 dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
529 BlockValueStack.pop_back();
530 BlockValueSet.erase(e);
532 // More work needs to be done before revisiting.
533 assert(BlockValueStack.back() != e && "Stack should have been pushed!");
538 std::optional<ValueLatticeElement>
539 LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,
541 // If already a constant, there is nothing to compute.
542 if (Constant *VC = dyn_cast<Constant>(Val))
543 return ValueLatticeElement::get(VC);
545 if (std::optional<ValueLatticeElement> OptLatticeVal =
546 TheCache.getCachedValueInfo(Val, BB)) {
547 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
548 return OptLatticeVal;
551 // We have hit a cycle, assume overdefined.
552 if (!pushBlockValue({ BB, Val }))
553 return ValueLatticeElement::getOverdefined();
555 // Yet to be resolved.
559 static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
560 switch (BBI->getOpcode()) {
562 case Instruction::Load:
563 case Instruction::Call:
564 case Instruction::Invoke:
565 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
566 if (isa<IntegerType>(BBI->getType())) {
567 return ValueLatticeElement::getRange(
568 getConstantRangeFromMetadata(*Ranges));
572 // Nothing known - will be intersected with other facts
573 return ValueLatticeElement::getOverdefined();
576 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
577 assert(!isa<Constant>(Val) && "Value should not be constant");
578 assert(!TheCache.getCachedValueInfo(Val, BB) &&
579 "Value should not be in cache");
581 // Hold off inserting this value into the Cache in case we have to return
582 // false and come back later.
583 std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
585 // Work pushed, will revisit
588 TheCache.insertResult(Val, BB, *Res);
592 std::optional<ValueLatticeElement>
593 LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) {
594 Instruction *BBI = dyn_cast<Instruction>(Val);
595 if (!BBI || BBI->getParent() != BB)
596 return solveBlockValueNonLocal(Val, BB);
598 if (PHINode *PN = dyn_cast<PHINode>(BBI))
599 return solveBlockValuePHINode(PN, BB);
601 if (auto *SI = dyn_cast<SelectInst>(BBI))
602 return solveBlockValueSelect(SI, BB);
604 // If this value is a nonnull pointer, record it's range and bailout. Note
605 // that for all other pointer typed values, we terminate the search at the
606 // definition. We could easily extend this to look through geps, bitcasts,
607 // and the like to prove non-nullness, but it's not clear that's worth it
608 // compile time wise. The context-insensitive value walk done inside
609 // isKnownNonZero gets most of the profitable cases at much less expense.
610 // This does mean that we have a sensitivity to where the defining
611 // instruction is placed, even if it could legally be hoisted much higher.
612 // That is unfortunate.
613 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
614 if (PT && isKnownNonZero(BBI, DL))
615 return ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
617 if (BBI->getType()->isIntegerTy()) {
618 if (auto *CI = dyn_cast<CastInst>(BBI))
619 return solveBlockValueCast(CI, BB);
621 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
622 return solveBlockValueBinaryOp(BO, BB);
624 if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
625 return solveBlockValueExtractValue(EVI, BB);
627 if (auto *II = dyn_cast<IntrinsicInst>(BBI))
628 return solveBlockValueIntrinsic(II, BB);
631 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
632 << "' - unknown inst def found.\n");
633 return getFromRangeMetadata(BBI);
636 static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) {
637 // TODO: Use NullPointerIsDefined instead.
638 if (Ptr->getType()->getPointerAddressSpace() == 0)
639 PtrSet.insert(getUnderlyingObject(Ptr));
642 static void AddNonNullPointersByInstruction(
643 Instruction *I, NonNullPointerSet &PtrSet) {
644 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
645 AddNonNullPointer(L->getPointerOperand(), PtrSet);
646 } else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
647 AddNonNullPointer(S->getPointerOperand(), PtrSet);
648 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
649 if (MI->isVolatile()) return;
651 // FIXME: check whether it has a valuerange that excludes zero?
652 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
653 if (!Len || Len->isZero()) return;
655 AddNonNullPointer(MI->getRawDest(), PtrSet);
656 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
657 AddNonNullPointer(MTI->getRawSource(), PtrSet);
661 bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
662 if (NullPointerIsDefined(BB->getParent(),
663 Val->getType()->getPointerAddressSpace()))
666 Val = Val->stripInBoundsOffsets();
667 return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
668 NonNullPointerSet NonNullPointers;
669 for (Instruction &I : *BB)
670 AddNonNullPointersByInstruction(&I, NonNullPointers);
671 return NonNullPointers;
675 std::optional<ValueLatticeElement>
676 LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {
677 ValueLatticeElement Result; // Start Undefined.
679 // If this is the entry block, we must be asking about an argument. The
680 // value is overdefined.
681 if (BB->isEntryBlock()) {
682 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
683 return ValueLatticeElement::getOverdefined();
686 // Loop over all of our predecessors, merging what we know from them into
687 // result. If we encounter an unexplored predecessor, we eagerly explore it
688 // in a depth first manner. In practice, this has the effect of discovering
689 // paths we can't analyze eagerly without spending compile times analyzing
690 // other paths. This heuristic benefits from the fact that predecessors are
691 // frequently arranged such that dominating ones come first and we quickly
692 // find a path to function entry. TODO: We should consider explicitly
693 // canonicalizing to make this true rather than relying on this happy
695 for (BasicBlock *Pred : predecessors(BB)) {
696 std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
698 // Explore that input, then return here
701 Result.mergeIn(*EdgeResult);
703 // If we hit overdefined, exit early. The BlockVals entry is already set
705 if (Result.isOverdefined()) {
706 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
707 << "' - overdefined because of pred '"
708 << Pred->getName() << "' (non local).\n");
713 // Return the merged value, which is more precise than 'overdefined'.
714 assert(!Result.isOverdefined());
718 std::optional<ValueLatticeElement>
719 LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {
720 ValueLatticeElement Result; // Start Undefined.
722 // Loop over all of our predecessors, merging what we know from them into
723 // result. See the comment about the chosen traversal order in
724 // solveBlockValueNonLocal; the same reasoning applies here.
725 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
726 BasicBlock *PhiBB = PN->getIncomingBlock(i);
727 Value *PhiVal = PN->getIncomingValue(i);
728 // Note that we can provide PN as the context value to getEdgeValue, even
729 // though the results will be cached, because PN is the value being used as
730 // the cache key in the caller.
731 std::optional<ValueLatticeElement> EdgeResult =
732 getEdgeValue(PhiVal, PhiBB, BB, PN);
734 // Explore that input, then return here
737 Result.mergeIn(*EdgeResult);
739 // If we hit overdefined, exit early. The BlockVals entry is already set
741 if (Result.isOverdefined()) {
742 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
743 << "' - overdefined because of pred (local).\n");
749 // Return the merged value, which is more precise than 'overdefined'.
750 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
754 static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
755 bool isTrueDest = true);
757 // If we can determine a constraint on the value given conditions assumed by
758 // the program, intersect those constraints with BBLV
759 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
760 Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
761 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
765 BasicBlock *BB = BBI->getParent();
766 for (auto &AssumeVH : AC->assumptionsFor(Val)) {
770 // Only check assumes in the block of the context instruction. Other
771 // assumes will have already been taken into account when the value was
772 // propagated from predecessor blocks.
773 auto *I = cast<CallInst>(AssumeVH);
774 if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
777 BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
780 // If guards are not used in the module, don't spend time looking for them
781 if (GuardDecl && !GuardDecl->use_empty() &&
782 BBI->getIterator() != BB->begin()) {
783 for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
785 Value *Cond = nullptr;
786 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
787 BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
791 if (BBLV.isOverdefined()) {
792 // Check whether we're checking at the terminator, and the pointer has
793 // been dereferenced in this block.
794 PointerType *PTy = dyn_cast<PointerType>(Val->getType());
795 if (PTy && BB->getTerminator() == BBI &&
796 isNonNullAtEndOfBlock(Val, BB))
797 BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
801 static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val,
802 Type *Ty, const DataLayout &DL) {
803 if (Val.isConstantRange())
804 return Val.getConstantRange();
805 return ConstantRange::getFull(DL.getTypeSizeInBits(Ty));
808 std::optional<ValueLatticeElement>
809 LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) {
810 // Recurse on our inputs if needed
811 std::optional<ValueLatticeElement> OptTrueVal =
812 getBlockValue(SI->getTrueValue(), BB, SI);
815 ValueLatticeElement &TrueVal = *OptTrueVal;
817 std::optional<ValueLatticeElement> OptFalseVal =
818 getBlockValue(SI->getFalseValue(), BB, SI);
821 ValueLatticeElement &FalseVal = *OptFalseVal;
823 if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
824 const ConstantRange &TrueCR =
825 getConstantRangeOrFull(TrueVal, SI->getType(), DL);
826 const ConstantRange &FalseCR =
827 getConstantRangeOrFull(FalseVal, SI->getType(), DL);
828 Value *LHS = nullptr;
829 Value *RHS = nullptr;
830 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
831 // Is this a min specifically of our two inputs? (Avoid the risk of
832 // ValueTracking getting smarter looking back past our immediate inputs.)
833 if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
834 ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
835 (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
836 ConstantRange ResultCR = [&]() {
837 switch (SPR.Flavor) {
839 llvm_unreachable("unexpected minmax type!");
840 case SPF_SMIN: /// Signed minimum
841 return TrueCR.smin(FalseCR);
842 case SPF_UMIN: /// Unsigned minimum
843 return TrueCR.umin(FalseCR);
844 case SPF_SMAX: /// Signed maximum
845 return TrueCR.smax(FalseCR);
846 case SPF_UMAX: /// Unsigned maximum
847 return TrueCR.umax(FalseCR);
850 return ValueLatticeElement::getRange(
851 ResultCR, TrueVal.isConstantRangeIncludingUndef() ||
852 FalseVal.isConstantRangeIncludingUndef());
855 if (SPR.Flavor == SPF_ABS) {
856 if (LHS == SI->getTrueValue())
857 return ValueLatticeElement::getRange(
858 TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
859 if (LHS == SI->getFalseValue())
860 return ValueLatticeElement::getRange(
861 FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
864 if (SPR.Flavor == SPF_NABS) {
865 ConstantRange Zero(APInt::getZero(TrueCR.getBitWidth()));
866 if (LHS == SI->getTrueValue())
867 return ValueLatticeElement::getRange(
868 Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
869 if (LHS == SI->getFalseValue())
870 return ValueLatticeElement::getRange(
871 Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
875 // Can we constrain the facts about the true and false values by using the
876 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
877 // TODO: We could potentially refine an overdefined true value above.
878 Value *Cond = SI->getCondition();
879 // If the value is undef, a different value may be chosen in
880 // the select condition.
881 if (isGuaranteedNotToBeUndefOrPoison(Cond, AC)) {
882 TrueVal = intersect(TrueVal,
883 getValueFromCondition(SI->getTrueValue(), Cond, true));
884 FalseVal = intersect(
885 FalseVal, getValueFromCondition(SI->getFalseValue(), Cond, false));
888 ValueLatticeElement Result = TrueVal;
889 Result.mergeIn(FalseVal);
893 std::optional<ConstantRange>
894 LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) {
895 std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
898 return getConstantRangeOrFull(*OptVal, V->getType(), DL);
901 std::optional<ValueLatticeElement>
902 LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {
903 // Without knowing how wide the input is, we can't analyze it in any useful
905 if (!CI->getOperand(0)->getType()->isSized())
906 return ValueLatticeElement::getOverdefined();
908 // Filter out casts we don't know how to reason about before attempting to
909 // recurse on our operand. This can cut a long search short if we know we're
910 // not going to be able to get any useful information anways.
911 switch (CI->getOpcode()) {
912 case Instruction::Trunc:
913 case Instruction::SExt:
914 case Instruction::ZExt:
915 case Instruction::BitCast:
918 // Unhandled instructions are overdefined.
919 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
920 << "' - overdefined (unknown cast).\n");
921 return ValueLatticeElement::getOverdefined();
924 // Figure out the range of the LHS. If that fails, we still apply the
925 // transfer rule on the full set since we may be able to locally infer
926 // interesting facts.
927 std::optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB);
929 // More work to do before applying this transfer rule.
931 const ConstantRange &LHSRange = *LHSRes;
933 const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
935 // NOTE: We're currently limited by the set of operations that ConstantRange
936 // can evaluate symbolically. Enhancing that set will allows us to analyze
938 return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
942 std::optional<ValueLatticeElement>
943 LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
944 Instruction *I, BasicBlock *BB,
945 std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
947 // Figure out the ranges of the operands. If that fails, use a
948 // conservative range, but apply the transfer rule anyways. This
949 // lets us pick up facts from expressions like "and i32 (call i32
951 std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB);
952 std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB);
953 if (!LHSRes || !RHSRes)
954 // More work to do before applying this transfer rule.
957 const ConstantRange &LHSRange = *LHSRes;
958 const ConstantRange &RHSRange = *RHSRes;
959 return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
962 std::optional<ValueLatticeElement>
963 LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) {
964 assert(BO->getOperand(0)->getType()->isSized() &&
965 "all operands to binary operators are sized");
966 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
967 unsigned NoWrapKind = 0;
968 if (OBO->hasNoUnsignedWrap())
969 NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
970 if (OBO->hasNoSignedWrap())
971 NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap;
973 return solveBlockValueBinaryOpImpl(
975 [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
976 return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
980 return solveBlockValueBinaryOpImpl(
981 BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
982 return CR1.binaryOp(BO->getOpcode(), CR2);
986 std::optional<ValueLatticeElement>
987 LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
989 return solveBlockValueBinaryOpImpl(
990 WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
991 return CR1.binaryOp(WO->getBinaryOp(), CR2);
995 std::optional<ValueLatticeElement>
996 LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) {
997 ValueLatticeElement MetadataVal = getFromRangeMetadata(II);
998 if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
999 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1000 << "' - unknown intrinsic.\n");
1004 SmallVector<ConstantRange, 2> OpRanges;
1005 for (Value *Op : II->args()) {
1006 std::optional<ConstantRange> Range = getRangeFor(Op, II, BB);
1008 return std::nullopt;
1009 OpRanges.push_back(*Range);
1012 return intersect(ValueLatticeElement::getRange(ConstantRange::intrinsic(
1013 II->getIntrinsicID(), OpRanges)),
1017 std::optional<ValueLatticeElement>
1018 LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
1020 if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1021 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
1022 return solveBlockValueOverflowIntrinsic(WO, BB);
1024 // Handle extractvalue of insertvalue to allow further simplification
1025 // based on replaced with.overflow intrinsics.
1026 if (Value *V = simplifyExtractValueInst(
1027 EVI->getAggregateOperand(), EVI->getIndices(),
1028 EVI->getModule()->getDataLayout()))
1029 return getBlockValue(V, BB, EVI);
1031 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1032 << "' - overdefined (unknown extractvalue).\n");
1033 return ValueLatticeElement::getOverdefined();
1036 static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
1037 ICmpInst::Predicate Pred) {
1041 // Handle range checking idiom produced by InstCombine. We will subtract the
1042 // offset from the allowed range for RHS in this case.
1044 if (match(LHS, m_Add(m_Specific(Val), m_APInt(C)))) {
1049 // Handle the symmetric case. This appears in saturation patterns like
1050 // (x == 16) ? 16 : (x + 1).
1051 if (match(Val, m_Add(m_Specific(LHS), m_APInt(C)))) {
1056 // If (x | y) < C, then (x < C) && (y < C).
1057 if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
1058 (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
1061 // If (x & y) > C, then (x > C) && (y > C).
1062 if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
1063 (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
1069 /// Get value range for a "(Val + Offset) Pred RHS" condition.
1070 static ValueLatticeElement getValueFromSimpleICmpCondition(
1071 CmpInst::Predicate Pred, Value *RHS, const APInt &Offset) {
1072 ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1073 /*isFullSet=*/true);
1074 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1075 RHSRange = ConstantRange(CI->getValue());
1076 else if (Instruction *I = dyn_cast<Instruction>(RHS))
1077 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1078 RHSRange = getConstantRangeFromMetadata(*Ranges);
1080 ConstantRange TrueValues =
1081 ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1082 return ValueLatticeElement::getRange(TrueValues.subtract(Offset));
1085 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1087 Value *LHS = ICI->getOperand(0);
1088 Value *RHS = ICI->getOperand(1);
1090 // Get the predicate that must hold along the considered edge.
1091 CmpInst::Predicate EdgePred =
1092 isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
1094 if (isa<Constant>(RHS)) {
1095 if (ICI->isEquality() && LHS == Val) {
1096 if (EdgePred == ICmpInst::ICMP_EQ)
1097 return ValueLatticeElement::get(cast<Constant>(RHS));
1098 else if (!isa<UndefValue>(RHS))
1099 return ValueLatticeElement::getNot(cast<Constant>(RHS));
1103 Type *Ty = Val->getType();
1104 if (!Ty->isIntegerTy())
1105 return ValueLatticeElement::getOverdefined();
1107 unsigned BitWidth = Ty->getScalarSizeInBits();
1108 APInt Offset(BitWidth, 0);
1109 if (matchICmpOperand(Offset, LHS, Val, EdgePred))
1110 return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset);
1112 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred);
1113 if (matchICmpOperand(Offset, RHS, Val, SwappedPred))
1114 return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset);
1116 const APInt *Mask, *C;
1117 if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) &&
1118 match(RHS, m_APInt(C))) {
1119 // If (Val & Mask) == C then all the masked bits are known and we can
1120 // compute a value range based on that.
1121 if (EdgePred == ICmpInst::ICMP_EQ) {
1123 Known.Zero = ~*C & *Mask;
1124 Known.One = *C & *Mask;
1125 return ValueLatticeElement::getRange(
1126 ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
1128 // If (Val & Mask) != 0 then the value must be larger than the lowest set
1130 if (EdgePred == ICmpInst::ICMP_NE && !Mask->isZero() && C->isZero()) {
1131 return ValueLatticeElement::getRange(ConstantRange::getNonEmpty(
1132 APInt::getOneBitSet(BitWidth, Mask->countr_zero()),
1133 APInt::getZero(BitWidth)));
1137 // If (X urem Modulus) >= C, then X >= C.
1138 // If trunc X >= C, then X >= C.
1139 // TODO: An upper bound could be computed as well.
1140 if (match(LHS, m_CombineOr(m_URem(m_Specific(Val), m_Value()),
1141 m_Trunc(m_Specific(Val)))) &&
1142 match(RHS, m_APInt(C))) {
1143 // Use the icmp region so we don't have to deal with different predicates.
1144 ConstantRange CR = ConstantRange::makeExactICmpRegion(EdgePred, *C);
1145 if (!CR.isEmptySet())
1146 return ValueLatticeElement::getRange(ConstantRange::getNonEmpty(
1147 CR.getUnsignedMin().zext(BitWidth), APInt(BitWidth, 0)));
1150 return ValueLatticeElement::getOverdefined();
1153 // Handle conditions of the form
1154 // extractvalue(op.with.overflow(%x, C), 1).
1155 static ValueLatticeElement getValueFromOverflowCondition(
1156 Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1157 // TODO: This only works with a constant RHS for now. We could also compute
1158 // the range of the RHS, but this doesn't fit into the current structure of
1159 // the edge value calculation.
1161 if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
1162 return ValueLatticeElement::getOverdefined();
1164 // Calculate the possible values of %x for which no overflow occurs.
1165 ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
1166 WO->getBinaryOp(), *C, WO->getNoWrapKind());
1168 // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1169 // constrained to it's inverse (all values that might cause overflow).
1171 NWR = NWR.inverse();
1172 return ValueLatticeElement::getRange(NWR);
1175 // Tracks a Value * condition and whether we're interested in it or its inverse
1176 typedef PointerIntPair<Value *, 1, bool> CondValue;
1178 static std::optional<ValueLatticeElement> getValueFromConditionImpl(
1179 Value *Val, CondValue CondVal, bool isRevisit,
1180 SmallDenseMap<CondValue, ValueLatticeElement> &Visited,
1181 SmallVectorImpl<CondValue> &Worklist) {
1183 Value *Cond = CondVal.getPointer();
1184 bool isTrueDest = CondVal.getInt();
1186 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1187 return getValueFromICmpCondition(Val, ICI, isTrueDest);
1189 if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
1190 if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1191 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1192 return getValueFromOverflowCondition(Val, WO, isTrueDest);
1196 if (match(Cond, m_Not(m_Value(N)))) {
1197 CondValue NKey(N, !isTrueDest);
1198 auto NV = Visited.find(NKey);
1199 if (NV == Visited.end()) {
1200 Worklist.push_back(NKey);
1201 return std::nullopt;
1208 if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))))
1210 else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
1213 return ValueLatticeElement::getOverdefined();
1215 auto LV = Visited.find(CondValue(L, isTrueDest));
1216 auto RV = Visited.find(CondValue(R, isTrueDest));
1218 // if (L && R) -> intersect L and R
1219 // if (!(L || R)) -> intersect !L and !R
1220 // if (L || R) -> union L and R
1221 // if (!(L && R)) -> union !L and !R
1222 if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) {
1223 ValueLatticeElement V = LV->second;
1224 if (V.isOverdefined())
1226 if (RV != Visited.end()) {
1227 V.mergeIn(RV->second);
1232 if (LV == Visited.end() || RV == Visited.end()) {
1234 if (LV == Visited.end())
1235 Worklist.push_back(CondValue(L, isTrueDest));
1236 if (RV == Visited.end())
1237 Worklist.push_back(CondValue(R, isTrueDest));
1238 return std::nullopt;
1241 return intersect(LV->second, RV->second);
1244 ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
1246 assert(Cond && "precondition");
1247 SmallDenseMap<CondValue, ValueLatticeElement> Visited;
1248 SmallVector<CondValue> Worklist;
1250 CondValue CondKey(Cond, isTrueDest);
1251 Worklist.push_back(CondKey);
1253 CondValue CurrentCond = Worklist.back();
1254 // Insert an Overdefined placeholder into the set to prevent
1255 // infinite recursion if there exists IRs that use not
1256 // dominated by its def as in this example:
1257 // "%tmp3 = or i1 undef, %tmp4"
1258 // "%tmp4 = or i1 undef, %tmp3"
1260 Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined());
1261 bool isRevisit = !Iter.second;
1262 std::optional<ValueLatticeElement> Result = getValueFromConditionImpl(
1263 Val, CurrentCond, isRevisit, Visited, Worklist);
1265 Visited[CurrentCond] = *Result;
1266 Worklist.pop_back();
1268 } while (!Worklist.empty());
1270 auto Result = Visited.find(CondKey);
1271 assert(Result != Visited.end());
1272 return Result->second;
1275 // Return true if Usr has Op as an operand, otherwise false.
1276 static bool usesOperand(User *Usr, Value *Op) {
1277 return is_contained(Usr->operands(), Op);
1280 // Return true if the instruction type of Val is supported by
1281 // constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
1282 // Call this before calling constantFoldUser() to find out if it's even worth
1283 // attempting to call it.
1284 static bool isOperationFoldable(User *Usr) {
1285 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1288 // Check if Usr can be simplified to an integer constant when the value of one
1289 // of its operands Op is an integer constant OpConstVal. If so, return it as an
1290 // lattice value range with a single element or otherwise return an overdefined
1292 static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1293 const APInt &OpConstVal,
1294 const DataLayout &DL) {
1295 assert(isOperationFoldable(Usr) && "Precondition");
1296 Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1297 // Check if Usr can be simplified to a constant.
1298 if (auto *CI = dyn_cast<CastInst>(Usr)) {
1299 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1300 if (auto *C = dyn_cast_or_null<ConstantInt>(
1301 simplifyCastInst(CI->getOpcode(), OpConst,
1302 CI->getDestTy(), DL))) {
1303 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1305 } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1306 bool Op0Match = BO->getOperand(0) == Op;
1307 bool Op1Match = BO->getOperand(1) == Op;
1308 assert((Op0Match || Op1Match) &&
1309 "Operand 0 nor Operand 1 isn't a match");
1310 Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1311 Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1312 if (auto *C = dyn_cast_or_null<ConstantInt>(
1313 simplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1314 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1316 } else if (isa<FreezeInst>(Usr)) {
1317 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
1318 return ValueLatticeElement::getRange(ConstantRange(OpConstVal));
1320 return ValueLatticeElement::getOverdefined();
1323 /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1324 /// Val is not constrained on the edge. Result is unspecified if return value
1326 static std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
1329 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1330 // know that v != 0.
1331 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1332 // If this is a conditional branch and only one successor goes to BBTo, then
1333 // we may be able to infer something from the condition.
1334 if (BI->isConditional() &&
1335 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1336 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1337 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1338 "BBTo isn't a successor of BBFrom");
1339 Value *Condition = BI->getCondition();
1341 // If V is the condition of the branch itself, then we know exactly what
1343 if (Condition == Val)
1344 return ValueLatticeElement::get(ConstantInt::get(
1345 Type::getInt1Ty(Val->getContext()), isTrueDest));
1347 // If the condition of the branch is an equality comparison, we may be
1348 // able to infer the value.
1349 ValueLatticeElement Result = getValueFromCondition(Val, Condition,
1351 if (!Result.isOverdefined())
1354 if (User *Usr = dyn_cast<User>(Val)) {
1355 assert(Result.isOverdefined() && "Result isn't overdefined");
1356 // Check with isOperationFoldable() first to avoid linearly iterating
1357 // over the operands unnecessarily which can be expensive for
1358 // instructions with many operands.
1359 if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1360 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1361 if (usesOperand(Usr, Condition)) {
1362 // If Val has Condition as an operand and Val can be folded into a
1363 // constant with either Condition == true or Condition == false,
1364 // propagate the constant.
1366 // ; %Val is true on the edge to %then.
1367 // %Val = and i1 %Condition, true.
1368 // br %Condition, label %then, label %else
1369 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1370 Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1372 // If one of Val's operand has an inferred value, we may be able to
1373 // infer the value of Val.
1375 // ; %Val is 94 on the edge to %then.
1376 // %Val = add i8 %Op, 1
1377 // %Condition = icmp eq i8 %Op, 93
1378 // br i1 %Condition, label %then, label %else
1379 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1380 Value *Op = Usr->getOperand(i);
1381 ValueLatticeElement OpLatticeVal =
1382 getValueFromCondition(Op, Condition, isTrueDest);
1383 if (std::optional<APInt> OpConst =
1384 OpLatticeVal.asConstantInteger()) {
1385 Result = constantFoldUser(Usr, Op, *OpConst, DL);
1392 if (!Result.isOverdefined())
1397 // If the edge was formed by a switch on the value, then we may know exactly
1399 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1400 Value *Condition = SI->getCondition();
1401 if (!isa<IntegerType>(Val->getType()))
1402 return std::nullopt;
1403 bool ValUsesConditionAndMayBeFoldable = false;
1404 if (Condition != Val) {
1405 // Check if Val has Condition as an operand.
1406 if (User *Usr = dyn_cast<User>(Val))
1407 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1408 usesOperand(Usr, Condition);
1409 if (!ValUsesConditionAndMayBeFoldable)
1410 return std::nullopt;
1412 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1413 "Condition != Val nor Val doesn't use Condition");
1415 bool DefaultCase = SI->getDefaultDest() == BBTo;
1416 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1417 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1419 for (auto Case : SI->cases()) {
1420 APInt CaseValue = Case.getCaseValue()->getValue();
1421 ConstantRange EdgeVal(CaseValue);
1422 if (ValUsesConditionAndMayBeFoldable) {
1423 User *Usr = cast<User>(Val);
1424 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1425 ValueLatticeElement EdgeLatticeVal =
1426 constantFoldUser(Usr, Condition, CaseValue, DL);
1427 if (EdgeLatticeVal.isOverdefined())
1428 return std::nullopt;
1429 EdgeVal = EdgeLatticeVal.getConstantRange();
1432 // It is possible that the default destination is the destination of
1433 // some cases. We cannot perform difference for those cases.
1434 // We know Condition != CaseValue in BBTo. In some cases we can use
1435 // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1436 // only do this when f is identity (i.e. Val == Condition), but we
1437 // should be able to do this for any injective f.
1438 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1439 EdgesVals = EdgesVals.difference(EdgeVal);
1440 } else if (Case.getCaseSuccessor() == BBTo)
1441 EdgesVals = EdgesVals.unionWith(EdgeVal);
1443 return ValueLatticeElement::getRange(std::move(EdgesVals));
1445 return std::nullopt;
1448 /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1449 /// the basic block if the edge does not constrain Val.
1450 std::optional<ValueLatticeElement>
1451 LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1452 BasicBlock *BBTo, Instruction *CxtI) {
1453 // If already a constant, there is nothing to compute.
1454 if (Constant *VC = dyn_cast<Constant>(Val))
1455 return ValueLatticeElement::get(VC);
1457 ValueLatticeElement LocalResult =
1458 getEdgeValueLocal(Val, BBFrom, BBTo)
1459 .value_or(ValueLatticeElement::getOverdefined());
1460 if (hasSingleValue(LocalResult))
1461 // Can't get any more precise here
1464 std::optional<ValueLatticeElement> OptInBlock =
1465 getBlockValue(Val, BBFrom, BBFrom->getTerminator());
1467 return std::nullopt;
1468 ValueLatticeElement &InBlock = *OptInBlock;
1470 // We can use the context instruction (generically the ultimate instruction
1471 // the calling pass is trying to simplify) here, even though the result of
1472 // this function is generally cached when called from the solve* functions
1473 // (and that cached result might be used with queries using a different
1474 // context instruction), because when this function is called from the solve*
1475 // functions, the context instruction is not provided. When called from
1476 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1477 // but then the result is not cached.
1478 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1480 return intersect(LocalResult, InBlock);
1483 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1484 Instruction *CxtI) {
1485 LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1486 << BB->getName() << "'\n");
1488 assert(BlockValueStack.empty() && BlockValueSet.empty());
1489 std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
1492 OptResult = getBlockValue(V, BB, CxtI);
1493 assert(OptResult && "Value not available after solving");
1496 ValueLatticeElement Result = *OptResult;
1497 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1501 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1502 LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1505 if (auto *C = dyn_cast<Constant>(V))
1506 return ValueLatticeElement::get(C);
1508 ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1509 if (auto *I = dyn_cast<Instruction>(V))
1510 Result = getFromRangeMetadata(I);
1511 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1513 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1517 ValueLatticeElement LazyValueInfoImpl::
1518 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1519 Instruction *CxtI) {
1520 LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1521 << FromBB->getName() << "' to '" << ToBB->getName()
1524 std::optional<ValueLatticeElement> Result =
1525 getEdgeValue(V, FromBB, ToBB, CxtI);
1528 Result = getEdgeValue(V, FromBB, ToBB, CxtI);
1529 assert(Result && "More work to do after problem solved?");
1532 LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");
1536 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1537 BasicBlock *NewSucc) {
1538 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1541 //===----------------------------------------------------------------------===//
1542 // LazyValueInfo Impl
1543 //===----------------------------------------------------------------------===//
1545 /// This lazily constructs the LazyValueInfoImpl.
1546 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1549 assert(M && "getCache() called with a null Module");
1550 const DataLayout &DL = M->getDataLayout();
1551 Function *GuardDecl = M->getFunction(
1552 Intrinsic::getName(Intrinsic::experimental_guard));
1553 PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl);
1555 return *static_cast<LazyValueInfoImpl*>(PImpl);
1558 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1559 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1560 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1563 getImpl(Info.PImpl, Info.AC, F.getParent()).clear();
1569 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1570 AU.setPreservesAll();
1571 AU.addRequired<AssumptionCacheTracker>();
1572 AU.addRequired<TargetLibraryInfoWrapperPass>();
1575 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1577 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1579 void LazyValueInfo::releaseMemory() {
1580 // If the cache was allocated, free it.
1582 delete &getImpl(PImpl, AC, nullptr);
1587 bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1588 FunctionAnalysisManager::Invalidator &Inv) {
1589 // We need to invalidate if we have either failed to preserve this analyses
1590 // result directly or if any of its dependencies have been invalidated.
1591 auto PAC = PA.getChecker<LazyValueAnalysis>();
1592 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
1598 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1600 LazyValueInfo LazyValueAnalysis::run(Function &F,
1601 FunctionAnalysisManager &FAM) {
1602 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1603 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1605 return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI);
1608 /// Returns true if we can statically tell that this value will never be a
1609 /// "useful" constant. In practice, this means we've got something like an
1610 /// alloca or a malloc call for which a comparison against a constant can
1611 /// only be guarding dead code. Note that we are potentially giving up some
1612 /// precision in dead code (a constant result) in favour of avoiding a
1613 /// expensive search for a easily answered common query.
1614 static bool isKnownNonConstant(Value *V) {
1615 V = V->stripPointerCasts();
1616 // The return val of alloc cannot be a Constant.
1617 if (isa<AllocaInst>(V))
1622 Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) {
1623 // Bail out early if V is known not to be a Constant.
1624 if (isKnownNonConstant(V))
1627 BasicBlock *BB = CxtI->getParent();
1628 ValueLatticeElement Result =
1629 getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI);
1631 if (Result.isConstant())
1632 return Result.getConstant();
1633 if (Result.isConstantRange()) {
1634 const ConstantRange &CR = Result.getConstantRange();
1635 if (const APInt *SingleVal = CR.getSingleElement())
1636 return ConstantInt::get(V->getContext(), *SingleVal);
1641 ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI,
1642 bool UndefAllowed) {
1643 assert(V->getType()->isIntegerTy());
1644 unsigned Width = V->getType()->getIntegerBitWidth();
1645 BasicBlock *BB = CxtI->getParent();
1646 ValueLatticeElement Result =
1647 getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI);
1648 if (Result.isUnknown())
1649 return ConstantRange::getEmpty(Width);
1650 if (Result.isConstantRange(UndefAllowed))
1651 return Result.getConstantRange(UndefAllowed);
1652 // We represent ConstantInt constants as constant ranges but other kinds
1653 // of integer constants, i.e. ConstantExpr will be tagged as constants
1654 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1655 "ConstantInt value must be represented as constantrange");
1656 return ConstantRange::getFull(Width);
1659 ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U,
1660 bool UndefAllowed) {
1663 getConstantRange(V, cast<Instruction>(U.getUser()), UndefAllowed);
1665 // Check whether the only (possibly transitive) use of the value is in a
1666 // position where V can be constrained by a select or branch condition.
1667 const Use *CurrU = &U;
1668 // TODO: Increase limit?
1669 const unsigned MaxUsesToInspect = 3;
1670 for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
1671 std::optional<ValueLatticeElement> CondVal;
1672 auto *CurrI = cast<Instruction>(CurrU->getUser());
1673 if (auto *SI = dyn_cast<SelectInst>(CurrI)) {
1674 // If the value is undef, a different value may be chosen in
1675 // the select condition and at use.
1676 if (!isGuaranteedNotToBeUndefOrPoison(SI->getCondition(), AC))
1678 if (CurrU->getOperandNo() == 1)
1679 CondVal = getValueFromCondition(V, SI->getCondition(), true);
1680 else if (CurrU->getOperandNo() == 2)
1681 CondVal = getValueFromCondition(V, SI->getCondition(), false);
1682 } else if (auto *PHI = dyn_cast<PHINode>(CurrI)) {
1683 // TODO: Use non-local query?
1685 getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU), PHI->getParent());
1687 if (CondVal && CondVal->isConstantRange())
1688 CR = CR.intersectWith(CondVal->getConstantRange());
1690 // Only follow one-use chain, to allow direct intersection of conditions.
1691 // If there are multiple uses, we would have to intersect with the union of
1692 // all conditions at different uses.
1693 // Stop walking if we hit a non-speculatable instruction. Even if the
1694 // result is only used under a specific condition, executing the
1695 // instruction itself may cause side effects or UB already.
1696 // This also disallows looking through phi nodes: If the phi node is part
1697 // of a cycle, we might end up reasoning about values from different cycle
1698 // iterations (PR60629).
1699 if (!CurrI->hasOneUse() || !isSafeToSpeculativelyExecute(CurrI))
1701 CurrU = &*CurrI->use_begin();
1706 /// Determine whether the specified value is known to be a
1707 /// constant on the specified edge. Return null if not.
1708 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1710 Instruction *CxtI) {
1711 Module *M = FromBB->getModule();
1712 ValueLatticeElement Result =
1713 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1715 if (Result.isConstant())
1716 return Result.getConstant();
1717 if (Result.isConstantRange()) {
1718 const ConstantRange &CR = Result.getConstantRange();
1719 if (const APInt *SingleVal = CR.getSingleElement())
1720 return ConstantInt::get(V->getContext(), *SingleVal);
1725 ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
1728 Instruction *CxtI) {
1729 unsigned Width = V->getType()->getIntegerBitWidth();
1730 Module *M = FromBB->getModule();
1731 ValueLatticeElement Result =
1732 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1734 if (Result.isUnknown())
1735 return ConstantRange::getEmpty(Width);
1736 if (Result.isConstantRange())
1737 return Result.getConstantRange();
1738 // We represent ConstantInt constants as constant ranges but other kinds
1739 // of integer constants, i.e. ConstantExpr will be tagged as constants
1740 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1741 "ConstantInt value must be represented as constantrange");
1742 return ConstantRange::getFull(Width);
1745 static LazyValueInfo::Tristate
1746 getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1747 const DataLayout &DL, TargetLibraryInfo *TLI) {
1748 // If we know the value is a constant, evaluate the conditional.
1749 Constant *Res = nullptr;
1750 if (Val.isConstant()) {
1751 Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1752 if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
1753 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1754 return LazyValueInfo::Unknown;
1757 if (Val.isConstantRange()) {
1758 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1759 if (!CI) return LazyValueInfo::Unknown;
1761 const ConstantRange &CR = Val.getConstantRange();
1762 if (Pred == ICmpInst::ICMP_EQ) {
1763 if (!CR.contains(CI->getValue()))
1764 return LazyValueInfo::False;
1766 if (CR.isSingleElement())
1767 return LazyValueInfo::True;
1768 } else if (Pred == ICmpInst::ICMP_NE) {
1769 if (!CR.contains(CI->getValue()))
1770 return LazyValueInfo::True;
1772 if (CR.isSingleElement())
1773 return LazyValueInfo::False;
1775 // Handle more complex predicates.
1776 ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1777 (ICmpInst::Predicate)Pred, CI->getValue());
1778 if (TrueValues.contains(CR))
1779 return LazyValueInfo::True;
1780 if (TrueValues.inverse().contains(CR))
1781 return LazyValueInfo::False;
1783 return LazyValueInfo::Unknown;
1786 if (Val.isNotConstant()) {
1787 // If this is an equality comparison, we can try to fold it knowing that
1789 if (Pred == ICmpInst::ICMP_EQ) {
1790 // !C1 == C -> false iff C1 == C.
1791 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1792 Val.getNotConstant(), C, DL,
1794 if (Res && Res->isNullValue())
1795 return LazyValueInfo::False;
1796 } else if (Pred == ICmpInst::ICMP_NE) {
1797 // !C1 != C -> true iff C1 == C.
1798 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1799 Val.getNotConstant(), C, DL,
1801 if (Res && Res->isNullValue())
1802 return LazyValueInfo::True;
1804 return LazyValueInfo::Unknown;
1807 return LazyValueInfo::Unknown;
1810 /// Determine whether the specified value comparison with a constant is known to
1811 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1812 LazyValueInfo::Tristate
1813 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1814 BasicBlock *FromBB, BasicBlock *ToBB,
1815 Instruction *CxtI) {
1816 Module *M = FromBB->getModule();
1817 ValueLatticeElement Result =
1818 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1820 return getPredicateResult(Pred, C, Result, M->getDataLayout(), TLI);
1823 LazyValueInfo::Tristate
1824 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1825 Instruction *CxtI, bool UseBlockValue) {
1826 // Is or is not NonNull are common predicates being queried. If
1827 // isKnownNonZero can tell us the result of the predicate, we can
1828 // return it quickly. But this is only a fastpath, and falling
1829 // through would still be correct.
1830 Module *M = CxtI->getModule();
1831 const DataLayout &DL = M->getDataLayout();
1832 if (V->getType()->isPointerTy() && C->isNullValue() &&
1833 isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) {
1834 if (Pred == ICmpInst::ICMP_EQ)
1835 return LazyValueInfo::False;
1836 else if (Pred == ICmpInst::ICMP_NE)
1837 return LazyValueInfo::True;
1840 ValueLatticeElement Result = UseBlockValue
1841 ? getImpl(PImpl, AC, M).getValueInBlock(V, CxtI->getParent(), CxtI)
1842 : getImpl(PImpl, AC, M).getValueAt(V, CxtI);
1843 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1847 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1848 // LVI as a whole tries to compute a lattice value which is conservatively
1849 // correct at a given location. In this case, we have a predicate which we
1850 // weren't able to prove about the merged result, and we're pushing that
1851 // predicate back along each incoming edge to see if we can prove it
1852 // separately for each input. As a motivating example, consider:
1854 // %v1 = ... ; constantrange<1, 5>
1857 // %v2 = ... ; constantrange<10, 20>
1860 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1861 // %pred = icmp eq i32 %phi, 8
1862 // We can't tell from the lattice value for '%phi' that '%pred' is false
1863 // along each path, but by checking the predicate over each input separately,
1865 // We limit the search to one step backwards from the current BB and value.
1866 // We could consider extending this to search further backwards through the
1867 // CFG and/or value graph, but there are non-obvious compile time vs quality
1869 BasicBlock *BB = CxtI->getParent();
1871 // Function entry or an unreachable block. Bail to avoid confusing
1873 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1877 // If V is a PHI node in the same block as the context, we need to ask
1878 // questions about the predicate as applied to the incoming value along
1879 // each edge. This is useful for eliminating cases where the predicate is
1880 // known along all incoming edges.
1881 if (auto *PHI = dyn_cast<PHINode>(V))
1882 if (PHI->getParent() == BB) {
1883 Tristate Baseline = Unknown;
1884 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1885 Value *Incoming = PHI->getIncomingValue(i);
1886 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1887 // Note that PredBB may be BB itself.
1889 getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI);
1891 // Keep going as long as we've seen a consistent known result for
1893 Baseline = (i == 0) ? Result /* First iteration */
1894 : (Baseline == Result ? Baseline
1895 : Unknown); /* All others */
1896 if (Baseline == Unknown)
1899 if (Baseline != Unknown)
1903 // For a comparison where the V is outside this block, it's possible
1904 // that we've branched on it before. Look to see if the value is known
1905 // on all incoming edges.
1906 if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
1907 // For predecessor edge, determine if the comparison is true or false
1908 // on that edge. If they're all true or all false, we can conclude
1909 // the value of the comparison in this block.
1910 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1911 if (Baseline != Unknown) {
1912 // Check that all remaining incoming values match the first one.
1913 while (++PI != PE) {
1914 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1915 if (Ret != Baseline)
1918 // If we terminated early, then one of the values didn't match.
1928 LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS,
1931 bool UseBlockValue) {
1932 CmpInst::Predicate Pred = (CmpInst::Predicate)P;
1934 if (auto *C = dyn_cast<Constant>(RHS))
1935 return getPredicateAt(P, LHS, C, CxtI, UseBlockValue);
1936 if (auto *C = dyn_cast<Constant>(LHS))
1937 return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI,
1940 // Got two non-Constant values. Try to determine the comparison results based
1941 // on the block values of the two operands, e.g. because they have
1942 // non-overlapping ranges.
1943 if (UseBlockValue) {
1944 Module *M = CxtI->getModule();
1945 ValueLatticeElement L =
1946 getImpl(PImpl, AC, M).getValueInBlock(LHS, CxtI->getParent(), CxtI);
1947 if (L.isOverdefined())
1948 return LazyValueInfo::Unknown;
1950 ValueLatticeElement R =
1951 getImpl(PImpl, AC, M).getValueInBlock(RHS, CxtI->getParent(), CxtI);
1952 Type *Ty = CmpInst::makeCmpResultType(LHS->getType());
1953 if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R,
1954 M->getDataLayout())) {
1955 if (Res->isNullValue())
1956 return LazyValueInfo::False;
1957 if (Res->isOneValue())
1958 return LazyValueInfo::True;
1961 return LazyValueInfo::Unknown;
1964 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1965 BasicBlock *NewSucc) {
1967 getImpl(PImpl, AC, PredBB->getModule())
1968 .threadEdge(PredBB, OldSucc, NewSucc);
1972 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1974 getImpl(PImpl, AC, BB->getModule()).eraseBlock(BB);
1978 void LazyValueInfo::clear(const Module *M) {
1980 getImpl(PImpl, AC, M).clear();
1984 void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
1986 getImpl(PImpl, AC, F.getParent()).printLVI(F, DTree, OS);
1990 // Print the LVI for the function arguments at the start of each basic block.
1991 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1992 const BasicBlock *BB, formatted_raw_ostream &OS) {
1993 // Find if there are latticevalues defined for arguments of the function.
1994 auto *F = BB->getParent();
1995 for (const auto &Arg : F->args()) {
1996 ValueLatticeElement Result = LVIImpl->getValueInBlock(
1997 const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1998 if (Result.isUnknown())
2000 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
2004 // This function prints the LVI analysis for the instruction I at the beginning
2005 // of various basic blocks. It relies on calculated values that are stored in
2006 // the LazyValueInfoCache, and in the absence of cached values, recalculate the
2007 // LazyValueInfo for `I`, and print that info.
2008 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2009 const Instruction *I, formatted_raw_ostream &OS) {
2011 auto *ParentBB = I->getParent();
2012 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
2013 // We can generate (solve) LVI values only for blocks that are dominated by
2014 // the I's parent. However, to avoid generating LVI for all dominating blocks,
2015 // that contain redundant/uninteresting information, we print LVI for
2016 // blocks that may use this LVI information (such as immediate successor
2017 // blocks, and blocks that contain uses of `I`).
2018 auto printResult = [&](const BasicBlock *BB) {
2019 if (!BlocksContainingLVI.insert(BB).second)
2021 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2022 const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
2023 OS << "; LatticeVal for: '" << *I << "' in BB: '";
2024 BB->printAsOperand(OS, false);
2025 OS << "' is: " << Result << "\n";
2028 printResult(ParentBB);
2029 // Print the LVI analysis results for the immediate successor blocks, that
2030 // are dominated by `ParentBB`.
2031 for (const auto *BBSucc : successors(ParentBB))
2032 if (DT.dominates(ParentBB, BBSucc))
2033 printResult(BBSucc);
2035 // Print LVI in blocks where `I` is used.
2036 for (const auto *U : I->users())
2037 if (auto *UseI = dyn_cast<Instruction>(U))
2038 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
2039 printResult(UseI->getParent());
2044 // Printer class for LazyValueInfo results.
2045 class LazyValueInfoPrinter : public FunctionPass {
2047 static char ID; // Pass identification, replacement for typeid
2048 LazyValueInfoPrinter() : FunctionPass(ID) {
2049 initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
2052 void getAnalysisUsage(AnalysisUsage &AU) const override {
2053 AU.setPreservesAll();
2054 AU.addRequired<LazyValueInfoWrapperPass>();
2055 AU.addRequired<DominatorTreeWrapperPass>();
2058 // Get the mandatory dominator tree analysis and pass this in to the
2059 // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
2060 bool runOnFunction(Function &F) override {
2061 dbgs() << "LVI for function '" << F.getName() << "':\n";
2062 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
2063 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2064 LVI.printLVI(F, DTree, dbgs());
2070 char LazyValueInfoPrinter::ID = 0;
2071 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
2072 "Lazy Value Info Printer Pass", false, false)
2073 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
2074 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
2075 "Lazy Value Info Printer Pass", false, false)