LLVM 19.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
437 // For the following methods, if UseBlockValue is true, the function may
438 // push additional values to the worklist and return nullopt. If
439 // UseBlockValue is false, it will never return nullopt.
440
441 std::optional<ValueLatticeElement>
442 getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS,
443 const APInt &Offset, Instruction *CxtI,
444 bool UseBlockValue);
445
446 std::optional<ValueLatticeElement>
447 getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest,
448 bool UseBlockValue);
449
450 std::optional<ValueLatticeElement>
451 getValueFromCondition(Value *Val, Value *Cond, bool IsTrueDest,
452 bool UseBlockValue, unsigned Depth = 0);
453
454 std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
455 BasicBlock *BBFrom,
456 BasicBlock *BBTo,
457 bool UseBlockValue);
458
459public:
460 /// This is the query interface to determine the lattice value for the
461 /// specified Value* at the context instruction (if specified) or at the
462 /// start of the block.
464 Instruction *CxtI = nullptr);
465
466 /// This is the query interface to determine the lattice value for the
467 /// specified Value* at the specified instruction using only information
468 /// from assumes/guards and range metadata. Unlike getValueInBlock(), no
469 /// recursive query is performed.
471
472 /// This is the query interface to determine the lattice
473 /// value for the specified Value* that is true on the specified edge.
475 BasicBlock *ToBB,
476 Instruction *CxtI = nullptr);
477
479
480 /// Complete flush all previously computed values
481 void clear() {
482 TheCache.clear();
483 }
484
485 /// Printing the LazyValueInfo Analysis.
487 LazyValueInfoAnnotatedWriter Writer(this, DTree);
488 F.print(OS, &Writer);
489 }
490
491 /// This is part of the update interface to remove information related to this
492 /// value from the cache.
493 void forgetValue(Value *V) { TheCache.eraseValue(V); }
494
495 /// This is part of the update interface to inform the cache
496 /// that a block has been deleted.
498 TheCache.eraseBlock(BB);
499 }
500
501 /// This is the update interface to inform the cache that an edge from
502 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
503 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
504
506 Function *GuardDecl)
507 : AC(AC), DL(DL), GuardDecl(GuardDecl) {}
508};
509} // namespace llvm
510
511void LazyValueInfoImpl::solve() {
513 BlockValueStack.begin(), BlockValueStack.end());
514
515 unsigned processedCount = 0;
516 while (!BlockValueStack.empty()) {
517 processedCount++;
518 // Abort if we have to process too many values to get a result for this one.
519 // Because of the design of the overdefined cache currently being per-block
520 // to avoid naming-related issues (IE it wants to try to give different
521 // results for the same name in different blocks), overdefined results don't
522 // get cached globally, which in turn means we will often try to rediscover
523 // the same overdefined result again and again. Once something like
524 // PredicateInfo is used in LVI or CVP, we should be able to make the
525 // overdefined cache global, and remove this throttle.
526 if (processedCount > MaxProcessedPerValue) {
528 dbgs() << "Giving up on stack because we are getting too deep\n");
529 // Fill in the original values
530 while (!StartingStack.empty()) {
531 std::pair<BasicBlock *, Value *> &e = StartingStack.back();
532 TheCache.insertResult(e.second, e.first,
534 StartingStack.pop_back();
535 }
536 BlockValueSet.clear();
537 BlockValueStack.clear();
538 return;
539 }
540 std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
541 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
542 unsigned StackSize = BlockValueStack.size();
543 (void) StackSize;
544
545 if (solveBlockValue(e.second, e.first)) {
546 // The work item was completely processed.
547 assert(BlockValueStack.size() == StackSize &&
548 BlockValueStack.back() == e && "Nothing should have been pushed!");
549#ifndef NDEBUG
550 std::optional<ValueLatticeElement> BBLV =
551 TheCache.getCachedValueInfo(e.second, e.first);
552 assert(BBLV && "Result should be in cache!");
554 dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
555 << *BBLV << "\n");
556#endif
557
558 BlockValueStack.pop_back();
559 BlockValueSet.erase(e);
560 } else {
561 // More work needs to be done before revisiting.
562 assert(BlockValueStack.size() == StackSize + 1 &&
563 "Exactly one element should have been pushed!");
564 }
565 }
566}
567
568std::optional<ValueLatticeElement>
569LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,
570 Instruction *CxtI) {
571 // If already a constant, there is nothing to compute.
572 if (Constant *VC = dyn_cast<Constant>(Val))
573 return ValueLatticeElement::get(VC);
574
575 if (std::optional<ValueLatticeElement> OptLatticeVal =
576 TheCache.getCachedValueInfo(Val, BB)) {
577 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
578 return OptLatticeVal;
579 }
580
581 // We have hit a cycle, assume overdefined.
582 if (!pushBlockValue({ BB, Val }))
584
585 // Yet to be resolved.
586 return std::nullopt;
587}
588
590 switch (BBI->getOpcode()) {
591 default:
592 break;
593 case Instruction::Call:
594 case Instruction::Invoke:
595 if (std::optional<ConstantRange> Range = cast<CallBase>(BBI)->getRange())
596 return ValueLatticeElement::getRange(*Range);
597 [[fallthrough]];
598 case Instruction::Load:
599 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
600 if (isa<IntegerType>(BBI->getType())) {
603 }
604 break;
605 };
606 // Nothing known - will be intersected with other facts
608}
609
610bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
611 assert(!isa<Constant>(Val) && "Value should not be constant");
612 assert(!TheCache.getCachedValueInfo(Val, BB) &&
613 "Value should not be in cache");
614
615 // Hold off inserting this value into the Cache in case we have to return
616 // false and come back later.
617 std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
618 if (!Res)
619 // Work pushed, will revisit
620 return false;
621
622 TheCache.insertResult(Val, BB, *Res);
623 return true;
624}
625
626std::optional<ValueLatticeElement>
627LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) {
628 Instruction *BBI = dyn_cast<Instruction>(Val);
629 if (!BBI || BBI->getParent() != BB)
630 return solveBlockValueNonLocal(Val, BB);
631
632 if (PHINode *PN = dyn_cast<PHINode>(BBI))
633 return solveBlockValuePHINode(PN, BB);
634
635 if (auto *SI = dyn_cast<SelectInst>(BBI))
636 return solveBlockValueSelect(SI, BB);
637
638 // If this value is a nonnull pointer, record it's range and bailout. Note
639 // that for all other pointer typed values, we terminate the search at the
640 // definition. We could easily extend this to look through geps, bitcasts,
641 // and the like to prove non-nullness, but it's not clear that's worth it
642 // compile time wise. The context-insensitive value walk done inside
643 // isKnownNonZero gets most of the profitable cases at much less expense.
644 // This does mean that we have a sensitivity to where the defining
645 // instruction is placed, even if it could legally be hoisted much higher.
646 // That is unfortunate.
647 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
648 if (PT && isKnownNonZero(BBI, /*Depth=*/0, DL))
650
651 if (BBI->getType()->isIntegerTy()) {
652 if (auto *CI = dyn_cast<CastInst>(BBI))
653 return solveBlockValueCast(CI, BB);
654
655 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
656 return solveBlockValueBinaryOp(BO, BB);
657
658 if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
659 return solveBlockValueExtractValue(EVI, BB);
660
661 if (auto *II = dyn_cast<IntrinsicInst>(BBI))
662 return solveBlockValueIntrinsic(II, BB);
663 }
664
665 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
666 << "' - unknown inst def found.\n");
667 return getFromRangeMetadata(BBI);
668}
669
670static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) {
671 // TODO: Use NullPointerIsDefined instead.
672 if (Ptr->getType()->getPointerAddressSpace() == 0)
673 PtrSet.insert(getUnderlyingObject(Ptr));
674}
675
677 Instruction *I, NonNullPointerSet &PtrSet) {
678 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
679 AddNonNullPointer(L->getPointerOperand(), PtrSet);
680 } else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
681 AddNonNullPointer(S->getPointerOperand(), PtrSet);
682 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
683 if (MI->isVolatile()) return;
684
685 // FIXME: check whether it has a valuerange that excludes zero?
686 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
687 if (!Len || Len->isZero()) return;
688
689 AddNonNullPointer(MI->getRawDest(), PtrSet);
690 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
691 AddNonNullPointer(MTI->getRawSource(), PtrSet);
692 }
693}
694
695bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
698 return false;
699
700 Val = Val->stripInBoundsOffsets();
701 return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
702 NonNullPointerSet NonNullPointers;
703 for (Instruction &I : *BB)
704 AddNonNullPointersByInstruction(&I, NonNullPointers);
705 return NonNullPointers;
706 });
707}
708
709std::optional<ValueLatticeElement>
710LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {
711 ValueLatticeElement Result; // Start Undefined.
712
713 // If this is the entry block, we must be asking about an argument.
714 if (BB->isEntryBlock()) {
715 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
716 if (std::optional<ConstantRange> Range = cast<Argument>(Val)->getRange())
717 return ValueLatticeElement::getRange(*Range);
719 }
720
721 // Loop over all of our predecessors, merging what we know from them into
722 // result. If we encounter an unexplored predecessor, we eagerly explore it
723 // in a depth first manner. In practice, this has the effect of discovering
724 // paths we can't analyze eagerly without spending compile times analyzing
725 // other paths. This heuristic benefits from the fact that predecessors are
726 // frequently arranged such that dominating ones come first and we quickly
727 // find a path to function entry. TODO: We should consider explicitly
728 // canonicalizing to make this true rather than relying on this happy
729 // accident.
730 for (BasicBlock *Pred : predecessors(BB)) {
731 std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
732 if (!EdgeResult)
733 // Explore that input, then return here
734 return std::nullopt;
735
736 Result.mergeIn(*EdgeResult);
737
738 // If we hit overdefined, exit early. The BlockVals entry is already set
739 // to overdefined.
740 if (Result.isOverdefined()) {
741 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
742 << "' - overdefined because of pred '"
743 << Pred->getName() << "' (non local).\n");
744 return Result;
745 }
746 }
747
748 // Return the merged value, which is more precise than 'overdefined'.
749 assert(!Result.isOverdefined());
750 return Result;
751}
752
753std::optional<ValueLatticeElement>
754LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {
755 ValueLatticeElement Result; // Start Undefined.
756
757 // Loop over all of our predecessors, merging what we know from them into
758 // result. See the comment about the chosen traversal order in
759 // solveBlockValueNonLocal; the same reasoning applies here.
760 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
761 BasicBlock *PhiBB = PN->getIncomingBlock(i);
762 Value *PhiVal = PN->getIncomingValue(i);
763 // Note that we can provide PN as the context value to getEdgeValue, even
764 // though the results will be cached, because PN is the value being used as
765 // the cache key in the caller.
766 std::optional<ValueLatticeElement> EdgeResult =
767 getEdgeValue(PhiVal, PhiBB, BB, PN);
768 if (!EdgeResult)
769 // Explore that input, then return here
770 return std::nullopt;
771
772 Result.mergeIn(*EdgeResult);
773
774 // If we hit overdefined, exit early. The BlockVals entry is already set
775 // to overdefined.
776 if (Result.isOverdefined()) {
777 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
778 << "' - overdefined because of pred (local).\n");
779
780 return Result;
781 }
782 }
783
784 // Return the merged value, which is more precise than 'overdefined'.
785 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
786 return Result;
787}
788
789// If we can determine a constraint on the value given conditions assumed by
790// the program, intersect those constraints with BBLV
791void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
792 Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
793 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
794 if (!BBI)
795 return;
796
797 BasicBlock *BB = BBI->getParent();
798 for (auto &AssumeVH : AC->assumptionsFor(Val)) {
799 if (!AssumeVH)
800 continue;
801
802 // Only check assumes in the block of the context instruction. Other
803 // assumes will have already been taken into account when the value was
804 // propagated from predecessor blocks.
805 auto *I = cast<CallInst>(AssumeVH);
806 if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
807 continue;
808
809 BBLV = intersect(BBLV, *getValueFromCondition(Val, I->getArgOperand(0),
810 /*IsTrueDest*/ true,
811 /*UseBlockValue*/ false));
812 }
813
814 // If guards are not used in the module, don't spend time looking for them
815 if (GuardDecl && !GuardDecl->use_empty() &&
816 BBI->getIterator() != BB->begin()) {
817 for (Instruction &I :
818 make_range(std::next(BBI->getIterator().getReverse()), BB->rend())) {
819 Value *Cond = nullptr;
820 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
821 BBLV = intersect(BBLV,
822 *getValueFromCondition(Val, Cond, /*IsTrueDest*/ true,
823 /*UseBlockValue*/ false));
824 }
825 }
826
827 if (BBLV.isOverdefined()) {
828 // Check whether we're checking at the terminator, and the pointer has
829 // been dereferenced in this block.
830 PointerType *PTy = dyn_cast<PointerType>(Val->getType());
831 if (PTy && BB->getTerminator() == BBI &&
832 isNonNullAtEndOfBlock(Val, BB))
834 }
835}
836
838 Type *Ty, bool UndefAllowed = false) {
839 assert(Ty->isIntOrIntVectorTy() && "Must be integer type");
840 if (Val.isConstantRange(UndefAllowed))
841 return Val.getConstantRange();
842 unsigned BW = Ty->getScalarSizeInBits();
843 if (Val.isUnknown())
844 return ConstantRange::getEmpty(BW);
845 return ConstantRange::getFull(BW);
846}
847
848std::optional<ValueLatticeElement>
849LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) {
850 // Recurse on our inputs if needed
851 std::optional<ValueLatticeElement> OptTrueVal =
852 getBlockValue(SI->getTrueValue(), BB, SI);
853 if (!OptTrueVal)
854 return std::nullopt;
855 ValueLatticeElement &TrueVal = *OptTrueVal;
856
857 std::optional<ValueLatticeElement> OptFalseVal =
858 getBlockValue(SI->getFalseValue(), BB, SI);
859 if (!OptFalseVal)
860 return std::nullopt;
861 ValueLatticeElement &FalseVal = *OptFalseVal;
862
863 if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
864 const ConstantRange &TrueCR = toConstantRange(TrueVal, SI->getType());
865 const ConstantRange &FalseCR = toConstantRange(FalseVal, SI->getType());
866 Value *LHS = nullptr;
867 Value *RHS = nullptr;
868 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
869 // Is this a min specifically of our two inputs? (Avoid the risk of
870 // ValueTracking getting smarter looking back past our immediate inputs.)
872 ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
873 (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
874 ConstantRange ResultCR = [&]() {
875 switch (SPR.Flavor) {
876 default:
877 llvm_unreachable("unexpected minmax type!");
878 case SPF_SMIN: /// Signed minimum
879 return TrueCR.smin(FalseCR);
880 case SPF_UMIN: /// Unsigned minimum
881 return TrueCR.umin(FalseCR);
882 case SPF_SMAX: /// Signed maximum
883 return TrueCR.smax(FalseCR);
884 case SPF_UMAX: /// Unsigned maximum
885 return TrueCR.umax(FalseCR);
886 };
887 }();
889 ResultCR, TrueVal.isConstantRangeIncludingUndef() ||
890 FalseVal.isConstantRangeIncludingUndef());
891 }
892
893 if (SPR.Flavor == SPF_ABS) {
894 if (LHS == SI->getTrueValue())
896 TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
897 if (LHS == SI->getFalseValue())
899 FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
900 }
901
902 if (SPR.Flavor == SPF_NABS) {
904 if (LHS == SI->getTrueValue())
906 Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
907 if (LHS == SI->getFalseValue())
909 Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
910 }
911 }
912
913 // Can we constrain the facts about the true and false values by using the
914 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
915 // TODO: We could potentially refine an overdefined true value above.
916 Value *Cond = SI->getCondition();
917 // If the value is undef, a different value may be chosen in
918 // the select condition.
920 TrueVal =
921 intersect(TrueVal, *getValueFromCondition(SI->getTrueValue(), Cond,
922 /*IsTrueDest*/ true,
923 /*UseBlockValue*/ false));
924 FalseVal =
925 intersect(FalseVal, *getValueFromCondition(SI->getFalseValue(), Cond,
926 /*IsTrueDest*/ false,
927 /*UseBlockValue*/ false));
928 }
929
931 Result.mergeIn(FalseVal);
932 return Result;
933}
934
935std::optional<ConstantRange>
936LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) {
937 std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
938 if (!OptVal)
939 return std::nullopt;
940 return toConstantRange(*OptVal, V->getType());
941}
942
943std::optional<ValueLatticeElement>
944LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {
945 // Filter out casts we don't know how to reason about before attempting to
946 // recurse on our operand. This can cut a long search short if we know we're
947 // not going to be able to get any useful information anways.
948 switch (CI->getOpcode()) {
949 case Instruction::Trunc:
950 case Instruction::SExt:
951 case Instruction::ZExt:
952 break;
953 default:
954 // Unhandled instructions are overdefined.
955 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
956 << "' - overdefined (unknown cast).\n");
958 }
959
960 // Figure out the range of the LHS. If that fails, we still apply the
961 // transfer rule on the full set since we may be able to locally infer
962 // interesting facts.
963 std::optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB);
964 if (!LHSRes)
965 // More work to do before applying this transfer rule.
966 return std::nullopt;
967 const ConstantRange &LHSRange = *LHSRes;
968
969 const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
970
971 // NOTE: We're currently limited by the set of operations that ConstantRange
972 // can evaluate symbolically. Enhancing that set will allows us to analyze
973 // more definitions.
974 return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
975 ResultBitWidth));
976}
977
978std::optional<ValueLatticeElement>
979LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
981 std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
982 OpFn) {
983 // Figure out the ranges of the operands. If that fails, use a
984 // conservative range, but apply the transfer rule anyways. This
985 // lets us pick up facts from expressions like "and i32 (call i32
986 // @foo()), 32"
987 std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB);
988 if (!LHSRes)
989 return std::nullopt;
990
991 std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB);
992 if (!RHSRes)
993 return std::nullopt;
994
995 const ConstantRange &LHSRange = *LHSRes;
996 const ConstantRange &RHSRange = *RHSRes;
997 return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
998}
999
1000std::optional<ValueLatticeElement>
1001LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) {
1002 assert(BO->getOperand(0)->getType()->isSized() &&
1003 "all operands to binary operators are sized");
1004 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
1005 unsigned NoWrapKind = OBO->getNoWrapKind();
1006 return solveBlockValueBinaryOpImpl(
1007 BO, BB,
1008 [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
1009 return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
1010 });
1011 }
1012
1013 return solveBlockValueBinaryOpImpl(
1014 BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
1015 return CR1.binaryOp(BO->getOpcode(), CR2);
1016 });
1017}
1018
1019std::optional<ValueLatticeElement>
1020LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
1021 BasicBlock *BB) {
1022 return solveBlockValueBinaryOpImpl(
1023 WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
1024 return CR1.binaryOp(WO->getBinaryOp(), CR2);
1025 });
1026}
1027
1028std::optional<ValueLatticeElement>
1029LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) {
1030 ValueLatticeElement MetadataVal = getFromRangeMetadata(II);
1032 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1033 << "' - unknown intrinsic.\n");
1034 return MetadataVal;
1035 }
1036
1038 for (Value *Op : II->args()) {
1039 std::optional<ConstantRange> Range = getRangeFor(Op, II, BB);
1040 if (!Range)
1041 return std::nullopt;
1042 OpRanges.push_back(*Range);
1043 }
1044
1046 II->getIntrinsicID(), OpRanges)),
1047 MetadataVal);
1048}
1049
1050std::optional<ValueLatticeElement>
1051LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
1052 BasicBlock *BB) {
1053 if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1054 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
1055 return solveBlockValueOverflowIntrinsic(WO, BB);
1056
1057 // Handle extractvalue of insertvalue to allow further simplification
1058 // based on replaced with.overflow intrinsics.
1060 EVI->getAggregateOperand(), EVI->getIndices(),
1061 EVI->getModule()->getDataLayout()))
1062 return getBlockValue(V, BB, EVI);
1063
1064 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1065 << "' - overdefined (unknown extractvalue).\n");
1067}
1068
1069static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
1070 ICmpInst::Predicate Pred) {
1071 if (LHS == Val)
1072 return true;
1073
1074 // Handle range checking idiom produced by InstCombine. We will subtract the
1075 // offset from the allowed range for RHS in this case.
1076 const APInt *C;
1077 if (match(LHS, m_AddLike(m_Specific(Val), m_APInt(C)))) {
1078 Offset = *C;
1079 return true;
1080 }
1081
1082 // Handle the symmetric case. This appears in saturation patterns like
1083 // (x == 16) ? 16 : (x + 1).
1084 if (match(Val, m_AddLike(m_Specific(LHS), m_APInt(C)))) {
1085 Offset = -*C;
1086 return true;
1087 }
1088
1089 // If (x | y) < C, then (x < C) && (y < C).
1090 if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
1091 (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
1092 return true;
1093
1094 // If (x & y) > C, then (x > C) && (y > C).
1095 if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
1096 (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
1097 return true;
1098
1099 return false;
1100}
1101
1102/// Get value range for a "(Val + Offset) Pred RHS" condition.
1103std::optional<ValueLatticeElement>
1104LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,
1105 Value *RHS,
1106 const APInt &Offset,
1107 Instruction *CxtI,
1108 bool UseBlockValue) {
1110 /*isFullSet=*/true);
1111 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1112 RHSRange = ConstantRange(CI->getValue());
1113 } else if (UseBlockValue) {
1114 std::optional<ValueLatticeElement> R =
1115 getBlockValue(RHS, CxtI->getParent(), CxtI);
1116 if (!R)
1117 return std::nullopt;
1118 RHSRange = toConstantRange(*R, RHS->getType());
1119 } else if (Instruction *I = dyn_cast<Instruction>(RHS)) {
1120 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1121 RHSRange = getConstantRangeFromMetadata(*Ranges);
1122 }
1123
1124 ConstantRange TrueValues =
1126 return ValueLatticeElement::getRange(TrueValues.subtract(Offset));
1127}
1128
1129static std::optional<ConstantRange>
1131 function_ref<std::optional<ConstantRange>(const APInt &)> Fn) {
1132 bool Invert = false;
1133 if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) {
1134 Pred = ICmpInst::getInversePredicate(Pred);
1135 Invert = true;
1136 }
1137 if (Pred == ICmpInst::ICMP_SLE) {
1138 Pred = ICmpInst::ICMP_SLT;
1139 if (RHS.isMaxSignedValue())
1140 return std::nullopt; // Could also return full/empty here, if we wanted.
1141 ++RHS;
1142 }
1143 assert(Pred == ICmpInst::ICMP_SLT && "Must be signed predicate");
1144 if (auto CR = Fn(RHS))
1145 return Invert ? CR->inverse() : CR;
1146 return std::nullopt;
1147}
1148
1149std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(
1150 Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) {
1151 Value *LHS = ICI->getOperand(0);
1152 Value *RHS = ICI->getOperand(1);
1153
1154 // Get the predicate that must hold along the considered edge.
1155 CmpInst::Predicate EdgePred =
1156 isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
1157
1158 if (isa<Constant>(RHS)) {
1159 if (ICI->isEquality() && LHS == Val) {
1160 if (EdgePred == ICmpInst::ICMP_EQ)
1161 return ValueLatticeElement::get(cast<Constant>(RHS));
1162 else if (!isa<UndefValue>(RHS))
1163 return ValueLatticeElement::getNot(cast<Constant>(RHS));
1164 }
1165 }
1166
1167 Type *Ty = Val->getType();
1168 if (!Ty->isIntegerTy())
1170
1171 unsigned BitWidth = Ty->getScalarSizeInBits();
1172 APInt Offset(BitWidth, 0);
1173 if (matchICmpOperand(Offset, LHS, Val, EdgePred))
1174 return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset, ICI,
1175 UseBlockValue);
1176
1177 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred);
1178 if (matchICmpOperand(Offset, RHS, Val, SwappedPred))
1179 return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset, ICI,
1180 UseBlockValue);
1181
1182 const APInt *Mask, *C;
1183 if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) &&
1184 match(RHS, m_APInt(C))) {
1185 // If (Val & Mask) == C then all the masked bits are known and we can
1186 // compute a value range based on that.
1187 if (EdgePred == ICmpInst::ICMP_EQ) {
1188 KnownBits Known;
1189 Known.Zero = ~*C & *Mask;
1190 Known.One = *C & *Mask;
1192 ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
1193 }
1194 // If (Val & Mask) != 0 then the value must be larger than the lowest set
1195 // bit of Mask.
1196 if (EdgePred == ICmpInst::ICMP_NE && !Mask->isZero() && C->isZero()) {
1198 APInt::getOneBitSet(BitWidth, Mask->countr_zero()),
1200 }
1201 }
1202
1203 // If (X urem Modulus) >= C, then X >= C.
1204 // If trunc X >= C, then X >= C.
1205 // TODO: An upper bound could be computed as well.
1206 if (match(LHS, m_CombineOr(m_URem(m_Specific(Val), m_Value()),
1207 m_Trunc(m_Specific(Val)))) &&
1208 match(RHS, m_APInt(C))) {
1209 // Use the icmp region so we don't have to deal with different predicates.
1211 if (!CR.isEmptySet())
1214 }
1215
1216 // Recognize:
1217 // icmp slt (ashr X, ShAmtC), C --> icmp slt X, C << ShAmtC
1218 // Preconditions: (C << ShAmtC) >> ShAmtC == C
1219 const APInt *ShAmtC;
1220 if (CmpInst::isSigned(EdgePred) &&
1221 match(LHS, m_AShr(m_Specific(Val), m_APInt(ShAmtC))) &&
1222 match(RHS, m_APInt(C))) {
1223 auto CR = getRangeViaSLT(
1224 EdgePred, *C, [&](const APInt &RHS) -> std::optional<ConstantRange> {
1225 APInt New = RHS << *ShAmtC;
1226 if ((New.ashr(*ShAmtC)) != RHS)
1227 return std::nullopt;
1229 APInt::getSignedMinValue(New.getBitWidth()), New);
1230 });
1231 if (CR)
1233 }
1234
1236}
1237
1238// Handle conditions of the form
1239// extractvalue(op.with.overflow(%x, C), 1).
1241 Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1242 // TODO: This only works with a constant RHS for now. We could also compute
1243 // the range of the RHS, but this doesn't fit into the current structure of
1244 // the edge value calculation.
1245 const APInt *C;
1246 if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
1248
1249 // Calculate the possible values of %x for which no overflow occurs.
1251 WO->getBinaryOp(), *C, WO->getNoWrapKind());
1252
1253 // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1254 // constrained to it's inverse (all values that might cause overflow).
1255 if (IsTrueDest)
1256 NWR = NWR.inverse();
1258}
1259
1260std::optional<ValueLatticeElement>
1261LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond,
1262 bool IsTrueDest, bool UseBlockValue,
1263 unsigned Depth) {
1264 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1265 return getValueFromICmpCondition(Val, ICI, IsTrueDest, UseBlockValue);
1266
1267 if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
1268 if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1269 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1270 return getValueFromOverflowCondition(Val, WO, IsTrueDest);
1271
1274
1275 Value *N;
1276 if (match(Cond, m_Not(m_Value(N))))
1277 return getValueFromCondition(Val, N, !IsTrueDest, UseBlockValue, Depth);
1278
1279 Value *L, *R;
1280 bool IsAnd;
1281 if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))))
1282 IsAnd = true;
1283 else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
1284 IsAnd = false;
1285 else
1287
1288 std::optional<ValueLatticeElement> LV =
1289 getValueFromCondition(Val, L, IsTrueDest, UseBlockValue, Depth);
1290 if (!LV)
1291 return std::nullopt;
1292 std::optional<ValueLatticeElement> RV =
1293 getValueFromCondition(Val, R, IsTrueDest, UseBlockValue, Depth);
1294 if (!RV)
1295 return std::nullopt;
1296
1297 // if (L && R) -> intersect L and R
1298 // if (!(L || R)) -> intersect !L and !R
1299 // if (L || R) -> union L and R
1300 // if (!(L && R)) -> union !L and !R
1301 if (IsTrueDest ^ IsAnd) {
1302 LV->mergeIn(*RV);
1303 return *LV;
1304 }
1305
1306 return intersect(*LV, *RV);
1307}
1308
1309// Return true if Usr has Op as an operand, otherwise false.
1310static bool usesOperand(User *Usr, Value *Op) {
1311 return is_contained(Usr->operands(), Op);
1312}
1313
1314// Return true if the instruction type of Val is supported by
1315// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
1316// Call this before calling constantFoldUser() to find out if it's even worth
1317// attempting to call it.
1318static bool isOperationFoldable(User *Usr) {
1319 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1320}
1321
1322// Check if Usr can be simplified to an integer constant when the value of one
1323// of its operands Op is an integer constant OpConstVal. If so, return it as an
1324// lattice value range with a single element or otherwise return an overdefined
1325// lattice value.
1327 const APInt &OpConstVal,
1328 const DataLayout &DL) {
1329 assert(isOperationFoldable(Usr) && "Precondition");
1330 Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1331 // Check if Usr can be simplified to a constant.
1332 if (auto *CI = dyn_cast<CastInst>(Usr)) {
1333 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1334 if (auto *C = dyn_cast_or_null<ConstantInt>(
1335 simplifyCastInst(CI->getOpcode(), OpConst,
1336 CI->getDestTy(), DL))) {
1337 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1338 }
1339 } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1340 bool Op0Match = BO->getOperand(0) == Op;
1341 bool Op1Match = BO->getOperand(1) == Op;
1342 assert((Op0Match || Op1Match) &&
1343 "Operand 0 nor Operand 1 isn't a match");
1344 Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1345 Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1346 if (auto *C = dyn_cast_or_null<ConstantInt>(
1347 simplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1348 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1349 }
1350 } else if (isa<FreezeInst>(Usr)) {
1351 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
1352 return ValueLatticeElement::getRange(ConstantRange(OpConstVal));
1353 }
1355}
1356
1357/// Compute the value of Val on the edge BBFrom -> BBTo.
1358std::optional<ValueLatticeElement>
1359LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1360 BasicBlock *BBTo, bool UseBlockValue) {
1361 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1362 // know that v != 0.
1363 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1364 // If this is a conditional branch and only one successor goes to BBTo, then
1365 // we may be able to infer something from the condition.
1366 if (BI->isConditional() &&
1367 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1368 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1369 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1370 "BBTo isn't a successor of BBFrom");
1371 Value *Condition = BI->getCondition();
1372
1373 // If V is the condition of the branch itself, then we know exactly what
1374 // it is.
1375 if (Condition == Val)
1376 return ValueLatticeElement::get(ConstantInt::get(
1377 Type::getInt1Ty(Val->getContext()), isTrueDest));
1378
1379 // If the condition of the branch is an equality comparison, we may be
1380 // able to infer the value.
1381 std::optional<ValueLatticeElement> Result =
1382 getValueFromCondition(Val, Condition, isTrueDest, UseBlockValue);
1383 if (!Result)
1384 return std::nullopt;
1385
1386 if (!Result->isOverdefined())
1387 return Result;
1388
1389 if (User *Usr = dyn_cast<User>(Val)) {
1390 assert(Result->isOverdefined() && "Result isn't overdefined");
1391 // Check with isOperationFoldable() first to avoid linearly iterating
1392 // over the operands unnecessarily which can be expensive for
1393 // instructions with many operands.
1394 if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1395 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1396 if (usesOperand(Usr, Condition)) {
1397 // If Val has Condition as an operand and Val can be folded into a
1398 // constant with either Condition == true or Condition == false,
1399 // propagate the constant.
1400 // eg.
1401 // ; %Val is true on the edge to %then.
1402 // %Val = and i1 %Condition, true.
1403 // br %Condition, label %then, label %else
1404 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1405 Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1406 } else {
1407 // If one of Val's operand has an inferred value, we may be able to
1408 // infer the value of Val.
1409 // eg.
1410 // ; %Val is 94 on the edge to %then.
1411 // %Val = add i8 %Op, 1
1412 // %Condition = icmp eq i8 %Op, 93
1413 // br i1 %Condition, label %then, label %else
1414 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1415 Value *Op = Usr->getOperand(i);
1416 ValueLatticeElement OpLatticeVal = *getValueFromCondition(
1417 Op, Condition, isTrueDest, /*UseBlockValue*/ false);
1418 if (std::optional<APInt> OpConst =
1419 OpLatticeVal.asConstantInteger()) {
1420 Result = constantFoldUser(Usr, Op, *OpConst, DL);
1421 break;
1422 }
1423 }
1424 }
1425 }
1426 }
1427 if (!Result->isOverdefined())
1428 return Result;
1429 }
1430 }
1431
1432 // If the edge was formed by a switch on the value, then we may know exactly
1433 // what it is.
1434 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1435 Value *Condition = SI->getCondition();
1436 if (!isa<IntegerType>(Val->getType()))
1438 bool ValUsesConditionAndMayBeFoldable = false;
1439 if (Condition != Val) {
1440 // Check if Val has Condition as an operand.
1441 if (User *Usr = dyn_cast<User>(Val))
1442 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1443 usesOperand(Usr, Condition);
1444 if (!ValUsesConditionAndMayBeFoldable)
1446 }
1447 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1448 "Condition != Val nor Val doesn't use Condition");
1449
1450 bool DefaultCase = SI->getDefaultDest() == BBTo;
1451 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1452 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1453
1454 for (auto Case : SI->cases()) {
1455 APInt CaseValue = Case.getCaseValue()->getValue();
1456 ConstantRange EdgeVal(CaseValue);
1457 if (ValUsesConditionAndMayBeFoldable) {
1458 User *Usr = cast<User>(Val);
1459 const DataLayout &DL = BBTo->getModule()->getDataLayout();
1460 ValueLatticeElement EdgeLatticeVal =
1461 constantFoldUser(Usr, Condition, CaseValue, DL);
1462 if (EdgeLatticeVal.isOverdefined())
1464 EdgeVal = EdgeLatticeVal.getConstantRange();
1465 }
1466 if (DefaultCase) {
1467 // It is possible that the default destination is the destination of
1468 // some cases. We cannot perform difference for those cases.
1469 // We know Condition != CaseValue in BBTo. In some cases we can use
1470 // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1471 // only do this when f is identity (i.e. Val == Condition), but we
1472 // should be able to do this for any injective f.
1473 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1474 EdgesVals = EdgesVals.difference(EdgeVal);
1475 } else if (Case.getCaseSuccessor() == BBTo)
1476 EdgesVals = EdgesVals.unionWith(EdgeVal);
1477 }
1478 return ValueLatticeElement::getRange(std::move(EdgesVals));
1479 }
1481}
1482
1483/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1484/// the basic block if the edge does not constrain Val.
1485std::optional<ValueLatticeElement>
1486LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1487 BasicBlock *BBTo, Instruction *CxtI) {
1488 // If already a constant, there is nothing to compute.
1489 if (Constant *VC = dyn_cast<Constant>(Val))
1490 return ValueLatticeElement::get(VC);
1491
1492 std::optional<ValueLatticeElement> LocalResult =
1493 getEdgeValueLocal(Val, BBFrom, BBTo, /*UseBlockValue*/ true);
1494 if (!LocalResult)
1495 return std::nullopt;
1496
1497 if (hasSingleValue(*LocalResult))
1498 // Can't get any more precise here
1499 return LocalResult;
1500
1501 std::optional<ValueLatticeElement> OptInBlock =
1502 getBlockValue(Val, BBFrom, BBFrom->getTerminator());
1503 if (!OptInBlock)
1504 return std::nullopt;
1505 ValueLatticeElement &InBlock = *OptInBlock;
1506
1507 // We can use the context instruction (generically the ultimate instruction
1508 // the calling pass is trying to simplify) here, even though the result of
1509 // this function is generally cached when called from the solve* functions
1510 // (and that cached result might be used with queries using a different
1511 // context instruction), because when this function is called from the solve*
1512 // functions, the context instruction is not provided. When called from
1513 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1514 // but then the result is not cached.
1515 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1516
1517 return intersect(*LocalResult, InBlock);
1518}
1519
1521 Instruction *CxtI) {
1522 LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1523 << BB->getName() << "'\n");
1524
1525 assert(BlockValueStack.empty() && BlockValueSet.empty());
1526 std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
1527 if (!OptResult) {
1528 solve();
1529 OptResult = getBlockValue(V, BB, CxtI);
1530 assert(OptResult && "Value not available after solving");
1531 }
1532
1533 ValueLatticeElement Result = *OptResult;
1534 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1535 return Result;
1536}
1537
1539 LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1540 << "'\n");
1541
1542 if (auto *C = dyn_cast<Constant>(V))
1544
1546 if (auto *I = dyn_cast<Instruction>(V))
1547 Result = getFromRangeMetadata(I);
1548 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1549
1550 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1551 return Result;
1552}
1553
1555getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1556 Instruction *CxtI) {
1557 LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1558 << FromBB->getName() << "' to '" << ToBB->getName()
1559 << "'\n");
1560
1561 std::optional<ValueLatticeElement> Result =
1562 getEdgeValue(V, FromBB, ToBB, CxtI);
1563 while (!Result) {
1564 // As the worklist only explicitly tracks block values (but not edge values)
1565 // we may have to call solve() multiple times, as the edge value calculation
1566 // may request additional block values.
1567 solve();
1568 Result = getEdgeValue(V, FromBB, ToBB, CxtI);
1569 }
1570
1571 LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");
1572 return *Result;
1573}
1574
1576 Value *V = U.get();
1577 auto *CxtI = cast<Instruction>(U.getUser());
1578 ValueLatticeElement VL = getValueInBlock(V, CxtI->getParent(), CxtI);
1579
1580 // Check whether the only (possibly transitive) use of the value is in a
1581 // position where V can be constrained by a select or branch condition.
1582 const Use *CurrU = &U;
1583 // TODO: Increase limit?
1584 const unsigned MaxUsesToInspect = 3;
1585 for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
1586 std::optional<ValueLatticeElement> CondVal;
1587 auto *CurrI = cast<Instruction>(CurrU->getUser());
1588 if (auto *SI = dyn_cast<SelectInst>(CurrI)) {
1589 // If the value is undef, a different value may be chosen in
1590 // the select condition and at use.
1591 if (!isGuaranteedNotToBeUndef(SI->getCondition(), AC))
1592 break;
1593 if (CurrU->getOperandNo() == 1)
1594 CondVal =
1595 *getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ true,
1596 /*UseBlockValue*/ false);
1597 else if (CurrU->getOperandNo() == 2)
1598 CondVal =
1599 *getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ false,
1600 /*UseBlockValue*/ false);
1601 } else if (auto *PHI = dyn_cast<PHINode>(CurrI)) {
1602 // TODO: Use non-local query?
1603 CondVal = *getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU),
1604 PHI->getParent(), /*UseBlockValue*/ false);
1605 }
1606 if (CondVal)
1607 VL = intersect(VL, *CondVal);
1608
1609 // Only follow one-use chain, to allow direct intersection of conditions.
1610 // If there are multiple uses, we would have to intersect with the union of
1611 // all conditions at different uses.
1612 // Stop walking if we hit a non-speculatable instruction. Even if the
1613 // result is only used under a specific condition, executing the
1614 // instruction itself may cause side effects or UB already.
1615 // This also disallows looking through phi nodes: If the phi node is part
1616 // of a cycle, we might end up reasoning about values from different cycle
1617 // iterations (PR60629).
1618 if (!CurrI->hasOneUse() || !isSafeToSpeculativelyExecute(CurrI))
1619 break;
1620 CurrU = &*CurrI->use_begin();
1621 }
1622 return VL;
1623}
1624
1626 BasicBlock *NewSucc) {
1627 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1628}
1629
1630//===----------------------------------------------------------------------===//
1631// LazyValueInfo Impl
1632//===----------------------------------------------------------------------===//
1633
1635 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1636
1637 if (auto *Impl = Info.getImpl())
1638 Impl->clear();
1639
1640 // Fully lazy.
1641 return false;
1642}
1643
1645 AU.setPreservesAll();
1648}
1649
1651
1652/// This lazily constructs the LazyValueInfoImpl.
1653LazyValueInfoImpl &LazyValueInfo::getOrCreateImpl(const Module *M) {
1654 if (!PImpl) {
1655 assert(M && "getCache() called with a null Module");
1656 const DataLayout &DL = M->getDataLayout();
1657 Function *GuardDecl =
1658 M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
1659 PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl);
1660 }
1661 return *static_cast<LazyValueInfoImpl *>(PImpl);
1662}
1663
1664LazyValueInfoImpl *LazyValueInfo::getImpl() {
1665 if (!PImpl)
1666 return nullptr;
1667 return static_cast<LazyValueInfoImpl *>(PImpl);
1668}
1669
1671
1673 // If the cache was allocated, free it.
1674 if (auto *Impl = getImpl()) {
1675 delete &*Impl;
1676 PImpl = nullptr;
1677 }
1678}
1679
1682 // We need to invalidate if we have either failed to preserve this analyses
1683 // result directly or if any of its dependencies have been invalidated.
1684 auto PAC = PA.getChecker<LazyValueAnalysis>();
1685 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
1686 return true;
1687
1688 return false;
1689}
1690
1692
1695 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1696
1697 return LazyValueInfo(&AC, &F.getParent()->getDataLayout());
1698}
1699
1700/// Returns true if we can statically tell that this value will never be a
1701/// "useful" constant. In practice, this means we've got something like an
1702/// alloca or a malloc call for which a comparison against a constant can
1703/// only be guarding dead code. Note that we are potentially giving up some
1704/// precision in dead code (a constant result) in favour of avoiding a
1705/// expensive search for a easily answered common query.
1706static bool isKnownNonConstant(Value *V) {
1707 V = V->stripPointerCasts();
1708 // The return val of alloc cannot be a Constant.
1709 if (isa<AllocaInst>(V))
1710 return true;
1711 return false;
1712}
1713
1715 // Bail out early if V is known not to be a Constant.
1716 if (isKnownNonConstant(V))
1717 return nullptr;
1718
1719 BasicBlock *BB = CxtI->getParent();
1720 ValueLatticeElement Result =
1721 getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);
1722
1723 if (Result.isConstant())
1724 return Result.getConstant();
1725 if (Result.isConstantRange()) {
1726 const ConstantRange &CR = Result.getConstantRange();
1727 if (const APInt *SingleVal = CR.getSingleElement())
1728 return ConstantInt::get(V->getContext(), *SingleVal);
1729 }
1730 return nullptr;
1731}
1732
1734 bool UndefAllowed) {
1735 assert(V->getType()->isIntegerTy());
1736 BasicBlock *BB = CxtI->getParent();
1737 ValueLatticeElement Result =
1738 getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);
1739 return toConstantRange(Result, V->getType(), UndefAllowed);
1740}
1741
1743 bool UndefAllowed) {
1744 auto *Inst = cast<Instruction>(U.getUser());
1745 ValueLatticeElement Result =
1746 getOrCreateImpl(Inst->getModule()).getValueAtUse(U);
1747 return toConstantRange(Result, U->getType(), UndefAllowed);
1748}
1749
1750/// Determine whether the specified value is known to be a
1751/// constant on the specified edge. Return null if not.
1753 BasicBlock *ToBB,
1754 Instruction *CxtI) {
1755 Module *M = FromBB->getModule();
1756 ValueLatticeElement Result =
1757 getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1758
1759 if (Result.isConstant())
1760 return Result.getConstant();
1761 if (Result.isConstantRange()) {
1762 const ConstantRange &CR = Result.getConstantRange();
1763 if (const APInt *SingleVal = CR.getSingleElement())
1764 return ConstantInt::get(V->getContext(), *SingleVal);
1765 }
1766 return nullptr;
1767}
1768
1770 BasicBlock *FromBB,
1771 BasicBlock *ToBB,
1772 Instruction *CxtI) {
1773 Module *M = FromBB->getModule();
1774 ValueLatticeElement Result =
1775 getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1776 // TODO: Should undef be allowed here?
1777 return toConstantRange(Result, V->getType(), /*UndefAllowed*/ true);
1778}
1779
1782 const DataLayout &DL) {
1783 // If we know the value is a constant, evaluate the conditional.
1784 Constant *Res = nullptr;
1785 if (Val.isConstant()) {
1786 Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL);
1787 if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
1788 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1790 }
1791
1792 if (Val.isConstantRange()) {
1793 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1794 if (!CI) return LazyValueInfo::Unknown;
1795
1796 const ConstantRange &CR = Val.getConstantRange();
1797 if (Pred == ICmpInst::ICMP_EQ) {
1798 if (!CR.contains(CI->getValue()))
1799 return LazyValueInfo::False;
1800
1801 if (CR.isSingleElement())
1802 return LazyValueInfo::True;
1803 } else if (Pred == ICmpInst::ICMP_NE) {
1804 if (!CR.contains(CI->getValue()))
1805 return LazyValueInfo::True;
1806
1807 if (CR.isSingleElement())
1808 return LazyValueInfo::False;
1809 } else {
1810 // Handle more complex predicates.
1812 (ICmpInst::Predicate)Pred, CI->getValue());
1813 if (TrueValues.contains(CR))
1814 return LazyValueInfo::True;
1815 if (TrueValues.inverse().contains(CR))
1816 return LazyValueInfo::False;
1817 }
1819 }
1820
1821 if (Val.isNotConstant()) {
1822 // If this is an equality comparison, we can try to fold it knowing that
1823 // "V != C1".
1824 if (Pred == ICmpInst::ICMP_EQ) {
1825 // !C1 == C -> false iff C1 == C.
1827 Val.getNotConstant(), C, DL);
1828 if (Res && Res->isNullValue())
1829 return LazyValueInfo::False;
1830 } else if (Pred == ICmpInst::ICMP_NE) {
1831 // !C1 != C -> true iff C1 == C.
1833 Val.getNotConstant(), C, DL);
1834 if (Res && Res->isNullValue())
1835 return LazyValueInfo::True;
1836 }
1838 }
1839
1841}
1842
1843/// Determine whether the specified value comparison with a constant is known to
1844/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1847 BasicBlock *FromBB, BasicBlock *ToBB,
1848 Instruction *CxtI) {
1849 Module *M = FromBB->getModule();
1850 ValueLatticeElement Result =
1851 getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1852
1853 return getPredicateResult(Pred, C, Result, M->getDataLayout());
1854}
1855
1858 Instruction *CxtI, bool UseBlockValue) {
1859 // Is or is not NonNull are common predicates being queried. If
1860 // isKnownNonZero can tell us the result of the predicate, we can
1861 // return it quickly. But this is only a fastpath, and falling
1862 // through would still be correct.
1863 Module *M = CxtI->getModule();
1864 const DataLayout &DL = M->getDataLayout();
1865 if (V->getType()->isPointerTy() && C->isNullValue() &&
1866 isKnownNonZero(V->stripPointerCastsSameRepresentation(), /*Depth=*/0,
1867 DL)) {
1868 if (Pred == ICmpInst::ICMP_EQ)
1869 return LazyValueInfo::False;
1870 else if (Pred == ICmpInst::ICMP_NE)
1871 return LazyValueInfo::True;
1872 }
1873
1874 auto &Impl = getOrCreateImpl(M);
1875 ValueLatticeElement Result =
1876 UseBlockValue ? Impl.getValueInBlock(V, CxtI->getParent(), CxtI)
1877 : Impl.getValueAt(V, CxtI);
1878 Tristate Ret = getPredicateResult(Pred, C, Result, DL);
1879 if (Ret != Unknown)
1880 return Ret;
1881
1882 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1883 // LVI as a whole tries to compute a lattice value which is conservatively
1884 // correct at a given location. In this case, we have a predicate which we
1885 // weren't able to prove about the merged result, and we're pushing that
1886 // predicate back along each incoming edge to see if we can prove it
1887 // separately for each input. As a motivating example, consider:
1888 // bb1:
1889 // %v1 = ... ; constantrange<1, 5>
1890 // br label %merge
1891 // bb2:
1892 // %v2 = ... ; constantrange<10, 20>
1893 // br label %merge
1894 // merge:
1895 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1896 // %pred = icmp eq i32 %phi, 8
1897 // We can't tell from the lattice value for '%phi' that '%pred' is false
1898 // along each path, but by checking the predicate over each input separately,
1899 // we can.
1900 // We limit the search to one step backwards from the current BB and value.
1901 // We could consider extending this to search further backwards through the
1902 // CFG and/or value graph, but there are non-obvious compile time vs quality
1903 // tradeoffs.
1904 BasicBlock *BB = CxtI->getParent();
1905
1906 // Function entry or an unreachable block. Bail to avoid confusing
1907 // analysis below.
1908 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1909 if (PI == PE)
1910 return Unknown;
1911
1912 // If V is a PHI node in the same block as the context, we need to ask
1913 // questions about the predicate as applied to the incoming value along
1914 // each edge. This is useful for eliminating cases where the predicate is
1915 // known along all incoming edges.
1916 if (auto *PHI = dyn_cast<PHINode>(V))
1917 if (PHI->getParent() == BB) {
1918 Tristate Baseline = Unknown;
1919 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1920 Value *Incoming = PHI->getIncomingValue(i);
1921 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1922 // Note that PredBB may be BB itself.
1923 Tristate Result =
1924 getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI);
1925
1926 // Keep going as long as we've seen a consistent known result for
1927 // all inputs.
1928 Baseline = (i == 0) ? Result /* First iteration */
1929 : (Baseline == Result ? Baseline
1930 : Unknown); /* All others */
1931 if (Baseline == Unknown)
1932 break;
1933 }
1934 if (Baseline != Unknown)
1935 return Baseline;
1936 }
1937
1938 // For a comparison where the V is outside this block, it's possible
1939 // that we've branched on it before. Look to see if the value is known
1940 // on all incoming edges.
1941 if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
1942 // For predecessor edge, determine if the comparison is true or false
1943 // on that edge. If they're all true or all false, we can conclude
1944 // the value of the comparison in this block.
1945 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1946 if (Baseline != Unknown) {
1947 // Check that all remaining incoming values match the first one.
1948 while (++PI != PE) {
1949 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1950 if (Ret != Baseline)
1951 break;
1952 }
1953 // If we terminated early, then one of the values didn't match.
1954 if (PI == PE) {
1955 return Baseline;
1956 }
1957 }
1958 }
1959
1960 return Unknown;
1961}
1962
1964 Value *RHS,
1965 Instruction *CxtI,
1966 bool UseBlockValue) {
1968
1969 if (auto *C = dyn_cast<Constant>(RHS))
1970 return getPredicateAt(P, LHS, C, CxtI, UseBlockValue);
1971 if (auto *C = dyn_cast<Constant>(LHS))
1972 return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI,
1973 UseBlockValue);
1974
1975 // Got two non-Constant values. Try to determine the comparison results based
1976 // on the block values of the two operands, e.g. because they have
1977 // non-overlapping ranges.
1978 if (UseBlockValue) {
1979 Module *M = CxtI->getModule();
1981 getOrCreateImpl(M).getValueInBlock(LHS, CxtI->getParent(), CxtI);
1982 if (L.isOverdefined())
1984
1986 getOrCreateImpl(M).getValueInBlock(RHS, CxtI->getParent(), CxtI);
1988 if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R,
1989 M->getDataLayout())) {
1990 if (Res->isNullValue())
1991 return LazyValueInfo::False;
1992 if (Res->isOneValue())
1993 return LazyValueInfo::True;
1994 }
1995 }
1997}
1998
2000 BasicBlock *NewSucc) {
2001 if (auto *Impl = getImpl())
2002 Impl->threadEdge(PredBB, OldSucc, NewSucc);
2003}
2004
2006 if (auto *Impl = getImpl())
2007 Impl->forgetValue(V);
2008}
2009
2011 if (auto *Impl = getImpl())
2012 Impl->eraseBlock(BB);
2013}
2014
2016 if (auto *Impl = getImpl())
2017 Impl->clear();
2018}
2019
2021 if (auto *Impl = getImpl())
2022 Impl->printLVI(F, DTree, OS);
2023}
2024
2025// Print the LVI for the function arguments at the start of each basic block.
2026void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
2027 const BasicBlock *BB, formatted_raw_ostream &OS) {
2028 // Find if there are latticevalues defined for arguments of the function.
2029 auto *F = BB->getParent();
2030 for (const auto &Arg : F->args()) {
2031 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2032 const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
2033 if (Result.isUnknown())
2034 continue;
2035 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
2036 }
2037}
2038
2039// This function prints the LVI analysis for the instruction I at the beginning
2040// of various basic blocks. It relies on calculated values that are stored in
2041// the LazyValueInfoCache, and in the absence of cached values, recalculate the
2042// LazyValueInfo for `I`, and print that info.
2043void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2045
2046 auto *ParentBB = I->getParent();
2047 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
2048 // We can generate (solve) LVI values only for blocks that are dominated by
2049 // the I's parent. However, to avoid generating LVI for all dominating blocks,
2050 // that contain redundant/uninteresting information, we print LVI for
2051 // blocks that may use this LVI information (such as immediate successor
2052 // blocks, and blocks that contain uses of `I`).
2053 auto printResult = [&](const BasicBlock *BB) {
2054 if (!BlocksContainingLVI.insert(BB).second)
2055 return;
2056 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2057 const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
2058 OS << "; LatticeVal for: '" << *I << "' in BB: '";
2059 BB->printAsOperand(OS, false);
2060 OS << "' is: " << Result << "\n";
2061 };
2062
2063 printResult(ParentBB);
2064 // Print the LVI analysis results for the immediate successor blocks, that
2065 // are dominated by `ParentBB`.
2066 for (const auto *BBSucc : successors(ParentBB))
2067 if (DT.dominates(ParentBB, BBSucc))
2068 printResult(BBSucc);
2069
2070 // Print LVI in blocks where `I` is used.
2071 for (const auto *U : I->users())
2072 if (auto *UseI = dyn_cast<Instruction>(U))
2073 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
2074 printResult(UseI->getParent());
2075
2076}
2077
2080 OS << "LVI for function '" << F.getName() << "':\n";
2081 auto &LVI = AM.getResult<LazyValueAnalysis>(F);
2082 auto &DTree = AM.getResult<DominatorTreeAnalysis>(F);
2083 LVI.printLVI(F, DTree, OS);
2084 return PreservedAnalyses::all();
2085}
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:148
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 std::optional< ConstantRange > getRange(Value *V, const InstrInfoQuery &IIQ)
Helper method to get range from metadata or attribute.
static bool isOperationFoldable(User *Usr)
static ConstantRange toConstantRange(const ValueLatticeElement &Val, Type *Ty, bool UndefAllowed=false)
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL)
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 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 ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
lazy value info
static bool isKnownNonConstant(Value *V)
Returns true if we can statically tell that this value will never be a "useful" constant.
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
Natural Loop Information
Definition: LoopInfo.cpp:1177
#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: Analysis.h:47
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:360
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
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:31
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.
void clear()
Clear the cache of @llvm.assume intrinsics for 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:430
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:564
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
reverse_iterator rend()
Definition: BasicBlock.h:448
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:221
const Instruction & back() const
Definition: BasicBlock.h:455
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:289
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:486
Conditional or Unconditional Branch instruction.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1651
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:574
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:903
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:910
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1335
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:966
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:995
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:996
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:990
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:989
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:993
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:991
@ ICMP_EQ
equal
Definition: InstrTypes.h:987
@ ICMP_NE
not equal
Definition: InstrTypes.h:988
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:994
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:992
bool isSigned() const
Definition: InstrTypes.h:1238
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1140
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:1102
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:1078
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:145
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1775
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.
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:400
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:90
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_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:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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:80
const BasicBlock * getParent() const
Definition: Instruction.h:152
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:359
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:252
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...
ValueLatticeElement getValueAtUse(const Use &U)
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
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
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:61
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.
An instruction for reading from memory.
Definition: Instructions.h:184
Metadata node.
Definition: Metadata.h:1067
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:293
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...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:317
Multiway switch.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:234
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:214
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:208
std::optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:275
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:269
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:249
static ValueLatticeElement get(Constant *C)
Definition: ValueLattice.h:203
Constant * getNotConstant() const
Definition: ValueLattice.h:260
Constant * getConstant() const
Definition: ValueLattice.h:255
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:231
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:5079
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.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:121
@ 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:1031
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
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:821
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.
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:294
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
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:234
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
pred_iterator pred_end(BasicBlock *BB)
Definition: CFG.h:114
@ Offset
Definition: DWP.cpp:456
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
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:2073
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.
bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be undef, but may be poison.
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.
pred_iterator pred_begin(BasicBlock *BB)
Definition: CFG.h:110
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:47
@ 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:2032
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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 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:1879
void initializeLazyValueInfoWrapperPassPass(PassRegistry &)
bool isKnownNonZero(const Value *V, unsigned Depth, const SimplifyQuery &Q)
Return true if the given value is known to be non-zero when defined.
#define N
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
SelectPatternFlavor Flavor
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?