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/AssumeBundleQueries.h"
18#include "llvm/Analysis/AssumptionCache.h"
19#include "llvm/Analysis/ConstantFolding.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/Passes.h"
22#include "llvm/Analysis/TargetLibraryInfo.h"
23#include "llvm/Analysis/ValueLattice.h"
24#include "llvm/Analysis/ValueTracking.h"
25#include "llvm/IR/AssemblyAnnotationWriter.h"
26#include "llvm/IR/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 (RetainedKnowledge RK = getKnowledgeFromBundle(
860 Assume&: *I, BOI: I->bundle_op_info_begin()[AssumeVH.Index])) {
861 if (RK.WasOn != Val)
862 continue;
863 switch (RK.AttrKind) {
864 case Attribute::NonNull:
865 BBLV = BBLV.intersect(Other: ValueLatticeElement::getNot(
866 C: Constant::getNullValue(Ty: RK.WasOn->getType())));
867 break;
868
869 case Attribute::Dereferenceable:
870 if (auto *CI = dyn_cast<ConstantInt>(Val: RK.IRArgValue);
871 CI && !CI->isZero())
872 BBLV = BBLV.intersect(Other: ValueLatticeElement::getNot(
873 C: Constant::getNullValue(Ty: RK.WasOn->getType())));
874 break;
875
876 default:
877 break;
878 }
879 }
880 } else {
881 BBLV = BBLV.intersect(Other: *getValueFromCondition(Val, Cond: I->getArgOperand(i: 0),
882 /*IsTrueDest*/ true,
883 /*UseBlockValue*/ false));
884 }
885 }
886
887 // If guards are not used in the module, don't spend time looking for them
888 if (GuardDecl && !GuardDecl->use_empty() &&
889 BBI->getIterator() != BB->begin()) {
890 for (Instruction &I :
891 make_range(x: std::next(x: BBI->getIterator().getReverse()), y: BB->rend())) {
892 Value *Cond = nullptr;
893 if (match(V: &I, P: m_Intrinsic<Intrinsic::experimental_guard>(Op0: m_Value(V&: Cond))))
894 BBLV = BBLV.intersect(Other: *getValueFromCondition(Val, Cond,
895 /*IsTrueDest*/ true,
896 /*UseBlockValue*/ false));
897 }
898 }
899
900 if (BBLV.isOverdefined()) {
901 // Check whether we're checking at the terminator, and the pointer has
902 // been dereferenced in this block.
903 PointerType *PTy = dyn_cast<PointerType>(Val: Val->getType());
904 if (PTy && BB->getTerminator() == BBI &&
905 isNonNullAtEndOfBlock(Val, BB))
906 BBLV = ValueLatticeElement::getNot(C: ConstantPointerNull::get(T: PTy));
907 }
908}
909
910std::optional<ValueLatticeElement>
911LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) {
912 // Recurse on our inputs if needed
913 std::optional<ValueLatticeElement> OptTrueVal =
914 getBlockValue(Val: SI->getTrueValue(), BB, CxtI: SI);
915 if (!OptTrueVal)
916 return std::nullopt;
917 ValueLatticeElement &TrueVal = *OptTrueVal;
918
919 std::optional<ValueLatticeElement> OptFalseVal =
920 getBlockValue(Val: SI->getFalseValue(), BB, CxtI: SI);
921 if (!OptFalseVal)
922 return std::nullopt;
923 ValueLatticeElement &FalseVal = *OptFalseVal;
924
925 if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
926 const ConstantRange &TrueCR = TrueVal.asConstantRange(Ty: SI->getType());
927 const ConstantRange &FalseCR = FalseVal.asConstantRange(Ty: SI->getType());
928 Value *LHS = nullptr;
929 Value *RHS = nullptr;
930 SelectPatternResult SPR = matchSelectPattern(V: SI, LHS, RHS);
931 // Is this a min specifically of our two inputs? (Avoid the risk of
932 // ValueTracking getting smarter looking back past our immediate inputs.)
933 if (SelectPatternResult::isMinOrMax(SPF: SPR.Flavor) &&
934 ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
935 (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
936 ConstantRange ResultCR = [&]() {
937 switch (SPR.Flavor) {
938 default:
939 llvm_unreachable("unexpected minmax type!");
940 case SPF_SMIN: /// Signed minimum
941 return TrueCR.smin(Other: FalseCR);
942 case SPF_UMIN: /// Unsigned minimum
943 return TrueCR.umin(Other: FalseCR);
944 case SPF_SMAX: /// Signed maximum
945 return TrueCR.smax(Other: FalseCR);
946 case SPF_UMAX: /// Unsigned maximum
947 return TrueCR.umax(Other: FalseCR);
948 };
949 }();
950 return ValueLatticeElement::getRange(
951 CR: ResultCR, MayIncludeUndef: TrueVal.isConstantRangeIncludingUndef() ||
952 FalseVal.isConstantRangeIncludingUndef());
953 }
954
955 if (SPR.Flavor == SPF_ABS) {
956 if (LHS == SI->getTrueValue())
957 return ValueLatticeElement::getRange(
958 CR: TrueCR.abs(), MayIncludeUndef: TrueVal.isConstantRangeIncludingUndef());
959 if (LHS == SI->getFalseValue())
960 return ValueLatticeElement::getRange(
961 CR: FalseCR.abs(), MayIncludeUndef: FalseVal.isConstantRangeIncludingUndef());
962 }
963
964 if (SPR.Flavor == SPF_NABS) {
965 ConstantRange Zero(APInt::getZero(numBits: TrueCR.getBitWidth()));
966 if (LHS == SI->getTrueValue())
967 return ValueLatticeElement::getRange(
968 CR: Zero.sub(Other: TrueCR.abs()), MayIncludeUndef: FalseVal.isConstantRangeIncludingUndef());
969 if (LHS == SI->getFalseValue())
970 return ValueLatticeElement::getRange(
971 CR: Zero.sub(Other: FalseCR.abs()), MayIncludeUndef: FalseVal.isConstantRangeIncludingUndef());
972 }
973 }
974
975 // Can we constrain the facts about the true and false values by using the
976 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
977 // TODO: We could potentially refine an overdefined true value above.
978 Value *Cond = SI->getCondition();
979 // If the value is undef, a different value may be chosen in
980 // the select condition.
981 if (isGuaranteedNotToBeUndef(V: Cond, AC)) {
982 TrueVal =
983 TrueVal.intersect(Other: *getValueFromCondition(Val: SI->getTrueValue(), Cond,
984 /*IsTrueDest*/ true,
985 /*UseBlockValue*/ false));
986 FalseVal =
987 FalseVal.intersect(Other: *getValueFromCondition(Val: SI->getFalseValue(), Cond,
988 /*IsTrueDest*/ false,
989 /*UseBlockValue*/ false));
990 }
991
992 TrueVal.mergeIn(RHS: FalseVal);
993 return TrueVal;
994}
995
996std::optional<ConstantRange>
997LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) {
998 std::optional<ValueLatticeElement> OptVal = getBlockValue(Val: V, BB, CxtI);
999 if (!OptVal)
1000 return std::nullopt;
1001 return OptVal->asConstantRange(Ty: V->getType());
1002}
1003
1004std::optional<ValueLatticeElement>
1005LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {
1006 // Filter out casts we don't know how to reason about before attempting to
1007 // recurse on our operand. This can cut a long search short if we know we're
1008 // not going to be able to get any useful information anways.
1009 switch (CI->getOpcode()) {
1010 case Instruction::Trunc:
1011 case Instruction::SExt:
1012 case Instruction::ZExt:
1013 break;
1014 default:
1015 // Unhandled instructions are overdefined.
1016 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1017 << "' - overdefined (unknown cast).\n");
1018 return ValueLatticeElement::getOverdefined();
1019 }
1020
1021 // Figure out the range of the LHS. If that fails, we still apply the
1022 // transfer rule on the full set since we may be able to locally infer
1023 // interesting facts.
1024 std::optional<ConstantRange> LHSRes = getRangeFor(V: CI->getOperand(i_nocapture: 0), CxtI: CI, BB);
1025 if (!LHSRes)
1026 // More work to do before applying this transfer rule.
1027 return std::nullopt;
1028 const ConstantRange &LHSRange = *LHSRes;
1029
1030 const unsigned ResultBitWidth = CI->getType()->getScalarSizeInBits();
1031
1032 // NOTE: We're currently limited by the set of operations that ConstantRange
1033 // can evaluate symbolically. Enhancing that set will allows us to analyze
1034 // more definitions.
1035 ConstantRange Res = ConstantRange::getEmpty(BitWidth: ResultBitWidth);
1036 if (auto *Trunc = dyn_cast<TruncInst>(Val: CI))
1037 Res = LHSRange.truncate(BitWidth: ResultBitWidth, NoWrapKind: Trunc->getNoWrapKind());
1038 else
1039 Res = LHSRange.castOp(CastOp: CI->getOpcode(), BitWidth: ResultBitWidth);
1040
1041 return ValueLatticeElement::getRange(CR: Res);
1042}
1043
1044std::optional<ValueLatticeElement>
1045LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
1046 Instruction *I, BasicBlock *BB,
1047 std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
1048 OpFn) {
1049 Value *LHS = I->getOperand(i: 0);
1050 Value *RHS = I->getOperand(i: 1);
1051
1052 auto ThreadBinOpOverSelect =
1053 [&](Value *X, const ConstantRange &CRX, SelectInst *Y,
1054 bool XIsLHS) -> std::optional<ValueLatticeElement> {
1055 Value *Cond = Y->getCondition();
1056 // Only handle selects with constant values.
1057 Constant *TrueC = dyn_cast<Constant>(Val: Y->getTrueValue());
1058 if (!TrueC)
1059 return std::nullopt;
1060 Constant *FalseC = dyn_cast<Constant>(Val: Y->getFalseValue());
1061 if (!FalseC)
1062 return std::nullopt;
1063 if (!isGuaranteedNotToBeUndef(V: Cond, AC))
1064 return std::nullopt;
1065
1066 ConstantRange TrueX =
1067 CRX.intersectWith(CR: getValueFromCondition(Val: X, Cond, /*CondIsTrue=*/IsTrueDest: true,
1068 /*UseBlockValue=*/false)
1069 ->asConstantRange(Ty: X->getType()));
1070 ConstantRange FalseX =
1071 CRX.intersectWith(CR: getValueFromCondition(Val: X, Cond, /*CondIsTrue=*/IsTrueDest: false,
1072 /*UseBlockValue=*/false)
1073 ->asConstantRange(Ty: X->getType()));
1074 ConstantRange TrueY = TrueC->toConstantRange();
1075 ConstantRange FalseY = FalseC->toConstantRange();
1076
1077 if (XIsLHS)
1078 return ValueLatticeElement::getRange(
1079 CR: OpFn(TrueX, TrueY).unionWith(CR: OpFn(FalseX, FalseY)));
1080 return ValueLatticeElement::getRange(
1081 CR: OpFn(TrueY, TrueX).unionWith(CR: OpFn(FalseY, FalseX)));
1082 };
1083
1084 // Figure out the ranges of the operands. If that fails, use a
1085 // conservative range, but apply the transfer rule anyways. This
1086 // lets us pick up facts from expressions like "and i32 (call i32
1087 // @foo()), 32"
1088 std::optional<ConstantRange> LHSRes = getRangeFor(V: LHS, CxtI: I, BB);
1089 if (!LHSRes)
1090 return std::nullopt;
1091
1092 // Try to thread binop over rhs select
1093 if (auto *SI = dyn_cast<SelectInst>(Val: RHS)) {
1094 if (auto Res = ThreadBinOpOverSelect(LHS, *LHSRes, SI, /*XIsLHS=*/true))
1095 return *Res;
1096 }
1097
1098 std::optional<ConstantRange> RHSRes = getRangeFor(V: RHS, CxtI: I, BB);
1099 if (!RHSRes)
1100 return std::nullopt;
1101
1102 // Try to thread binop over lhs select
1103 if (auto *SI = dyn_cast<SelectInst>(Val: LHS)) {
1104 if (auto Res = ThreadBinOpOverSelect(RHS, *RHSRes, SI, /*XIsLHS=*/false))
1105 return *Res;
1106 }
1107
1108 const ConstantRange &LHSRange = *LHSRes;
1109 const ConstantRange &RHSRange = *RHSRes;
1110
1111 std::optional<ValueLatticeElement> MergedResult =
1112 ValueLatticeElement::getRange(CR: OpFn(LHSRange, RHSRange));
1113
1114 if (!PerPredRanges)
1115 return MergedResult;
1116
1117 std::optional<BBLatticeElementMap> PredLHS =
1118 TheCache.getCachedPredecessorInfo(V: LHS, BB);
1119 if (!PredLHS)
1120 return MergedResult;
1121 std::optional<BBLatticeElementMap> PredRHS =
1122 TheCache.getCachedPredecessorInfo(V: RHS, BB);
1123 if (!PredRHS)
1124 return MergedResult;
1125
1126 const BBLatticeElementMap &LHSPredMap = *PredLHS;
1127 const BBLatticeElementMap &RHSPredMap = *PredRHS;
1128
1129 BBLatticeElementMap PredLatticeElements;
1130 ValueLatticeElement OverallPredResult;
1131 for (auto *Pred : predecessors(BB)) {
1132 auto LHSIt = LHSPredMap.find_as(Val: Pred);
1133 if (LHSIt == LHSPredMap.end())
1134 return MergedResult;
1135 const ValueLatticeElement &LHSFromPred = LHSIt->second;
1136 std::optional<ConstantRange> LHSFromPredRes =
1137 LHSFromPred.asConstantRange(Ty: LHS->getType());
1138 if (!LHSFromPredRes)
1139 return MergedResult;
1140
1141 auto RHSIt = RHSPredMap.find_as(Val: Pred);
1142 if (RHSIt == RHSPredMap.end())
1143 return MergedResult;
1144 const ValueLatticeElement &RHSFromPred = RHSIt->second;
1145 std::optional<ConstantRange> RHSFromPredRes =
1146 RHSFromPred.asConstantRange(Ty: RHS->getType());
1147 if (!RHSFromPredRes)
1148 return MergedResult;
1149
1150 const ConstantRange &LHSFromPredRange = *LHSFromPredRes;
1151 const ConstantRange &RHSFromPredRange = *RHSFromPredRes;
1152 std::optional<ValueLatticeElement> PredResult =
1153 ValueLatticeElement::getRange(CR: OpFn(LHSFromPredRange, RHSFromPredRange));
1154 if (!PredResult)
1155 return MergedResult;
1156 if (PredResult->isOverdefined()) {
1157 LLVM_DEBUG(
1158 dbgs() << " pred BB '" << Pred->getName() << "' for BB '"
1159 << BB->getName()
1160 << "' overdefined. Discarding all predecessor intervals.\n");
1161 return MergedResult;
1162 }
1163 PredLatticeElements.insert(KV: {Pred, *PredResult});
1164 OverallPredResult.mergeIn(RHS: *PredResult);
1165 }
1166
1167 // If this point is reached, all predecessors for both LHS and RHS have
1168 // constant ranges previously computed. Can cache result and use the
1169 // OverallPredResult;
1170 TheCache.insertPredecessorResults(Val: I, BB, PredLatticeElements);
1171
1172 LLVM_DEBUG(dbgs() << " Using predecessor intervals, evaluated " << *I
1173 << " to: " << OverallPredResult << ".\n");
1174
1175 if (!MergedResult)
1176 return OverallPredResult;
1177
1178 LLVM_DEBUG(dbgs() << " Intersecting intervals for " << *I << ": "
1179 << OverallPredResult << " and " << MergedResult << ".\n");
1180 return MergedResult->intersect(Other: OverallPredResult);
1181}
1182
1183std::optional<ValueLatticeElement>
1184LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) {
1185 assert(BO->getOperand(0)->getType()->isSized() &&
1186 "all operands to binary operators are sized");
1187 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: BO)) {
1188 unsigned NoWrapKind = OBO->getNoWrapKind();
1189 return solveBlockValueBinaryOpImpl(
1190 I: BO, BB,
1191 OpFn: [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
1192 return CR1.overflowingBinaryOp(BinOp: BO->getOpcode(), Other: CR2, NoWrapKind);
1193 });
1194 }
1195
1196 return solveBlockValueBinaryOpImpl(
1197 I: BO, BB, OpFn: [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
1198 return CR1.binaryOp(BinOp: BO->getOpcode(), Other: CR2);
1199 });
1200}
1201
1202std::optional<ValueLatticeElement>
1203LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
1204 BasicBlock *BB) {
1205 return solveBlockValueBinaryOpImpl(
1206 I: WO, BB, OpFn: [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
1207 return CR1.binaryOp(BinOp: WO->getBinaryOp(), Other: CR2);
1208 });
1209}
1210
1211std::optional<ValueLatticeElement>
1212LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) {
1213 ValueLatticeElement MetadataVal = getFromRangeMetadata(BBI: II);
1214 if (!ConstantRange::isIntrinsicSupported(IntrinsicID: II->getIntrinsicID())) {
1215 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1216 << "' - unknown intrinsic.\n");
1217 return MetadataVal;
1218 }
1219
1220 SmallVector<ConstantRange, 2> OpRanges;
1221 for (Value *Op : II->args()) {
1222 std::optional<ConstantRange> Range = getRangeFor(V: Op, CxtI: II, BB);
1223 if (!Range)
1224 return std::nullopt;
1225 OpRanges.push_back(Elt: *Range);
1226 }
1227
1228 return ValueLatticeElement::getRange(
1229 CR: ConstantRange::intrinsic(IntrinsicID: II->getIntrinsicID(), Ops: OpRanges))
1230 .intersect(Other: MetadataVal);
1231}
1232
1233std::optional<ValueLatticeElement>
1234LazyValueInfoImpl::solveBlockValueInsertElement(InsertElementInst *IEI,
1235 BasicBlock *BB) {
1236 std::optional<ValueLatticeElement> OptEltVal =
1237 getBlockValue(Val: IEI->getOperand(i_nocapture: 1), BB, CxtI: IEI);
1238 if (!OptEltVal)
1239 return std::nullopt;
1240 ValueLatticeElement &Res = *OptEltVal;
1241
1242 std::optional<ValueLatticeElement> OptVecVal =
1243 getBlockValue(Val: IEI->getOperand(i_nocapture: 0), BB, CxtI: IEI);
1244 if (!OptVecVal)
1245 return std::nullopt;
1246
1247 // Bail out if the inserted element is a constant expression. Unlike other
1248 // ValueLattice types, these are not considered an implicit splat when a
1249 // vector type is used.
1250 // We could call ConstantFoldInsertElementInstruction here to handle these.
1251 if (OptEltVal->isConstant())
1252 return ValueLatticeElement::getOverdefined();
1253
1254 Res.mergeIn(RHS: *OptVecVal);
1255 return Res;
1256}
1257
1258std::optional<ValueLatticeElement>
1259LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
1260 BasicBlock *BB) {
1261 if (auto *WO = dyn_cast<WithOverflowInst>(Val: EVI->getAggregateOperand()))
1262 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
1263 return solveBlockValueOverflowIntrinsic(WO, BB);
1264
1265 // Handle extractvalue of insertvalue to allow further simplification
1266 // based on replaced with.overflow intrinsics.
1267 if (Value *V = simplifyExtractValueInst(
1268 Agg: EVI->getAggregateOperand(), Idxs: EVI->getIndices(),
1269 Q: EVI->getDataLayout()))
1270 return getBlockValue(Val: V, BB, CxtI: EVI);
1271
1272 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1273 << "' - overdefined (unknown extractvalue).\n");
1274 return ValueLatticeElement::getOverdefined();
1275}
1276
1277static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
1278 ICmpInst::Predicate Pred) {
1279 if (LHS == Val)
1280 return true;
1281
1282 // Handle range checking idiom produced by InstCombine. We will subtract the
1283 // offset from the allowed range for RHS in this case.
1284 const APInt *C;
1285 if (match(V: LHS, P: m_AddLike(L: m_Specific(V: Val), R: m_APInt(Res&: C)))) {
1286 Offset = *C;
1287 return true;
1288 }
1289
1290 // Handle the symmetric case. This appears in saturation patterns like
1291 // (x == 16) ? 16 : (x + 1).
1292 if (match(V: Val, P: m_AddLike(L: m_Specific(V: LHS), R: m_APInt(Res&: C)))) {
1293 Offset = -*C;
1294 return true;
1295 }
1296
1297 // If (x | y) < C, then (x < C) && (y < C).
1298 if (match(V: LHS, P: m_c_Or(L: m_Specific(V: Val), R: m_Value())) &&
1299 (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
1300 return true;
1301
1302 // If (x & y) > C, then (x > C) && (y > C).
1303 if (match(V: LHS, P: m_c_And(L: m_Specific(V: Val), R: m_Value())) &&
1304 (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
1305 return true;
1306
1307 return false;
1308}
1309
1310/// Get value range for a "(Val + Offset) Pred RHS" condition.
1311std::optional<ValueLatticeElement>
1312LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,
1313 Value *RHS,
1314 const APInt &Offset,
1315 Instruction *CxtI,
1316 bool UseBlockValue) {
1317 ConstantRange RHSRange(RHS->getType()->getScalarSizeInBits(),
1318 /*isFullSet=*/true);
1319 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: RHS)) {
1320 RHSRange = ConstantRange(CI->getValue());
1321 } else if (UseBlockValue) {
1322 std::optional<ValueLatticeElement> R =
1323 getBlockValue(Val: RHS, BB: CxtI->getParent(), CxtI);
1324 if (!R)
1325 return std::nullopt;
1326 RHSRange = R->asConstantRange(Ty: RHS->getType());
1327 }
1328
1329 ConstantRange TrueValues =
1330 ConstantRange::makeAllowedICmpRegion(Pred, Other: RHSRange);
1331 return ValueLatticeElement::getRange(CR: TrueValues.subtract(CI: Offset));
1332}
1333
1334static std::optional<ConstantRange>
1335getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS,
1336 function_ref<std::optional<ConstantRange>(const APInt &)> Fn) {
1337 bool Invert = false;
1338 if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) {
1339 Pred = ICmpInst::getInversePredicate(pred: Pred);
1340 Invert = true;
1341 }
1342 if (Pred == ICmpInst::ICMP_SLE) {
1343 Pred = ICmpInst::ICMP_SLT;
1344 if (RHS.isMaxSignedValue())
1345 return std::nullopt; // Could also return full/empty here, if we wanted.
1346 ++RHS;
1347 }
1348 assert(Pred == ICmpInst::ICMP_SLT && "Must be signed predicate");
1349 if (auto CR = Fn(RHS))
1350 return Invert ? CR->inverse() : CR;
1351 return std::nullopt;
1352}
1353
1354/// Get value range for a "ctpop(Val) Pred RHS" condition.
1355static ValueLatticeElement getValueFromICmpCtpop(ICmpInst::Predicate Pred,
1356 Value *RHS) {
1357 unsigned BitWidth = RHS->getType()->getScalarSizeInBits();
1358
1359 auto *RHSConst = dyn_cast<ConstantInt>(Val: RHS);
1360 if (!RHSConst)
1361 return ValueLatticeElement::getOverdefined();
1362
1363 ConstantRange ResValRange =
1364 ConstantRange::makeExactICmpRegion(Pred, Other: RHSConst->getValue());
1365
1366 unsigned ResMin = ResValRange.getUnsignedMin().getLimitedValue(Limit: BitWidth);
1367 unsigned ResMax = ResValRange.getUnsignedMax().getLimitedValue(Limit: BitWidth);
1368
1369 APInt ValMin = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: ResMin);
1370 APInt ValMax = APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ResMax);
1371 return ValueLatticeElement::getRange(
1372 CR: ConstantRange::getNonEmpty(Lower: std::move(ValMin), Upper: ValMax + 1));
1373}
1374
1375std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(
1376 Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) {
1377 Value *LHS = ICI->getOperand(i_nocapture: 0);
1378 Value *RHS = ICI->getOperand(i_nocapture: 1);
1379
1380 // Get the predicate that must hold along the considered edge.
1381 CmpInst::Predicate EdgePred =
1382 isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
1383
1384 if (isa<Constant>(Val: RHS)) {
1385 if (ICI->isEquality() && LHS == Val) {
1386 if (EdgePred == ICmpInst::ICMP_EQ)
1387 return ValueLatticeElement::get(C: cast<Constant>(Val: RHS));
1388 else if (!isa<UndefValue>(Val: RHS))
1389 return ValueLatticeElement::getNot(C: cast<Constant>(Val: RHS));
1390 }
1391 }
1392
1393 Type *Ty = Val->getType();
1394 if (!Ty->isIntegerTy())
1395 return ValueLatticeElement::getOverdefined();
1396
1397 unsigned BitWidth = Ty->getScalarSizeInBits();
1398 APInt Offset(BitWidth, 0);
1399 if (matchICmpOperand(Offset, LHS, Val, Pred: EdgePred))
1400 return getValueFromSimpleICmpCondition(Pred: EdgePred, RHS, Offset, CxtI: ICI,
1401 UseBlockValue);
1402
1403 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(pred: EdgePred);
1404 if (matchICmpOperand(Offset, LHS: RHS, Val, Pred: SwappedPred))
1405 return getValueFromSimpleICmpCondition(Pred: SwappedPred, RHS: LHS, Offset, CxtI: ICI,
1406 UseBlockValue);
1407
1408 if (match(V: LHS, P: m_Intrinsic<Intrinsic::ctpop>(Op0: m_Specific(V: Val))))
1409 return getValueFromICmpCtpop(Pred: EdgePred, RHS);
1410
1411 const APInt *Mask, *C;
1412 if (match(V: LHS, P: m_And(L: m_Specific(V: Val), R: m_APInt(Res&: Mask))) &&
1413 match(V: RHS, P: m_APInt(Res&: C))) {
1414 // If (Val & Mask) == C then all the masked bits are known and we can
1415 // compute a value range based on that.
1416 if (EdgePred == ICmpInst::ICMP_EQ) {
1417 KnownBits Known;
1418 Known.Zero = ~*C & *Mask;
1419 Known.One = *C & *Mask;
1420 return ValueLatticeElement::getRange(
1421 CR: ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
1422 }
1423
1424 if (EdgePred == ICmpInst::ICMP_NE)
1425 return ValueLatticeElement::getRange(
1426 CR: ConstantRange::makeMaskNotEqualRange(Mask: *Mask, C: *C));
1427 }
1428
1429 // If (X urem Modulus) >= C, then X >= C.
1430 // If trunc X >= C, then X >= C.
1431 // TODO: An upper bound could be computed as well.
1432 if (match(V: LHS, P: m_CombineOr(L: m_URem(L: m_Specific(V: Val), R: m_Value()),
1433 R: m_Trunc(Op: m_Specific(V: Val)))) &&
1434 match(V: RHS, P: m_APInt(Res&: C))) {
1435 // Use the icmp region so we don't have to deal with different predicates.
1436 ConstantRange CR = ConstantRange::makeExactICmpRegion(Pred: EdgePred, Other: *C);
1437 if (!CR.isEmptySet())
1438 return ValueLatticeElement::getRange(CR: ConstantRange::getNonEmpty(
1439 Lower: CR.getUnsignedMin().zext(width: BitWidth), Upper: APInt(BitWidth, 0)));
1440 }
1441
1442 // Recognize:
1443 // icmp slt (ashr X, ShAmtC), C --> icmp slt X, C << ShAmtC
1444 // Preconditions: (C << ShAmtC) >> ShAmtC == C
1445 const APInt *ShAmtC;
1446 if (CmpInst::isSigned(Pred: EdgePred) &&
1447 match(V: LHS, P: m_AShr(L: m_Specific(V: Val), R: m_APInt(Res&: ShAmtC))) &&
1448 match(V: RHS, P: m_APInt(Res&: C))) {
1449 auto CR = getRangeViaSLT(
1450 Pred: EdgePred, RHS: *C, Fn: [&](const APInt &RHS) -> std::optional<ConstantRange> {
1451 APInt New = RHS << *ShAmtC;
1452 if ((New.ashr(ShiftAmt: *ShAmtC)) != RHS)
1453 return std::nullopt;
1454 return ConstantRange::getNonEmpty(
1455 Lower: APInt::getSignedMinValue(numBits: New.getBitWidth()), Upper: New);
1456 });
1457 if (CR)
1458 return ValueLatticeElement::getRange(CR: *CR);
1459 }
1460
1461 // a - b or ptrtoint(a) - ptrtoint(b) ==/!= 0 if a ==/!= b
1462 Value *X, *Y;
1463 if (ICI->isEquality() && match(V: Val, P: m_Sub(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1464 // Peek through ptrtoints
1465 match(V: X, P: m_PtrToIntSameSize(DL, Op: m_Value(V&: X)));
1466 match(V: Y, P: m_PtrToIntSameSize(DL, Op: m_Value(V&: Y)));
1467 if ((X == LHS && Y == RHS) || (X == RHS && Y == LHS)) {
1468 Constant *NullVal = Constant::getNullValue(Ty: Val->getType());
1469 if (EdgePred == ICmpInst::ICMP_EQ)
1470 return ValueLatticeElement::get(C: NullVal);
1471 return ValueLatticeElement::getNot(C: NullVal);
1472 }
1473 }
1474
1475 return ValueLatticeElement::getOverdefined();
1476}
1477
1478ValueLatticeElement LazyValueInfoImpl::getValueFromTrunc(Value *Val,
1479 TruncInst *Trunc,
1480 bool IsTrueDest) {
1481 assert(Trunc->getType()->isIntOrIntVectorTy(1));
1482
1483 if (Trunc->getOperand(i_nocapture: 0) != Val)
1484 return ValueLatticeElement::getOverdefined();
1485
1486 Type *Ty = Val->getType();
1487
1488 if (Trunc->hasNoUnsignedWrap()) {
1489 if (IsTrueDest)
1490 return ValueLatticeElement::get(C: ConstantInt::get(Ty, V: 1));
1491 return ValueLatticeElement::get(C: Constant::getNullValue(Ty));
1492 }
1493
1494 if (IsTrueDest)
1495 return ValueLatticeElement::getNot(C: Constant::getNullValue(Ty));
1496 return ValueLatticeElement::getNot(C: Constant::getAllOnesValue(Ty));
1497}
1498
1499// Handle conditions of the form
1500// extractvalue(op.with.overflow(%x, C), 1).
1501static ValueLatticeElement getValueFromOverflowCondition(
1502 Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1503 // TODO: This only works with a constant RHS for now. We could also compute
1504 // the range of the RHS, but this doesn't fit into the current structure of
1505 // the edge value calculation.
1506 const APInt *C;
1507 if (WO->getLHS() != Val || !match(V: WO->getRHS(), P: m_APInt(Res&: C)))
1508 return ValueLatticeElement::getOverdefined();
1509
1510 // Calculate the possible values of %x for which no overflow occurs.
1511 ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
1512 BinOp: WO->getBinaryOp(), Other: *C, NoWrapKind: WO->getNoWrapKind());
1513
1514 // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1515 // constrained to it's inverse (all values that might cause overflow).
1516 if (IsTrueDest)
1517 NWR = NWR.inverse();
1518 return ValueLatticeElement::getRange(CR: NWR);
1519}
1520
1521std::optional<ValueLatticeElement>
1522LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond,
1523 bool IsTrueDest, bool UseBlockValue,
1524 unsigned Depth) {
1525 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Val: Cond))
1526 return getValueFromICmpCondition(Val, ICI, isTrueDest: IsTrueDest, UseBlockValue);
1527
1528 if (auto *Trunc = dyn_cast<TruncInst>(Val: Cond))
1529 return getValueFromTrunc(Val, Trunc, IsTrueDest);
1530
1531 if (auto *EVI = dyn_cast<ExtractValueInst>(Val: Cond))
1532 if (auto *WO = dyn_cast<WithOverflowInst>(Val: EVI->getAggregateOperand()))
1533 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1534 return getValueFromOverflowCondition(Val, WO, IsTrueDest);
1535
1536 if (++Depth == MaxAnalysisRecursionDepth)
1537 return ValueLatticeElement::getOverdefined();
1538
1539 Value *N;
1540 if (match(V: Cond, P: m_Not(V: m_Value(V&: N))))
1541 return getValueFromCondition(Val, Cond: N, IsTrueDest: !IsTrueDest, UseBlockValue, Depth);
1542
1543 Value *L, *R;
1544 bool IsAnd;
1545 if (match(V: Cond, P: m_LogicalAnd(L: m_Value(V&: L), R: m_Value(V&: R))))
1546 IsAnd = true;
1547 else if (match(V: Cond, P: m_LogicalOr(L: m_Value(V&: L), R: m_Value(V&: R))))
1548 IsAnd = false;
1549 else
1550 return ValueLatticeElement::getOverdefined();
1551
1552 std::optional<ValueLatticeElement> LV =
1553 getValueFromCondition(Val, Cond: L, IsTrueDest, UseBlockValue, Depth);
1554 if (!LV)
1555 return std::nullopt;
1556 std::optional<ValueLatticeElement> RV =
1557 getValueFromCondition(Val, Cond: R, IsTrueDest, UseBlockValue, Depth);
1558 if (!RV)
1559 return std::nullopt;
1560
1561 // if (L && R) -> intersect L and R
1562 // if (!(L || R)) -> intersect !L and !R
1563 // if (L || R) -> union L and R
1564 // if (!(L && R)) -> union !L and !R
1565 if (IsTrueDest ^ IsAnd) {
1566 LV->mergeIn(RHS: *RV);
1567 return *LV;
1568 }
1569
1570 return LV->intersect(Other: *RV);
1571}
1572
1573// Return true if Usr has Op as an operand, otherwise false.
1574static bool usesOperand(User *Usr, Value *Op) {
1575 return is_contained(Range: Usr->operands(), Element: Op);
1576}
1577
1578// Return true if the instruction type of Val is supported by
1579// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
1580// Call this before calling constantFoldUser() to find out if it's even worth
1581// attempting to call it.
1582static bool isOperationFoldable(User *Usr) {
1583 return isa<CastInst>(Val: Usr) || isa<BinaryOperator>(Val: Usr) || isa<FreezeInst>(Val: Usr);
1584}
1585
1586// Check if Usr can be simplified to an integer constant when the value of one
1587// of its operands Op is an integer constant OpConstVal. If so, return it as an
1588// lattice value range with a single element or otherwise return an overdefined
1589// lattice value.
1590static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1591 const APInt &OpConstVal,
1592 const DataLayout &DL) {
1593 assert(isOperationFoldable(Usr) && "Precondition");
1594 Constant* OpConst = Constant::getIntegerValue(Ty: Op->getType(), V: OpConstVal);
1595 // Check if Usr can be simplified to a constant.
1596 if (auto *CI = dyn_cast<CastInst>(Val: Usr)) {
1597 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1598 if (auto *C = dyn_cast_or_null<ConstantInt>(
1599 Val: simplifyCastInst(CastOpc: CI->getOpcode(), Op: OpConst,
1600 Ty: CI->getDestTy(), Q: DL))) {
1601 return ValueLatticeElement::getRange(CR: ConstantRange(C->getValue()));
1602 }
1603 } else if (auto *BO = dyn_cast<BinaryOperator>(Val: Usr)) {
1604 bool Op0Match = BO->getOperand(i_nocapture: 0) == Op;
1605 bool Op1Match = BO->getOperand(i_nocapture: 1) == Op;
1606 assert((Op0Match || Op1Match) &&
1607 "Operand 0 nor Operand 1 isn't a match");
1608 Value *LHS = Op0Match ? OpConst : BO->getOperand(i_nocapture: 0);
1609 Value *RHS = Op1Match ? OpConst : BO->getOperand(i_nocapture: 1);
1610 if (auto *C = dyn_cast_or_null<ConstantInt>(
1611 Val: simplifyBinOp(Opcode: BO->getOpcode(), LHS, RHS, Q: DL))) {
1612 return ValueLatticeElement::getRange(CR: ConstantRange(C->getValue()));
1613 }
1614 } else if (isa<FreezeInst>(Val: Usr)) {
1615 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
1616 return ValueLatticeElement::getRange(CR: ConstantRange(OpConstVal));
1617 }
1618 return ValueLatticeElement::getOverdefined();
1619}
1620
1621/// Compute the value of Val on the edge BBFrom -> BBTo.
1622std::optional<ValueLatticeElement>
1623LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1624 BasicBlock *BBTo, bool UseBlockValue) {
1625 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1626 // know that v != 0.
1627 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: BBFrom->getTerminator())) {
1628 // If this is a conditional branch and only one successor goes to BBTo, then
1629 // we may be able to infer something from the condition.
1630 if (BI->getSuccessor(i: 0) != BI->getSuccessor(i: 1)) {
1631 bool isTrueDest = BI->getSuccessor(i: 0) == BBTo;
1632 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1633 "BBTo isn't a successor of BBFrom");
1634 Value *Condition = BI->getCondition();
1635
1636 // If V is the condition of the branch itself, then we know exactly what
1637 // it is.
1638 // NB: The condition on a `br` can't be a vector type.
1639 if (Condition == Val)
1640 return ValueLatticeElement::get(C: ConstantInt::get(
1641 Ty: Type::getInt1Ty(C&: Val->getContext()), V: isTrueDest));
1642
1643 // If the condition of the branch is an equality comparison, we may be
1644 // able to infer the value.
1645 std::optional<ValueLatticeElement> Result =
1646 getValueFromCondition(Val, Cond: Condition, IsTrueDest: isTrueDest, UseBlockValue);
1647 if (!Result)
1648 return std::nullopt;
1649
1650 if (!Result->isOverdefined())
1651 return Result;
1652
1653 if (User *Usr = dyn_cast<User>(Val)) {
1654 assert(Result->isOverdefined() && "Result isn't overdefined");
1655 // Check with isOperationFoldable() first to avoid linearly iterating
1656 // over the operands unnecessarily which can be expensive for
1657 // instructions with many operands.
1658 if (isa<IntegerType>(Val: Usr->getType()) && isOperationFoldable(Usr)) {
1659 const DataLayout &DL = BBTo->getDataLayout();
1660 if (usesOperand(Usr, Op: Condition)) {
1661 // If Val has Condition as an operand and Val can be folded into a
1662 // constant with either Condition == true or Condition == false,
1663 // propagate the constant.
1664 // eg.
1665 // ; %Val is true on the edge to %then.
1666 // %Val = and i1 %Condition, true.
1667 // br %Condition, label %then, label %else
1668 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1669 Result = constantFoldUser(Usr, Op: Condition, OpConstVal: ConditionVal, DL);
1670 } else if (isa<TruncInst, ZExtInst, SExtInst>(Val: Usr)) {
1671 ValueLatticeElement OpLatticeVal =
1672 *getValueFromCondition(Val: Usr->getOperand(i: 0), Cond: Condition,
1673 IsTrueDest: isTrueDest, /*UseBlockValue*/ false);
1674
1675 if (OpLatticeVal.isConstantRange()) {
1676 const unsigned ResultBitWidth =
1677 Usr->getType()->getScalarSizeInBits();
1678 if (auto *Trunc = dyn_cast<TruncInst>(Val: Usr))
1679 return ValueLatticeElement::getRange(
1680 CR: OpLatticeVal.getConstantRange().truncate(
1681 BitWidth: ResultBitWidth, NoWrapKind: Trunc->getNoWrapKind()));
1682
1683 return ValueLatticeElement::getRange(
1684 CR: OpLatticeVal.getConstantRange().castOp(
1685 CastOp: cast<CastInst>(Val: Usr)->getOpcode(), BitWidth: ResultBitWidth));
1686 }
1687 if (OpLatticeVal.isConstant()) {
1688 Constant *C = OpLatticeVal.getConstant();
1689 if (auto *CastC = ConstantFoldCastOperand(
1690 Opcode: cast<CastInst>(Val: Usr)->getOpcode(), C, DestTy: Usr->getType(), DL))
1691 return ValueLatticeElement::get(C: CastC);
1692 }
1693 return ValueLatticeElement::getOverdefined();
1694 } else {
1695 // If one of Val's operand has an inferred value, we may be able to
1696 // infer the value of Val.
1697 // eg.
1698 // ; %Val is 94 on the edge to %then.
1699 // %Val = add i8 %Op, 1
1700 // %Condition = icmp eq i8 %Op, 93
1701 // br i1 %Condition, label %then, label %else
1702 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1703 Value *Op = Usr->getOperand(i);
1704 ValueLatticeElement OpLatticeVal = *getValueFromCondition(
1705 Val: Op, Cond: Condition, IsTrueDest: isTrueDest, /*UseBlockValue*/ false);
1706 if (std::optional<APInt> OpConst =
1707 OpLatticeVal.asConstantInteger()) {
1708 Result = constantFoldUser(Usr, Op, OpConstVal: *OpConst, DL);
1709 break;
1710 }
1711 }
1712 }
1713 }
1714 }
1715 if (!Result->isOverdefined())
1716 return Result;
1717 }
1718 }
1719
1720 // If the edge was formed by a switch on the value, then we may know exactly
1721 // what it is.
1722 if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: BBFrom->getTerminator())) {
1723 Value *Condition = SI->getCondition();
1724 if (!isa<IntegerType>(Val: Val->getType()))
1725 return ValueLatticeElement::getOverdefined();
1726 bool ValUsesConditionAndMayBeFoldable = false;
1727 if (Condition != Val) {
1728 // Check if Val has Condition as an operand.
1729 if (User *Usr = dyn_cast<User>(Val))
1730 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1731 usesOperand(Usr, Op: Condition);
1732 if (!ValUsesConditionAndMayBeFoldable)
1733 return ValueLatticeElement::getOverdefined();
1734 }
1735 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1736 "Condition != Val nor Val doesn't use Condition");
1737
1738 bool DefaultCase = SI->getDefaultDest() == BBTo;
1739 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1740 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1741
1742 for (auto Case : SI->cases()) {
1743 APInt CaseValue = Case.getCaseValue()->getValue();
1744 ConstantRange EdgeVal(CaseValue);
1745 if (ValUsesConditionAndMayBeFoldable) {
1746 User *Usr = cast<User>(Val);
1747 const DataLayout &DL = BBTo->getDataLayout();
1748 ValueLatticeElement EdgeLatticeVal =
1749 constantFoldUser(Usr, Op: Condition, OpConstVal: CaseValue, DL);
1750 if (EdgeLatticeVal.isOverdefined())
1751 return ValueLatticeElement::getOverdefined();
1752 EdgeVal = EdgeLatticeVal.getConstantRange();
1753 }
1754 if (DefaultCase) {
1755 // It is possible that the default destination is the destination of
1756 // some cases. We cannot perform difference for those cases.
1757 // We know Condition != CaseValue in BBTo. In some cases we can use
1758 // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1759 // only do this when f is identity (i.e. Val == Condition), but we
1760 // should be able to do this for any injective f.
1761 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1762 EdgesVals = EdgesVals.difference(CR: EdgeVal);
1763 } else if (Case.getCaseSuccessor() == BBTo)
1764 EdgesVals = EdgesVals.unionWith(CR: EdgeVal);
1765 }
1766 return ValueLatticeElement::getRange(CR: std::move(EdgesVals));
1767 }
1768 return ValueLatticeElement::getOverdefined();
1769}
1770
1771/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1772/// the basic block if the edge does not constrain Val.
1773std::optional<ValueLatticeElement>
1774LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1775 BasicBlock *BBTo, Instruction *CxtI) {
1776 // If already a constant, there is nothing to compute.
1777 if (Constant *VC = dyn_cast<Constant>(Val))
1778 return ValueLatticeElement::get(C: VC);
1779
1780 std::optional<ValueLatticeElement> LocalResult =
1781 getEdgeValueLocal(Val, BBFrom, BBTo, /*UseBlockValue*/ true);
1782 if (!LocalResult)
1783 return std::nullopt;
1784
1785 if (hasSingleValue(Val: *LocalResult))
1786 // Can't get any more precise here
1787 return LocalResult;
1788
1789 std::optional<ValueLatticeElement> OptInBlock =
1790 getBlockValue(Val, BB: BBFrom, CxtI: BBFrom->getTerminator());
1791 if (!OptInBlock)
1792 return std::nullopt;
1793 ValueLatticeElement &InBlock = *OptInBlock;
1794
1795 // We can use the context instruction (generically the ultimate instruction
1796 // the calling pass is trying to simplify) here, even though the result of
1797 // this function is generally cached when called from the solve* functions
1798 // (and that cached result might be used with queries using a different
1799 // context instruction), because when this function is called from the solve*
1800 // functions, the context instruction is not provided. When called from
1801 // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1802 // but then the result is not cached.
1803 intersectAssumeOrGuardBlockValueConstantRange(Val, BBLV&: InBlock, BBI: CxtI);
1804
1805 return LocalResult->intersect(Other: InBlock);
1806}
1807
1808ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1809 Instruction *CxtI) {
1810 LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1811 << BB->getName() << "'\n");
1812
1813 assert(BlockValueStack.empty() && BlockValueSet.empty());
1814 std::optional<ValueLatticeElement> OptResult = getBlockValue(Val: V, BB, CxtI);
1815 if (!OptResult) {
1816 solve();
1817 OptResult = getBlockValue(Val: V, BB, CxtI);
1818 assert(OptResult && "Value not available after solving");
1819 }
1820
1821 LLVM_DEBUG(dbgs() << " Result = " << *OptResult << "\n");
1822 return *OptResult;
1823}
1824
1825ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1826 LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1827 << "'\n");
1828
1829 if (auto *C = dyn_cast<Constant>(Val: V))
1830 return ValueLatticeElement::get(C);
1831
1832 ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1833 if (auto *I = dyn_cast<Instruction>(Val: V))
1834 Result = getFromRangeMetadata(BBI: I);
1835 intersectAssumeOrGuardBlockValueConstantRange(Val: V, BBLV&: Result, BBI: CxtI);
1836
1837 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1838 return Result;
1839}
1840
1841ValueLatticeElement LazyValueInfoImpl::
1842getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1843 Instruction *CxtI) {
1844 LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1845 << FromBB->getName() << "' to '" << ToBB->getName()
1846 << "'\n");
1847
1848 std::optional<ValueLatticeElement> Result =
1849 getEdgeValue(Val: V, BBFrom: FromBB, BBTo: ToBB, CxtI);
1850 while (!Result) {
1851 // As the worklist only explicitly tracks block values (but not edge values)
1852 // we may have to call solve() multiple times, as the edge value calculation
1853 // may request additional block values.
1854 solve();
1855 Result = getEdgeValue(Val: V, BBFrom: FromBB, BBTo: ToBB, CxtI);
1856 }
1857
1858 LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");
1859 return *Result;
1860}
1861
1862ValueLatticeElement LazyValueInfoImpl::getValueAtUse(const Use &U) {
1863 Value *V = U.get();
1864 auto *CxtI = cast<Instruction>(Val: U.getUser());
1865 ValueLatticeElement VL = getValueInBlock(V, BB: CxtI->getParent(), CxtI);
1866
1867 // Check whether the only (possibly transitive) use of the value is in a
1868 // position where V can be constrained by a select or branch condition.
1869 const Use *CurrU = &U;
1870 // TODO: Increase limit?
1871 const unsigned MaxUsesToInspect = 3;
1872 for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
1873 std::optional<ValueLatticeElement> CondVal;
1874 auto *CurrI = cast<Instruction>(Val: CurrU->getUser());
1875 if (auto *SI = dyn_cast<SelectInst>(Val: CurrI)) {
1876 // If the value is undef, a different value may be chosen in
1877 // the select condition and at use.
1878 if (!isGuaranteedNotToBeUndef(V: SI->getCondition(), AC))
1879 break;
1880 if (CurrU->getOperandNo() == 1)
1881 CondVal =
1882 *getValueFromCondition(Val: V, Cond: SI->getCondition(), /*IsTrueDest*/ true,
1883 /*UseBlockValue*/ false);
1884 else if (CurrU->getOperandNo() == 2)
1885 CondVal =
1886 *getValueFromCondition(Val: V, Cond: SI->getCondition(), /*IsTrueDest*/ false,
1887 /*UseBlockValue*/ false);
1888 } else if (auto *PHI = dyn_cast<PHINode>(Val: CurrI)) {
1889 // TODO: Use non-local query?
1890 CondVal = *getEdgeValueLocal(Val: V, BBFrom: PHI->getIncomingBlock(U: *CurrU),
1891 BBTo: PHI->getParent(), /*UseBlockValue*/ false);
1892 }
1893 if (CondVal)
1894 VL = VL.intersect(Other: *CondVal);
1895
1896 // Only follow one-use chain, to allow direct intersection of conditions.
1897 // If there are multiple uses, we would have to intersect with the union of
1898 // all conditions at different uses.
1899 // Stop walking if we hit a non-speculatable instruction. Even if the
1900 // result is only used under a specific condition, executing the
1901 // instruction itself may cause side effects or UB already.
1902 // This also disallows looking through phi nodes: If the phi node is part
1903 // of a cycle, we might end up reasoning about values from different cycle
1904 // iterations (PR60629).
1905 if (!CurrI->hasOneUse() ||
1906 !isSafeToSpeculativelyExecuteWithVariableReplaced(
1907 I: CurrI, /*IgnoreUBImplyingAttrs=*/false))
1908 break;
1909 CurrU = &*CurrI->use_begin();
1910 }
1911 return VL;
1912}
1913
1914void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1915 BasicBlock *NewSucc) {
1916 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1917}
1918
1919//===----------------------------------------------------------------------===//
1920// LazyValueInfo Impl
1921//===----------------------------------------------------------------------===//
1922
1923bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1924 Info.F = &F;
1925 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1926
1927 if (auto *Impl = Info.getImpl())
1928 Impl->clear();
1929
1930 // Fully lazy.
1931 return false;
1932}
1933
1934void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1935 AU.setPreservesAll();
1936 AU.addRequired<AssumptionCacheTracker>();
1937 AU.addRequired<TargetLibraryInfoWrapperPass>();
1938}
1939
1940LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1941
1942/// This lazily constructs the LazyValueInfoImpl.
1943LazyValueInfoImpl &LazyValueInfo::getOrCreateImpl() {
1944 if (!PImpl) {
1945 const DataLayout &DL = F->getDataLayout();
1946 Function *GuardDecl = Intrinsic::getDeclarationIfExists(
1947 M: F->getParent(), id: Intrinsic::experimental_guard);
1948 PImpl = new LazyValueInfoImpl(F, AC, DL, GuardDecl);
1949 }
1950 return *PImpl;
1951}
1952
1953LazyValueInfoImpl *LazyValueInfo::getImpl() { return PImpl; }
1954
1955LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1956
1957void LazyValueInfo::releaseMemory() {
1958 // If the cache was allocated, free it.
1959 if (auto *Impl = getImpl()) {
1960 delete &*Impl;
1961 PImpl = nullptr;
1962 }
1963}
1964
1965bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1966 FunctionAnalysisManager::Invalidator &Inv) {
1967 // We need to invalidate if we have either failed to preserve this analyses
1968 // result directly or if any of its dependencies have been invalidated.
1969 auto PAC = PA.getChecker<LazyValueAnalysis>();
1970 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
1971 return true;
1972
1973 return false;
1974}
1975
1976void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1977
1978LazyValueInfo LazyValueAnalysis::run(Function &F,
1979 FunctionAnalysisManager &FAM) {
1980 auto &AC = FAM.getResult<AssumptionAnalysis>(IR&: F);
1981
1982 return LazyValueInfo(&F, &AC);
1983}
1984
1985/// Returns true if we can statically tell that this value will never be a
1986/// "useful" constant. In practice, this means we've got something like an
1987/// alloca or a malloc call for which a comparison against a constant can
1988/// only be guarding dead code. Note that we are potentially giving up some
1989/// precision in dead code (a constant result) in favour of avoiding a
1990/// expensive search for a easily answered common query.
1991static bool isKnownNonConstant(Value *V) {
1992 V = V->stripPointerCasts();
1993 // The return val of alloc cannot be a Constant.
1994 if (isa<AllocaInst>(Val: V))
1995 return true;
1996 return false;
1997}
1998
1999Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) {
2000 // Bail out early if V is known not to be a Constant.
2001 if (isKnownNonConstant(V))
2002 return nullptr;
2003
2004 BasicBlock *BB = CxtI->getParent();
2005 ValueLatticeElement Result = getOrCreateImpl().getValueInBlock(V, BB, CxtI);
2006
2007 if (Result.isConstant())
2008 return Result.getConstant();
2009 if (Result.isConstantRange()) {
2010 const ConstantRange &CR = Result.getConstantRange();
2011 if (const APInt *SingleVal = CR.getSingleElement())
2012 return ConstantInt::get(Ty: V->getType(), V: *SingleVal);
2013 }
2014 return nullptr;
2015}
2016
2017ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI,
2018 bool UndefAllowed) {
2019 BasicBlock *BB = CxtI->getParent();
2020 ValueLatticeElement Result = getOrCreateImpl().getValueInBlock(V, BB, CxtI);
2021 return Result.asConstantRange(Ty: V->getType(), UndefAllowed);
2022}
2023
2024ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U,
2025 bool UndefAllowed) {
2026 ValueLatticeElement Result = getOrCreateImpl().getValueAtUse(U);
2027 return Result.asConstantRange(Ty: U->getType(), UndefAllowed);
2028}
2029
2030/// Determine whether the specified value is known to be a
2031/// constant on the specified edge. Return null if not.
2032Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
2033 BasicBlock *ToBB,
2034 Instruction *CxtI) {
2035 ValueLatticeElement Result =
2036 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CxtI);
2037
2038 if (Result.isConstant())
2039 return Result.getConstant();
2040 if (Result.isConstantRange()) {
2041 const ConstantRange &CR = Result.getConstantRange();
2042 if (const APInt *SingleVal = CR.getSingleElement())
2043 return ConstantInt::get(Ty: V->getType(), V: *SingleVal);
2044 }
2045 return nullptr;
2046}
2047
2048ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
2049 BasicBlock *FromBB,
2050 BasicBlock *ToBB,
2051 Instruction *CxtI) {
2052 ValueLatticeElement Result =
2053 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CxtI);
2054 // TODO: Should undef be allowed here?
2055 return Result.asConstantRange(Ty: V->getType(), /*UndefAllowed*/ true);
2056}
2057
2058static Constant *getPredicateResult(CmpInst::Predicate Pred, Constant *C,
2059 const ValueLatticeElement &Val,
2060 const DataLayout &DL) {
2061 // If we know the value is a constant, evaluate the conditional.
2062 if (Val.isConstant())
2063 return ConstantFoldCompareInstOperands(Predicate: Pred, LHS: Val.getConstant(), RHS: C, DL);
2064
2065 Type *ResTy = CmpInst::makeCmpResultType(opnd_type: C->getType());
2066 if (Val.isConstantRange()) {
2067 const ConstantRange &CR = Val.getConstantRange();
2068 ConstantRange RHS = C->toConstantRange();
2069 if (CR.icmp(Pred, Other: RHS))
2070 return ConstantInt::getTrue(Ty: ResTy);
2071 if (CR.icmp(Pred: CmpInst::getInversePredicate(pred: Pred), Other: RHS))
2072 return ConstantInt::getFalse(Ty: ResTy);
2073 return nullptr;
2074 }
2075
2076 if (Val.isNotConstant()) {
2077 // If this is an equality comparison, we can try to fold it knowing that
2078 // "V != C1".
2079 if (Pred == ICmpInst::ICMP_EQ) {
2080 // !C1 == C -> false iff C1 == C.
2081 Constant *Res = ConstantFoldCompareInstOperands(
2082 Predicate: ICmpInst::ICMP_NE, LHS: Val.getNotConstant(), RHS: C, DL);
2083 if (Res && Res->isNullValue())
2084 return ConstantInt::getFalse(Ty: ResTy);
2085 } else if (Pred == ICmpInst::ICMP_NE) {
2086 // !C1 != C -> true iff C1 == C.
2087 Constant *Res = ConstantFoldCompareInstOperands(
2088 Predicate: ICmpInst::ICMP_NE, LHS: Val.getNotConstant(), RHS: C, DL);
2089 if (Res && Res->isNullValue())
2090 return ConstantInt::getTrue(Ty: ResTy);
2091 }
2092 return nullptr;
2093 }
2094
2095 return nullptr;
2096}
2097
2098/// Determine whether the specified value comparison with a constant is known to
2099/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
2100Constant *LazyValueInfo::getPredicateOnEdge(CmpInst::Predicate Pred, Value *V,
2101 Constant *C, BasicBlock *FromBB,
2102 BasicBlock *ToBB,
2103 Instruction *CxtI) {
2104 ValueLatticeElement Result =
2105 getOrCreateImpl().getValueOnEdge(V, FromBB, ToBB, CxtI);
2106
2107 return getPredicateResult(Pred, C, Val: Result, DL: FromBB->getDataLayout());
2108}
2109
2110Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred, Value *V,
2111 Constant *C, Instruction *CxtI,
2112 bool UseBlockValue) {
2113 // Is or is not NonNull are common predicates being queried. If
2114 // isKnownNonZero can tell us the result of the predicate, we can
2115 // return it quickly. But this is only a fastpath, and falling
2116 // through would still be correct.
2117 const DataLayout &DL = CxtI->getDataLayout();
2118 if (V->getType()->isPointerTy() && C->isNullValue() &&
2119 isKnownNonZero(V: V->stripPointerCastsSameRepresentation(), Q: DL)) {
2120 Type *ResTy = CmpInst::makeCmpResultType(opnd_type: C->getType());
2121 if (Pred == ICmpInst::ICMP_EQ)
2122 return ConstantInt::getFalse(Ty: ResTy);
2123 else if (Pred == ICmpInst::ICMP_NE)
2124 return ConstantInt::getTrue(Ty: ResTy);
2125 }
2126
2127 auto &Impl = getOrCreateImpl();
2128 ValueLatticeElement Result =
2129 UseBlockValue ? Impl.getValueInBlock(V, BB: CxtI->getParent(), CxtI)
2130 : Impl.getValueAt(V, CxtI);
2131 Constant *Ret = getPredicateResult(Pred, C, Val: Result, DL);
2132 if (Ret)
2133 return Ret;
2134
2135 // Note: The following bit of code is somewhat distinct from the rest of LVI;
2136 // LVI as a whole tries to compute a lattice value which is conservatively
2137 // correct at a given location. In this case, we have a predicate which we
2138 // weren't able to prove about the merged result, and we're pushing that
2139 // predicate back along each incoming edge to see if we can prove it
2140 // separately for each input. As a motivating example, consider:
2141 // bb1:
2142 // %v1 = ... ; constantrange<1, 5>
2143 // br label %merge
2144 // bb2:
2145 // %v2 = ... ; constantrange<10, 20>
2146 // br label %merge
2147 // merge:
2148 // %phi = phi [%v1, %v2] ; constantrange<1,20>
2149 // %pred = icmp eq i32 %phi, 8
2150 // We can't tell from the lattice value for '%phi' that '%pred' is false
2151 // along each path, but by checking the predicate over each input separately,
2152 // we can.
2153 // We limit the search to one step backwards from the current BB and value.
2154 // We could consider extending this to search further backwards through the
2155 // CFG and/or value graph, but there are non-obvious compile time vs quality
2156 // tradeoffs.
2157 BasicBlock *BB = CxtI->getParent();
2158
2159 // Function entry or an unreachable block. Bail to avoid confusing
2160 // analysis below.
2161 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
2162 if (PI == PE)
2163 return nullptr;
2164
2165 // If V is a PHI node in the same block as the context, we need to ask
2166 // questions about the predicate as applied to the incoming value along
2167 // each edge. This is useful for eliminating cases where the predicate is
2168 // known along all incoming edges.
2169 if (auto *PHI = dyn_cast<PHINode>(Val: V))
2170 if (PHI->getParent() == BB) {
2171 Constant *Baseline = nullptr;
2172 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
2173 Value *Incoming = PHI->getIncomingValue(i);
2174 BasicBlock *PredBB = PHI->getIncomingBlock(i);
2175 // Note that PredBB may be BB itself.
2176 Constant *Result =
2177 getPredicateOnEdge(Pred, V: Incoming, C, FromBB: PredBB, ToBB: BB, CxtI);
2178
2179 // Keep going as long as we've seen a consistent known result for
2180 // all inputs.
2181 Baseline = (i == 0) ? Result /* First iteration */
2182 : (Baseline == Result ? Baseline
2183 : nullptr); /* All others */
2184 if (!Baseline)
2185 break;
2186 }
2187 if (Baseline)
2188 return Baseline;
2189 }
2190
2191 // For a comparison where the V is outside this block, it's possible
2192 // that we've branched on it before. Look to see if the value is known
2193 // on all incoming edges.
2194 if (!isa<Instruction>(Val: V) || cast<Instruction>(Val: V)->getParent() != BB) {
2195 // For predecessor edge, determine if the comparison is true or false
2196 // on that edge. If they're all true or all false, we can conclude
2197 // the value of the comparison in this block.
2198 Constant *Baseline = getPredicateOnEdge(Pred, V, C, FromBB: *PI, ToBB: BB, CxtI);
2199 if (Baseline) {
2200 // Check that all remaining incoming values match the first one.
2201 while (++PI != PE) {
2202 Constant *Ret = getPredicateOnEdge(Pred, V, C, FromBB: *PI, ToBB: BB, CxtI);
2203 if (Ret != Baseline)
2204 break;
2205 }
2206 // If we terminated early, then one of the values didn't match.
2207 if (PI == PE) {
2208 return Baseline;
2209 }
2210 }
2211 }
2212
2213 return nullptr;
2214}
2215
2216Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred, Value *LHS,
2217 Value *RHS, Instruction *CxtI,
2218 bool UseBlockValue) {
2219 if (auto *C = dyn_cast<Constant>(Val: RHS))
2220 return getPredicateAt(Pred, V: LHS, C, CxtI, UseBlockValue);
2221 if (auto *C = dyn_cast<Constant>(Val: LHS))
2222 return getPredicateAt(Pred: CmpInst::getSwappedPredicate(pred: Pred), V: RHS, C, CxtI,
2223 UseBlockValue);
2224
2225 // Got two non-Constant values. Try to determine the comparison results based
2226 // on the block values of the two operands, e.g. because they have
2227 // non-overlapping ranges.
2228 if (UseBlockValue) {
2229 ValueLatticeElement L =
2230 getOrCreateImpl().getValueInBlock(V: LHS, BB: CxtI->getParent(), CxtI);
2231 if (L.isOverdefined())
2232 return nullptr;
2233
2234 ValueLatticeElement R =
2235 getOrCreateImpl().getValueInBlock(V: RHS, BB: CxtI->getParent(), CxtI);
2236 Type *Ty = CmpInst::makeCmpResultType(opnd_type: LHS->getType());
2237 return L.getCompare(Pred, Ty, Other: R, DL: CxtI->getDataLayout());
2238 }
2239 return nullptr;
2240}
2241
2242void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
2243 BasicBlock *NewSucc) {
2244 if (auto *Impl = getImpl())
2245 Impl->threadEdge(PredBB, OldSucc, NewSucc);
2246}
2247
2248void LazyValueInfo::forgetValue(Value *V) {
2249 if (auto *Impl = getImpl())
2250 Impl->forgetValue(V);
2251}
2252
2253void LazyValueInfo::eraseBlock(BasicBlock *BB) {
2254 if (auto *Impl = getImpl())
2255 Impl->eraseBlock(BB);
2256}
2257
2258void LazyValueInfo::clear() {
2259 if (auto *Impl = getImpl())
2260 Impl->clear();
2261}
2262
2263void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
2264 if (auto *Impl = getImpl())
2265 Impl->printLVI(F, DTree, OS);
2266}
2267
2268// Print the LVI for the function arguments at the start of each basic block.
2269void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
2270 const BasicBlock *BB, formatted_raw_ostream &OS) {
2271 // Find if there are latticevalues defined for arguments of the function.
2272 auto *F = BB->getParent();
2273 for (const auto &Arg : F->args()) {
2274 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2275 V: const_cast<Argument *>(&Arg), BB: const_cast<BasicBlock *>(BB));
2276 if (Result.isUnknown())
2277 continue;
2278 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
2279 }
2280}
2281
2282// This function prints the LVI analysis for the instruction I at the beginning
2283// of various basic blocks. It relies on calculated values that are stored in
2284// the LazyValueInfoCache, and in the absence of cached values, recalculate the
2285// LazyValueInfo for `I`, and print that info.
2286void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2287 const Instruction *I, formatted_raw_ostream &OS) {
2288
2289 auto *ParentBB = I->getParent();
2290 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
2291 // We can generate (solve) LVI values only for blocks that are dominated by
2292 // the I's parent. However, to avoid generating LVI for all dominating blocks,
2293 // that contain redundant/uninteresting information, we print LVI for
2294 // blocks that may use this LVI information (such as immediate successor
2295 // blocks, and blocks that contain uses of `I`).
2296 auto printResult = [&](const BasicBlock *BB) {
2297 if (!BlocksContainingLVI.insert(Ptr: BB).second)
2298 return;
2299 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2300 V: const_cast<Instruction *>(I), BB: const_cast<BasicBlock *>(BB));
2301 OS << "; LatticeVal for: '" << *I << "' in BB: '";
2302 BB->printAsOperand(O&: OS, PrintType: false);
2303 OS << "' is: " << Result << "\n";
2304 };
2305
2306 printResult(ParentBB);
2307 // Print the LVI analysis results for the immediate successor blocks, that
2308 // are dominated by `ParentBB`.
2309 for (const auto *BBSucc : successors(BB: ParentBB))
2310 if (DT.dominates(A: ParentBB, B: BBSucc))
2311 printResult(BBSucc);
2312
2313 // Print LVI in blocks where `I` is used.
2314 for (const auto *U : I->users())
2315 if (auto *UseI = dyn_cast<Instruction>(Val: U))
2316 if (!isa<PHINode>(Val: UseI) || DT.dominates(A: ParentBB, B: UseI->getParent()))
2317 printResult(UseI->getParent());
2318
2319}
2320
2321PreservedAnalyses LazyValueInfoPrinterPass::run(Function &F,
2322 FunctionAnalysisManager &AM) {
2323 OS << "LVI for function '" << F.getName() << "':\n";
2324 auto &LVI = AM.getResult<LazyValueAnalysis>(IR&: F);
2325 auto &DTree = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2326 LVI.printLVI(F, DTree, OS);
2327 return PreservedAnalyses::all();
2328}
2329