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