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