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
14#include "llvm/Analysis/LazyValueInfo.h"
15#include "AnalysisOptions.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/Analysis/AssumptionCache.h"
19#include "llvm/Analysis/ConstantFolding.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/Passes.h"
22#include "llvm/Analysis/TargetLibraryInfo.h"
23#include "llvm/Analysis/ValueLattice.h"
24#include "llvm/Analysis/ValueTracking.h"
25#include "llvm/IR/AssemblyAnnotationWriter.h"
26#include "llvm/IR/BundleAttributes.h"
27#include "llvm/IR/CFG.h"
28#include "llvm/IR/ConstantRange.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/DataLayout.h"
31#include "llvm/IR/DebugInfo.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/InstrTypes.h"
34#include "llvm/IR/Instructions.h"
35#include "llvm/IR/IntrinsicInst.h"
36#include "llvm/IR/Intrinsics.h"
37#include "llvm/IR/LLVMContext.h"
38#include "llvm/IR/Module.h"
39#include "llvm/IR/PatternMatch.h"
40#include "llvm/IR/ValueHandle.h"
41#include "llvm/InitializePasses.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/FormattedStream.h"
44#include "llvm/Support/KnownBits.h"
45#include "llvm/Support/raw_ostream.h"
46#include <optional>
47using namespace llvm;
48using namespace PatternMatch;
49
50#define DEBUG_TYPE "lazy-value-info"
51
52// This is the number of worklist items we will process to try to discover an
53// answer for a given value.
54static const unsigned MaxProcessedPerValue = 500;
55
56char LazyValueInfoWrapperPass::ID = 0;
57LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) {}
58INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
59 "Lazy Value Information Analysis", false, true)
60INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
61INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
62INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
63 "Lazy Value Information Analysis", false, true)
64
65namespace llvm {
66FunctionPass *createLazyValueInfoPass() {
67 return new LazyValueInfoWrapperPass();
68}
69} // namespace llvm
70
71AnalysisKey LazyValueAnalysis::Key;
72
73/// Returns true if this lattice value represents at most one possible value.
74/// This is as precise as any lattice value can get while still representing
75/// reachable code.
76static bool hasSingleValue(const ValueLatticeElement &Val) {
77 if (Val.isConstantRange() &&
78 Val.getConstantRange().isSingleElement())
79 // Integer constants are single element ranges
80 return true;
81 if (Val.isConstant())
82 // Non integer constants
83 return true;
84 return false;
85}
86
87//===----------------------------------------------------------------------===//
88// LazyValueInfoCache Decl
89//===----------------------------------------------------------------------===//
90
91namespace {
92 /// A callback value handle updates the cache when values are erased.
93 class LazyValueInfoCache;
94 struct LVIValueHandle final : public CallbackVH {
95 LazyValueInfoCache *Parent;
96
97 LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr)
98 : CallbackVH(V), Parent(P) { }
99
100 void deleted() override;
101 void allUsesReplacedWith(Value *V) override {
102 deleted();
103 }
104 };
105} // end anonymous namespace
106
107namespace {
108using NonNullPointerSet = SmallDenseSet<AssertingVH<Value>, 2>;
109using BBLatticeElementMap =
110 SmallDenseMap<PoisoningVH<BasicBlock>, ValueLatticeElement, 4>;
111using PredecessorValueLatticeMap =
112 SmallDenseMap<AssertingVH<Value>, BBLatticeElementMap, 2>;
113
114/// This is the cache kept by LazyValueInfo which
115/// maintains information about queries across the clients' queries.
116class LazyValueInfoCache {
117 /// This is all of the cached information for one basic block. It contains
118 /// the per-value lattice elements, as well as a separate set for
119 /// overdefined values to reduce memory usage. Additionally pointers
120 /// dereferenced in the block are cached for nullability queries.
121 struct BlockCacheEntry {
122 SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
123 SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
124 // std::nullopt indicates that the nonnull pointers for this basic block
125 // block have not been computed yet.
126 std::optional<NonNullPointerSet> NonNullPointers;
127 // This is an extension of the above LatticeElements, caching, for each
128 // Value, a ValueLatticeElement, for each predecessor of the BB tracked by
129 // this entry.
130 std::optional<PredecessorValueLatticeMap> PredecessorLatticeElements;
131 };
132
133 const bool PerPredRanges;
134
135 /// Cached information per basic block, indexed by block number.
136 SmallVector<std::unique_ptr<BlockCacheEntry>> BlockCache;
137 /// Set of value handles used to erase values from the cache on deletion.
138 DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
139 /// Block number epoch on construction.
140 unsigned BlockNumberEpoch;
141
142 const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const {
143 assert(BlockNumberEpoch == BB->getParent()->getBlockNumberEpoch());
144 if (BB->getNumber() < BlockCache.size())
145 return BlockCache[BB->getNumber()].get();
146 return nullptr;
147 }
148
149 BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {
150 assert(BlockNumberEpoch == BB->getParent()->getBlockNumberEpoch());
151 unsigned Number = BB->getNumber();
152 if (Number >= BlockCache.size())
153 BlockCache.resize(N: BB->getParent()->getMaxBlockNumber());
154
155 if (BlockCacheEntry *Entry = BlockCache[Number].get())
156 return Entry;
157
158 BlockCache[Number] = std::make_unique<BlockCacheEntry>();
159 if (PerPredRanges)
160 BlockCache[Number]->PredecessorLatticeElements =
161 std::make_optional<PredecessorValueLatticeMap>();
162
163 return BlockCache[Number].get();
164 }
165
166 void addValueHandle(Value *Val) {
167 auto HandleIt = ValueHandles.find_as(Val);
168 if (HandleIt == ValueHandles.end())
169 ValueHandles.insert(V: {Val, this});
170 }
171
172public:
173 LazyValueInfoCache(const Function *F, bool PerPredRanges)
174 : PerPredRanges(PerPredRanges),
175 BlockNumberEpoch(F->getBlockNumberEpoch()) {}
176
177 void insertResult(Value *Val, BasicBlock *BB,
178 const ValueLatticeElement &Result) {
179 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
180
181 // Insert over-defined values into their own cache to reduce memory
182 // overhead.
183 if (Result.isOverdefined())
184 Entry->OverDefined.insert(V: Val);
185 else
186 Entry->LatticeElements.insert(KV: {Val, Result});
187
188 addValueHandle(Val);
189 }
190
191 void insertPredecessorResults(Value *Val, BasicBlock *BB,
192 BBLatticeElementMap &PredLatticeElements) {
193 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
194
195 Entry->PredecessorLatticeElements->insert(KV: {Val, PredLatticeElements});
196
197 addValueHandle(Val);
198 }
199
200 std::optional<BBLatticeElementMap>
201 getCachedPredecessorInfo(Value *V, BasicBlock *BB) const {
202 const BlockCacheEntry *Entry = getBlockEntry(BB);
203 if (!Entry)
204 return std::nullopt;
205
206 auto LatticeIt = Entry->PredecessorLatticeElements->find_as(Val: V);
207 if (LatticeIt == Entry->PredecessorLatticeElements->end())
208 return std::nullopt;
209
210 return LatticeIt->second;
211 }
212
213 std::optional<ValueLatticeElement> getCachedValueInfo(Value *V,
214 BasicBlock *BB) const {
215 const BlockCacheEntry *Entry = getBlockEntry(BB);
216 if (!Entry)
217 return std::nullopt;
218
219 if (Entry->OverDefined.count(V))
220 return ValueLatticeElement::getOverdefined();
221
222 auto LatticeIt = Entry->LatticeElements.find_as(Val: V);
223 if (LatticeIt == Entry->LatticeElements.end())
224 return std::nullopt;
225
226 return LatticeIt->second;
227 }
228
229 bool
230 isNonNullAtEndOfBlock(Value *V, BasicBlock *BB,
231 function_ref<NonNullPointerSet(BasicBlock *)> InitFn) {
232 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
233 if (!Entry->NonNullPointers) {
234 Entry->NonNullPointers = InitFn(BB);
235 for (Value *V : *Entry->NonNullPointers)
236 addValueHandle(Val: V);
237 }
238
239 return Entry->NonNullPointers->count(V);
240 }
241
242 /// clear - Empty the cache.
243 void clear() {
244 BlockCache.clear();
245 ValueHandles.clear();
246 }
247
248 /// Inform the cache that a given value has been deleted.
249 void eraseValue(Value *V);
250
251 /// This is part of the update interface to inform the cache
252 /// that a block has been deleted.
253 void eraseBlock(BasicBlock *BB);
254
255 /// Updates the cache to remove any influence an overdefined value in
256 /// OldSucc might have (unless also overdefined in NewSucc). This just
257 /// flushes elements from the cache and does not add any.
258 void threadEdgeImpl(BasicBlock *OldSucc, BasicBlock *NewSucc);
259};
260} // namespace
261
262void LazyValueInfoCache::eraseValue(Value *V) {
263 for (auto &Elem : BlockCache) {
264 if (!Elem)
265 continue;
266
267 Elem->LatticeElements.erase(Val: V);
268 Elem->OverDefined.erase(V);
269 if (Elem->NonNullPointers)
270 Elem->NonNullPointers->erase(V);
271 if (PerPredRanges)
272 Elem->PredecessorLatticeElements->erase(Val: V);
273 }
274
275 auto HandleIt = ValueHandles.find_as(Val: V);
276 if (HandleIt != ValueHandles.end())
277 ValueHandles.erase(I: HandleIt);
278}
279
280void LVIValueHandle::deleted() {
281 // This erasure deallocates *this, so it MUST happen after we're done
282 // using any and all members of *this.
283 Parent->eraseValue(V: *this);
284}
285
286void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
287 assert(BlockNumberEpoch == BB->getParent()->getBlockNumberEpoch());
288 // Clear all when a BB is removed.
289 if (PerPredRanges)
290 for (auto &Elem : BlockCache)
291 if (Elem)
292 Elem->PredecessorLatticeElements->clear();
293 if (BB->getNumber() < BlockCache.size())
294 BlockCache[BB->getNumber()].reset();
295}
296
297void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
298 BasicBlock *NewSucc) {
299 // When an edge in the graph has been threaded, values that we could not
300 // determine a value for before (i.e. were marked overdefined) may be
301 // possible to solve now. We do NOT try to proactively update these values.
302 // Instead, we clear their entries from the cache, and allow lazy updating to
303 // recompute them when needed.
304
305 // The updating process is fairly simple: we need to drop cached info
306 // for all values that were marked overdefined in OldSucc, and for those same
307 // values in any successor of OldSucc (except NewSucc) in which they were
308 // also marked overdefined.
309 std::vector<BasicBlock*> worklist;
310 worklist.push_back(x: OldSucc);
311
312 const BlockCacheEntry *Entry = getBlockEntry(BB: OldSucc);
313 if (!Entry || Entry->OverDefined.empty())
314 return; // Nothing to process here.
315 SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),
316 Entry->OverDefined.end());
317
318 // Use a worklist to perform a depth-first search of OldSucc's successors.
319 // NOTE: We do not need a visited list since any blocks we have already
320 // visited will have had their overdefined markers cleared already, and we
321 // thus won't loop to their successors.
322 while (!worklist.empty()) {
323 BasicBlock *ToUpdate = worklist.back();
324 worklist.pop_back();
325
326 // Skip blocks only accessible through NewSucc.
327 if (ToUpdate == NewSucc) continue;
328
329 // If a value was marked overdefined in OldSucc, and is here too...
330 BlockCacheEntry *WorklistEntry =
331 ToUpdate->getNumber() < BlockCache.size()
332 ? BlockCache[ToUpdate->getNumber()].get()
333 : nullptr;
334 if (!WorklistEntry || WorklistEntry->OverDefined.empty())
335 continue;
336 auto &ValueSet = WorklistEntry->OverDefined;
337
338 bool changed = false;
339 for (Value *V : ValsToClear) {
340 if (!ValueSet.erase(V))
341 continue;
342
343 // If we removed anything, then we potentially need to update
344 // blocks successors too.
345 changed = true;
346 }
347
348 if (!changed) continue;
349
350 llvm::append_range(C&: worklist, R: successors(BB: ToUpdate));
351 }
352}
353
354namespace llvm {
355namespace {
356/// An assembly annotator class to print LazyValueCache information in
357/// comments.
358class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
359 LazyValueInfoImpl *LVIImpl;
360 // While analyzing which blocks we can solve values for, we need the dominator
361 // information.
362 DominatorTree &DT;
363
364public:
365 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
366 : LVIImpl(L), DT(DTree) {}
367
368 void emitBasicBlockStartAnnot(const BasicBlock *BB,
369 formatted_raw_ostream &OS) override;
370
371 void emitInstructionAnnot(const Instruction *I,
372 formatted_raw_ostream &OS) override;
373};
374} // namespace
375// The actual implementation of the lazy analysis and update.
376class LazyValueInfoImpl {
377 const bool PerPredRanges;
378
379 /// Cached results from previous queries
380 LazyValueInfoCache TheCache;
381
382 /// This stack holds the state of the value solver during a query.
383 /// It basically emulates the callstack of the naive
384 /// recursive value lookup process.
385 SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
386
387 /// Keeps track of which block-value pairs are in BlockValueStack.
388 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
389
390 /// Push BV onto BlockValueStack unless it's already in there.
391 /// Returns true on success.
392 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
393 if (!BlockValueSet.insert(V: BV).second)
394 return false; // It's already in the stack.
395
396 LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
397 << BV.first->getName() << "\n");
398 BlockValueStack.push_back(Elt: BV);
399 return true;
400 }
401
402 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
403 const DataLayout &DL; ///< A mandatory DataLayout
404
405 /// Declaration of the llvm.experimental.guard() intrinsic,
406 /// if it exists in the module.
407 Function *GuardDecl;
408
409 std::optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB,
410 Instruction *CtxI);
411 std::optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
412 BasicBlock *T,
413 Instruction *CtxI = nullptr);
414
415 // These methods process one work item and may add more. A false value
416 // returned means that the work item was not completely processed and must
417 // be revisited after going through the new items.
418 bool solveBlockValue(Value *Val, BasicBlock *BB);
419 std::optional<ValueLatticeElement> solveBlockValueImpl(Value *Val,
420 BasicBlock *BB);
421 std::optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
422 BasicBlock *BB);
423 std::optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,
424 BasicBlock *BB);
425 std::optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,
426 BasicBlock *BB);
427 std::optional<ConstantRange> getRangeFor(Value *V, Instruction *CtxI,
428 BasicBlock *BB);
429 std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
430 Instruction *I, BasicBlock *BB,
431 std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
432 OpFn);
433 std::optional<ValueLatticeElement>
434 solveBlockValueBinaryOp(BinaryOperator *BBI, BasicBlock *BB);
435 std::optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI,
436 BasicBlock *BB);
437 std::optional<ValueLatticeElement>
438 solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB);
439 std::optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
440 BasicBlock *BB);
441 std::optional<ValueLatticeElement>
442 solveBlockValueInsertElement(InsertElementInst *IEI, BasicBlock *BB);
443 std::optional<ValueLatticeElement>
444 solveBlockValueExtractValue(ExtractValueInst *EVI, BasicBlock *BB);
445 bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB);
446 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
447 ValueLatticeElement &BBLV,
448 Instruction *BBI);
449
450 void solve();
451
452 // For the following methods, if UseBlockValue is true, the function may
453 // push additional values to the worklist and return nullopt. If
454 // UseBlockValue is false, it will never return nullopt.
455
456 std::optional<ValueLatticeElement>
457 getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS,
458 const APInt &Offset, Instruction *CtxI,
459 bool UseBlockValue);
460
461 std::optional<ValueLatticeElement>
462 getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest,
463 bool UseBlockValue);
464 ValueLatticeElement getValueFromTrunc(Value *Val, TruncInst *Trunc,
465 bool IsTrueDest);
466
467 std::optional<ValueLatticeElement>
468 getValueFromCondition(Value *Val, Value *Cond, bool IsTrueDest,
469 bool UseBlockValue, unsigned Depth = 0);
470
471 std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
472 BasicBlock *BBFrom,
473 BasicBlock *BBTo,
474 bool UseBlockValue);
475
476public:
477 /// This is the query interface to determine the lattice value for the
478 /// specified Value* at the context instruction (if specified) or at the
479 /// start of the block.
480 ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
481 Instruction *CtxI = nullptr);
482
483 /// This is the query interface to determine the lattice value for the
484 /// specified Value* at the specified instruction using only information
485 /// from assumes/guards and range metadata. Unlike getValueInBlock(), no
486 /// recursive query is performed.
487 ValueLatticeElement getValueAt(Value *V, Instruction *CtxI);
488
489 /// This is the query interface to determine the lattice
490 /// value for the specified Value* that is true on the specified edge.
491 ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
492 BasicBlock *ToBB,
493 Instruction *CtxI = nullptr);
494
495 ValueLatticeElement
496 getValueAtUse(const Use &U,
497 SmallVectorImpl<DbgVariableRecord *> *DebugUsers = nullptr);
498
499 /// Complete flush all previously computed values
500 void clear() {
501 TheCache.clear();
502 }
503
504 /// Printing the LazyValueInfo Analysis.
505 void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
506 LazyValueInfoAnnotatedWriter Writer(this, DTree);
507 F.print(OS, AAW: &Writer);
508 }
509
510 /// This is part of the update interface to remove information related to this
511 /// value from the cache.
512 void forgetValue(Value *V) { TheCache.eraseValue(V); }
513
514 /// This is part of the update interface to inform the cache
515 /// that a block has been deleted.
516 void eraseBlock(BasicBlock *BB) {
517 TheCache.eraseBlock(BB);
518 }
519
520 /// This is the update interface to inform the cache that an edge from
521 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
522 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
523
524 LazyValueInfoImpl(Function *F, AssumptionCache *AC, const DataLayout &DL,
525 Function *GuardDecl)
526 : PerPredRanges(getAnalysisOptions(F: *F).lvi_per_pred_ranges),
527 TheCache(F, PerPredRanges), AC(AC), DL(DL), GuardDecl(GuardDecl) {}
528};
529} // namespace llvm
530
531void LazyValueInfoImpl::solve() {
532 SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack =
533 BlockValueStack;
534
535 unsigned processedCount = 0;
536 while (!BlockValueStack.empty()) {
537 processedCount++;
538 // Abort if we have to process too many values to get a result for this one.
539 // Because of the design of the overdefined cache currently being per-block
540 // to avoid naming-related issues (IE it wants to try to give different
541 // results for the same name in different blocks), overdefined results don't
542 // get cached globally, which in turn means we will often try to rediscover
543 // the same overdefined result again and again. Once something like
544 // PredicateInfo is used in LVI or CVP, we should be able to make the
545 // overdefined cache global, and remove this throttle.
546 if (processedCount > MaxProcessedPerValue) {
547 LLVM_DEBUG(
548 dbgs() << "Giving up on stack because we are getting too deep\n");
549 // Fill in the original values
550 while (!StartingStack.empty()) {
551 std::pair<BasicBlock *, Value *> &e = StartingStack.back();
552 TheCache.insertResult(Val: e.second, BB: e.first,
553 Result: ValueLatticeElement::getOverdefined());
554 StartingStack.pop_back();
555 }
556 BlockValueSet.clear();
557 BlockValueStack.clear();
558 return;
559 }
560 std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
561 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
562 unsigned StackSize = BlockValueStack.size();
563 (void) StackSize;
564
565 if (solveBlockValue(Val: e.second, BB: e.first)) {
566 // The work item was completely processed.
567 assert(BlockValueStack.size() == StackSize &&
568 BlockValueStack.back() == e && "Nothing should have been pushed!");
569#ifndef NDEBUG
570 std::optional<ValueLatticeElement> BBLV =
571 TheCache.getCachedValueInfo(e.second, e.first);
572 assert(BBLV && "Result should be in cache!");
573 LLVM_DEBUG(
574 dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
575 << *BBLV << "\n");
576#endif
577
578 BlockValueStack.pop_back();
579 BlockValueSet.erase(V: e);
580 } else {
581 // More work needs to be done before revisiting.
582 assert(BlockValueStack.size() == StackSize + 1 &&
583 "Exactly one element should have been pushed!");
584 }
585 }
586}
587
588std::optional<ValueLatticeElement>
589LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,
590 Instruction *CtxI) {
591 // If already a constant, there is nothing to compute.
592 if (Constant *VC = dyn_cast<Constant>(Val))
593 return ValueLatticeElement::get(C: VC);
594
595 if (std::optional<ValueLatticeElement> OptLatticeVal =
596 TheCache.getCachedValueInfo(V: Val, BB)) {
597 intersectAssumeOrGuardBlockValueConstantRange(Val, BBLV&: *OptLatticeVal, BBI: CtxI);
598 return OptLatticeVal;
599 }
600
601 // We have hit a cycle, assume overdefined.
602 if (!pushBlockValue(BV: { BB, Val }))
603 return ValueLatticeElement::getOverdefined();
604
605 // Yet to be resolved.
606 return std::nullopt;
607}
608
609static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
610 switch (BBI->getOpcode()) {
611 default:
612 break;
613 case Instruction::Call:
614 case Instruction::Invoke:
615 if (std::optional<ConstantRange> Range = cast<CallBase>(Val: BBI)->getRange())
616 return ValueLatticeElement::getRange(CR: *Range);
617 [[fallthrough]];
618 case Instruction::Load:
619 if (MDNode *Ranges = BBI->getMetadata(KindID: LLVMContext::MD_range))
620 if (isa<IntegerType>(Val: BBI->getType())) {
621 return ValueLatticeElement::getRange(
622 CR: getConstantRangeFromMetadata(RangeMD: *Ranges));
623 }
624 break;
625 };
626 // Nothing known - will be intersected with other facts
627 return ValueLatticeElement::getOverdefined();
628}
629
630bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
631 assert(!isa<Constant>(Val) && "Value should not be constant");
632 assert(!TheCache.getCachedValueInfo(Val, BB) &&
633 "Value should not be in cache");
634
635 // Hold off inserting this value into the Cache in case we have to return
636 // false and come back later.
637 std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
638 if (!Res)
639 // Work pushed, will revisit
640 return false;
641
642 TheCache.insertResult(Val, BB, Result: *Res);
643 return true;
644}
645
646std::optional<ValueLatticeElement>
647LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) {
648 Instruction *BBI = dyn_cast<Instruction>(Val);
649 if (!BBI || BBI->getParent() != BB)
650 return solveBlockValueNonLocal(Val, BB);
651
652 if (PHINode *PN = dyn_cast<PHINode>(Val: BBI))
653 return solveBlockValuePHINode(PN, BB);
654
655 if (auto *SI = dyn_cast<SelectInst>(Val: BBI))
656 return solveBlockValueSelect(S: SI, BB);
657
658 // If this value is a nonnull pointer, record it's range and bailout. Note
659 // that for all other pointer typed values, we terminate the search at the
660 // definition. We could easily extend this to look through geps, bitcasts,
661 // and the like to prove non-nullness, but it's not clear that's worth it
662 // compile time wise. The context-insensitive value walk done inside
663 // isKnownNonZero gets most of the profitable cases at much less expense.
664 // This does mean that we have a sensitivity to where the defining
665 // instruction is placed, even if it could legally be hoisted much higher.
666 // That is unfortunate.
667 PointerType *PT = dyn_cast<PointerType>(Val: BBI->getType());
668 if (PT && isKnownNonZero(V: BBI, Q: DL))
669 return ValueLatticeElement::getNot(C: ConstantPointerNull::get(T: PT));
670
671 if (BBI->getType()->isIntOrIntVectorTy()) {
672 if (auto *CI = dyn_cast<CastInst>(Val: BBI))
673 return solveBlockValueCast(CI, BB);
674
675 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: BBI))
676 return solveBlockValueBinaryOp(BBI: BO, BB);
677
678 if (auto *IEI = dyn_cast<InsertElementInst>(Val: BBI))
679 return solveBlockValueInsertElement(IEI, BB);
680
681 if (auto *EVI = dyn_cast<ExtractValueInst>(Val: BBI))
682 return solveBlockValueExtractValue(EVI, BB);
683
684 if (auto *II = dyn_cast<IntrinsicInst>(Val: BBI))
685 return solveBlockValueIntrinsic(II, BB);
686 }
687
688 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
689 << "' - unknown inst def found.\n");
690 return getFromRangeMetadata(BBI);
691}
692
693static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet,
694 bool IsDereferenced = true) {
695 // TODO: Use NullPointerIsDefined instead.
696 if (Ptr->getType()->getPointerAddressSpace() == 0)
697 PtrSet.insert(V: IsDereferenced ? getUnderlyingObject(V: Ptr)
698 : Ptr->stripInBoundsOffsets());
699}
700
701static void AddNonNullPointersByInstruction(
702 Instruction *I, NonNullPointerSet &PtrSet) {
703 if (LoadInst *L = dyn_cast<LoadInst>(Val: I)) {
704 AddNonNullPointer(Ptr: L->getPointerOperand(), PtrSet);
705 } else if (StoreInst *S = dyn_cast<StoreInst>(Val: I)) {
706 AddNonNullPointer(Ptr: S->getPointerOperand(), PtrSet);
707 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: I)) {
708 if (MI->isVolatile()) return;
709
710 // FIXME: check whether it has a valuerange that excludes zero?
711 ConstantInt *Len = dyn_cast<ConstantInt>(Val: MI->getLength());
712 if (!Len || Len->isZero()) return;
713
714 AddNonNullPointer(Ptr: MI->getRawDest(), PtrSet);
715 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Val: MI))
716 AddNonNullPointer(Ptr: MTI->getRawSource(), PtrSet);
717 } else if (auto *CB = dyn_cast<CallBase>(Val: I)) {
718 for (auto &U : CB->args()) {
719 if (U->getType()->isPointerTy() &&
720 CB->paramHasNonNullAttr(ArgNo: CB->getArgOperandNo(U: &U),
721 /*AllowUndefOrPoison=*/false))
722 AddNonNullPointer(Ptr: U.get(), PtrSet, /*IsDereferenced=*/false);
723 }
724 }
725}
726
727bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
728 if (NullPointerIsDefined(F: BB->getParent(),
729 AS: Val->getType()->getPointerAddressSpace()))
730 return false;
731
732 Val = Val->stripInBoundsOffsets();
733 return TheCache.isNonNullAtEndOfBlock(V: Val, BB, InitFn: [](BasicBlock *BB) {
734 NonNullPointerSet NonNullPointers;
735 for (Instruction &I : *BB)
736 AddNonNullPointersByInstruction(I: &I, PtrSet&: NonNullPointers);
737 return NonNullPointers;
738 });
739}
740
741std::optional<ValueLatticeElement>
742LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {
743 ValueLatticeElement Result; // Start Undefined.
744
745 // If this is the entry block, we must be asking about an argument.
746 if (BB->isEntryBlock()) {
747 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
748 if (std::optional<ConstantRange> Range = cast<Argument>(Val)->getRange())
749 return ValueLatticeElement::getRange(CR: *Range);
750 return ValueLatticeElement::getOverdefined();
751 }
752
753 // Loop over all of our predecessors, merging what we know from them into
754 // result. If we encounter an unexplored predecessor, we eagerly explore it
755 // in a depth first manner. In practice, this has the effect of discovering
756 // paths we can't analyze eagerly without spending compile times analyzing
757 // other paths. This heuristic benefits from the fact that predecessors are
758 // frequently arranged such that dominating ones come first and we quickly
759 // find a path to function entry. TODO: We should consider explicitly
760 // canonicalizing to make this true rather than relying on this happy
761 // accident.
762 std::optional<BBLatticeElementMap> PredLatticeElements;
763 if (PerPredRanges)
764 PredLatticeElements = std::make_optional<BBLatticeElementMap>();
765 for (BasicBlock *Pred : predecessors(BB)) {
766 // Skip self loops.
767 if (Pred == BB)
768 continue;
769 std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(V: Val, F: Pred, T: BB);
770 if (!EdgeResult)
771 // Explore that input, then return here
772 return std::nullopt;
773
774 Result.mergeIn(RHS: *EdgeResult);
775
776 // If we hit overdefined, exit early. The BlockVals entry is already set
777 // to overdefined.
778 if (Result.isOverdefined()) {
779 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
780 << "' - overdefined because of pred '"
781 << Pred->getName() << "' (non local).\n");
782 return Result;
783 }
784 if (PerPredRanges)
785 PredLatticeElements->insert(KV: {Pred, *EdgeResult});
786 }
787
788 if (PerPredRanges)
789 TheCache.insertPredecessorResults(Val, BB, PredLatticeElements&: *PredLatticeElements);
790
791 // Return the merged value, which is more precise than 'overdefined'.
792 assert(!Result.isOverdefined());
793 return Result;
794}
795
796std::optional<ValueLatticeElement>
797LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {
798 ValueLatticeElement Result; // Start Undefined.
799
800 // Loop over all of our predecessors, merging what we know from them into
801 // result. See the comment about the chosen traversal order in
802 // solveBlockValueNonLocal; the same reasoning applies here.
803 std::optional<BBLatticeElementMap> PredLatticeElements;
804 if (PerPredRanges)
805 PredLatticeElements = std::make_optional<BBLatticeElementMap>();
806 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
807 BasicBlock *PhiBB = PN->getIncomingBlock(i);
808 Value *PhiVal = PN->getIncomingValue(i);
809 // Note that we can provide PN as the context value to getEdgeValue, even
810 // though the results will be cached, because PN is the value being used as
811 // the cache key in the caller.
812 std::optional<ValueLatticeElement> EdgeResult =
813 getEdgeValue(V: PhiVal, F: PhiBB, T: BB, CtxI: PN);
814 if (!EdgeResult)
815 // Explore that input, then return here
816 return std::nullopt;
817
818 Result.mergeIn(RHS: *EdgeResult);
819
820 // If we hit overdefined, exit early. The BlockVals entry is already set
821 // to overdefined.
822 if (Result.isOverdefined()) {
823 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
824 << "' - overdefined because of pred (local).\n");
825
826 return Result;
827 }
828
829 if (PerPredRanges)
830 PredLatticeElements->insert(KV: {PhiBB, *EdgeResult});
831 }
832
833 if (PerPredRanges)
834 TheCache.insertPredecessorResults(Val: PN, BB, PredLatticeElements&: *PredLatticeElements);
835
836 // Return the merged value, which is more precise than 'overdefined'.
837 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
838 return Result;
839}
840
841// If we can determine a constraint on the value given conditions assumed by
842// the program, intersect those constraints with BBLV
843void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
844 Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
845 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
846 if (!BBI)
847 return;
848
849 BasicBlock *BB = BBI->getParent();
850 for (auto &AssumeVH : AC->assumptionsFor(V: Val)) {
851 if (!AssumeVH)
852 continue;
853
854 // Only check assumes in the block of the context instruction. Other
855 // assumes will have already been taken into account when the value was
856 // propagated from predecessor blocks.
857 auto *I = cast<AssumeInst>(Val&: AssumeVH);
858
859 if (I->getParent() != BB || !isValidAssumeForContext(I, CtxI: BBI))
860 continue;
861
862 if (AssumeVH.Index != AssumptionCache::ExprResultIdx) {
863 auto OBU = I->getOperandBundleAt(Index: AssumeVH.Index);
864 switch (getBundleAttrFromOBU(OBU)) {
865 case BundleAttr::Range: {
866 auto [V, Range] = getAssumeRangeInfo(OBU);
867 if (Val == V) {
868 BBLV =
869 BBLV.intersect(Other: ValueLatticeElement::getRange(CR: std::move(Range)));
870 }
871 } break;
872 default:
873 if (assumeBundleImpliesNonNull(Val, Context: BBI->getFunction(),
874 OBU: I->getOperandBundleAt(Index: AssumeVH.Index)))
875 BBLV = BBLV.intersect(Other: ValueLatticeElement::getNot(
876 C: Constant::getNullValue(Ty: Val->getType())));
877 }
878 } else {
879 BBLV = BBLV.intersect(Other: *getValueFromCondition(Val, Cond: I->getArgOperand(i: 0),
880 /*IsTrueDest*/ true,
881 /*UseBlockValue*/ false));
882 }
883 }
884
885 // If guards are not used in the module, don't spend time looking for them
886 if (GuardDecl && !GuardDecl->use_empty() &&
887 BBI->getIterator() != BB->begin()) {
888 for (Instruction &I :
889 make_range(x: std::next(x: BBI->getIterator().getReverse()), y: BB->rend())) {
890 Value *Cond = nullptr;
891 if (match(V: &I, P: m_Intrinsic<Intrinsic::experimental_guard>(Ops: m_Value(V&: Cond))))
892 BBLV = BBLV.intersect(Other: *getValueFromCondition(Val, Cond,
893 /*IsTrueDest*/ true,
894 /*UseBlockValue*/ false));
895 }
896 }
897
898 if (BBLV.isOverdefined()) {
899 // Check whether we're checking at the terminator, and the pointer has
900 // been dereferenced in this block.
901 PointerType *PTy = dyn_cast<PointerType>(Val: Val->getType());
902 if (PTy && BB->getTerminator() == BBI &&
903 isNonNullAtEndOfBlock(Val, BB))
904 BBLV = ValueLatticeElement::getNot(C: ConstantPointerNull::get(T: PTy));
905 }
906}
907
908std::optional<ValueLatticeElement>
909LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) {
910 // Recurse on our inputs if needed
911 std::optional<ValueLatticeElement> OptTrueVal =
912 getBlockValue(Val: SI->getTrueValue(), BB, CtxI: SI);
913 if (!OptTrueVal)
914 return std::nullopt;
915 ValueLatticeElement &TrueVal = *OptTrueVal;
916
917 std::optional<ValueLatticeElement> OptFalseVal =
918 getBlockValue(Val: SI->getFalseValue(), BB, CtxI: SI);
919 if (!OptFalseVal)
920 return std::nullopt;
921 ValueLatticeElement &FalseVal = *OptFalseVal;
922
923 if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
924 const ConstantRange &TrueCR = TrueVal.asConstantRange(Ty: SI->getType());
925 const ConstantRange &FalseCR = FalseVal.asConstantRange(Ty: SI->getType());
926 Value *LHS = nullptr;
927 Value *RHS = nullptr;
928 SelectPatternResult SPR = matchSelectPattern(V: SI, LHS, RHS);
929 // Is this a min specifically of our two inputs? (Avoid the risk of
930 // ValueTracking getting smarter looking back past our immediate inputs.)
931 if (SelectPatternResult::isMinOrMax(SPF: SPR.Flavor) &&
932 ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
933 (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
934 ConstantRange ResultCR = [&]() {
935 switch (SPR.Flavor) {
936 default:
937 llvm_unreachable("unexpected minmax type!");
938 case SPF_SMIN: /// Signed minimum
939 return TrueCR.smin(Other: FalseCR);
940 case SPF_UMIN: /// Unsigned minimum
941 return TrueCR.umin(Other: FalseCR);
942 case SPF_SMAX: /// Signed maximum
943 return TrueCR.smax(Other: FalseCR);
944 case SPF_UMAX: /// Unsigned maximum
945 return TrueCR.umax(Other: FalseCR);
946 };
947 }();
948 return ValueLatticeElement::getRange(
949 CR: ResultCR, MayIncludeUndef: TrueVal.isConstantRangeIncludingUndef() ||
950 FalseVal.isConstantRangeIncludingUndef());
951 }
952
953 if (SPR.Flavor == SPF_ABS) {
954 if (LHS == SI->getTrueValue())
955 return ValueLatticeElement::getRange(
956 CR: TrueCR.abs(), MayIncludeUndef: TrueVal.isConstantRangeIncludingUndef());
957 if (LHS == SI->getFalseValue())
958 return ValueLatticeElement::getRange(
959 CR: FalseCR.abs(), MayIncludeUndef: FalseVal.isConstantRangeIncludingUndef());
960 }
961
962 if (SPR.Flavor == SPF_NABS) {
963 ConstantRange Zero(APInt::getZero(numBits: TrueCR.getBitWidth()));
964 if (LHS == SI->getTrueValue())
965 return ValueLatticeElement::getRange(
966 CR: Zero.sub(Other: TrueCR.abs()), MayIncludeUndef: FalseVal.isConstantRangeIncludingUndef());
967 if (LHS == SI->getFalseValue())
968 return ValueLatticeElement::getRange(
969 CR: Zero.sub(Other: FalseCR.abs()), MayIncludeUndef: FalseVal.isConstantRangeIncludingUndef());
970 }
971 }
972
973 // Can we constrain the facts about the true and false values by using the
974 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
975 // TODO: We could potentially refine an overdefined true value above.
976 Value *Cond = SI->getCondition();
977 // If the value is undef, a different value may be chosen in
978 // the select condition.
979 if (isGuaranteedNotToBeUndef(V: Cond, AC)) {
980 TrueVal =
981 TrueVal.intersect(Other: *getValueFromCondition(Val: SI->getTrueValue(), Cond,
982 /*IsTrueDest*/ true,
983 /*UseBlockValue*/ false));
984 FalseVal =
985 FalseVal.intersect(Other: *getValueFromCondition(Val: SI->getFalseValue(), Cond,
986 /*IsTrueDest*/ false,
987 /*UseBlockValue*/ false));
988 }
989
990 TrueVal.mergeIn(RHS: FalseVal);
991 return TrueVal;
992}
993
994std::optional<ConstantRange>
995LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CtxI, BasicBlock *BB) {
996 std::optional<ValueLatticeElement> OptVal = getBlockValue(Val: V, BB, CtxI);
997 if (!OptVal)
998 return std::nullopt;
999 return OptVal->asConstantRange(Ty: V->getType());
1000}
1001
1002std::optional<ValueLatticeElement>
1003LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {
1004 // Filter out casts we don't know how to reason about before attempting to
1005 // recurse on our operand. This can cut a long search short if we know we're
1006 // not going to be able to get any useful information anways.
1007 switch (CI->getOpcode()) {
1008 case Instruction::Trunc:
1009 case Instruction::SExt:
1010 case Instruction::ZExt:
1011 break;
1012 default:
1013 // Unhandled instructions are overdefined.
1014 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1015 << "' - overdefined (unknown cast).\n");
1016 return ValueLatticeElement::getOverdefined();
1017 }
1018
1019 // Figure out the range of the LHS. If that fails, we still apply the
1020 // transfer rule on the full set since we may be able to locally infer
1021 // interesting facts.
1022 std::optional<ConstantRange> LHSRes = getRangeFor(V: CI->getOperand(i_nocapture: 0), CtxI: CI, BB);
1023 if (!LHSRes)
1024 // More work to do before applying this transfer rule.
1025 return std::nullopt;
1026 const ConstantRange &LHSRange = *LHSRes;
1027
1028 const unsigned ResultBitWidth = CI->getType()->getScalarSizeInBits();
1029
1030 // NOTE: We're currently limited by the set of operations that ConstantRange
1031 // can evaluate symbolically. Enhancing that set will allows us to analyze
1032 // more definitions.
1033 ConstantRange Res = ConstantRange::getEmpty(BitWidth: ResultBitWidth);
1034 if (auto *Trunc = dyn_cast<TruncInst>(Val: CI))
1035 Res = LHSRange.truncate(BitWidth: ResultBitWidth, NoWrapKind: Trunc->getNoWrapKind());
1036 else
1037 Res = LHSRange.castOp(CastOp: CI->getOpcode(), BitWidth: ResultBitWidth);
1038
1039 return ValueLatticeElement::getRange(CR: Res);
1040}
1041
1042std::optional<ValueLatticeElement>
1043LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
1044 Instruction *I, BasicBlock *BB,
1045 std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
1046 OpFn) {
1047 Value *LHS = I->getOperand(i: 0);
1048 Value *RHS = I->getOperand(i: 1);
1049
1050 auto ThreadBinOpOverSelect =
1051 [&](Value *X, const ConstantRange &CRX, SelectInst *Y,
1052 bool XIsLHS) -> std::optional<ValueLatticeElement> {
1053 Value *Cond = Y->getCondition();
1054 // Only handle selects with constant values.
1055 Constant *TrueC = dyn_cast<Constant>(Val: Y->getTrueValue());
1056 if (!TrueC)
1057 return std::nullopt;
1058 Constant *FalseC = dyn_cast<Constant>(Val: Y->getFalseValue());
1059 if (!FalseC)
1060 return std::nullopt;
1061 if (!isGuaranteedNotToBeUndef(V: Cond, AC))
1062 return std::nullopt;
1063
1064 ConstantRange TrueX =
1065 CRX.intersectWith(CR: getValueFromCondition(Val: X, Cond, /*CondIsTrue=*/IsTrueDest: true,
1066 /*UseBlockValue=*/false)
1067 ->asConstantRange(Ty: X->getType()));
1068 ConstantRange FalseX =
1069 CRX.intersectWith(CR: getValueFromCondition(Val: X, Cond, /*CondIsTrue=*/IsTrueDest: false,
1070 /*UseBlockValue=*/false)
1071 ->asConstantRange(Ty: X->getType()));
1072 ConstantRange TrueY = TrueC->toConstantRange();
1073 ConstantRange FalseY = FalseC->toConstantRange();
1074
1075 if (XIsLHS)
1076 return ValueLatticeElement::getRange(
1077 CR: OpFn(TrueX, TrueY).unionWith(CR: OpFn(FalseX, FalseY)));
1078 return ValueLatticeElement::getRange(
1079 CR: OpFn(TrueY, TrueX).unionWith(CR: OpFn(FalseY, FalseX)));
1080 };
1081
1082 // Figure out the ranges of the operands. If that fails, use a
1083 // conservative range, but apply the transfer rule anyways. This
1084 // lets us pick up facts from expressions like "and i32 (call i32
1085 // @foo()), 32"
1086 std::optional<ConstantRange> LHSRes = getRangeFor(V: LHS, CtxI: I, BB);
1087 if (!LHSRes)
1088 return std::nullopt;
1089
1090 // Try to thread binop over rhs select
1091 if (auto *SI = dyn_cast<SelectInst>(Val: RHS)) {
1092 if (auto Res = ThreadBinOpOverSelect(LHS, *LHSRes, SI, /*XIsLHS=*/true))
1093 return *Res;
1094 }
1095
1096 std::optional<ConstantRange> RHSRes = getRangeFor(V: RHS, CtxI: I, BB);
1097 if (!RHSRes)
1098 return std::nullopt;
1099
1100 // Try to thread binop over lhs select
1101 if (auto *SI = dyn_cast<SelectInst>(Val: LHS)) {
1102 if (auto Res = ThreadBinOpOverSelect(RHS, *RHSRes, SI, /*XIsLHS=*/false))
1103 return *Res;
1104 }
1105
1106 const ConstantRange &LHSRange = *LHSRes;
1107 const ConstantRange &RHSRange = *RHSRes;
1108
1109 std::optional<ValueLatticeElement> MergedResult =
1110 ValueLatticeElement::getRange(CR: OpFn(LHSRange, RHSRange));
1111
1112 if (!PerPredRanges)
1113 return MergedResult;
1114
1115 std::optional<BBLatticeElementMap> PredLHS =
1116 TheCache.getCachedPredecessorInfo(V: LHS, BB);
1117 if (!PredLHS)
1118 return MergedResult;
1119 std::optional<BBLatticeElementMap> PredRHS =
1120 TheCache.getCachedPredecessorInfo(V: RHS, BB);
1121 if (!PredRHS)
1122 return MergedResult;
1123
1124 const BBLatticeElementMap &LHSPredMap = *PredLHS;
1125 const BBLatticeElementMap &RHSPredMap = *PredRHS;
1126
1127 BBLatticeElementMap PredLatticeElements;
1128 ValueLatticeElement OverallPredResult;
1129 for (auto *Pred : predecessors(BB)) {
1130 auto LHSIt = LHSPredMap.find_as(Val: Pred);
1131 if (LHSIt == LHSPredMap.end())
1132 return MergedResult;
1133 const ValueLatticeElement &LHSFromPred = LHSIt->second;
1134 std::optional<ConstantRange> LHSFromPredRes =
1135 LHSFromPred.asConstantRange(Ty: LHS->getType());
1136 if (!LHSFromPredRes)
1137 return MergedResult;
1138
1139 auto RHSIt = RHSPredMap.find_as(Val: Pred);
1140 if (RHSIt == RHSPredMap.end())
1141 return MergedResult;
1142 const ValueLatticeElement &RHSFromPred = RHSIt->second;
1143 std::optional<ConstantRange> RHSFromPredRes =
1144 RHSFromPred.asConstantRange(Ty: RHS->getType());
1145 if (!RHSFromPredRes)
1146 return MergedResult;
1147
1148 const ConstantRange &LHSFromPredRange = *LHSFromPredRes;
1149 const ConstantRange &RHSFromPredRange = *RHSFromPredRes;
1150 std::optional<ValueLatticeElement> PredResult =
1151 ValueLatticeElement::getRange(CR: OpFn(LHSFromPredRange, RHSFromPredRange));
1152 if (!PredResult)
1153 return MergedResult;
1154 if (PredResult->isOverdefined()) {
1155 LLVM_DEBUG(
1156 dbgs() << " pred BB '" << Pred->getName() << "' for BB '"
1157 << BB->getName()
1158 << "' overdefined. Discarding all predecessor intervals.\n");
1159 return MergedResult;
1160 }
1161 PredLatticeElements.insert(KV: {Pred, *PredResult});
1162 OverallPredResult.mergeIn(RHS: *PredResult);
1163 }
1164
1165 // If this point is reached, all predecessors for both LHS and RHS have
1166 // constant ranges previously computed. Can cache result and use the
1167 // OverallPredResult;
1168 TheCache.insertPredecessorResults(Val: I, BB, PredLatticeElements);
1169
1170 LLVM_DEBUG(dbgs() << " Using predecessor intervals, evaluated " << *I
1171 << " to: " << OverallPredResult << ".\n");
1172
1173 if (!MergedResult)
1174 return OverallPredResult;
1175
1176 LLVM_DEBUG(dbgs() << " Intersecting intervals for " << *I << ": "
1177 << OverallPredResult << " and " << MergedResult << ".\n");
1178 return MergedResult->intersect(Other: OverallPredResult);
1179}
1180
1181std::optional<ValueLatticeElement>
1182LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) {
1183 assert(BO->getOperand(0)->getType()->isSized() &&
1184 "all operands to binary operators are sized");
1185
1186 return solveBlockValueBinaryOpImpl(
1187 I: BO, BB, OpFn: [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
1188 return CR1.binaryOp(BO: *BO, Other: CR2);
1189 });
1190}
1191
1192std::optional<ValueLatticeElement>
1193LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
1194 BasicBlock *BB) {
1195 return solveBlockValueBinaryOpImpl(
1196 I: WO, BB, OpFn: [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
1197 return CR1.binaryOp(BinOp: WO->getBinaryOp(), Other: CR2);
1198 });
1199}
1200
1201std::optional<ValueLatticeElement>
1202LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) {
1203 ValueLatticeElement MetadataVal = getFromRangeMetadata(BBI: II);
1204 if (!ConstantRange::isIntrinsicSupported(IntrinsicID: II->getIntrinsicID())) {
1205 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1206 << "' - unknown intrinsic.\n");
1207 return MetadataVal;
1208 }
1209
1210 SmallVector<ConstantRange, 2> OpRanges;
1211 for (Value *Op : II->args()) {
1212 std::optional<ConstantRange> Range = getRangeFor(V: Op, CtxI: II, BB);
1213 if (!Range)
1214 return std::nullopt;
1215 OpRanges.push_back(Elt: *Range);
1216 }
1217
1218 return ValueLatticeElement::getRange(
1219 CR: ConstantRange::intrinsic(IntrinsicID: II->getIntrinsicID(), Ops: OpRanges))
1220 .intersect(Other: MetadataVal);
1221}
1222
1223std::optional<ValueLatticeElement>
1224LazyValueInfoImpl::solveBlockValueInsertElement(InsertElementInst *IEI,
1225 BasicBlock *BB) {
1226 std::optional<ValueLatticeElement> OptEltVal =
1227 getBlockValue(Val: IEI->getOperand(i_nocapture: 1), BB, CtxI: IEI);
1228 if (!OptEltVal)
1229 return std::nullopt;
1230 ValueLatticeElement &Res = *OptEltVal;
1231
1232 std::optional<ValueLatticeElement> OptVecVal =
1233 getBlockValue(Val: IEI->getOperand(i_nocapture: 0), BB, CtxI: IEI);
1234 if (!OptVecVal)
1235 return std::nullopt;
1236
1237 // Bail out if the inserted element is a constant expression. Unlike other
1238 // ValueLattice types, these are not considered an implicit splat when a
1239 // vector type is used.
1240 // We could call ConstantFoldInsertElementInstruction here to handle these.
1241 if (OptEltVal->isConstant())
1242 return ValueLatticeElement::getOverdefined();
1243
1244 Res.mergeIn(RHS: *OptVecVal);
1245 return Res;
1246}
1247
1248std::optional<ValueLatticeElement>
1249LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
1250 BasicBlock *BB) {
1251 if (auto *WO = dyn_cast<WithOverflowInst>(Val: EVI->getAggregateOperand()))
1252 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
1253 return solveBlockValueOverflowIntrinsic(WO, BB);
1254
1255 // Handle extractvalue of insertvalue to allow further simplification
1256 // based on replaced with.overflow intrinsics.
1257 if (Value *V = simplifyExtractValueInst(
1258 Agg: EVI->getAggregateOperand(), Idxs: EVI->getIndices(),
1259 Q: EVI->getDataLayout()))
1260 return getBlockValue(Val: V, BB, CtxI: EVI);
1261
1262 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1263 << "' - overdefined (unknown extractvalue).\n");
1264 return ValueLatticeElement::getOverdefined();
1265}
1266
1267static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
1268 ICmpInst::Predicate Pred) {
1269 if (LHS == Val)
1270 return true;
1271
1272 // Handle range checking idiom produced by InstCombine. We will subtract the
1273 // offset from the allowed range for RHS in this case.
1274 const APInt *C;
1275 if (match(V: LHS, P: m_AddLike(L: m_Specific(V: Val), R: m_APInt(Res&: C)))) {
1276 Offset = *C;
1277 return true;
1278 }
1279
1280 // Handle the symmetric case. This appears in saturation patterns like
1281 // (x == 16) ? 16 : (x + 1).
1282 if (match(V: Val, P: m_AddLike(L: m_Specific(V: LHS), R: m_APInt(Res&: C)))) {
1283 Offset = -*C;
1284 return true;
1285 }
1286
1287 // If (x | y) < C, then (x < C) && (y < C).
1288 if (match(V: LHS, P: m_c_Or(L: m_Specific(V: Val), R: m_Value())) &&
1289 (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
1290 return true;
1291
1292 // If (x & y) > C, then (x > C) && (y > C).
1293 if (match(V: LHS, P: m_c_And(L: m_Specific(V: Val), R: m_Value())) &&
1294 (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
1295 return true;
1296
1297 return false;
1298}
1299
1300/// Get value range for a "(Val + Offset) Pred RHS" condition.
1301std::optional<ValueLatticeElement>
1302LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,
1303 Value *RHS,
1304 const APInt &Offset,
1305 Instruction *CtxI,
1306 bool UseBlockValue) {
1307 ConstantRange RHSRange(RHS->getType()->getScalarSizeInBits(),
1308 /*isFullSet=*/true);
1309 if (auto *C = dyn_cast<Constant>(Val: RHS)) {
1310 RHSRange = C->toConstantRange();
1311 } else if (UseBlockValue) {
1312 std::optional<ValueLatticeElement> R =
1313 getBlockValue(Val: RHS, BB: CtxI->getParent(), CtxI);
1314 if (!R)
1315 return std::nullopt;
1316 RHSRange = R->asConstantRange(Ty: RHS->getType());
1317 }
1318
1319 ConstantRange TrueValues =
1320 ConstantRange::makeAllowedICmpRegion(Pred, Other: RHSRange);
1321 return ValueLatticeElement::getRange(CR: TrueValues.subtract(CI: Offset));
1322}
1323
1324static std::optional<ConstantRange>
1325getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS,
1326 function_ref<std::optional<ConstantRange>(const APInt &)> Fn) {
1327 bool Invert = false;
1328 if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) {
1329 Pred = ICmpInst::getInversePredicate(pred: Pred);
1330 Invert = true;
1331 }
1332 if (Pred == ICmpInst::ICMP_SLE) {
1333 Pred = ICmpInst::ICMP_SLT;
1334 if (RHS.isMaxSignedValue())
1335 return std::nullopt; // Could also return full/empty here, if we wanted.
1336 ++RHS;
1337 }
1338 assert(Pred == ICmpInst::ICMP_SLT && "Must be signed predicate");
1339 if (auto CR = Fn(RHS))
1340 return Invert ? CR->inverse() : CR;
1341 return std::nullopt;
1342}
1343
1344/// Get value range for a "ctpop(Val) Pred RHS" condition.
1345static ValueLatticeElement getValueFromICmpCtpop(ICmpInst::Predicate Pred,
1346 Value *RHS) {
1347 unsigned BitWidth = RHS->getType()->getScalarSizeInBits();
1348
1349 auto *RHSConst = dyn_cast<ConstantInt>(Val: RHS);
1350 if (!RHSConst)
1351 return ValueLatticeElement::getOverdefined();
1352
1353 ConstantRange ResValRange =
1354 ConstantRange::makeExactICmpRegion(Pred, Other: RHSConst->getValue());
1355
1356 unsigned ResMin = ResValRange.getUnsignedMin().getLimitedValue(Limit: BitWidth);
1357 unsigned ResMax = ResValRange.getUnsignedMax().getLimitedValue(Limit: BitWidth);
1358
1359 APInt ValMin = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: ResMin);
1360 APInt ValMax = APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ResMax);
1361 return ValueLatticeElement::getRange(
1362 CR: ConstantRange::getNonEmpty(Lower: std::move(ValMin), Upper: ValMax + 1));
1363}
1364
1365/// Get the unsigned range for \p V from a `mul nuw V, V` comparison.
1366static std::optional<ConstantRange>
1367getRangeForNUWMulSquare(const Value *V, CmpInst::Predicate Pred,
1368 const Value *LHS, const Value *RHS) {
1369 if (!V->getType()->isIntegerTy())
1370 return std::nullopt;
1371
1372 if (!match(V: LHS, P: m_NUWMul(L: m_Specific(V), R: m_Specific(V)))) {
1373 if (!match(V: RHS, P: m_NUWMul(L: m_Specific(V), R: m_Specific(V))))
1374 return std::nullopt;
1375
1376 Pred = CmpInst::getSwappedPredicate(pred: Pred);
1377 RHS = LHS;
1378 }
1379
1380 ConstantRange MulCR =
1381 ConstantRange::getFull(BitWidth: V->getType()->getScalarSizeInBits());
1382 const APInt *C;
1383 if (match(V: RHS, P: m_APInt(Res&: C)))
1384 MulCR = ConstantRange::makeExactICmpRegion(Pred, Other: *C);
1385
1386 ConstantRange Res = MulCR.sqrtFloor();
1387 if (Res.isFullSet())
1388 return std::nullopt;
1389 return Res;
1390}
1391
1392std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(
1393 Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) {
1394 Value *LHS = ICI->getOperand(i_nocapture: 0);
1395 Value *RHS = ICI->getOperand(i_nocapture: 1);
1396
1397 // Get the predicate that must hold along the considered edge.
1398 CmpInst::Predicate EdgePred =
1399 isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
1400
1401 if (isa<Constant>(Val: RHS)) {
1402 if (ICI->isEquality() && LHS == Val) {
1403 if (EdgePred == ICmpInst::ICMP_EQ)
1404 return ValueLatticeElement::get(C: cast<Constant>(Val: RHS));
1405 else if (!isa<UndefValue>(Val: RHS))
1406 return ValueLatticeElement::getNot(C: cast<Constant>(Val: RHS));
1407 }
1408 }
1409
1410 Type *Ty = Val->getType();
1411 if (!Ty->isIntOrIntVectorTy())
1412 return ValueLatticeElement::getOverdefined();
1413
1414 unsigned BitWidth = Ty->getScalarSizeInBits();
1415 if (auto Range = getRangeForNUWMulSquare(V: Val, Pred: EdgePred, LHS, RHS))
1416 return ValueLatticeElement::getRange(CR: *Range);
1417
1418 APInt Offset(BitWidth, 0);
1419 if (matchICmpOperand(Offset, LHS, Val, Pred: EdgePred))
1420 return getValueFromSimpleICmpCondition(Pred: EdgePred, RHS, Offset, CtxI: ICI,
1421 UseBlockValue);
1422
1423 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(pred: EdgePred);
1424 if (matchICmpOperand(Offset, LHS: RHS, Val, Pred: SwappedPred))
1425 return getValueFromSimpleICmpCondition(Pred: SwappedPred, RHS: LHS, Offset, CtxI: ICI,
1426 UseBlockValue);
1427
1428 if (match(V: LHS, P: m_Ctpop(Op0: m_Specific(V: Val))))
1429 return getValueFromICmpCtpop(Pred: EdgePred, RHS);
1430
1431 const APInt *Mask, *C;
1432 if (match(V: LHS, P: m_And(L: m_Specific(V: Val), R: m_APInt(Res&: Mask))) &&
1433 match(V: RHS, P: m_APInt(Res&: C))) {
1434 // If (Val & Mask) == C then all the masked bits are known and we can
1435 // compute a value range based on that.
1436 if (EdgePred == ICmpInst::ICMP_EQ) {
1437 KnownBits Known;
1438 Known.Zero = ~*C & *Mask;
1439 Known.One = *C & *Mask;
1440 return ValueLatticeElement::getRange(
1441 CR: ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
1442 }
1443
1444 if (EdgePred == ICmpInst::ICMP_NE)
1445 return ValueLatticeElement::getRange(
1446 CR: ConstantRange::makeMaskNotEqualRange(Mask: *Mask, C: *C));
1447 }
1448
1449 // If (X urem Modulus) >= C, then X >= C.
1450 // If trunc X >= C, then X >= C.
1451 // TODO: An upper bound could be computed as well.
1452 if (match(V: LHS, P: m_CombineOr(Ps: m_URem(L: m_Specific(V: Val), R: m_Value()),
1453 Ps: m_Trunc(Op: m_Specific(V: Val)))) &&
1454 match(V: RHS, P: m_APInt(Res&: C))) {
1455 // Use the icmp region so we don't have to deal with different predicates.
1456 ConstantRange CR = ConstantRange::makeExactICmpRegion(Pred: EdgePred, Other: *C);
1457 if (!CR.isEmptySet())
1458 return ValueLatticeElement::getRange(CR: ConstantRange::getNonEmpty(
1459 Lower: CR.getUnsignedMin().zext(width: BitWidth), Upper: APInt(BitWidth, 0)));
1460 }
1461
1462 // Recognize:
1463 // icmp slt (ashr X, ShAmtC), C --> icmp slt X, C << ShAmtC
1464 // Preconditions: (C << ShAmtC) >> ShAmtC == C
1465 const APInt *ShAmtC;
1466 if (CmpInst::isSigned(Pred: EdgePred) &&
1467 match(V: LHS, P: m_AShr(L: m_Specific(V: Val), R: m_APInt(Res&: ShAmtC))) &&
1468 match(V: RHS, P: m_APInt(Res&: C))) {
1469 auto CR = getRangeViaSLT(
1470 Pred: EdgePred, RHS: *C, Fn: [&](const APInt &RHS) -> std::optional<ConstantRange> {
1471 APInt New = RHS << *ShAmtC;
1472 if ((New.ashr(ShiftAmt: *ShAmtC)) != RHS)
1473 return std::nullopt;
1474 return ConstantRange::getNonEmpty(
1475 Lower: APInt::getSignedMinValue(numBits: New.getBitWidth()), Upper: New);
1476 });
1477 if (CR)
1478 return ValueLatticeElement::getRange(CR: *CR);
1479 }
1480
1481 // a - b or ptrtoint(a) - ptrtoint(b) ==/!= 0 if a ==/!= b
1482 Value *X, *Y;
1483 if (ICI->isEquality() && match(V: Val, P: m_Sub(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1484 // Peek through ptrtoints
1485 match(V: X, P: m_PtrToIntSameSize(DL, Op: m_Value(V&: X)));
1486 match(V: Y, P: m_PtrToIntSameSize(DL, Op: m_Value(V&: Y)));
1487 if ((X == LHS && Y == RHS) || (X == RHS && Y == LHS)) {
1488 Constant *NullVal = Constant::getNullValue(Ty: Val->getType());
1489 if (EdgePred == ICmpInst::ICMP_EQ)
1490 return ValueLatticeElement::get(C: NullVal);
1491 return ValueLatticeElement::getNot(C: NullVal);
1492 }
1493 }
1494
1495 return ValueLatticeElement::getOverdefined();
1496}
1497
1498ValueLatticeElement LazyValueInfoImpl::getValueFromTrunc(Value *Val,
1499 TruncInst *Trunc,
1500 bool IsTrueDest) {
1501 assert(Trunc->getType()->isIntOrIntVectorTy(1));
1502
1503 if (Trunc->getOperand(i_nocapture: 0) != Val)
1504 return ValueLatticeElement::getOverdefined();
1505
1506 Type *Ty = Val->getType();
1507
1508 if (Trunc->hasNoUnsignedWrap()) {
1509 if (IsTrueDest)
1510 return ValueLatticeElement::get(C: ConstantInt::get(Ty, V: 1));
1511 return ValueLatticeElement::get(C: Constant::getNullValue(Ty));
1512 }
1513
1514 if (IsTrueDest)
1515 return ValueLatticeElement::getNot(C: Constant::getNullValue(Ty));
1516 return ValueLatticeElement::getNot(C: Constant::getAllOnesValue(Ty));
1517}
1518
1519// Handle conditions of the form
1520// extractvalue(op.with.overflow(%x, C), 1).
1521static ValueLatticeElement getValueFromOverflowCondition(
1522 Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1523 // TODO: This only works with a constant RHS for now. We could also compute
1524 // the range of the RHS, but this doesn't fit into the current structure of
1525 // the edge value calculation.
1526 const APInt *C;
1527 if (WO->getLHS() != Val || !match(V: WO->getRHS(), P: m_APInt(Res&: C)))
1528 return ValueLatticeElement::getOverdefined();
1529
1530 // Calculate the possible values of %x for which no overflow occurs.
1531 ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
1532 BinOp: WO->getBinaryOp(), Other: *C, NoWrapKind: WO->getNoWrapKind());
1533
1534 // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1535 // constrained to it's inverse (all values that might cause overflow).
1536 if (IsTrueDest)
1537 NWR = NWR.inverse();
1538 return ValueLatticeElement::getRange(CR: NWR);
1539}
1540
1541std::optional<ValueLatticeElement>
1542LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond,
1543 bool IsTrueDest, bool UseBlockValue,
1544 unsigned Depth) {
1545 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Val: Cond))
1546 return getValueFromICmpCondition(Val, ICI, isTrueDest: IsTrueDest, UseBlockValue);
1547
1548 if (auto *Trunc = dyn_cast<TruncInst>(Val: Cond))
1549 return getValueFromTrunc(Val, Trunc, IsTrueDest);
1550
1551 if (auto *EVI = dyn_cast<ExtractValueInst>(Val: Cond))
1552 if (auto *WO = dyn_cast<WithOverflowInst>(Val: EVI->getAggregateOperand()))
1553 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1554 return getValueFromOverflowCondition(Val, WO, IsTrueDest);
1555
1556 if (++Depth == MaxAnalysisRecursionDepth)
1557 return ValueLatticeElement::getOverdefined();
1558
1559 Value *N;
1560 if (match(V: Cond, P: m_Not(V: m_Value(V&: N))))
1561 return getValueFromCondition(Val, Cond: N, IsTrueDest: !IsTrueDest, UseBlockValue, Depth);
1562
1563 Value *L, *R;
1564 bool IsAnd;
1565 if (match(V: Cond, P: m_LogicalAnd(L: m_Value(V&: L), R: m_Value(V&: R))))
1566 IsAnd = true;
1567 else if (match(V: Cond, P: m_LogicalOr(L: m_Value(V&: L), R: m_Value(V&: R))))
1568 IsAnd = false;
1569 else
1570 return ValueLatticeElement::getOverdefined();
1571
1572 std::optional<ValueLatticeElement> LV =
1573 getValueFromCondition(Val, Cond: L, IsTrueDest, UseBlockValue, Depth);
1574 if (!LV)
1575 return std::nullopt;
1576 std::optional<ValueLatticeElement> RV =
1577 getValueFromCondition(Val, Cond: R, IsTrueDest, UseBlockValue, Depth);
1578 if (!RV)
1579 return std::nullopt;
1580
1581 // if (L && R) -> intersect L and R
1582 // if (!(L || R)) -> intersect !L and !R
1583 // if (L || R) -> union L and R
1584 // if (!(L && R)) -> union !L and !R
1585 if (IsTrueDest ^ IsAnd) {
1586 LV->mergeIn(RHS: *RV);
1587 return *LV;
1588 }
1589
1590 return LV->intersect(Other: *RV);
1591}
1592
1593// Return true if Usr has Op as an operand, otherwise false.
1594static bool usesOperand(User *Usr, Value *Op) {
1595 return is_contained(Range: Usr->operands(), Element: Op);
1596}
1597
1598// Return true if the instruction type of Val is supported by
1599// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
1600// Call this before calling constantFoldUser() to find out if it's even worth
1601// attempting to call it.
1602static bool isOperationFoldable(User *Usr) {
1603 return isa<CastInst>(Val: Usr) || isa<BinaryOperator>(Val: Usr) || isa<FreezeInst>(Val: Usr);
1604}
1605
1606// Check if Usr can be simplified to an integer constant when the value of one
1607// of its operands Op is an integer constant OpConstVal. If so, return it as an
1608// lattice value range with a single element or otherwise return an overdefined
1609// lattice value.
1610static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1611 const APInt &OpConstVal,
1612 const DataLayout &DL) {
1613 assert(isOperationFoldable(Usr) && "Precondition");
1614 Constant* OpConst = Constant::getIntegerValue(Ty: Op->getType(), V: OpConstVal);
1615 // Check if Usr can be simplified to a constant.
1616 if (auto *CI = dyn_cast<CastInst>(Val: Usr)) {
1617 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1618 if (auto *C = dyn_cast_or_null<ConstantInt>(
1619 Val: simplifyCastInst(CastOpc: CI->getOpcode(), Op: OpConst,
1620 Ty: CI->getDestTy(), Q: DL))) {
1621 return ValueLatticeElement::getRange(CR: ConstantRange(C->getValue()));
1622 }
1623 } else if (auto *BO = dyn_cast<BinaryOperator>(Val: Usr)) {
1624 bool Op0Match = BO->getOperand(i_nocapture: 0) == Op;
1625 bool Op1Match = BO->getOperand(i_nocapture: 1) == Op;
1626 assert((Op0Match || Op1Match) &&
1627 "Operand 0 nor Operand 1 isn't a match");
1628 Value *LHS = Op0Match ? OpConst : BO->getOperand(i_nocapture: 0);
1629 Value *RHS = Op1Match ? OpConst : BO->getOperand(i_nocapture: 1);
1630 if (auto *C = dyn_cast_or_null<ConstantInt>(
1631 Val: simplifyBinOp(Opcode: BO->getOpcode(), LHS, RHS, Q: DL))) {
1632 return ValueLatticeElement::getRange(CR: ConstantRange(C->getValue()));
1633 }
1634 } else if (isa<FreezeInst>(Val: Usr)) {
1635 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
1636 return ValueLatticeElement::getRange(CR: ConstantRange(OpConstVal));
1637 }
1638 return ValueLatticeElement::getOverdefined();
1639}
1640
1641/// Compute the value of Val on the edge BBFrom -> BBTo.
1642std::optional<ValueLatticeElement>
1643LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1644 BasicBlock *BBTo, bool UseBlockValue) {
1645 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1646 // know that v != 0.
1647 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: BBFrom->getTerminator())) {
1648 // If this is a conditional branch and only one successor goes to BBTo, then
1649 // we may be able to infer something from the condition.
1650 if (BI->getSuccessor(i: 0) != BI->getSuccessor(i: 1)) {
1651 bool isTrueDest = BI->getSuccessor(i: 0) == BBTo;
1652 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1653 "BBTo isn't a successor of BBFrom");
1654 Value *Condition = BI->getCondition();
1655
1656 // If V is the condition of the branch itself, then we know exactly what
1657 // it is.
1658 // NB: The condition on a `br` can't be a vector type.
1659 if (Condition == Val)
1660 return ValueLatticeElement::get(C: ConstantInt::get(
1661 Ty: Type::getInt1Ty(C&: Val->getContext()), V: isTrueDest));
1662
1663 // If the condition of the branch is an equality comparison, we may be
1664 // able to infer the value.
1665 std::optional<ValueLatticeElement> Result =
1666 getValueFromCondition(Val, Cond: Condition, IsTrueDest: isTrueDest, UseBlockValue);
1667 if (!Result)
1668 return std::nullopt;
1669
1670 if (!Result->isOverdefined())
1671 return Result;
1672
1673 if (User *Usr = dyn_cast<User>(Val)) {
1674 assert(Result->isOverdefined() && "Result isn't overdefined");
1675 // Check with isOperationFoldable() first to avoid linearly iterating
1676 // over the operands unnecessarily which can be expensive for
1677 // instructions with many operands.
1678 if (isa<IntegerType>(Val: Usr->getType()) && isOperationFoldable(Usr)) {
1679 const DataLayout &DL = BBTo->getDataLayout();
1680 Value *TempCond = Condition;
1681 if (usesOperand(Usr, Op: Condition) ||
1682 (match(V: Condition, P: m_Not(V: m_Value(V&: TempCond))) &&
1683 usesOperand(Usr, Op: TempCond))) {
1684 // If Val has Condition as an operand and Val can be folded into a
1685 // constant with either Condition == true or Condition == false,
1686 // propagate the constant.
1687 // eg.
1688 // ; %Val is true on the edge to %then.
1689 // %Val = and i1 %Condition, true.
1690 // br %Condition, label %then, label %else
1691 APInt ConditionVal(1, isTrueDest ^ (TempCond != Condition) ? 1 : 0);
1692 Result = constantFoldUser(Usr, Op: TempCond, OpConstVal: ConditionVal, DL);
1693 } else if (isa<TruncInst, ZExtInst, SExtInst>(Val: Usr)) {
1694 ValueLatticeElement OpLatticeVal =
1695 *getValueFromCondition(Val: Usr->getOperand(i: 0), Cond: Condition,
1696 IsTrueDest: isTrueDest, /*UseBlockValue*/ false);
1697
1698 if (OpLatticeVal.isConstantRange()) {
1699 const unsigned ResultBitWidth =
1700 Usr->getType()->getScalarSizeInBits();
1701 if (auto *Trunc = dyn_cast<TruncInst>(Val: Usr))
1702 return ValueLatticeElement::getRange(
1703 CR: OpLatticeVal.getConstantRange().truncate(
1704 BitWidth: ResultBitWidth, NoWrapKind: Trunc->getNoWrapKind()));
1705
1706 return ValueLatticeElement::getRange(
1707 CR: OpLatticeVal.getConstantRange().castOp(
1708 CastOp: cast<CastInst>(Val: Usr)->getOpcode(), BitWidth: ResultBitWidth));
1709 }
1710 if (OpLatticeVal.isConstant()) {
1711 Constant *C = OpLatticeVal.getConstant();
1712 if (auto *CastC = ConstantFoldCastOperand(
1713 Opcode: cast<CastInst>(Val: Usr)->getOpcode(), C, DestTy: Usr->getType(), DL))
1714 return ValueLatticeElement::get(C: CastC);
1715 }
1716 return ValueLatticeElement::getOverdefined();
1717 } else {
1718 // If one of Val's operand has an inferred value, we may be able to
1719 // infer the value of Val.
1720 // eg.
1721 // ; %Val is 94 on the edge to %then.
1722 // %Val = add i8 %Op, 1
1723 // %Condition = icmp eq i8 %Op, 93
1724 // br i1 %Condition, label %then, label %else
1725 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1726 Value *Op = Usr->getOperand(i);
1727 ValueLatticeElement OpLatticeVal = *getValueFromCondition(
1728 Val: Op, Cond: Condition, IsTrueDest: isTrueDest, /*UseBlockValue*/ false);
1729 if (std::optional<APInt> OpConst =
1730 OpLatticeVal.asConstantInteger()) {
1731 Result = constantFoldUser(Usr, Op, OpConstVal: *OpConst, DL);
1732 break;
1733 }
1734 }
1735 }
1736 }
1737 }
1738 if (!Result->isOverdefined())
1739 return Result;
1740 }
1741 }
1742
1743 // If the edge was formed by a switch on the value, then we may know exactly
1744 // what it is.
1745 if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: BBFrom->getTerminator())) {
1746 Value *Condition = SI->getCondition();
1747 if (!isa<IntegerType>(Val: Val->getType()))
1748 return ValueLatticeElement::getOverdefined();
1749 bool ValUsesConditionAndMayBeFoldable = false;
1750 if (Condition != Val) {
1751 // Check if Val has Condition as an operand.
1752 if (User *Usr = dyn_cast<User>(Val))
1753 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1754 usesOperand(Usr, Op: Condition);
1755 if (!ValUsesConditionAndMayBeFoldable)
1756 return ValueLatticeElement::getOverdefined();
1757 }
1758 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1759 "Condition != Val nor Val doesn't use Condition");
1760
1761 bool DefaultCase = SI->getDefaultDest() == BBTo;
1762 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1763 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1764
1765 for (auto Case : SI->cases()) {
1766 APInt CaseValue = Case.getCaseValue()->getValue();
1767 ConstantRange EdgeVal(CaseValue);
1768 if (ValUsesConditionAndMayBeFoldable) {
1769 User *Usr = cast<User>(Val);
1770 const DataLayout &DL = BBTo->getDataLayout();
1771 ValueLatticeElement EdgeLatticeVal =
1772 constantFoldUser(Usr, Op: Condition, OpConstVal: CaseValue, DL);
1773 if (EdgeLatticeVal.isOverdefined())
1774 return ValueLatticeElement::getOverdefined();
1775 EdgeVal = EdgeLatticeVal.getConstantRange();
1776 }
1777 if (DefaultCase) {
1778 // It is possible that the default destination is the destination of
1779 // some cases. We cannot perform difference for those cases.
1780 // We know Condition != CaseValue in BBTo. In some cases we can use
1781 // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1782 // only do this when f is identity (i.e. Val == Condition), but we
1783 // should be able to do this for any injective f.
1784 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1785 EdgesVals = EdgesVals.difference(CR: EdgeVal);
1786 } else if (Case.getCaseSuccessor() == BBTo)
1787 EdgesVals = EdgesVals.unionWith(CR: EdgeVal);
1788 }
1789 return ValueLatticeElement::getRange(CR: std::move(EdgesVals));
1790 }
1791 return ValueLatticeElement::getOverdefined();
1792}
1793
1794/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1795/// the basic block if the edge does not constrain Val.
1796std::optional<ValueLatticeElement>
1797LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1798 BasicBlock *BBTo, Instruction *CtxI) {
1799 // If already a constant, there is nothing to compute.
1800 if (Constant *VC = dyn_cast<Constant>(Val))
1801 return ValueLatticeElement::get(C: VC);
1802
1803 std::optional<ValueLatticeElement> LocalResult =
1804 getEdgeValueLocal(Val, BBFrom, BBTo, /*UseBlockValue*/ true);
1805 if (!LocalResult)
1806 return std::nullopt;
1807
1808 if (hasSingleValue(Val: *LocalResult))
1809 // Can't get any more precise here
1810 return LocalResult;
1811
1812 std::optional<ValueLatticeElement> OptInBlock =
1813 getBlockValue(Val, BB: BBFrom, CtxI: BBFrom->getTerminator());
1814 if (!OptInBlock)
1815 return std::nullopt;
1816 ValueLatticeElement &InBlock = *OptInBlock;
1817
1818 // We can use the context instruction (generically the ultimate instruction
1819 // the calling pass is trying to simplify) here, even though the result of
1820 // this function is generally cached when called from the solve* functions
1821 // (and that cached result might be used with queries using a different
1822 // context instruction), because when this function is called from the solve*
1823 // functions, the context instruction is not provided. When called from
1824 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1825 // but then the result is not cached.
1826 intersectAssumeOrGuardBlockValueConstantRange(Val, BBLV&: InBlock, BBI: CtxI);
1827
1828 return LocalResult->intersect(Other: InBlock);
1829}
1830
1831ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1832 Instruction *CtxI) {
1833 LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1834 << BB->getName() << "'\n");
1835
1836 assert(BlockValueStack.empty() && BlockValueSet.empty());
1837 std::optional<ValueLatticeElement> OptResult = getBlockValue(Val: V, BB, CtxI);
1838 if (!OptResult) {
1839 solve();
1840 OptResult = getBlockValue(Val: V, BB, CtxI);
1841 assert(OptResult && "Value not available after solving");
1842 }
1843
1844 LLVM_DEBUG(dbgs() << " Result = " << *OptResult << "\n");
1845 return *OptResult;
1846}
1847
1848ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CtxI) {
1849 LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CtxI->getName()
1850 << "'\n");
1851
1852 if (auto *C = dyn_cast<Constant>(Val: V))
1853 return ValueLatticeElement::get(C);
1854
1855 ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1856 if (auto *I = dyn_cast<Instruction>(Val: V))
1857 Result = getFromRangeMetadata(BBI: I);
1858 intersectAssumeOrGuardBlockValueConstantRange(Val: V, BBLV&: Result, BBI: CtxI);
1859
1860 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1861 return Result;
1862}
1863
1864ValueLatticeElement LazyValueInfoImpl::
1865getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1866 Instruction *CtxI) {
1867 LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1868 << FromBB->getName() << "' to '" << ToBB->getName()
1869 << "'\n");
1870
1871 std::optional<ValueLatticeElement> Result =
1872 getEdgeValue(Val: V, BBFrom: FromBB, BBTo: ToBB, CtxI);
1873 while (!Result) {
1874 // As the worklist only explicitly tracks block values (but not edge values)
1875 // we may have to call solve() multiple times, as the edge value calculation
1876 // may request additional block values.
1877 solve();
1878 Result = getEdgeValue(Val: V, BBFrom: FromBB, BBTo: ToBB, CtxI);
1879 }
1880
1881 LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");
1882 return *Result;
1883}
1884
1885ValueLatticeElement LazyValueInfoImpl::getValueAtUse(
1886 const Use &U, SmallVectorImpl<DbgVariableRecord *> *DebugUsers) {
1887 Value *V = U.get();
1888 auto *CtxI = cast<Instruction>(Val: U.getUser());
1889 ValueLatticeElement VL = getValueInBlock(V, BB: CtxI->getParent(), CtxI);
1890 BasicBlock *LastQueriedBB = CtxI->getParent();
1891
1892 // Check whether the only (possibly transitive) use of the value is in a
1893 // position where V can be constrained by a select or branch condition.
1894 const Use *CurrU = &U;
1895 // TODO: Increase limit?
1896 const unsigned MaxUsesToInspect = 3;
1897 for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
1898 std::optional<ValueLatticeElement> CondVal;
1899 auto *CurrI = cast<Instruction>(Val: CurrU->getUser());
1900
1901 // Collect debug users of this value that isn't the starting value
1902 if (DebugUsers && CurrU != &U)
1903 findDbgUsers(V: CurrU->get(), DbgVariableRecords&: *DebugUsers);
1904
1905 // All instructions on the one-use chain between the original use and CurrI
1906 // are speculatable and have a single user each, so they could be sunk to
1907 // CurrI. This means information that holds at CurrI also holds for the
1908 // original use and can be used to refine it. Skip phis, as V may not
1909 // dominate their block.
1910 if (I != 0 && !isa<PHINode>(Val: CurrI) && CurrI->getParent() != LastQueriedBB) {
1911 LastQueriedBB = CurrI->getParent();
1912 VL = VL.intersect(Other: getValueInBlock(V, BB: LastQueriedBB, CtxI: CurrI));
1913 }
1914
1915 if (auto *SI = dyn_cast<SelectInst>(Val: CurrI)) {
1916 // If the value is undef, a different value may be chosen in
1917 // the select condition and at use.
1918 if (!isGuaranteedNotToBeUndef(V: SI->getCondition(), AC))
1919 break;
1920 if (CurrU->getOperandNo() == 1)
1921 CondVal =
1922 *getValueFromCondition(Val: V, Cond: SI->getCondition(), /*IsTrueDest*/ true,
1923 /*UseBlockValue*/ false);
1924 else if (CurrU->getOperandNo() == 2)
1925 CondVal =
1926 *getValueFromCondition(Val: V, Cond: SI->getCondition(), /*IsTrueDest*/ false,
1927 /*UseBlockValue*/ false);
1928 } else if (auto *PHI = dyn_cast<PHINode>(Val: CurrI)) {
1929 // TODO: Use non-local query?
1930 CondVal = *getEdgeValueLocal(Val: V, BBFrom: PHI->getIncomingBlock(U: *CurrU),
1931 BBTo: PHI->getParent(), /*UseBlockValue*/ false);
1932 }
1933 if (CondVal)
1934 VL = VL.intersect(Other: *CondVal);
1935
1936 // Only follow one-use chain, to allow direct intersection of conditions.
1937 // If there are multiple uses, we would have to intersect with the union of
1938 // all conditions at different uses.
1939 // Stop walking if we hit a non-speculatable instruction. Even if the
1940 // result is only used under a specific condition, executing the
1941 // instruction itself may cause side effects or UB already.
1942 // This also disallows looking through phi nodes: If the phi node is part
1943 // of a cycle, we might end up reasoning about values from different cycle
1944 // iterations (PR60629).
1945 if (!CurrI->hasOneUse() ||
1946 !isSafeToSpeculativelyExecuteWithVariableReplaced(
1947 I: CurrI, /*IgnoreUBImplyingAttrs=*/false))
1948 break;
1949 // Also stop walking at cross-lane operations, since they may rearrange
1950 // lanes so that a later select per-lane condition might no longer
1951 // correspond to the original value's lanes.
1952 if (V->getType()->isVectorTy() && !isNotCrossLaneOperation(I: CurrI))
1953 break;
1954 CurrU = &*CurrI->use_begin();
1955 }
1956 return VL;
1957}
1958
1959void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1960 BasicBlock *NewSucc) {
1961 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1962}
1963
1964//===----------------------------------------------------------------------===//
1965// LazyValueInfo Impl
1966//===----------------------------------------------------------------------===//
1967
1968bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1969 Info.F = &F;
1970 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1971
1972 if (auto *Impl = Info.getImpl())
1973 Impl->clear();
1974
1975 // Fully lazy.
1976 return false;
1977}
1978
1979void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1980 AU.setPreservesAll();
1981 AU.addRequired<AssumptionCacheTracker>();
1982 AU.addRequired<TargetLibraryInfoWrapperPass>();
1983}
1984
1985LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1986
1987/// This lazily constructs the LazyValueInfoImpl.
1988LazyValueInfoImpl &LazyValueInfo::getOrCreateImpl() {
1989 if (!PImpl) {
1990 const DataLayout &DL = F->getDataLayout();
1991 Function *GuardDecl = Intrinsic::getDeclarationIfExists(
1992 M: F->getParent(), id: Intrinsic::experimental_guard);
1993 PImpl = new LazyValueInfoImpl(F, AC, DL, GuardDecl);
1994 }
1995 return *PImpl;
1996}
1997
1998LazyValueInfoImpl *LazyValueInfo::getImpl() { return PImpl; }
1999
2000LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
2001
2002void LazyValueInfo::releaseMemory() {
2003 // If the cache was allocated, free it.
2004 if (auto *Impl = getImpl()) {
2005 delete &*Impl;
2006 PImpl = nullptr;
2007 }
2008}
2009
2010bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
2011 FunctionAnalysisManager::Invalidator &Inv) {
2012 // We need to invalidate if we have either failed to preserve this analyses
2013 // result directly or if any of its dependencies have been invalidated.
2014 auto PAC = PA.getChecker<LazyValueAnalysis>();
2015 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
2016 return true;
2017
2018 return false;
2019}
2020
2021void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
2022
2023LazyValueInfo LazyValueAnalysis::run(Function &F,
2024 FunctionAnalysisManager &FAM) {
2025 auto &AC = FAM.getResult<AssumptionAnalysis>(IR&: F);
2026
2027 return LazyValueInfo(&F, &AC);
2028}
2029
2030/// Returns true if we can statically tell that this value will never be a
2031/// "useful" constant. In practice, this means we've got something like an
2032/// alloca or a malloc call for which a comparison against a constant can
2033/// only be guarding dead code. Note that we are potentially giving up some
2034/// precision in dead code (a constant result) in favour of avoiding a
2035/// expensive search for a easily answered common query.
2036static bool isKnownNonConstant(Value *V) {
2037 V = V->stripPointerCasts();
2038 // The return val of alloc cannot be a Constant.
2039 if (isa<AllocaInst>(Val: V))
2040 return true;
2041 return false;
2042}
2043
2044Constant *LazyValueInfo::getConstant(Value *V, Instruction *CtxI) {
2045 // Bail out early if V is known not to be a Constant.
2046 if (isKnownNonConstant(V))
2047 return nullptr;
2048
2049 BasicBlock *BB = CtxI->getParent();
2050 ValueLatticeElement Result = getOrCreateImpl().getValueInBlock(V, BB, CtxI);
2051
2052 if (Result.isConstant())
2053 return Result.getConstant();
2054 if (Result.isConstantRange()) {
2055 const ConstantRange &CR = Result.getConstantRange();
2056 if (const APInt *SingleVal = CR.getSingleElement())
2057 return ConstantInt::get(Ty: V->getType(), V: *SingleVal);
2058 }
2059 return nullptr;
2060}
2061
2062ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CtxI,
2063 bool UndefAllowed) {
2064 BasicBlock *BB = CtxI->getParent();
2065 ValueLatticeElement Result = getOrCreateImpl().getValueInBlock(V, BB, CtxI);
2066 return Result.asConstantRange(Ty: V->getType(), UndefAllowed);
2067}
2068
2069ConstantRange LazyValueInfo::getConstantRangeAtUse(
2070 const Use &U, bool UndefAllowed,
2071 SmallVectorImpl<DbgVariableRecord *> *DebugUsers) {
2072 ValueLatticeElement Result = getOrCreateImpl().getValueAtUse(U, DebugUsers);
2073 return Result.asConstantRange(Ty: U->getType(), UndefAllowed);
2074}
2075
2076/// Determine whether the specified value is known to be a
2077/// constant on the specified edge. Return null if not.
2078Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
2079 BasicBlock *ToBB,
2080 Instruction *CtxI) {
2081 ValueLatticeElement Result =
2082 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CtxI);
2083
2084 if (Result.isConstant())
2085 return Result.getConstant();
2086 if (Result.isConstantRange()) {
2087 const ConstantRange &CR = Result.getConstantRange();
2088 if (const APInt *SingleVal = CR.getSingleElement())
2089 return ConstantInt::get(Ty: V->getType(), V: *SingleVal);
2090 }
2091 return nullptr;
2092}
2093
2094ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
2095 BasicBlock *FromBB,
2096 BasicBlock *ToBB,
2097 Instruction *CtxI) {
2098 ValueLatticeElement Result =
2099 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CtxI);
2100 // TODO: Should undef be allowed here?
2101 return Result.asConstantRange(Ty: V->getType(), /*UndefAllowed*/ true);
2102}
2103
2104static Constant *getPredicateResult(CmpInst::Predicate Pred, Constant *C,
2105 const ValueLatticeElement &Val,
2106 const DataLayout &DL) {
2107 // If we know the value is a constant, evaluate the conditional.
2108 if (Val.isConstant())
2109 return ConstantFoldCompareInstOperands(Predicate: Pred, LHS: Val.getConstant(), RHS: C, DL);
2110
2111 Type *ResTy = CmpInst::makeCmpResultType(opnd_type: C->getType());
2112 if (Val.isConstantRange()) {
2113 const ConstantRange &CR = Val.getConstantRange();
2114 ConstantRange RHS = C->toConstantRange();
2115 if (CR.icmp(Pred, Other: RHS))
2116 return ConstantInt::getTrue(Ty: ResTy);
2117 if (CR.icmp(Pred: CmpInst::getInversePredicate(pred: Pred), Other: RHS))
2118 return ConstantInt::getFalse(Ty: ResTy);
2119 return nullptr;
2120 }
2121
2122 if (Val.isNotConstant()) {
2123 // If this is an equality comparison, we can try to fold it knowing that
2124 // "V != C1".
2125 if (Pred == ICmpInst::ICMP_EQ) {
2126 // !C1 == C -> false iff C1 == C.
2127 Constant *Res = ConstantFoldCompareInstOperands(
2128 Predicate: ICmpInst::ICMP_NE, LHS: Val.getNotConstant(), RHS: C, DL);
2129 if (Res && Res->isNullValue())
2130 return ConstantInt::getFalse(Ty: ResTy);
2131 } else if (Pred == ICmpInst::ICMP_NE) {
2132 // !C1 != C -> true iff C1 == C.
2133 Constant *Res = ConstantFoldCompareInstOperands(
2134 Predicate: ICmpInst::ICMP_NE, LHS: Val.getNotConstant(), RHS: C, DL);
2135 if (Res && Res->isNullValue())
2136 return ConstantInt::getTrue(Ty: ResTy);
2137 }
2138 return nullptr;
2139 }
2140
2141 return nullptr;
2142}
2143
2144/// Determine whether the specified value comparison with a constant is known to
2145/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
2146Constant *LazyValueInfo::getPredicateOnEdge(CmpInst::Predicate Pred, Value *V,
2147 Constant *C, BasicBlock *FromBB,
2148 BasicBlock *ToBB,
2149 Instruction *CtxI) {
2150 ValueLatticeElement Result =
2151 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CtxI);
2152
2153 return getPredicateResult(Pred, C, Val: Result, DL: FromBB->getDataLayout());
2154}
2155
2156Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred, Value *V,
2157 Constant *C, Instruction *CtxI,
2158 bool UseBlockValue) {
2159 // Is or is not NonNull are common predicates being queried. If
2160 // isKnownNonZero can tell us the result of the predicate, we can
2161 // return it quickly. But this is only a fastpath, and falling
2162 // through would still be correct.
2163 const DataLayout &DL = CtxI->getDataLayout();
2164 // NOTE: This check is meant to determine whether a pointer is semantically a
2165 // null pointer, not just whether its value equals ConstantPointerNull. If the
2166 // semantics of ConstantPointerNull change in the future, this should be
2167 // updated to use a semantic check (e.g. isKnownNonNull).
2168 if (V->getType()->isPointerTy() && C->isNullValue() &&
2169 isKnownNonZero(V: V->stripPointerCastsSameRepresentation(), Q: DL)) {
2170 Type *ResTy = CmpInst::makeCmpResultType(opnd_type: C->getType());
2171 if (Pred == ICmpInst::ICMP_EQ)
2172 return ConstantInt::getFalse(Ty: ResTy);
2173 else if (Pred == ICmpInst::ICMP_NE)
2174 return ConstantInt::getTrue(Ty: ResTy);
2175 }
2176
2177 auto &Impl = getOrCreateImpl();
2178 ValueLatticeElement Result =
2179 UseBlockValue ? Impl.getValueInBlock(V, BB: CtxI->getParent(), CtxI)
2180 : Impl.getValueAt(V, CtxI);
2181 Constant *Ret = getPredicateResult(Pred, C, Val: Result, DL);
2182 if (Ret)
2183 return Ret;
2184
2185 // Note: The following bit of code is somewhat distinct from the rest of LVI;
2186 // LVI as a whole tries to compute a lattice value which is conservatively
2187 // correct at a given location. In this case, we have a predicate which we
2188 // weren't able to prove about the merged result, and we're pushing that
2189 // predicate back along each incoming edge to see if we can prove it
2190 // separately for each input. As a motivating example, consider:
2191 // bb1:
2192 // %v1 = ... ; constantrange<1, 5>
2193 // br label %merge
2194 // bb2:
2195 // %v2 = ... ; constantrange<10, 20>
2196 // br label %merge
2197 // merge:
2198 // %phi = phi [%v1, %v2] ; constantrange<1,20>
2199 // %pred = icmp eq i32 %phi, 8
2200 // We can't tell from the lattice value for '%phi' that '%pred' is false
2201 // along each path, but by checking the predicate over each input separately,
2202 // we can.
2203 // We limit the search to one step backwards from the current BB and value.
2204 // We could consider extending this to search further backwards through the
2205 // CFG and/or value graph, but there are non-obvious compile time vs quality
2206 // tradeoffs.
2207 BasicBlock *BB = CtxI->getParent();
2208
2209 // Function entry or an unreachable block. Bail to avoid confusing
2210 // analysis below.
2211 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
2212 if (PI == PE)
2213 return nullptr;
2214
2215 // If V is a PHI node in the same block as the context, we need to ask
2216 // questions about the predicate as applied to the incoming value along
2217 // each edge. This is useful for eliminating cases where the predicate is
2218 // known along all incoming edges.
2219 if (auto *PHI = dyn_cast<PHINode>(Val: V))
2220 if (PHI->getParent() == BB) {
2221 Constant *Baseline = nullptr;
2222 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
2223 Value *Incoming = PHI->getIncomingValue(i);
2224 BasicBlock *PredBB = PHI->getIncomingBlock(i);
2225 // Note that PredBB may be BB itself.
2226 Constant *Result =
2227 getPredicateOnEdge(Pred, V: Incoming, C, FromBB: PredBB, ToBB: BB, CtxI);
2228
2229 // Keep going as long as we've seen a consistent known result for
2230 // all inputs.
2231 Baseline = (i == 0) ? Result /* First iteration */
2232 : (Baseline == Result ? Baseline
2233 : nullptr); /* All others */
2234 if (!Baseline)
2235 break;
2236 }
2237 if (Baseline)
2238 return Baseline;
2239 }
2240
2241 // For a comparison where the V is outside this block, it's possible
2242 // that we've branched on it before. Look to see if the value is known
2243 // on all incoming edges.
2244 if (!isa<Instruction>(Val: V) || cast<Instruction>(Val: V)->getParent() != BB) {
2245 // For predecessor edge, determine if the comparison is true or false
2246 // on that edge. If they're all true or all false, we can conclude
2247 // the value of the comparison in this block.
2248 Constant *Baseline = getPredicateOnEdge(Pred, V, C, FromBB: *PI, ToBB: BB, CtxI);
2249 if (Baseline) {
2250 // Check that all remaining incoming values match the first one.
2251 while (++PI != PE) {
2252 Constant *Ret = getPredicateOnEdge(Pred, V, C, FromBB: *PI, ToBB: BB, CtxI);
2253 if (Ret != Baseline)
2254 break;
2255 }
2256 // If we terminated early, then one of the values didn't match.
2257 if (PI == PE) {
2258 return Baseline;
2259 }
2260 }
2261 }
2262
2263 return nullptr;
2264}
2265
2266Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred, Value *LHS,
2267 Value *RHS, Instruction *CtxI,
2268 bool UseBlockValue) {
2269 if (auto *C = dyn_cast<Constant>(Val: RHS))
2270 return getPredicateAt(Pred, V: LHS, C, CtxI, UseBlockValue);
2271 if (auto *C = dyn_cast<Constant>(Val: LHS))
2272 return getPredicateAt(Pred: CmpInst::getSwappedPredicate(pred: Pred), V: RHS, C, CtxI,
2273 UseBlockValue);
2274
2275 // Got two non-Constant values. Try to determine the comparison results based
2276 // on the block values of the two operands, e.g. because they have
2277 // non-overlapping ranges.
2278 if (UseBlockValue) {
2279 ValueLatticeElement L =
2280 getOrCreateImpl().getValueInBlock(V: LHS, BB: CtxI->getParent(), CtxI);
2281 if (L.isOverdefined())
2282 return nullptr;
2283
2284 ValueLatticeElement R =
2285 getOrCreateImpl().getValueInBlock(V: RHS, BB: CtxI->getParent(), CtxI);
2286 Type *Ty = CmpInst::makeCmpResultType(opnd_type: LHS->getType());
2287 return L.getCompare(Pred, Ty, Other: R, DL: CtxI->getDataLayout());
2288 }
2289 return nullptr;
2290}
2291
2292void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
2293 BasicBlock *NewSucc) {
2294 if (auto *Impl = getImpl())
2295 Impl->threadEdge(PredBB, OldSucc, NewSucc);
2296}
2297
2298void LazyValueInfo::forgetValue(Value *V) {
2299 if (auto *Impl = getImpl())
2300 Impl->forgetValue(V);
2301}
2302
2303void LazyValueInfo::eraseBlock(BasicBlock *BB) {
2304 if (auto *Impl = getImpl())
2305 Impl->eraseBlock(BB);
2306}
2307
2308void LazyValueInfo::clear() {
2309 if (auto *Impl = getImpl())
2310 Impl->clear();
2311}
2312
2313void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
2314 if (auto *Impl = getImpl())
2315 Impl->printLVI(F, DTree, OS);
2316}
2317
2318// Print the LVI for the function arguments at the start of each basic block.
2319void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
2320 const BasicBlock *BB, formatted_raw_ostream &OS) {
2321 // Find if there are latticevalues defined for arguments of the function.
2322 auto *F = BB->getParent();
2323 for (const auto &Arg : F->args()) {
2324 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2325 V: const_cast<Argument *>(&Arg), BB: const_cast<BasicBlock *>(BB));
2326 if (Result.isUnknown())
2327 continue;
2328 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
2329 }
2330}
2331
2332// This function prints the LVI analysis for the instruction I at the beginning
2333// of various basic blocks. It relies on calculated values that are stored in
2334// the LazyValueInfoCache, and in the absence of cached values, recalculate the
2335// LazyValueInfo for `I`, and print that info.
2336void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2337 const Instruction *I, formatted_raw_ostream &OS) {
2338
2339 auto *ParentBB = I->getParent();
2340 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
2341 // We can generate (solve) LVI values only for blocks that are dominated by
2342 // the I's parent. However, to avoid generating LVI for all dominating blocks,
2343 // that contain redundant/uninteresting information, we print LVI for
2344 // blocks that may use this LVI information (such as immediate successor
2345 // blocks, and blocks that contain uses of `I`).
2346 auto printResult = [&](const BasicBlock *BB) {
2347 if (!BlocksContainingLVI.insert(Ptr: BB).second)
2348 return;
2349 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2350 V: const_cast<Instruction *>(I), BB: const_cast<BasicBlock *>(BB));
2351 OS << "; LatticeVal for: '" << *I << "' in BB: '";
2352 BB->printAsOperand(O&: OS, PrintType: false);
2353 OS << "' is: " << Result << "\n";
2354 };
2355
2356 printResult(ParentBB);
2357 // Print the LVI analysis results for the immediate successor blocks, that
2358 // are dominated by `ParentBB`.
2359 for (const auto *BBSucc : successors(BB: ParentBB))
2360 if (DT.dominates(A: ParentBB, B: BBSucc))
2361 printResult(BBSucc);
2362
2363 // Print LVI in blocks where `I` is used.
2364 for (const auto *U : I->users())
2365 if (auto *UseI = dyn_cast<Instruction>(Val: U))
2366 if (!isa<PHINode>(Val: UseI) || DT.dominates(A: ParentBB, B: UseI->getParent()))
2367 printResult(UseI->getParent());
2368
2369}
2370
2371PreservedAnalyses LazyValueInfoPrinterPass::run(Function &F,
2372 FunctionAnalysisManager &AM) {
2373 OS << "LVI for function '" << F.getName() << "':\n";
2374 auto &LVI = AM.getResult<LazyValueAnalysis>(IR&: F);
2375 auto &DTree = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2376 LVI.printLVI(F, DTree, OS);
2377 return PreservedAnalyses::all();
2378}
2379