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