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