Bug Summary

File:build/source/llvm/include/llvm/ADT/APInt.h
Warning:line 162, column 34
Assigned value is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name LazyValueInfo.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-16/lib/clang/16 -I lib/Analysis -I /build/source/llvm/lib/Analysis -I include -I /build/source/llvm/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1670584389 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-12-09-134624-15957-1 -x c++ /build/source/llvm/lib/Analysis/LazyValueInfo.cpp

/build/source/llvm/lib/Analysis/LazyValueInfo.cpp

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

/build/source/llvm/include/llvm/Analysis/ValueLattice.h

1//===- ValueLattice.h - 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#ifndef LLVM_ANALYSIS_VALUELATTICE_H
10#define LLVM_ANALYSIS_VALUELATTICE_H
11
12#include "llvm/IR/Constants.h"
13#include "llvm/IR/ConstantRange.h"
14#include "llvm/IR/Instructions.h"
15
16//===----------------------------------------------------------------------===//
17// ValueLatticeElement
18//===----------------------------------------------------------------------===//
19
20namespace llvm {
21
22class Constant;
23
24/// This class represents lattice values for constants.
25///
26/// FIXME: This is basically just for bringup, this can be made a lot more rich
27/// in the future.
28///
29class ValueLatticeElement {
30 enum ValueLatticeElementTy {
31 /// This Value has no known value yet. As a result, this implies the
32 /// producing instruction is dead. Caution: We use this as the starting
33 /// state in our local meet rules. In this usage, it's taken to mean
34 /// "nothing known yet".
35 /// Transition to any other state allowed.
36 unknown,
37
38 /// This Value is an UndefValue constant or produces undef. Undefined values
39 /// can be merged with constants (or single element constant ranges),
40 /// assuming all uses of the result will be replaced.
41 /// Transition allowed to the following states:
42 /// constant
43 /// constantrange_including_undef
44 /// overdefined
45 undef,
46
47 /// This Value has a specific constant value. The constant cannot be undef.
48 /// (For constant integers, constantrange is used instead. Integer typed
49 /// constantexprs can appear as constant.) Note that the constant state
50 /// can be reached by merging undef & constant states.
51 /// Transition allowed to the following states:
52 /// overdefined
53 constant,
54
55 /// This Value is known to not have the specified value. (For constant
56 /// integers, constantrange is used instead. As above, integer typed
57 /// constantexprs can appear here.)
58 /// Transition allowed to the following states:
59 /// overdefined
60 notconstant,
61
62 /// The Value falls within this range. (Used only for integer typed values.)
63 /// Transition allowed to the following states:
64 /// constantrange (new range must be a superset of the existing range)
65 /// constantrange_including_undef
66 /// overdefined
67 constantrange,
68
69 /// This Value falls within this range, but also may be undef.
70 /// Merging it with other constant ranges results in
71 /// constantrange_including_undef.
72 /// Transition allowed to the following states:
73 /// overdefined
74 constantrange_including_undef,
75
76 /// We can not precisely model the dynamic values this value might take.
77 /// No transitions are allowed after reaching overdefined.
78 overdefined,
79 };
80
81 ValueLatticeElementTy Tag : 8;
82 /// Number of times a constant range has been extended with widening enabled.
83 unsigned NumRangeExtensions : 8;
84
85 /// The union either stores a pointer to a constant or a constant range,
86 /// associated to the lattice element. We have to ensure that Range is
87 /// initialized or destroyed when changing state to or from constantrange.
88 union {
89 Constant *ConstVal;
90 ConstantRange Range;
91 };
92
93 /// Destroy contents of lattice value, without destructing the object.
94 void destroy() {
95 switch (Tag) {
96 case overdefined:
97 case unknown:
98 case undef:
99 case constant:
100 case notconstant:
101 break;
102 case constantrange_including_undef:
103 case constantrange:
104 Range.~ConstantRange();
105 break;
106 };
107 }
108
109public:
110 /// Struct to control some aspects related to merging constant ranges.
111 struct MergeOptions {
112 /// The merge value may include undef.
113 bool MayIncludeUndef;
114
115 /// Handle repeatedly extending a range by going to overdefined after a
116 /// number of steps.
117 bool CheckWiden;
118
119 /// The number of allowed widening steps (including setting the range
120 /// initially).
121 unsigned MaxWidenSteps;
122
123 MergeOptions() : MergeOptions(false, false) {}
124
125 MergeOptions(bool MayIncludeUndef, bool CheckWiden,
126 unsigned MaxWidenSteps = 1)
127 : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden),
128 MaxWidenSteps(MaxWidenSteps) {}
129
130 MergeOptions &setMayIncludeUndef(bool V = true) {
131 MayIncludeUndef = V;
132 return *this;
133 }
134
135 MergeOptions &setCheckWiden(bool V = true) {
136 CheckWiden = V;
137 return *this;
138 }
139
140 MergeOptions &setMaxWidenSteps(unsigned Steps = 1) {
141 CheckWiden = true;
142 MaxWidenSteps = Steps;
143 return *this;
144 }
145 };
146
147 // ConstVal and Range are initialized on-demand.
148 ValueLatticeElement() : Tag(unknown), NumRangeExtensions(0) {}
149
150 ~ValueLatticeElement() { destroy(); }
151
152 ValueLatticeElement(const ValueLatticeElement &Other)
153 : Tag(Other.Tag), NumRangeExtensions(0) {
154 switch (Other.Tag) {
155 case constantrange:
156 case constantrange_including_undef:
157 new (&Range) ConstantRange(Other.Range);
158 NumRangeExtensions = Other.NumRangeExtensions;
159 break;
160 case constant:
161 case notconstant:
162 ConstVal = Other.ConstVal;
163 break;
164 case overdefined:
165 case unknown:
166 case undef:
167 break;
168 }
169 }
170
171 ValueLatticeElement(ValueLatticeElement &&Other)
172 : Tag(Other.Tag), NumRangeExtensions(0) {
173 switch (Other.Tag) {
11
Control jumps to 'case constantrange_including_undef:' at line 175
174 case constantrange:
175 case constantrange_including_undef:
176 new (&Range) ConstantRange(std::move(Other.Range));
12
Calling implicit move constructor for 'ConstantRange'
13
Calling move constructor for 'APInt'
177 NumRangeExtensions = Other.NumRangeExtensions;
178 break;
179 case constant:
180 case notconstant:
181 ConstVal = Other.ConstVal;
182 break;
183 case overdefined:
184 case unknown:
185 case undef:
186 break;
187 }
188 Other.Tag = unknown;
189 }
190
191 ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
192 destroy();
193 new (this) ValueLatticeElement(Other);
194 return *this;
195 }
196
197 ValueLatticeElement &operator=(ValueLatticeElement &&Other) {
198 destroy();
199 new (this) ValueLatticeElement(std::move(Other));
200 return *this;
201 }
202
203 static ValueLatticeElement get(Constant *C) {
204 ValueLatticeElement Res;
205 if (isa<UndefValue>(C))
206 Res.markUndef();
207 else
208 Res.markConstant(C);
209 return Res;
210 }
211 static ValueLatticeElement getNot(Constant *C) {
212 ValueLatticeElement Res;
213 assert(!isa<UndefValue>(C) && "!= undef is not supported")(static_cast <bool> (!isa<UndefValue>(C) &&
"!= undef is not supported") ? void (0) : __assert_fail ("!isa<UndefValue>(C) && \"!= undef is not supported\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 213, __extension__
__PRETTY_FUNCTION__))
;
214 Res.markNotConstant(C);
215 return Res;
216 }
217 static ValueLatticeElement getRange(ConstantRange CR,
218 bool MayIncludeUndef = false) {
219 if (CR.isFullSet())
220 return getOverdefined();
221
222 if (CR.isEmptySet()) {
223 ValueLatticeElement Res;
224 if (MayIncludeUndef)
225 Res.markUndef();
226 return Res;
227 }
228
229 ValueLatticeElement Res;
230 Res.markConstantRange(std::move(CR),
231 MergeOptions().setMayIncludeUndef(MayIncludeUndef));
232 return Res;
233 }
234 static ValueLatticeElement getOverdefined() {
235 ValueLatticeElement Res;
236 Res.markOverdefined();
237 return Res;
238 }
239
240 bool isUndef() const { return Tag == undef; }
241 bool isUnknown() const { return Tag == unknown; }
242 bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
243 bool isConstant() const { return Tag == constant; }
244 bool isNotConstant() const { return Tag == notconstant; }
245 bool isConstantRangeIncludingUndef() const {
246 return Tag == constantrange_including_undef;
247 }
248 /// Returns true if this value is a constant range. Use \p UndefAllowed to
249 /// exclude non-singleton constant ranges that may also be undef. Note that
250 /// this function also returns true if the range may include undef, but only
251 /// contains a single element. In that case, it can be replaced by a constant.
252 bool isConstantRange(bool UndefAllowed = true) const {
253 return Tag == constantrange || (Tag == constantrange_including_undef &&
254 (UndefAllowed || Range.isSingleElement()));
255 }
256 bool isOverdefined() const { return Tag == overdefined; }
257
258 Constant *getConstant() const {
259 assert(isConstant() && "Cannot get the constant of a non-constant!")(static_cast <bool> (isConstant() && "Cannot get the constant of a non-constant!"
) ? void (0) : __assert_fail ("isConstant() && \"Cannot get the constant of a non-constant!\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 259, __extension__
__PRETTY_FUNCTION__))
;
260 return ConstVal;
261 }
262
263 Constant *getNotConstant() const {
264 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!")(static_cast <bool> (isNotConstant() && "Cannot get the constant of a non-notconstant!"
) ? void (0) : __assert_fail ("isNotConstant() && \"Cannot get the constant of a non-notconstant!\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 264, __extension__
__PRETTY_FUNCTION__))
;
265 return ConstVal;
266 }
267
268 /// Returns the constant range for this value. Use \p UndefAllowed to exclude
269 /// non-singleton constant ranges that may also be undef. Note that this
270 /// function also returns a range if the range may include undef, but only
271 /// contains a single element. In that case, it can be replaced by a constant.
272 const ConstantRange &getConstantRange(bool UndefAllowed = true) const {
273 assert(isConstantRange(UndefAllowed) &&(static_cast <bool> (isConstantRange(UndefAllowed) &&
"Cannot get the constant-range of a non-constant-range!") ? void
(0) : __assert_fail ("isConstantRange(UndefAllowed) && \"Cannot get the constant-range of a non-constant-range!\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 274, __extension__
__PRETTY_FUNCTION__))
274 "Cannot get the constant-range of a non-constant-range!")(static_cast <bool> (isConstantRange(UndefAllowed) &&
"Cannot get the constant-range of a non-constant-range!") ? void
(0) : __assert_fail ("isConstantRange(UndefAllowed) && \"Cannot get the constant-range of a non-constant-range!\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 274, __extension__
__PRETTY_FUNCTION__))
;
275 return Range;
276 }
277
278 Optional<APInt> asConstantInteger() const {
279 if (isConstant() && isa<ConstantInt>(getConstant())) {
280 return cast<ConstantInt>(getConstant())->getValue();
281 } else if (isConstantRange() && getConstantRange().isSingleElement()) {
282 return *getConstantRange().getSingleElement();
283 }
284 return std::nullopt;
285 }
286
287 bool markOverdefined() {
288 if (isOverdefined())
289 return false;
290 destroy();
291 Tag = overdefined;
292 return true;
293 }
294
295 bool markUndef() {
296 if (isUndef())
297 return false;
298
299 assert(isUnknown())(static_cast <bool> (isUnknown()) ? void (0) : __assert_fail
("isUnknown()", "llvm/include/llvm/Analysis/ValueLattice.h",
299, __extension__ __PRETTY_FUNCTION__))
;
300 Tag = undef;
301 return true;
302 }
303
304 bool markConstant(Constant *V, bool MayIncludeUndef = false) {
305 if (isa<UndefValue>(V))
306 return markUndef();
307
308 if (isConstant()) {
309 assert(getConstant() == V && "Marking constant with different value")(static_cast <bool> (getConstant() == V && "Marking constant with different value"
) ? void (0) : __assert_fail ("getConstant() == V && \"Marking constant with different value\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 309, __extension__
__PRETTY_FUNCTION__))
;
310 return false;
311 }
312
313 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
314 return markConstantRange(
315 ConstantRange(CI->getValue()),
316 MergeOptions().setMayIncludeUndef(MayIncludeUndef));
317
318 assert(isUnknown() || isUndef())(static_cast <bool> (isUnknown() || isUndef()) ? void (
0) : __assert_fail ("isUnknown() || isUndef()", "llvm/include/llvm/Analysis/ValueLattice.h"
, 318, __extension__ __PRETTY_FUNCTION__))
;
319 Tag = constant;
320 ConstVal = V;
321 return true;
322 }
323
324 bool markNotConstant(Constant *V) {
325 assert(V && "Marking constant with NULL")(static_cast <bool> (V && "Marking constant with NULL"
) ? void (0) : __assert_fail ("V && \"Marking constant with NULL\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 325, __extension__
__PRETTY_FUNCTION__))
;
326 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
327 return markConstantRange(
328 ConstantRange(CI->getValue() + 1, CI->getValue()));
329
330 if (isa<UndefValue>(V))
331 return false;
332
333 if (isNotConstant()) {
334 assert(getNotConstant() == V && "Marking !constant with different value")(static_cast <bool> (getNotConstant() == V && "Marking !constant with different value"
) ? void (0) : __assert_fail ("getNotConstant() == V && \"Marking !constant with different value\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 334, __extension__
__PRETTY_FUNCTION__))
;
335 return false;
336 }
337
338 assert(isUnknown())(static_cast <bool> (isUnknown()) ? void (0) : __assert_fail
("isUnknown()", "llvm/include/llvm/Analysis/ValueLattice.h",
338, __extension__ __PRETTY_FUNCTION__))
;
339 Tag = notconstant;
340 ConstVal = V;
341 return true;
342 }
343
344 /// Mark the object as constant range with \p NewR. If the object is already a
345 /// constant range, nothing changes if the existing range is equal to \p
346 /// NewR and the tag. Otherwise \p NewR must be a superset of the existing
347 /// range or the object must be undef. The tag is set to
348 /// constant_range_including_undef if either the existing value or the new
349 /// range may include undef.
350 bool markConstantRange(ConstantRange NewR,
351 MergeOptions Opts = MergeOptions()) {
352 assert(!NewR.isEmptySet() && "should only be called for non-empty sets")(static_cast <bool> (!NewR.isEmptySet() && "should only be called for non-empty sets"
) ? void (0) : __assert_fail ("!NewR.isEmptySet() && \"should only be called for non-empty sets\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 352, __extension__
__PRETTY_FUNCTION__))
;
353
354 if (NewR.isFullSet())
355 return markOverdefined();
356
357 ValueLatticeElementTy OldTag = Tag;
358 ValueLatticeElementTy NewTag =
359 (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef)
360 ? constantrange_including_undef
361 : constantrange;
362 if (isConstantRange()) {
363 Tag = NewTag;
364 if (getConstantRange() == NewR)
365 return Tag != OldTag;
366
367 // Simple form of widening. If a range is extended multiple times, go to
368 // overdefined.
369 if (Opts.CheckWiden && ++NumRangeExtensions > Opts.MaxWidenSteps)
370 return markOverdefined();
371
372 assert(NewR.contains(getConstantRange()) &&(static_cast <bool> (NewR.contains(getConstantRange()) &&
"Existing range must be a subset of NewR") ? void (0) : __assert_fail
("NewR.contains(getConstantRange()) && \"Existing range must be a subset of NewR\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 373, __extension__
__PRETTY_FUNCTION__))
373 "Existing range must be a subset of NewR")(static_cast <bool> (NewR.contains(getConstantRange()) &&
"Existing range must be a subset of NewR") ? void (0) : __assert_fail
("NewR.contains(getConstantRange()) && \"Existing range must be a subset of NewR\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 373, __extension__
__PRETTY_FUNCTION__))
;
374 Range = std::move(NewR);
375 return true;
376 }
377
378 assert(isUnknown() || isUndef())(static_cast <bool> (isUnknown() || isUndef()) ? void (
0) : __assert_fail ("isUnknown() || isUndef()", "llvm/include/llvm/Analysis/ValueLattice.h"
, 378, __extension__ __PRETTY_FUNCTION__))
;
379
380 NumRangeExtensions = 0;
381 Tag = NewTag;
382 new (&Range) ConstantRange(std::move(NewR));
383 return true;
384 }
385
386 /// Updates this object to approximate both this object and RHS. Returns
387 /// true if this object has been changed.
388 bool mergeIn(const ValueLatticeElement &RHS,
389 MergeOptions Opts = MergeOptions()) {
390 if (RHS.isUnknown() || isOverdefined())
391 return false;
392 if (RHS.isOverdefined()) {
393 markOverdefined();
394 return true;
395 }
396
397 if (isUndef()) {
398 assert(!RHS.isUnknown())(static_cast <bool> (!RHS.isUnknown()) ? void (0) : __assert_fail
("!RHS.isUnknown()", "llvm/include/llvm/Analysis/ValueLattice.h"
, 398, __extension__ __PRETTY_FUNCTION__))
;
399 if (RHS.isUndef())
400 return false;
401 if (RHS.isConstant())
402 return markConstant(RHS.getConstant(), true);
403 if (RHS.isConstantRange())
404 return markConstantRange(RHS.getConstantRange(true),
405 Opts.setMayIncludeUndef());
406 return markOverdefined();
407 }
408
409 if (isUnknown()) {
410 assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier")(static_cast <bool> (!RHS.isUnknown() && "Unknow RHS should be handled earlier"
) ? void (0) : __assert_fail ("!RHS.isUnknown() && \"Unknow RHS should be handled earlier\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 410, __extension__
__PRETTY_FUNCTION__))
;
411 *this = RHS;
412 return true;
413 }
414
415 if (isConstant()) {
416 if (RHS.isConstant() && getConstant() == RHS.getConstant())
417 return false;
418 if (RHS.isUndef())
419 return false;
420 markOverdefined();
421 return true;
422 }
423
424 if (isNotConstant()) {
425 if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
426 return false;
427 markOverdefined();
428 return true;
429 }
430
431 auto OldTag = Tag;
432 assert(isConstantRange() && "New ValueLattice type?")(static_cast <bool> (isConstantRange() && "New ValueLattice type?"
) ? void (0) : __assert_fail ("isConstantRange() && \"New ValueLattice type?\""
, "llvm/include/llvm/Analysis/ValueLattice.h", 432, __extension__
__PRETTY_FUNCTION__))
;
433 if (RHS.isUndef()) {
434 Tag = constantrange_including_undef;
435 return OldTag != Tag;
436 }
437
438 if (!RHS.isConstantRange()) {
439 // We can get here if we've encountered a constantexpr of integer type
440 // and merge it with a constantrange.
441 markOverdefined();
442 return true;
443 }
444
445 ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
446 return markConstantRange(
447 std::move(NewR),
448 Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef()));
449 }
450
451 // Compares this symbolic value with Other using Pred and returns either
452 /// true, false or undef constants, or nullptr if the comparison cannot be
453 /// evaluated.
454 Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
455 const ValueLatticeElement &Other,
456 const DataLayout &DL) const;
457
458 unsigned getNumRangeExtensions() const { return NumRangeExtensions; }
459 void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; }
460};
461
462static_assert(sizeof(ValueLatticeElement) <= 40,
463 "size of ValueLatticeElement changed unexpectedly");
464
465raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
466} // end namespace llvm
467#endif

/build/source/llvm/include/llvm/IR/ConstantRange.h

1//===- ConstantRange.h - Represent a range ----------------------*- 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// Represent a range of possible values that may occur when the program is run
10// for an integral value. This keeps track of a lower and upper bound for the
11// constant, which MAY wrap around the end of the numeric range. To do this, it
12// keeps track of a [lower, upper) bound, which specifies an interval just like
13// STL iterators. When used with boolean values, the following are important
14// ranges: :
15//
16// [F, F) = {} = Empty set
17// [T, F) = {T}
18// [F, T) = {F}
19// [T, T) = {F, T} = Full set
20//
21// The other integral ranges use min/max values for special range values. For
22// example, for 8-bit types, it uses:
23// [0, 0) = {} = Empty set
24// [255, 255) = {0..255} = Full Set
25//
26// Note that ConstantRange can be used to represent either signed or
27// unsigned ranges.
28//
29//===----------------------------------------------------------------------===//
30
31#ifndef LLVM_IR_CONSTANTRANGE_H
32#define LLVM_IR_CONSTANTRANGE_H
33
34#include "llvm/ADT/APInt.h"
35#include "llvm/IR/InstrTypes.h"
36#include "llvm/IR/Instruction.h"
37#include "llvm/Support/Compiler.h"
38#include <cstdint>
39
40namespace llvm {
41
42class MDNode;
43class raw_ostream;
44struct KnownBits;
45
46/// This class represents a range of values.
47class [[nodiscard]] ConstantRange {
48 APInt Lower, Upper;
49
50 /// Create empty constant range with same bitwidth.
51 ConstantRange getEmpty() const {
52 return ConstantRange(getBitWidth(), false);
53 }
54
55 /// Create full constant range with same bitwidth.
56 ConstantRange getFull() const {
57 return ConstantRange(getBitWidth(), true);
58 }
59
60public:
61 /// Initialize a full or empty set for the specified bit width.
62 explicit ConstantRange(uint32_t BitWidth, bool isFullSet);
63
64 /// Initialize a range to hold the single specified value.
65 ConstantRange(APInt Value);
66
67 /// Initialize a range of values explicitly. This will assert out if
68 /// Lower==Upper and Lower != Min or Max value for its type. It will also
69 /// assert out if the two APInt's are not the same bit width.
70 ConstantRange(APInt Lower, APInt Upper);
71
72 /// Create empty constant range with the given bit width.
73 static ConstantRange getEmpty(uint32_t BitWidth) {
74 return ConstantRange(BitWidth, false);
75 }
76
77 /// Create full constant range with the given bit width.
78 static ConstantRange getFull(uint32_t BitWidth) {
79 return ConstantRange(BitWidth, true);
80 }
81
82 /// Create non-empty constant range with the given bounds. If Lower and
83 /// Upper are the same, a full range is returned.
84 static ConstantRange getNonEmpty(APInt Lower, APInt Upper) {
85 if (Lower == Upper)
86 return getFull(Lower.getBitWidth());
87 return ConstantRange(std::move(Lower), std::move(Upper));
88 }
89
90 /// Initialize a range based on a known bits constraint. The IsSigned flag
91 /// indicates whether the constant range should not wrap in the signed or
92 /// unsigned domain.
93 static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned);
94
95 /// Produce the smallest range such that all values that may satisfy the given
96 /// predicate with any value contained within Other is contained in the
97 /// returned range. Formally, this returns a superset of
98 /// 'union over all y in Other . { x : icmp op x y is true }'. If the exact
99 /// answer is not representable as a ConstantRange, the return value will be a
100 /// proper superset of the above.
101 ///
102 /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)
103 static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred,
104 const ConstantRange &Other);
105
106 /// Produce the largest range such that all values in the returned range
107 /// satisfy the given predicate with all values contained within Other.
108 /// Formally, this returns a subset of
109 /// 'intersection over all y in Other . { x : icmp op x y is true }'. If the
110 /// exact answer is not representable as a ConstantRange, the return value
111 /// will be a proper subset of the above.
112 ///
113 /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2)
114 static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
115 const ConstantRange &Other);
116
117 /// Produce the exact range such that all values in the returned range satisfy
118 /// the given predicate with any value contained within Other. Formally, this
119 /// returns the exact answer when the superset of 'union over all y in Other
120 /// is exactly same as the subset of intersection over all y in Other.
121 /// { x : icmp op x y is true}'.
122 ///
123 /// Example: Pred = ult and Other = i8 3 returns [0, 3)
124 static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
125 const APInt &Other);
126
127 /// Does the predicate \p Pred hold between ranges this and \p Other?
128 /// NOTE: false does not mean that inverse predicate holds!
129 bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const;
130
131 /// Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
132 /// Does not depend on strictness/direction of the predicate.
133 static bool
134 areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1,
135 const ConstantRange &CR2);
136
137 /// Return true iff CR1 ult CR2 is equivalent to CR1 sge CR2.
138 /// Does not depend on strictness/direction of the predicate.
139 static bool
140 areInsensitiveToSignednessOfInvertedICmpPredicate(const ConstantRange &CR1,
141 const ConstantRange &CR2);
142
143 /// If the comparison between constant ranges this and Other
144 /// is insensitive to the signedness of the comparison predicate,
145 /// return a predicate equivalent to \p Pred, with flipped signedness
146 /// (i.e. unsigned instead of signed or vice versa), and maybe inverted,
147 /// otherwise returns CmpInst::Predicate::BAD_ICMP_PREDICATE.
148 static CmpInst::Predicate
149 getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred,
150 const ConstantRange &CR1,
151 const ConstantRange &CR2);
152
153 /// Produce the largest range containing all X such that "X BinOp Y" is
154 /// guaranteed not to wrap (overflow) for *all* Y in Other. However, there may
155 /// be *some* Y in Other for which additional X not contained in the result
156 /// also do not overflow.
157 ///
158 /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap.
159 ///
160 /// Examples:
161 /// typedef OverflowingBinaryOperator OBO;
162 /// #define MGNR makeGuaranteedNoWrapRegion
163 /// MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127)
164 /// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1)
165 /// MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set
166 /// MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4)
167 /// MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128)
168 /// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0)
169 static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
170 const ConstantRange &Other,
171 unsigned NoWrapKind);
172
173 /// Produce the range that contains X if and only if "X BinOp Other" does
174 /// not wrap.
175 static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
176 const APInt &Other,
177 unsigned NoWrapKind);
178
179 /// Returns true if ConstantRange calculations are supported for intrinsic
180 /// with \p IntrinsicID.
181 static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID);
182
183 /// Compute range of intrinsic result for the given operand ranges.
184 static ConstantRange intrinsic(Intrinsic::ID IntrinsicID,
185 ArrayRef<ConstantRange> Ops);
186
187 /// Set up \p Pred and \p RHS such that
188 /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this. Return true if
189 /// successful.
190 bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const;
191
192 /// Set up \p Pred, \p RHS and \p Offset such that (V + Offset) Pred RHS
193 /// is true iff V is in the range. Prefers using Offset == 0 if possible.
194 void
195 getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS, APInt &Offset) const;
196
197 /// Return the lower value for this range.
198 const APInt &getLower() const { return Lower; }
199
200 /// Return the upper value for this range.
201 const APInt &getUpper() const { return Upper; }
202
203 /// Get the bit width of this ConstantRange.
204 uint32_t getBitWidth() const { return Lower.getBitWidth(); }
205
206 /// Return true if this set contains all of the elements possible
207 /// for this data-type.
208 bool isFullSet() const;
209
210 /// Return true if this set contains no members.
211 bool isEmptySet() const;
212
213 /// Return true if this set wraps around the unsigned domain. Special cases:
214 /// * Empty set: Not wrapped.
215 /// * Full set: Not wrapped.
216 /// * [X, 0) == [X, Max]: Not wrapped.
217 bool isWrappedSet() const;
218
219 /// Return true if the exclusive upper bound wraps around the unsigned
220 /// domain. Special cases:
221 /// * Empty set: Not wrapped.
222 /// * Full set: Not wrapped.
223 /// * [X, 0): Wrapped.
224 bool isUpperWrapped() const;
225
226 /// Return true if this set wraps around the signed domain. Special cases:
227 /// * Empty set: Not wrapped.
228 /// * Full set: Not wrapped.
229 /// * [X, SignedMin) == [X, SignedMax]: Not wrapped.
230 bool isSignWrappedSet() const;
231
232 /// Return true if the (exclusive) upper bound wraps around the signed
233 /// domain. Special cases:
234 /// * Empty set: Not wrapped.
235 /// * Full set: Not wrapped.
236 /// * [X, SignedMin): Wrapped.
237 bool isUpperSignWrapped() const;
238
239 /// Return true if the specified value is in the set.
240 bool contains(const APInt &Val) const;
241
242 /// Return true if the other range is a subset of this one.
243 bool contains(const ConstantRange &CR) const;
244
245 /// If this set contains a single element, return it, otherwise return null.
246 const APInt *getSingleElement() const {
247 if (Upper == Lower + 1)
248 return &Lower;
249 return nullptr;
250 }
251
252 /// If this set contains all but a single element, return it, otherwise return
253 /// null.
254 const APInt *getSingleMissingElement() const {
255 if (Lower == Upper + 1)
256 return &Upper;
257 return nullptr;
258 }
259
260 /// Return true if this set contains exactly one member.
261 bool isSingleElement() const { return getSingleElement() != nullptr; }
262
263 /// Compare set size of this range with the range CR.
264 bool isSizeStrictlySmallerThan(const ConstantRange &CR) const;
265
266 /// Compare set size of this range with Value.
267 bool isSizeLargerThan(uint64_t MaxSize) const;
268
269 /// Return true if all values in this range are negative.
270 bool isAllNegative() const;
271
272 /// Return true if all values in this range are non-negative.
273 bool isAllNonNegative() const;
274
275 /// Return the largest unsigned value contained in the ConstantRange.
276 APInt getUnsignedMax() const;
277
278 /// Return the smallest unsigned value contained in the ConstantRange.
279 APInt getUnsignedMin() const;
280
281 /// Return the largest signed value contained in the ConstantRange.
282 APInt getSignedMax() const;
283
284 /// Return the smallest signed value contained in the ConstantRange.
285 APInt getSignedMin() const;
286
287 /// Return true if this range is equal to another range.
288 bool operator==(const ConstantRange &CR) const {
289 return Lower == CR.Lower && Upper == CR.Upper;
290 }
291 bool operator!=(const ConstantRange &CR) const {
292 return !operator==(CR);
293 }
294
295 /// Compute the maximal number of active bits needed to represent every value
296 /// in this range.
297 unsigned getActiveBits() const;
298
299 /// Compute the maximal number of bits needed to represent every value
300 /// in this signed range.
301 unsigned getMinSignedBits() const;
302
303 /// Subtract the specified constant from the endpoints of this constant range.
304 ConstantRange subtract(const APInt &CI) const;
305
306 /// Subtract the specified range from this range (aka relative complement of
307 /// the sets).
308 ConstantRange difference(const ConstantRange &CR) const;
309
310 /// If represented precisely, the result of some range operations may consist
311 /// of multiple disjoint ranges. As only a single range may be returned, any
312 /// range covering these disjoint ranges constitutes a valid result, but some
313 /// may be more useful than others depending on context. The preferred range
314 /// type specifies whether a range that is non-wrapping in the unsigned or
315 /// signed domain, or has the smallest size, is preferred. If a signedness is
316 /// preferred but all ranges are non-wrapping or all wrapping, then the
317 /// smallest set size is preferred. If there are multiple smallest sets, any
318 /// one of them may be returned.
319 enum PreferredRangeType { Smallest, Unsigned, Signed };
320
321 /// Return the range that results from the intersection of this range with
322 /// another range. If the intersection is disjoint, such that two results
323 /// are possible, the preferred range is determined by the PreferredRangeType.
324 ConstantRange intersectWith(const ConstantRange &CR,
325 PreferredRangeType Type = Smallest) const;
326
327 /// Return the range that results from the union of this range
328 /// with another range. The resultant range is guaranteed to include the
329 /// elements of both sets, but may contain more. For example, [3, 9) union
330 /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
331 /// in either set before.
332 ConstantRange unionWith(const ConstantRange &CR,
333 PreferredRangeType Type = Smallest) const;
334
335 /// Intersect the two ranges and return the result if it can be represented
336 /// exactly, otherwise return std::nullopt.
337 std::optional<ConstantRange>
338 exactIntersectWith(const ConstantRange &CR) const;
339
340 /// Union the two ranges and return the result if it can be represented
341 /// exactly, otherwise return std::nullopt.
342 std::optional<ConstantRange> exactUnionWith(const ConstantRange &CR) const;
343
344 /// Return a new range representing the possible values resulting
345 /// from an application of the specified cast operator to this range. \p
346 /// BitWidth is the target bitwidth of the cast. For casts which don't
347 /// change bitwidth, it must be the same as the source bitwidth. For casts
348 /// which do change bitwidth, the bitwidth must be consistent with the
349 /// requested cast and source bitwidth.
350 ConstantRange castOp(Instruction::CastOps CastOp,
351 uint32_t BitWidth) const;
352
353 /// Return a new range in the specified integer type, which must
354 /// be strictly larger than the current type. The returned range will
355 /// correspond to the possible range of values if the source range had been
356 /// zero extended to BitWidth.
357 ConstantRange zeroExtend(uint32_t BitWidth) const;
358
359 /// Return a new range in the specified integer type, which must
360 /// be strictly larger than the current type. The returned range will
361 /// correspond to the possible range of values if the source range had been
362 /// sign extended to BitWidth.
363 ConstantRange signExtend(uint32_t BitWidth) const;
364
365 /// Return a new range in the specified integer type, which must be
366 /// strictly smaller than the current type. The returned range will
367 /// correspond to the possible range of values if the source range had been
368 /// truncated to the specified type.
369 ConstantRange truncate(uint32_t BitWidth) const;
370
371 /// Make this range have the bit width given by \p BitWidth. The
372 /// value is zero extended, truncated, or left alone to make it that width.
373 ConstantRange zextOrTrunc(uint32_t BitWidth) const;
374
375 /// Make this range have the bit width given by \p BitWidth. The
376 /// value is sign extended, truncated, or left alone to make it that width.
377 ConstantRange sextOrTrunc(uint32_t BitWidth) const;
378
379 /// Return a new range representing the possible values resulting
380 /// from an application of the specified binary operator to an left hand side
381 /// of this range and a right hand side of \p Other.
382 ConstantRange binaryOp(Instruction::BinaryOps BinOp,
383 const ConstantRange &Other) const;
384
385 /// Return a new range representing the possible values resulting
386 /// from an application of the specified overflowing binary operator to a
387 /// left hand side of this range and a right hand side of \p Other given
388 /// the provided knowledge about lack of wrapping \p NoWrapKind.
389 ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp,
390 const ConstantRange &Other,
391 unsigned NoWrapKind) const;
392
393 /// Return a new range representing the possible values resulting
394 /// from an addition of a value in this range and a value in \p Other.
395 ConstantRange add(const ConstantRange &Other) const;
396
397 /// Return a new range representing the possible values resulting
398 /// from an addition with wrap type \p NoWrapKind of a value in this
399 /// range and a value in \p Other.
400 /// If the result range is disjoint, the preferred range is determined by the
401 /// \p PreferredRangeType.
402 ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
403 PreferredRangeType RangeType = Smallest) const;
404
405 /// Return a new range representing the possible values resulting
406 /// from a subtraction of a value in this range and a value in \p Other.
407 ConstantRange sub(const ConstantRange &Other) const;
408
409 /// Return a new range representing the possible values resulting
410 /// from an subtraction with wrap type \p NoWrapKind of a value in this
411 /// range and a value in \p Other.
412 /// If the result range is disjoint, the preferred range is determined by the
413 /// \p PreferredRangeType.
414 ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
415 PreferredRangeType RangeType = Smallest) const;
416
417 /// Return a new range representing the possible values resulting
418 /// from a multiplication of a value in this range and a value in \p Other,
419 /// treating both this and \p Other as unsigned ranges.
420 ConstantRange multiply(const ConstantRange &Other) const;
421
422 /// Return range of possible values for a signed multiplication of this and
423 /// \p Other. However, if overflow is possible always return a full range
424 /// rather than trying to determine a more precise result.
425 ConstantRange smul_fast(const ConstantRange &Other) const;
426
427 /// Return a new range representing the possible values resulting
428 /// from a signed maximum of a value in this range and a value in \p Other.
429 ConstantRange smax(const ConstantRange &Other) const;
430
431 /// Return a new range representing the possible values resulting
432 /// from an unsigned maximum of a value in this range and a value in \p Other.
433 ConstantRange umax(const ConstantRange &Other) const;
434
435 /// Return a new range representing the possible values resulting
436 /// from a signed minimum of a value in this range and a value in \p Other.
437 ConstantRange smin(const ConstantRange &Other) const;
438
439 /// Return a new range representing the possible values resulting
440 /// from an unsigned minimum of a value in this range and a value in \p Other.
441 ConstantRange umin(const ConstantRange &Other) const;
442
443 /// Return a new range representing the possible values resulting
444 /// from an unsigned division of a value in this range and a value in
445 /// \p Other.
446 ConstantRange udiv(const ConstantRange &Other) const;
447
448 /// Return a new range representing the possible values resulting
449 /// from a signed division of a value in this range and a value in
450 /// \p Other. Division by zero and division of SignedMin by -1 are considered
451 /// undefined behavior, in line with IR, and do not contribute towards the
452 /// result.
453 ConstantRange sdiv(const ConstantRange &Other) const;
454
455 /// Return a new range representing the possible values resulting
456 /// from an unsigned remainder operation of a value in this range and a
457 /// value in \p Other.
458 ConstantRange urem(const ConstantRange &Other) const;
459
460 /// Return a new range representing the possible values resulting
461 /// from a signed remainder operation of a value in this range and a
462 /// value in \p Other.
463 ConstantRange srem(const ConstantRange &Other) const;
464
465 /// Return a new range representing the possible values resulting from
466 /// a binary-xor of a value in this range by an all-one value,
467 /// aka bitwise complement operation.
468 ConstantRange binaryNot() const;
469
470 /// Return a new range representing the possible values resulting
471 /// from a binary-and of a value in this range by a value in \p Other.
472 ConstantRange binaryAnd(const ConstantRange &Other) const;
473
474 /// Return a new range representing the possible values resulting
475 /// from a binary-or of a value in this range by a value in \p Other.
476 ConstantRange binaryOr(const ConstantRange &Other) const;
477
478 /// Return a new range representing the possible values resulting
479 /// from a binary-xor of a value in this range by a value in \p Other.
480 ConstantRange binaryXor(const ConstantRange &Other) const;
481
482 /// Return a new range representing the possible values resulting
483 /// from a left shift of a value in this range by a value in \p Other.
484 /// TODO: This isn't fully implemented yet.
485 ConstantRange shl(const ConstantRange &Other) const;
486
487 /// Return a new range representing the possible values resulting from a
488 /// logical right shift of a value in this range and a value in \p Other.
489 ConstantRange lshr(const ConstantRange &Other) const;
490
491 /// Return a new range representing the possible values resulting from a
492 /// arithmetic right shift of a value in this range and a value in \p Other.
493 ConstantRange ashr(const ConstantRange &Other) const;
494
495 /// Perform an unsigned saturating addition of two constant ranges.
496 ConstantRange uadd_sat(const ConstantRange &Other) const;
497
498 /// Perform a signed saturating addition of two constant ranges.
499 ConstantRange sadd_sat(const ConstantRange &Other) const;
500
501 /// Perform an unsigned saturating subtraction of two constant ranges.
502 ConstantRange usub_sat(const ConstantRange &Other) const;
503
504 /// Perform a signed saturating subtraction of two constant ranges.
505 ConstantRange ssub_sat(const ConstantRange &Other) const;
506
507 /// Perform an unsigned saturating multiplication of two constant ranges.
508 ConstantRange umul_sat(const ConstantRange &Other) const;
509
510 /// Perform a signed saturating multiplication of two constant ranges.
511 ConstantRange smul_sat(const ConstantRange &Other) const;
512
513 /// Perform an unsigned saturating left shift of this constant range by a
514 /// value in \p Other.
515 ConstantRange ushl_sat(const ConstantRange &Other) const;
516
517 /// Perform a signed saturating left shift of this constant range by a
518 /// value in \p Other.
519 ConstantRange sshl_sat(const ConstantRange &Other) const;
520
521 /// Return a new range that is the logical not of the current set.
522 ConstantRange inverse() const;
523
524 /// Calculate absolute value range. If the original range contains signed
525 /// min, then the resulting range will contain signed min if and only if
526 /// \p IntMinIsPoison is false.
527 ConstantRange abs(bool IntMinIsPoison = false) const;
528
529 /// Represents whether an operation on the given constant range is known to
530 /// always or never overflow.
531 enum class OverflowResult {
532 /// Always overflows in the direction of signed/unsigned min value.
533 AlwaysOverflowsLow,
534 /// Always overflows in the direction of signed/unsigned max value.
535 AlwaysOverflowsHigh,
536 /// May or may not overflow.
537 MayOverflow,
538 /// Never overflows.
539 NeverOverflows,
540 };
541
542 /// Return whether unsigned add of the two ranges always/never overflows.
543 OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const;
544
545 /// Return whether signed add of the two ranges always/never overflows.
546 OverflowResult signedAddMayOverflow(const ConstantRange &Other) const;
547
548 /// Return whether unsigned sub of the two ranges always/never overflows.
549 OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const;
550
551 /// Return whether signed sub of the two ranges always/never overflows.
552 OverflowResult signedSubMayOverflow(const ConstantRange &Other) const;
553
554 /// Return whether unsigned mul of the two ranges always/never overflows.
555 OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const;
556
557 /// Return known bits for values in this range.
558 KnownBits toKnownBits() const;
559
560 /// Print out the bounds to a stream.
561 void print(raw_ostream &OS) const;
562
563 /// Allow printing from a debugger easily.
564 void dump() const;
565};
566
567inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
568 CR.print(OS);
569 return OS;
570}
571
572/// Parse out a conservative ConstantRange from !range metadata.
573///
574/// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
575ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD);
576
577} // end namespace llvm
578
579#endif // LLVM_IR_CONSTANTRANGE_H

/build/source/llvm/include/llvm/ADT/APInt.h

1//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- 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/// \file
10/// This file implements a class to represent arbitrary precision
11/// integral constant values and operations on them.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_APINT_H
16#define LLVM_ADT_APINT_H
17
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <optional>
24#include <utility>
25
26namespace llvm {
27class FoldingSetNodeID;
28class StringRef;
29class hash_code;
30class raw_ostream;
31
32template <typename T> class SmallVectorImpl;
33template <typename T> class ArrayRef;
34template <typename T> class Optional;
35template <typename T, typename Enable> struct DenseMapInfo;
36
37class APInt;
38
39inline APInt operator-(APInt);
40
41//===----------------------------------------------------------------------===//
42// APInt Class
43//===----------------------------------------------------------------------===//
44
45/// Class for arbitrary precision integers.
46///
47/// APInt is a functional replacement for common case unsigned integer type like
48/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
49/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
50/// than 64-bits of precision. APInt provides a variety of arithmetic operators
51/// and methods to manipulate integer values of any bit-width. It supports both
52/// the typical integer arithmetic and comparison operations as well as bitwise
53/// manipulation.
54///
55/// The class has several invariants worth noting:
56/// * All bit, byte, and word positions are zero-based.
57/// * Once the bit width is set, it doesn't change except by the Truncate,
58/// SignExtend, or ZeroExtend operations.
59/// * All binary operators must be on APInt instances of the same bit width.
60/// Attempting to use these operators on instances with different bit
61/// widths will yield an assertion.
62/// * The value is stored canonically as an unsigned value. For operations
63/// where it makes a difference, there are both signed and unsigned variants
64/// of the operation. For example, sdiv and udiv. However, because the bit
65/// widths must be the same, operations such as Mul and Add produce the same
66/// results regardless of whether the values are interpreted as signed or
67/// not.
68/// * In general, the class tries to follow the style of computation that LLVM
69/// uses in its IR. This simplifies its use for LLVM.
70/// * APInt supports zero-bit-width values, but operations that require bits
71/// are not defined on it (e.g. you cannot ask for the sign of a zero-bit
72/// integer). This means that operations like zero extension and logical
73/// shifts are defined, but sign extension and ashr is not. Zero bit values
74/// compare and hash equal to themselves, and countLeadingZeros returns 0.
75///
76class [[nodiscard]] APInt {
77public:
78 typedef uint64_t WordType;
79
80 /// This enum is used to hold the constants we needed for APInt.
81 enum : unsigned {
82 /// Byte size of a word.
83 APINT_WORD_SIZE = sizeof(WordType),
84 /// Bits in a word.
85 APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
86 };
87
88 enum class Rounding {
89 DOWN,
90 TOWARD_ZERO,
91 UP,
92 };
93
94 static constexpr WordType WORDTYPE_MAX = ~WordType(0);
95
96 /// \name Constructors
97 /// @{
98
99 /// Create a new APInt of numBits width, initialized as val.
100 ///
101 /// If isSigned is true then val is treated as if it were a signed value
102 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
103 /// will be done. Otherwise, no sign extension occurs (high order bits beyond
104 /// the range of val are zero filled).
105 ///
106 /// \param numBits the bit width of the constructed APInt
107 /// \param val the initial value of the APInt
108 /// \param isSigned how to treat signedness of val
109 APInt(unsigned numBits, uint64_t val, bool isSigned = false)
110 : BitWidth(numBits) {
111 if (isSingleWord()) {
112 U.VAL = val;
113 clearUnusedBits();
114 } else {
115 initSlowCase(val, isSigned);
116 }
117 }
118
119 /// Construct an APInt of numBits width, initialized as bigVal[].
120 ///
121 /// Note that bigVal.size() can be smaller or larger than the corresponding
122 /// bit width but any extraneous bits will be dropped.
123 ///
124 /// \param numBits the bit width of the constructed APInt
125 /// \param bigVal a sequence of words to form the initial value of the APInt
126 APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
127
128 /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
129 /// deprecated because this constructor is prone to ambiguity with the
130 /// APInt(unsigned, uint64_t, bool) constructor.
131 ///
132 /// If this overload is ever deleted, care should be taken to prevent calls
133 /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
134 /// constructor.
135 APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
136
137 /// Construct an APInt from a string representation.
138 ///
139 /// This constructor interprets the string \p str in the given radix. The
140 /// interpretation stops when the first character that is not suitable for the
141 /// radix is encountered, or the end of the string. Acceptable radix values
142 /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
143 /// string to require more bits than numBits.
144 ///
145 /// \param numBits the bit width of the constructed APInt
146 /// \param str the string to be interpreted
147 /// \param radix the radix to use for the conversion
148 APInt(unsigned numBits, StringRef str, uint8_t radix);
149
150 /// Default constructor that creates an APInt with a 1-bit zero value.
151 explicit APInt() { U.VAL = 0; }
152
153 /// Copy Constructor.
154 APInt(const APInt &that) : BitWidth(that.BitWidth) {
155 if (isSingleWord())
156 U.VAL = that.U.VAL;
157 else
158 initSlowCase(that);
159 }
160
161 /// Move Constructor.
162 APInt(APInt &&that) : BitWidth(that.BitWidth) {
14
Assigned value is garbage or undefined
163 memcpy(&U, &that.U, sizeof(U));
164 that.BitWidth = 0;
165 }
166
167 /// Destructor.
168 ~APInt() {
169 if (needsCleanup())
170 delete[] U.pVal;
171 }
172
173 /// @}
174 /// \name Value Generators
175 /// @{
176
177 /// Get the '0' value for the specified bit-width.
178 static APInt getZero(unsigned numBits) { return APInt(numBits, 0); }
179
180 /// NOTE: This is soft-deprecated. Please use `getZero()` instead.
181 static APInt getNullValue(unsigned numBits) { return getZero(numBits); }
182
183 /// Return an APInt zero bits wide.
184 static APInt getZeroWidth() { return getZero(0); }
185
186 /// Gets maximum unsigned value of APInt for specific bit width.
187 static APInt getMaxValue(unsigned numBits) { return getAllOnes(numBits); }
188
189 /// Gets maximum signed value of APInt for a specific bit width.
190 static APInt getSignedMaxValue(unsigned numBits) {
191 APInt API = getAllOnes(numBits);
192 API.clearBit(numBits - 1);
193 return API;
194 }
195
196 /// Gets minimum unsigned value of APInt for a specific bit width.
197 static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }
198
199 /// Gets minimum signed value of APInt for a specific bit width.
200 static APInt getSignedMinValue(unsigned numBits) {
201 APInt API(numBits, 0);
202 API.setBit(numBits - 1);
203 return API;
204 }
205
206 /// Get the SignMask for a specific bit width.
207 ///
208 /// This is just a wrapper function of getSignedMinValue(), and it helps code
209 /// readability when we want to get a SignMask.
210 static APInt getSignMask(unsigned BitWidth) {
211 return getSignedMinValue(BitWidth);
212 }
213
214 /// Return an APInt of a specified width with all bits set.
215 static APInt getAllOnes(unsigned numBits) {
216 return APInt(numBits, WORDTYPE_MAX, true);
217 }
218
219 /// NOTE: This is soft-deprecated. Please use `getAllOnes()` instead.
220 static APInt getAllOnesValue(unsigned numBits) { return getAllOnes(numBits); }
221
222 /// Return an APInt with exactly one bit set in the result.
223 static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
224 APInt Res(numBits, 0);
225 Res.setBit(BitNo);
226 return Res;
227 }
228
229 /// Get a value with a block of bits set.
230 ///
231 /// Constructs an APInt value that has a contiguous range of bits set. The
232 /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
233 /// bits will be zero. For example, with parameters(32, 0, 16) you would get
234 /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
235 /// \p hiBit.
236 ///
237 /// \param numBits the intended bit width of the result
238 /// \param loBit the index of the lowest bit set.
239 /// \param hiBit the index of the highest bit set.
240 ///
241 /// \returns An APInt value with the requested bits set.
242 static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
243 APInt Res(numBits, 0);
244 Res.setBits(loBit, hiBit);
245 return Res;
246 }
247
248 /// Wrap version of getBitsSet.
249 /// If \p hiBit is bigger than \p loBit, this is same with getBitsSet.
250 /// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example,
251 /// with parameters (32, 28, 4), you would get 0xF000000F.
252 /// If \p hiBit is equal to \p loBit, you would get a result with all bits
253 /// set.
254 static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
255 unsigned hiBit) {
256 APInt Res(numBits, 0);
257 Res.setBitsWithWrap(loBit, hiBit);
258 return Res;
259 }
260
261 /// Constructs an APInt value that has a contiguous range of bits set. The
262 /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
263 /// bits will be zero. For example, with parameters(32, 12) you would get
264 /// 0xFFFFF000.
265 ///
266 /// \param numBits the intended bit width of the result
267 /// \param loBit the index of the lowest bit to set.
268 ///
269 /// \returns An APInt value with the requested bits set.
270 static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) {
271 APInt Res(numBits, 0);
272 Res.setBitsFrom(loBit);
273 return Res;
274 }
275
276 /// Constructs an APInt value that has the top hiBitsSet bits set.
277 ///
278 /// \param numBits the bitwidth of the result
279 /// \param hiBitsSet the number of high-order bits set in the result.
280 static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
281 APInt Res(numBits, 0);
282 Res.setHighBits(hiBitsSet);
283 return Res;
284 }
285
286 /// Constructs an APInt value that has the bottom loBitsSet bits set.
287 ///
288 /// \param numBits the bitwidth of the result
289 /// \param loBitsSet the number of low-order bits set in the result.
290 static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
291 APInt Res(numBits, 0);
292 Res.setLowBits(loBitsSet);
293 return Res;
294 }
295
296 /// Return a value containing V broadcasted over NewLen bits.
297 static APInt getSplat(unsigned NewLen, const APInt &V);
298
299 /// @}
300 /// \name Value Tests
301 /// @{
302
303 /// Determine if this APInt just has one word to store value.
304 ///
305 /// \returns true if the number of bits <= 64, false otherwise.
306 bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
307
308 /// Determine sign of this APInt.
309 ///
310 /// This tests the high bit of this APInt to determine if it is set.
311 ///
312 /// \returns true if this APInt is negative, false otherwise
313 bool isNegative() const { return (*this)[BitWidth - 1]; }
314
315 /// Determine if this APInt Value is non-negative (>= 0)
316 ///
317 /// This tests the high bit of the APInt to determine if it is unset.
318 bool isNonNegative() const { return !isNegative(); }
319
320 /// Determine if sign bit of this APInt is set.
321 ///
322 /// This tests the high bit of this APInt to determine if it is set.
323 ///
324 /// \returns true if this APInt has its sign bit set, false otherwise.
325 bool isSignBitSet() const { return (*this)[BitWidth - 1]; }
326
327 /// Determine if sign bit of this APInt is clear.
328 ///
329 /// This tests the high bit of this APInt to determine if it is clear.
330 ///
331 /// \returns true if this APInt has its sign bit clear, false otherwise.
332 bool isSignBitClear() const { return !isSignBitSet(); }
333
334 /// Determine if this APInt Value is positive.
335 ///
336 /// This tests if the value of this APInt is positive (> 0). Note
337 /// that 0 is not a positive value.
338 ///
339 /// \returns true if this APInt is positive.
340 bool isStrictlyPositive() const { return isNonNegative() && !isZero(); }
341
342 /// Determine if this APInt Value is non-positive (<= 0).
343 ///
344 /// \returns true if this APInt is non-positive.
345 bool isNonPositive() const { return !isStrictlyPositive(); }
346
347 /// Determine if all bits are set. This is true for zero-width values.
348 bool isAllOnes() const {
349 if (BitWidth == 0)
350 return true;
351 if (isSingleWord())
352 return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
353 return countTrailingOnesSlowCase() == BitWidth;
354 }
355
356 /// NOTE: This is soft-deprecated. Please use `isAllOnes()` instead.
357 bool isAllOnesValue() const { return isAllOnes(); }
358
359 /// Determine if this value is zero, i.e. all bits are clear.
360 bool isZero() const {
361 if (isSingleWord())
362 return U.VAL == 0;
363 return countLeadingZerosSlowCase() == BitWidth;
364 }
365
366 /// NOTE: This is soft-deprecated. Please use `isZero()` instead.
367 bool isNullValue() const { return isZero(); }
368
369 /// Determine if this is a value of 1.
370 ///
371 /// This checks to see if the value of this APInt is one.
372 bool isOne() const {
373 if (isSingleWord())
374 return U.VAL == 1;
375 return countLeadingZerosSlowCase() == BitWidth - 1;
376 }
377
378 /// NOTE: This is soft-deprecated. Please use `isOne()` instead.
379 bool isOneValue() const { return isOne(); }
380
381 /// Determine if this is the largest unsigned value.
382 ///
383 /// This checks to see if the value of this APInt is the maximum unsigned
384 /// value for the APInt's bit width.
385 bool isMaxValue() const { return isAllOnes(); }
386
387 /// Determine if this is the largest signed value.
388 ///
389 /// This checks to see if the value of this APInt is the maximum signed
390 /// value for the APInt's bit width.
391 bool isMaxSignedValue() const {
392 if (isSingleWord()) {
393 assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 393, __extension__ __PRETTY_FUNCTION__
))
;
394 return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
395 }
396 return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
397 }
398
399 /// Determine if this is the smallest unsigned value.
400 ///
401 /// This checks to see if the value of this APInt is the minimum unsigned
402 /// value for the APInt's bit width.
403 bool isMinValue() const { return isZero(); }
404
405 /// Determine if this is the smallest signed value.
406 ///
407 /// This checks to see if the value of this APInt is the minimum signed
408 /// value for the APInt's bit width.
409 bool isMinSignedValue() const {
410 if (isSingleWord()) {
411 assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 411, __extension__ __PRETTY_FUNCTION__
))
;
412 return U.VAL == (WordType(1) << (BitWidth - 1));
413 }
414 return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
415 }
416
417 /// Check if this APInt has an N-bits unsigned integer value.
418 bool isIntN(unsigned N) const { return getActiveBits() <= N; }
419
420 /// Check if this APInt has an N-bits signed integer value.
421 bool isSignedIntN(unsigned N) const { return getSignificantBits() <= N; }
422
423 /// Check if this APInt's value is a power of two greater than zero.
424 ///
425 /// \returns true if the argument APInt value is a power of two > 0.
426 bool isPowerOf2() const {
427 if (isSingleWord()) {
428 assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 428, __extension__ __PRETTY_FUNCTION__
))
;
429 return isPowerOf2_64(U.VAL);
430 }
431 return countPopulationSlowCase() == 1;
432 }
433
434 /// Check if this APInt's negated value is a power of two greater than zero.
435 bool isNegatedPowerOf2() const {
436 assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 436, __extension__ __PRETTY_FUNCTION__
))
;
437 if (isNonNegative())
438 return false;
439 // NegatedPowerOf2 - shifted mask in the top bits.
440 unsigned LO = countLeadingOnes();
441 unsigned TZ = countTrailingZeros();
442 return (LO + TZ) == BitWidth;
443 }
444
445 /// Check if the APInt's value is returned by getSignMask.
446 ///
447 /// \returns true if this is the value returned by getSignMask.
448 bool isSignMask() const { return isMinSignedValue(); }
449
450 /// Convert APInt to a boolean value.
451 ///
452 /// This converts the APInt to a boolean value as a test against zero.
453 bool getBoolValue() const { return !isZero(); }
454
455 /// If this value is smaller than the specified limit, return it, otherwise
456 /// return the limit value. This causes the value to saturate to the limit.
457 uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) const {
458 return ugt(Limit) ? Limit : getZExtValue();
459 }
460
461 /// Check if the APInt consists of a repeated bit pattern.
462 ///
463 /// e.g. 0x01010101 satisfies isSplat(8).
464 /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
465 /// width without remainder.
466 bool isSplat(unsigned SplatSizeInBits) const;
467
468 /// \returns true if this APInt value is a sequence of \param numBits ones
469 /// starting at the least significant bit with the remainder zero.
470 bool isMask(unsigned numBits) const {
471 assert(numBits != 0 && "numBits must be non-zero")(static_cast <bool> (numBits != 0 && "numBits must be non-zero"
) ? void (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\""
, "llvm/include/llvm/ADT/APInt.h", 471, __extension__ __PRETTY_FUNCTION__
))
;
472 assert(numBits <= BitWidth && "numBits out of range")(static_cast <bool> (numBits <= BitWidth && "numBits out of range"
) ? void (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\""
, "llvm/include/llvm/ADT/APInt.h", 472, __extension__ __PRETTY_FUNCTION__
))
;
473 if (isSingleWord())
474 return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits));
475 unsigned Ones = countTrailingOnesSlowCase();
476 return (numBits == Ones) &&
477 ((Ones + countLeadingZerosSlowCase()) == BitWidth);
478 }
479
480 /// \returns true if this APInt is a non-empty sequence of ones starting at
481 /// the least significant bit with the remainder zero.
482 /// Ex. isMask(0x0000FFFFU) == true.
483 bool isMask() const {
484 if (isSingleWord())
485 return isMask_64(U.VAL);
486 unsigned Ones = countTrailingOnesSlowCase();
487 return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
488 }
489
490 /// Return true if this APInt value contains a non-empty sequence of ones with
491 /// the remainder zero.
492 bool isShiftedMask() const {
493 if (isSingleWord())
494 return isShiftedMask_64(U.VAL);
495 unsigned Ones = countPopulationSlowCase();
496 unsigned LeadZ = countLeadingZerosSlowCase();
497 return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
498 }
499
500 /// Return true if this APInt value contains a non-empty sequence of ones with
501 /// the remainder zero. If true, \p MaskIdx will specify the index of the
502 /// lowest set bit and \p MaskLen is updated to specify the length of the
503 /// mask, else neither are updated.
504 bool isShiftedMask(unsigned &MaskIdx, unsigned &MaskLen) const {
505 if (isSingleWord())
506 return isShiftedMask_64(U.VAL, MaskIdx, MaskLen);
507 unsigned Ones = countPopulationSlowCase();
508 unsigned LeadZ = countLeadingZerosSlowCase();
509 unsigned TrailZ = countTrailingZerosSlowCase();
510 if ((Ones + LeadZ + TrailZ) != BitWidth)
511 return false;
512 MaskLen = Ones;
513 MaskIdx = TrailZ;
514 return true;
515 }
516
517 /// Compute an APInt containing numBits highbits from this APInt.
518 ///
519 /// Get an APInt with the same BitWidth as this APInt, just zero mask the low
520 /// bits and right shift to the least significant bit.
521 ///
522 /// \returns the high "numBits" bits of this APInt.
523 APInt getHiBits(unsigned numBits) const;
524
525 /// Compute an APInt containing numBits lowbits from this APInt.
526 ///
527 /// Get an APInt with the same BitWidth as this APInt, just zero mask the high
528 /// bits.
529 ///
530 /// \returns the low "numBits" bits of this APInt.
531 APInt getLoBits(unsigned numBits) const;
532
533 /// Determine if two APInts have the same value, after zero-extending
534 /// one of them (if needed!) to ensure that the bit-widths match.
535 static bool isSameValue(const APInt &I1, const APInt &I2) {
536 if (I1.getBitWidth() == I2.getBitWidth())
537 return I1 == I2;
538
539 if (I1.getBitWidth() > I2.getBitWidth())
540 return I1 == I2.zext(I1.getBitWidth());
541
542 return I1.zext(I2.getBitWidth()) == I2;
543 }
544
545 /// Overload to compute a hash_code for an APInt value.
546 friend hash_code hash_value(const APInt &Arg);
547
548 /// This function returns a pointer to the internal storage of the APInt.
549 /// This is useful for writing out the APInt in binary form without any
550 /// conversions.
551 const uint64_t *getRawData() const {
552 if (isSingleWord())
553 return &U.VAL;
554 return &U.pVal[0];
555 }
556
557 /// @}
558 /// \name Unary Operators
559 /// @{
560
561 /// Postfix increment operator. Increment *this by 1.
562 ///
563 /// \returns a new APInt value representing the original value of *this.
564 APInt operator++(int) {
565 APInt API(*this);
566 ++(*this);
567 return API;
568 }
569
570 /// Prefix increment operator.
571 ///
572 /// \returns *this incremented by one
573 APInt &operator++();
574
575 /// Postfix decrement operator. Decrement *this by 1.
576 ///
577 /// \returns a new APInt value representing the original value of *this.
578 APInt operator--(int) {
579 APInt API(*this);
580 --(*this);
581 return API;
582 }
583
584 /// Prefix decrement operator.
585 ///
586 /// \returns *this decremented by one.
587 APInt &operator--();
588
589 /// Logical negation operation on this APInt returns true if zero, like normal
590 /// integers.
591 bool operator!() const { return isZero(); }
592
593 /// @}
594 /// \name Assignment Operators
595 /// @{
596
597 /// Copy assignment operator.
598 ///
599 /// \returns *this after assignment of RHS.
600 APInt &operator=(const APInt &RHS) {
601 // The common case (both source or dest being inline) doesn't require
602 // allocation or deallocation.
603 if (isSingleWord() && RHS.isSingleWord()) {
604 U.VAL = RHS.U.VAL;
605 BitWidth = RHS.BitWidth;
606 return *this;
607 }
608
609 assignSlowCase(RHS);
610 return *this;
611 }
612
613 /// Move assignment operator.
614 APInt &operator=(APInt &&that) {
615#ifdef EXPENSIVE_CHECKS
616 // Some std::shuffle implementations still do self-assignment.
617 if (this == &that)
618 return *this;
619#endif
620 assert(this != &that && "Self-move not supported")(static_cast <bool> (this != &that && "Self-move not supported"
) ? void (0) : __assert_fail ("this != &that && \"Self-move not supported\""
, "llvm/include/llvm/ADT/APInt.h", 620, __extension__ __PRETTY_FUNCTION__
))
;
621 if (!isSingleWord())
622 delete[] U.pVal;
623
624 // Use memcpy so that type based alias analysis sees both VAL and pVal
625 // as modified.
626 memcpy(&U, &that.U, sizeof(U));
627
628 BitWidth = that.BitWidth;
629 that.BitWidth = 0;
630 return *this;
631 }
632
633 /// Assignment operator.
634 ///
635 /// The RHS value is assigned to *this. If the significant bits in RHS exceed
636 /// the bit width, the excess bits are truncated. If the bit width is larger
637 /// than 64, the value is zero filled in the unspecified high order bits.
638 ///
639 /// \returns *this after assignment of RHS value.
640 APInt &operator=(uint64_t RHS) {
641 if (isSingleWord()) {
642 U.VAL = RHS;
643 return clearUnusedBits();
644 }
645 U.pVal[0] = RHS;
646 memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
647 return *this;
648 }
649
650 /// Bitwise AND assignment operator.
651 ///
652 /// Performs a bitwise AND operation on this APInt and RHS. The result is
653 /// assigned to *this.
654 ///
655 /// \returns *this after ANDing with RHS.
656 APInt &operator&=(const APInt &RHS) {
657 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 657, __extension__ __PRETTY_FUNCTION__
))
;
658 if (isSingleWord())
659 U.VAL &= RHS.U.VAL;
660 else
661 andAssignSlowCase(RHS);
662 return *this;
663 }
664
665 /// Bitwise AND assignment operator.
666 ///
667 /// Performs a bitwise AND operation on this APInt and RHS. RHS is
668 /// logically zero-extended or truncated to match the bit-width of
669 /// the LHS.
670 APInt &operator&=(uint64_t RHS) {
671 if (isSingleWord()) {
672 U.VAL &= RHS;
673 return *this;
674 }
675 U.pVal[0] &= RHS;
676 memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
677 return *this;
678 }
679
680 /// Bitwise OR assignment operator.
681 ///
682 /// Performs a bitwise OR operation on this APInt and RHS. The result is
683 /// assigned *this;
684 ///
685 /// \returns *this after ORing with RHS.
686 APInt &operator|=(const APInt &RHS) {
687 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 687, __extension__ __PRETTY_FUNCTION__
))
;
688 if (isSingleWord())
689 U.VAL |= RHS.U.VAL;
690 else
691 orAssignSlowCase(RHS);
692 return *this;
693 }
694
695 /// Bitwise OR assignment operator.
696 ///
697 /// Performs a bitwise OR operation on this APInt and RHS. RHS is
698 /// logically zero-extended or truncated to match the bit-width of
699 /// the LHS.
700 APInt &operator|=(uint64_t RHS) {
701 if (isSingleWord()) {
702 U.VAL |= RHS;
703 return clearUnusedBits();
704 }
705 U.pVal[0] |= RHS;
706 return *this;
707 }
708
709 /// Bitwise XOR assignment operator.
710 ///
711 /// Performs a bitwise XOR operation on this APInt and RHS. The result is
712 /// assigned to *this.
713 ///
714 /// \returns *this after XORing with RHS.
715 APInt &operator^=(const APInt &RHS) {
716 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 716, __extension__ __PRETTY_FUNCTION__
))
;
717 if (isSingleWord())
718 U.VAL ^= RHS.U.VAL;
719 else
720 xorAssignSlowCase(RHS);
721 return *this;
722 }
723
724 /// Bitwise XOR assignment operator.
725 ///
726 /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
727 /// logically zero-extended or truncated to match the bit-width of
728 /// the LHS.
729 APInt &operator^=(uint64_t RHS) {
730 if (isSingleWord()) {
731 U.VAL ^= RHS;
732 return clearUnusedBits();
733 }
734 U.pVal[0] ^= RHS;
735 return *this;
736 }
737
738 /// Multiplication assignment operator.
739 ///
740 /// Multiplies this APInt by RHS and assigns the result to *this.
741 ///
742 /// \returns *this
743 APInt &operator*=(const APInt &RHS);
744 APInt &operator*=(uint64_t RHS);
745
746 /// Addition assignment operator.
747 ///
748 /// Adds RHS to *this and assigns the result to *this.
749 ///
750 /// \returns *this
751 APInt &operator+=(const APInt &RHS);
752 APInt &operator+=(uint64_t RHS);
753
754 /// Subtraction assignment operator.
755 ///
756 /// Subtracts RHS from *this and assigns the result to *this.
757 ///
758 /// \returns *this
759 APInt &operator-=(const APInt &RHS);
760 APInt &operator-=(uint64_t RHS);
761
762 /// Left-shift assignment function.
763 ///
764 /// Shifts *this left by shiftAmt and assigns the result to *this.
765 ///
766 /// \returns *this after shifting left by ShiftAmt
767 APInt &operator<<=(unsigned ShiftAmt) {
768 assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth &&
"Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 768, __extension__ __PRETTY_FUNCTION__
))
;
769 if (isSingleWord()) {
770 if (ShiftAmt == BitWidth)
771 U.VAL = 0;
772 else
773 U.VAL <<= ShiftAmt;
774 return clearUnusedBits();
775 }
776 shlSlowCase(ShiftAmt);
777 return *this;
778 }
779
780 /// Left-shift assignment function.
781 ///
782 /// Shifts *this left by shiftAmt and assigns the result to *this.
783 ///
784 /// \returns *this after shifting left by ShiftAmt
785 APInt &operator<<=(const APInt &ShiftAmt);
786
787 /// @}
788 /// \name Binary Operators
789 /// @{
790
791 /// Multiplication operator.
792 ///
793 /// Multiplies this APInt by RHS and returns the result.
794 APInt operator*(const APInt &RHS) const;
795
796 /// Left logical shift operator.
797 ///
798 /// Shifts this APInt left by \p Bits and returns the result.
799 APInt operator<<(unsigned Bits) const { return shl(Bits); }
800
801 /// Left logical shift operator.
802 ///
803 /// Shifts this APInt left by \p Bits and returns the result.
804 APInt operator<<(const APInt &Bits) const { return shl(Bits); }
805
806 /// Arithmetic right-shift function.
807 ///
808 /// Arithmetic right-shift this APInt by shiftAmt.
809 APInt ashr(unsigned ShiftAmt) const {
810 APInt R(*this);
811 R.ashrInPlace(ShiftAmt);
812 return R;
813 }
814
815 /// Arithmetic right-shift this APInt by ShiftAmt in place.
816 void ashrInPlace(unsigned ShiftAmt) {
817 assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth &&
"Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 817, __extension__ __PRETTY_FUNCTION__
))
;
818 if (isSingleWord()) {
819 int64_t SExtVAL = SignExtend64(U.VAL, BitWidth);
820 if (ShiftAmt == BitWidth)
821 U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit.
822 else
823 U.VAL = SExtVAL >> ShiftAmt;
824 clearUnusedBits();
825 return;
826 }
827 ashrSlowCase(ShiftAmt);
828 }
829
830 /// Logical right-shift function.
831 ///
832 /// Logical right-shift this APInt by shiftAmt.
833 APInt lshr(unsigned shiftAmt) const {
834 APInt R(*this);
835 R.lshrInPlace(shiftAmt);
836 return R;
837 }
838
839 /// Logical right-shift this APInt by ShiftAmt in place.
840 void lshrInPlace(unsigned ShiftAmt) {
841 assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth &&
"Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 841, __extension__ __PRETTY_FUNCTION__
))
;
842 if (isSingleWord()) {
843 if (ShiftAmt == BitWidth)
844 U.VAL = 0;
845 else
846 U.VAL >>= ShiftAmt;
847 return;
848 }
849 lshrSlowCase(ShiftAmt);
850 }
851
852 /// Left-shift function.
853 ///
854 /// Left-shift this APInt by shiftAmt.
855 APInt shl(unsigned shiftAmt) const {
856 APInt R(*this);
857 R <<= shiftAmt;
858 return R;
859 }
860
861 /// relative logical shift right
862 APInt relativeLShr(int RelativeShift) const {
863 return RelativeShift > 0 ? lshr(RelativeShift) : shl(-RelativeShift);
864 }
865
866 /// relative logical shift left
867 APInt relativeLShl(int RelativeShift) const {
868 return relativeLShr(-RelativeShift);
869 }
870
871 /// relative arithmetic shift right
872 APInt relativeAShr(int RelativeShift) const {
873 return RelativeShift > 0 ? ashr(RelativeShift) : shl(-RelativeShift);
874 }
875
876 /// relative arithmetic shift left
877 APInt relativeAShl(int RelativeShift) const {
878 return relativeAShr(-RelativeShift);
879 }
880
881 /// Rotate left by rotateAmt.
882 APInt rotl(unsigned rotateAmt) const;
883
884 /// Rotate right by rotateAmt.
885 APInt rotr(unsigned rotateAmt) const;
886
887 /// Arithmetic right-shift function.
888 ///
889 /// Arithmetic right-shift this APInt by shiftAmt.
890 APInt ashr(const APInt &ShiftAmt) const {
891 APInt R(*this);
892 R.ashrInPlace(ShiftAmt);
893 return R;
894 }
895
896 /// Arithmetic right-shift this APInt by shiftAmt in place.
897 void ashrInPlace(const APInt &shiftAmt);
898
899 /// Logical right-shift function.
900 ///
901 /// Logical right-shift this APInt by shiftAmt.
902 APInt lshr(const APInt &ShiftAmt) const {
903 APInt R(*this);
904 R.lshrInPlace(ShiftAmt);
905 return R;
906 }
907
908 /// Logical right-shift this APInt by ShiftAmt in place.
909 void lshrInPlace(const APInt &ShiftAmt);
910
911 /// Left-shift function.
912 ///
913 /// Left-shift this APInt by shiftAmt.
914 APInt shl(const APInt &ShiftAmt) const {
915 APInt R(*this);
916 R <<= ShiftAmt;
917 return R;
918 }
919
920 /// Rotate left by rotateAmt.
921 APInt rotl(const APInt &rotateAmt) const;
922
923 /// Rotate right by rotateAmt.
924 APInt rotr(const APInt &rotateAmt) const;
925
926 /// Concatenate the bits from "NewLSB" onto the bottom of *this. This is
927 /// equivalent to:
928 /// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)
929 APInt concat(const APInt &NewLSB) const {
930 /// If the result will be small, then both the merged values are small.
931 unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();
932 if (NewWidth <= APINT_BITS_PER_WORD)
933 return APInt(NewWidth, (U.VAL << NewLSB.getBitWidth()) | NewLSB.U.VAL);
934 return concatSlowCase(NewLSB);
935 }
936
937 /// Unsigned division operation.
938 ///
939 /// Perform an unsigned divide operation on this APInt by RHS. Both this and
940 /// RHS are treated as unsigned quantities for purposes of this division.
941 ///
942 /// \returns a new APInt value containing the division result, rounded towards
943 /// zero.
944 APInt udiv(const APInt &RHS) const;
945 APInt udiv(uint64_t RHS) const;
946
947 /// Signed division function for APInt.
948 ///
949 /// Signed divide this APInt by APInt RHS.
950 ///
951 /// The result is rounded towards zero.
952 APInt sdiv(const APInt &RHS) const;
953 APInt sdiv(int64_t RHS) const;
954
955 /// Unsigned remainder operation.
956 ///
957 /// Perform an unsigned remainder operation on this APInt with RHS being the
958 /// divisor. Both this and RHS are treated as unsigned quantities for purposes
959 /// of this operation. Note that this is a true remainder operation and not a
960 /// modulo operation because the sign follows the sign of the dividend which
961 /// is *this.
962 ///
963 /// \returns a new APInt value containing the remainder result
964 APInt urem(const APInt &RHS) const;
965 uint64_t urem(uint64_t RHS) const;
966
967 /// Function for signed remainder operation.
968 ///
969 /// Signed remainder operation on APInt.
970 APInt srem(const APInt &RHS) const;
971 int64_t srem(int64_t RHS) const;
972
973 /// Dual division/remainder interface.
974 ///
975 /// Sometimes it is convenient to divide two APInt values and obtain both the
976 /// quotient and remainder. This function does both operations in the same
977 /// computation making it a little more efficient. The pair of input arguments
978 /// may overlap with the pair of output arguments. It is safe to call
979 /// udivrem(X, Y, X, Y), for example.
980 static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
981 APInt &Remainder);
982 static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
983 uint64_t &Remainder);
984
985 static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
986 APInt &Remainder);
987 static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
988 int64_t &Remainder);
989
990 // Operations that return overflow indicators.
991 APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
992 APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
993 APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
994 APInt usub_ov(const APInt &RHS, bool &Overflow) const;
995 APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
996 APInt smul_ov(const APInt &RHS, bool &Overflow) const;
997 APInt umul_ov(const APInt &RHS, bool &Overflow) const;
998 APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
999 APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
1000
1001 // Operations that saturate
1002 APInt sadd_sat(const APInt &RHS) const;
1003 APInt uadd_sat(const APInt &RHS) const;
1004 APInt ssub_sat(const APInt &RHS) const;
1005 APInt usub_sat(const APInt &RHS) const;
1006 APInt smul_sat(const APInt &RHS) const;
1007 APInt umul_sat(const APInt &RHS) const;
1008 APInt sshl_sat(const APInt &RHS) const;
1009 APInt ushl_sat(const APInt &RHS) const;
1010
1011 /// Array-indexing support.
1012 ///
1013 /// \returns the bit value at bitPosition
1014 bool operator[](unsigned bitPosition) const {
1015 assert(bitPosition < getBitWidth() && "Bit position out of bounds!")(static_cast <bool> (bitPosition < getBitWidth() &&
"Bit position out of bounds!") ? void (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\""
, "llvm/include/llvm/ADT/APInt.h", 1015, __extension__ __PRETTY_FUNCTION__
))
;
1016 return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
1017 }
1018
1019 /// @}
1020 /// \name Comparison Operators
1021 /// @{
1022
1023 /// Equality operator.
1024 ///
1025 /// Compares this APInt with RHS for the validity of the equality
1026 /// relationship.
1027 bool operator==(const APInt &RHS) const {
1028 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Comparison requires equal bit widths") ? void (0) : __assert_fail
("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\""
, "llvm/include/llvm/ADT/APInt.h", 1028, __extension__ __PRETTY_FUNCTION__
))
;
1029 if (isSingleWord())
1030 return U.VAL == RHS.U.VAL;
1031 return equalSlowCase(RHS);
1032 }
1033
1034 /// Equality operator.
1035 ///
1036 /// Compares this APInt with a uint64_t for the validity of the equality
1037 /// relationship.
1038 ///
1039 /// \returns true if *this == Val
1040 bool operator==(uint64_t Val) const {
1041 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
1042 }
1043
1044 /// Equality comparison.
1045 ///
1046 /// Compares this APInt with RHS for the validity of the equality
1047 /// relationship.
1048 ///
1049 /// \returns true if *this == Val
1050 bool eq(const APInt &RHS) const { return (*this) == RHS; }
1051
1052 /// Inequality operator.
1053 ///
1054 /// Compares this APInt with RHS for the validity of the inequality
1055 /// relationship.
1056 ///
1057 /// \returns true if *this != Val
1058 bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }
1059
1060 /// Inequality operator.
1061 ///
1062 /// Compares this APInt with a uint64_t for the validity of the inequality
1063 /// relationship.
1064 ///
1065 /// \returns true if *this != Val
1066 bool operator!=(uint64_t Val) const { return !((*this) == Val); }
1067
1068 /// Inequality comparison
1069 ///
1070 /// Compares this APInt with RHS for the validity of the inequality
1071 /// relationship.
1072 ///
1073 /// \returns true if *this != Val
1074 bool ne(const APInt &RHS) const { return !((*this) == RHS); }
1075
1076 /// Unsigned less than comparison
1077 ///
1078 /// Regards both *this and RHS as unsigned quantities and compares them for
1079 /// the validity of the less-than relationship.
1080 ///
1081 /// \returns true if *this < RHS when both are considered unsigned.
1082 bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
1083
1084 /// Unsigned less than comparison
1085 ///
1086 /// Regards both *this as an unsigned quantity and compares it with RHS for
1087 /// the validity of the less-than relationship.
1088 ///
1089 /// \returns true if *this < RHS when considered unsigned.
1090 bool ult(uint64_t RHS) const {
1091 // Only need to check active bits if not a single word.
1092 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
1093 }
1094
1095 /// Signed less than comparison
1096 ///
1097 /// Regards both *this and RHS as signed quantities and compares them for
1098 /// validity of the less-than relationship.
1099 ///
1100 /// \returns true if *this < RHS when both are considered signed.
1101 bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
1102
1103 /// Signed less than comparison
1104 ///
1105 /// Regards both *this as a signed quantity and compares it with RHS for
1106 /// the validity of the less-than relationship.
1107 ///
1108 /// \returns true if *this < RHS when considered signed.
1109 bool slt(int64_t RHS) const {
1110 return (!isSingleWord() && getSignificantBits() > 64)
1111 ? isNegative()
1112 : getSExtValue() < RHS;
1113 }
1114
1115 /// Unsigned less or equal comparison
1116 ///
1117 /// Regards both *this and RHS as unsigned quantities and compares them for
1118 /// validity of the less-or-equal relationship.
1119 ///
1120 /// \returns true if *this <= RHS when both are considered unsigned.
1121 bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
1122
1123 /// Unsigned less or equal comparison
1124 ///
1125 /// Regards both *this as an unsigned quantity and compares it with RHS for
1126 /// the validity of the less-or-equal relationship.
1127 ///
1128 /// \returns true if *this <= RHS when considered unsigned.
1129 bool ule(uint64_t RHS) const { return !ugt(RHS); }
1130
1131 /// Signed less or equal comparison
1132 ///
1133 /// Regards both *this and RHS as signed quantities and compares them for
1134 /// validity of the less-or-equal relationship.
1135 ///
1136 /// \returns true if *this <= RHS when both are considered signed.
1137 bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
1138
1139 /// Signed less or equal comparison
1140 ///
1141 /// Regards both *this as a signed quantity and compares it with RHS for the
1142 /// validity of the less-or-equal relationship.
1143 ///
1144 /// \returns true if *this <= RHS when considered signed.
1145 bool sle(uint64_t RHS) const { return !sgt(RHS); }
1146
1147 /// Unsigned greater than comparison
1148 ///
1149 /// Regards both *this and RHS as unsigned quantities and compares them for
1150 /// the validity of the greater-than relationship.
1151 ///
1152 /// \returns true if *this > RHS when both are considered unsigned.
1153 bool ugt(const APInt &RHS) const { return !ule(RHS); }
1154
1155 /// Unsigned greater than comparison
1156 ///
1157 /// Regards both *this as an unsigned quantity and compares it with RHS for
1158 /// the validity of the greater-than relationship.
1159 ///
1160 /// \returns true if *this > RHS when considered unsigned.
1161 bool ugt(uint64_t RHS) const {
1162 // Only need to check active bits if not a single word.
1163 return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
1164 }
1165
1166 /// Signed greater than comparison
1167 ///
1168 /// Regards both *this and RHS as signed quantities and compares them for the
1169 /// validity of the greater-than relationship.
1170 ///
1171 /// \returns true if *this > RHS when both are considered signed.
1172 bool sgt(const APInt &RHS) const { return !sle(RHS); }
1173
1174 /// Signed greater than comparison
1175 ///
1176 /// Regards both *this as a signed quantity and compares it with RHS for
1177 /// the validity of the greater-than relationship.
1178 ///
1179 /// \returns true if *this > RHS when considered signed.
1180 bool sgt(int64_t RHS) const {
1181 return (!isSingleWord() && getSignificantBits() > 64)
1182 ? !isNegative()
1183 : getSExtValue() > RHS;
1184 }
1185
1186 /// Unsigned greater or equal comparison
1187 ///
1188 /// Regards both *this and RHS as unsigned quantities and compares them for
1189 /// validity of the greater-or-equal relationship.
1190 ///
1191 /// \returns true if *this >= RHS when both are considered unsigned.
1192 bool uge(const APInt &RHS) const { return !ult(RHS); }
1193
1194 /// Unsigned greater or equal comparison
1195 ///
1196 /// Regards both *this as an unsigned quantity and compares it with RHS for
1197 /// the validity of the greater-or-equal relationship.
1198 ///
1199 /// \returns true if *this >= RHS when considered unsigned.
1200 bool uge(uint64_t RHS) const { return !ult(RHS); }
1201
1202 /// Signed greater or equal comparison
1203 ///
1204 /// Regards both *this and RHS as signed quantities and compares them for
1205 /// validity of the greater-or-equal relationship.
1206 ///
1207 /// \returns true if *this >= RHS when both are considered signed.
1208 bool sge(const APInt &RHS) const { return !slt(RHS); }
1209
1210 /// Signed greater or equal comparison
1211 ///
1212 /// Regards both *this as a signed quantity and compares it with RHS for
1213 /// the validity of the greater-or-equal relationship.
1214 ///
1215 /// \returns true if *this >= RHS when considered signed.
1216 bool sge(int64_t RHS) const { return !slt(RHS); }
1217
1218 /// This operation tests if there are any pairs of corresponding bits
1219 /// between this APInt and RHS that are both set.
1220 bool intersects(const APInt &RHS) const {
1221 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 1221, __extension__ __PRETTY_FUNCTION__
))
;
1222 if (isSingleWord())
1223 return (U.VAL & RHS.U.VAL) != 0;
1224 return intersectsSlowCase(RHS);
1225 }
1226
1227 /// This operation checks that all bits set in this APInt are also set in RHS.
1228 bool isSubsetOf(const APInt &RHS) const {
1229 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 1229, __extension__ __PRETTY_FUNCTION__
))
;
1230 if (isSingleWord())
1231 return (U.VAL & ~RHS.U.VAL) == 0;
1232 return isSubsetOfSlowCase(RHS);
1233 }
1234
1235 /// @}
1236 /// \name Resizing Operators
1237 /// @{
1238
1239 /// Truncate to new width.
1240 ///
1241 /// Truncate the APInt to a specified width. It is an error to specify a width
1242 /// that is greater than the current width.
1243 APInt trunc(unsigned width) const;
1244
1245 /// Truncate to new width with unsigned saturation.
1246 ///
1247 /// If the APInt, treated as unsigned integer, can be losslessly truncated to
1248 /// the new bitwidth, then return truncated APInt. Else, return max value.
1249 APInt truncUSat(unsigned width) const;
1250
1251 /// Truncate to new width with signed saturation.
1252 ///
1253 /// If this APInt, treated as signed integer, can be losslessly truncated to
1254 /// the new bitwidth, then return truncated APInt. Else, return either
1255 /// signed min value if the APInt was negative, or signed max value.
1256 APInt truncSSat(unsigned width) const;
1257
1258 /// Sign extend to a new width.
1259 ///
1260 /// This operation sign extends the APInt to a new width. If the high order
1261 /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1262 /// It is an error to specify a width that is less than the
1263 /// current width.
1264 APInt sext(unsigned width) const;
1265
1266 /// Zero extend to a new width.
1267 ///
1268 /// This operation zero extends the APInt to a new width. The high order bits
1269 /// are filled with 0 bits. It is an error to specify a width that is less
1270 /// than the current width.
1271 APInt zext(unsigned width) const;
1272
1273 /// Sign extend or truncate to width
1274 ///
1275 /// Make this APInt have the bit width given by \p width. The value is sign
1276 /// extended, truncated, or left alone to make it that width.
1277 APInt sextOrTrunc(unsigned width) const;
1278
1279 /// Zero extend or truncate to width
1280 ///
1281 /// Make this APInt have the bit width given by \p width. The value is zero
1282 /// extended, truncated, or left alone to make it that width.
1283 APInt zextOrTrunc(unsigned width) const;
1284
1285 /// @}
1286 /// \name Bit Manipulation Operators
1287 /// @{
1288
1289 /// Set every bit to 1.
1290 void setAllBits() {
1291 if (isSingleWord())
1292 U.VAL = WORDTYPE_MAX;
1293 else
1294 // Set all the bits in all the words.
1295 memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
1296 // Clear the unused ones
1297 clearUnusedBits();
1298 }
1299
1300 /// Set the given bit to 1 whose position is given as "bitPosition".
1301 void setBit(unsigned BitPosition) {
1302 assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition < BitWidth &&
"BitPosition out of range") ? void (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1302, __extension__ __PRETTY_FUNCTION__
))
;
1303 WordType Mask = maskBit(BitPosition);
1304 if (isSingleWord())
1305 U.VAL |= Mask;
1306 else
1307 U.pVal[whichWord(BitPosition)] |= Mask;
1308 }
1309
1310 /// Set the sign bit to 1.
1311 void setSignBit() { setBit(BitWidth - 1); }
1312
1313 /// Set a given bit to a given value.
1314 void setBitVal(unsigned BitPosition, bool BitValue) {
1315 if (BitValue)
1316 setBit(BitPosition);
1317 else
1318 clearBit(BitPosition);
1319 }
1320
1321 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1322 /// This function handles "wrap" case when \p loBit >= \p hiBit, and calls
1323 /// setBits when \p loBit < \p hiBit.
1324 /// For \p loBit == \p hiBit wrap case, set every bit to 1.
1325 void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
1326 assert(hiBit <= BitWidth && "hiBit out of range")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range"
) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1326, __extension__ __PRETTY_FUNCTION__
))
;
1327 assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range"
) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1327, __extension__ __PRETTY_FUNCTION__
))
;
1328 if (loBit < hiBit) {
1329 setBits(loBit, hiBit);
1330 return;
1331 }
1332 setLowBits(hiBit);
1333 setHighBits(BitWidth - loBit);
1334 }
1335
1336 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1337 /// This function handles case when \p loBit <= \p hiBit.
1338 void setBits(unsigned loBit, unsigned hiBit) {
1339 assert(hiBit <= BitWidth && "hiBit out of range")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range"
) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1339, __extension__ __PRETTY_FUNCTION__
))
;
1340 assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range"
) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1340, __extension__ __PRETTY_FUNCTION__
))
;
1341 assert(loBit <= hiBit && "loBit greater than hiBit")(static_cast <bool> (loBit <= hiBit && "loBit greater than hiBit"
) ? void (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\""
, "llvm/include/llvm/ADT/APInt.h", 1341, __extension__ __PRETTY_FUNCTION__
))
;
1342 if (loBit == hiBit)
1343 return;
1344 if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1345 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1346 mask <<= loBit;
1347 if (isSingleWord())
1348 U.VAL |= mask;
1349 else
1350 U.pVal[0] |= mask;
1351 } else {
1352 setBitsSlowCase(loBit, hiBit);
1353 }
1354 }
1355
1356 /// Set the top bits starting from loBit.
1357 void setBitsFrom(unsigned loBit) { return setBits(loBit, BitWidth); }
1358
1359 /// Set the bottom loBits bits.
1360 void setLowBits(unsigned loBits) { return setBits(0, loBits); }
1361
1362 /// Set the top hiBits bits.
1363 void setHighBits(unsigned hiBits) {
1364 return setBits(BitWidth - hiBits, BitWidth);
1365 }
1366
1367 /// Set every bit to 0.
1368 void clearAllBits() {
1369 if (isSingleWord())
1370 U.VAL = 0;
1371 else
1372 memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1373 }
1374
1375 /// Set a given bit to 0.
1376 ///
1377 /// Set the given bit to 0 whose position is given as "bitPosition".
1378 void clearBit(unsigned BitPosition) {
1379 assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition < BitWidth &&
"BitPosition out of range") ? void (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1379, __extension__ __PRETTY_FUNCTION__
))
;
1380 WordType Mask = ~maskBit(BitPosition);
1381 if (isSingleWord())
1382 U.VAL &= Mask;
1383 else
1384 U.pVal[whichWord(BitPosition)] &= Mask;
1385 }
1386
1387 /// Set bottom loBits bits to 0.
1388 void clearLowBits(unsigned loBits) {
1389 assert(loBits <= BitWidth && "More bits than bitwidth")(static_cast <bool> (loBits <= BitWidth && "More bits than bitwidth"
) ? void (0) : __assert_fail ("loBits <= BitWidth && \"More bits than bitwidth\""
, "llvm/include/llvm/ADT/APInt.h", 1389, __extension__ __PRETTY_FUNCTION__
))
;
1390 APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
1391 *this &= Keep;
1392 }
1393
1394 /// Set the sign bit to 0.
1395 void clearSignBit() { clearBit(BitWidth - 1); }
1396
1397 /// Toggle every bit to its opposite value.
1398 void flipAllBits() {
1399 if (isSingleWord()) {
1400 U.VAL ^= WORDTYPE_MAX;
1401 clearUnusedBits();
1402 } else {
1403 flipAllBitsSlowCase();
1404 }
1405 }
1406
1407 /// Toggles a given bit to its opposite value.
1408 ///
1409 /// Toggle a given bit to its opposite value whose position is given
1410 /// as "bitPosition".
1411 void flipBit(unsigned bitPosition);
1412
1413 /// Negate this APInt in place.
1414 void negate() {
1415 flipAllBits();
1416 ++(*this);
1417 }
1418
1419 /// Insert the bits from a smaller APInt starting at bitPosition.
1420 void insertBits(const APInt &SubBits, unsigned bitPosition);
1421 void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);
1422
1423 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1424 APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1425 uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;
1426
1427 /// @}
1428 /// \name Value Characterization Functions
1429 /// @{
1430
1431 /// Return the number of bits in the APInt.
1432 unsigned getBitWidth() const { return BitWidth; }
1433
1434 /// Get the number of words.
1435 ///
1436 /// Here one word's bitwidth equals to that of uint64_t.
1437 ///
1438 /// \returns the number of words to hold the integer value of this APInt.
1439 unsigned getNumWords() const { return getNumWords(BitWidth); }
1440
1441 /// Get the number of words.
1442 ///
1443 /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1444 ///
1445 /// \returns the number of words to hold the integer value with a given bit
1446 /// width.
1447 static unsigned getNumWords(unsigned BitWidth) {
1448 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1449 }
1450
1451 /// Compute the number of active bits in the value
1452 ///
1453 /// This function returns the number of active bits which is defined as the
1454 /// bit width minus the number of leading zeros. This is used in several
1455 /// computations to see how "wide" the value is.
1456 unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1457
1458 /// Compute the number of active words in the value of this APInt.
1459 ///
1460 /// This is used in conjunction with getActiveData to extract the raw value of
1461 /// the APInt.
1462 unsigned getActiveWords() const {
1463 unsigned numActiveBits = getActiveBits();
1464 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1465 }
1466
1467 /// Get the minimum bit size for this signed APInt
1468 ///
1469 /// Computes the minimum bit width for this APInt while considering it to be a
1470 /// signed (and probably negative) value. If the value is not negative, this
1471 /// function returns the same value as getActiveBits()+1. Otherwise, it
1472 /// returns the smallest bit width that will retain the negative value. For
1473 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1474 /// for -1, this function will always return 1.
1475 unsigned getSignificantBits() const {
1476 return BitWidth - getNumSignBits() + 1;
1477 }
1478
1479 /// NOTE: This is soft-deprecated. Please use `getSignificantBits()` instead.
1480 unsigned getMinSignedBits() const { return getSignificantBits(); }
1481
1482 /// Get zero extended value
1483 ///
1484 /// This method attempts to return the value of this APInt as a zero extended
1485 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1486 /// uint64_t. Otherwise an assertion will result.
1487 uint64_t getZExtValue() const {
1488 if (isSingleWord())
1489 return U.VAL;
1490 assert(getActiveBits() <= 64 && "Too many bits for uint64_t")(static_cast <bool> (getActiveBits() <= 64 &&
"Too many bits for uint64_t") ? void (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\""
, "llvm/include/llvm/ADT/APInt.h", 1490, __extension__ __PRETTY_FUNCTION__
))
;
1491 return U.pVal[0];
1492 }
1493
1494 /// Get sign extended value
1495 ///
1496 /// This method attempts to return the value of this APInt as a sign extended
1497 /// int64_t. The bit width must be <= 64 or the value must fit within an
1498 /// int64_t. Otherwise an assertion will result.
1499 int64_t getSExtValue() const {
1500 if (isSingleWord())
1501 return SignExtend64(U.VAL, BitWidth);
1502 assert(getSignificantBits() <= 64 && "Too many bits for int64_t")(static_cast <bool> (getSignificantBits() <= 64 &&
"Too many bits for int64_t") ? void (0) : __assert_fail ("getSignificantBits() <= 64 && \"Too many bits for int64_t\""
, "llvm/include/llvm/ADT/APInt.h", 1502, __extension__ __PRETTY_FUNCTION__
))
;
1503 return int64_t(U.pVal[0]);
1504 }
1505
1506 /// Get bits required for string value.
1507 ///
1508 /// This method determines how many bits are required to hold the APInt
1509 /// equivalent of the string given by \p str.
1510 static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1511
1512 /// Get the bits that are sufficient to represent the string value. This may
1513 /// over estimate the amount of bits required, but it does not require
1514 /// parsing the value in the string.
1515 static unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix);
1516
1517 /// The APInt version of the countLeadingZeros functions in
1518 /// MathExtras.h.
1519 ///
1520 /// It counts the number of zeros from the most significant bit to the first
1521 /// one bit.
1522 ///
1523 /// \returns BitWidth if the value is zero, otherwise returns the number of
1524 /// zeros from the most significant bit to the first one bits.
1525 unsigned countLeadingZeros() const {
1526 if (isSingleWord()) {
1527 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1528 return llvm::countLeadingZeros(U.VAL) - unusedBits;
1529 }
1530 return countLeadingZerosSlowCase();
1531 }
1532
1533 /// Count the number of leading one bits.
1534 ///
1535 /// This function is an APInt version of the countLeadingOnes
1536 /// functions in MathExtras.h. It counts the number of ones from the most
1537 /// significant bit to the first zero bit.
1538 ///
1539 /// \returns 0 if the high order bit is not set, otherwise returns the number
1540 /// of 1 bits from the most significant to the least
1541 unsigned countLeadingOnes() const {
1542 if (isSingleWord()) {
1543 if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
1544 return 0;
1545 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1546 }
1547 return countLeadingOnesSlowCase();
1548 }
1549
1550 /// Computes the number of leading bits of this APInt that are equal to its
1551 /// sign bit.
1552 unsigned getNumSignBits() const {
1553 return isNegative() ? countLeadingOnes() : countLeadingZeros();
1554 }
1555
1556 /// Count the number of trailing zero bits.
1557 ///
1558 /// This function is an APInt version of the countTrailingZeros
1559 /// functions in MathExtras.h. It counts the number of zeros from the least
1560 /// significant bit to the first set bit.
1561 ///
1562 /// \returns BitWidth if the value is zero, otherwise returns the number of
1563 /// zeros from the least significant bit to the first one bit.
1564 unsigned countTrailingZeros() const {
1565 if (isSingleWord()) {
1566 unsigned TrailingZeros = llvm::countTrailingZeros(U.VAL);
1567 return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros);
1568 }
1569 return countTrailingZerosSlowCase();
1570 }
1571
1572 /// Count the number of trailing one bits.
1573 ///
1574 /// This function is an APInt version of the countTrailingOnes
1575 /// functions in MathExtras.h. It counts the number of ones from the least
1576 /// significant bit to the first zero bit.
1577 ///
1578 /// \returns BitWidth if the value is all ones, otherwise returns the number
1579 /// of ones from the least significant bit to the first zero bit.
1580 unsigned countTrailingOnes() const {
1581 if (isSingleWord())
1582 return llvm::countTrailingOnes(U.VAL);
1583 return countTrailingOnesSlowCase();
1584 }
1585
1586 /// Count the number of bits set.
1587 ///
1588 /// This function is an APInt version of the countPopulation functions
1589 /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1590 ///
1591 /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1592 unsigned countPopulation() const {
1593 if (isSingleWord())
1594 return llvm::countPopulation(U.VAL);
1595 return countPopulationSlowCase();
1596 }
1597
1598 /// @}
1599 /// \name Conversion Functions
1600 /// @{
1601 void print(raw_ostream &OS, bool isSigned) const;
1602
1603 /// Converts an APInt to a string and append it to Str. Str is commonly a
1604 /// SmallString.
1605 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1606 bool formatAsCLiteral = false) const;
1607
1608 /// Considers the APInt to be unsigned and converts it into a string in the
1609 /// radix given. The radix can be 2, 8, 10 16, or 36.
1610 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1611 toString(Str, Radix, false, false);
1612 }
1613
1614 /// Considers the APInt to be signed and converts it into a string in the
1615 /// radix given. The radix can be 2, 8, 10, 16, or 36.
1616 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1617 toString(Str, Radix, true, false);
1618 }
1619
1620 /// \returns a byte-swapped representation of this APInt Value.
1621 APInt byteSwap() const;
1622
1623 /// \returns the value with the bit representation reversed of this APInt
1624 /// Value.
1625 APInt reverseBits() const;
1626
1627 /// Converts this APInt to a double value.
1628 double roundToDouble(bool isSigned) const;
1629
1630 /// Converts this unsigned APInt to a double value.
1631 double roundToDouble() const { return roundToDouble(false); }
1632
1633 /// Converts this signed APInt to a double value.
1634 double signedRoundToDouble() const { return roundToDouble(true); }
1635
1636 /// Converts APInt bits to a double
1637 ///
1638 /// The conversion does not do a translation from integer to double, it just
1639 /// re-interprets the bits as a double. Note that it is valid to do this on
1640 /// any bit width. Exactly 64 bits will be translated.
1641 double bitsToDouble() const { return BitsToDouble(getWord(0)); }
1642
1643 /// Converts APInt bits to a float
1644 ///
1645 /// The conversion does not do a translation from integer to float, it just
1646 /// re-interprets the bits as a float. Note that it is valid to do this on
1647 /// any bit width. Exactly 32 bits will be translated.
1648 float bitsToFloat() const {
1649 return BitsToFloat(static_cast<uint32_t>(getWord(0)));
1650 }
1651
1652 /// Converts a double to APInt bits.
1653 ///
1654 /// The conversion does not do a translation from double to integer, it just
1655 /// re-interprets the bits of the double.
1656 static APInt doubleToBits(double V) {
1657 return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
1658 }
1659
1660 /// Converts a float to APInt bits.
1661 ///
1662 /// The conversion does not do a translation from float to integer, it just
1663 /// re-interprets the bits of the float.
1664 static APInt floatToBits(float V) {
1665 return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
1666 }
1667
1668 /// @}
1669 /// \name Mathematics Operations
1670 /// @{
1671
1672 /// \returns the floor log base 2 of this APInt.
1673 unsigned logBase2() const { return getActiveBits() - 1; }
1674
1675 /// \returns the ceil log base 2 of this APInt.
1676 unsigned ceilLogBase2() const {
1677 APInt temp(*this);
1678 --temp;
1679 return temp.getActiveBits();
1680 }
1681
1682 /// \returns the nearest log base 2 of this APInt. Ties round up.
1683 ///
1684 /// NOTE: When we have a BitWidth of 1, we define:
1685 ///
1686 /// log2(0) = UINT32_MAX
1687 /// log2(1) = 0
1688 ///
1689 /// to get around any mathematical concerns resulting from
1690 /// referencing 2 in a space where 2 does no exist.
1691 unsigned nearestLogBase2() const;
1692
1693 /// \returns the log base 2 of this APInt if its an exact power of two, -1
1694 /// otherwise
1695 int32_t exactLogBase2() const {
1696 if (!isPowerOf2())
1697 return -1;
1698 return logBase2();
1699 }
1700
1701 /// Compute the square root.
1702 APInt sqrt() const;
1703
1704 /// Get the absolute value. If *this is < 0 then return -(*this), otherwise
1705 /// *this. Note that the "most negative" signed number (e.g. -128 for 8 bit
1706 /// wide APInt) is unchanged due to how negation works.
1707 APInt abs() const {
1708 if (isNegative())
1709 return -(*this);
1710 return *this;
1711 }
1712
1713 /// \returns the multiplicative inverse for a given modulo.
1714 APInt multiplicativeInverse(const APInt &modulo) const;
1715
1716 /// @}
1717 /// \name Building-block Operations for APInt and APFloat
1718 /// @{
1719
1720 // These building block operations operate on a representation of arbitrary
1721 // precision, two's-complement, bignum integer values. They should be
1722 // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1723 // generally a pointer to the base of an array of integer parts, representing
1724 // an unsigned bignum, and a count of how many parts there are.
1725
1726 /// Sets the least significant part of a bignum to the input value, and zeroes
1727 /// out higher parts.
1728 static void tcSet(WordType *, WordType, unsigned);
1729
1730 /// Assign one bignum to another.
1731 static void tcAssign(WordType *, const WordType *, unsigned);
1732
1733 /// Returns true if a bignum is zero, false otherwise.
1734 static bool tcIsZero(const WordType *, unsigned);
1735
1736 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1737 static int tcExtractBit(const WordType *, unsigned bit);
1738
1739 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1740 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1741 /// significant bit of DST. All high bits above srcBITS in DST are
1742 /// zero-filled.
1743 static void tcExtract(WordType *, unsigned dstCount, const WordType *,
1744 unsigned srcBits, unsigned srcLSB);
1745
1746 /// Set the given bit of a bignum. Zero-based.
1747 static void tcSetBit(WordType *, unsigned bit);
1748
1749 /// Clear the given bit of a bignum. Zero-based.
1750 static void tcClearBit(WordType *, unsigned bit);
1751
1752 /// Returns the bit number of the least or most significant set bit of a
1753 /// number. If the input number has no bits set -1U is returned.
1754 static unsigned tcLSB(const WordType *, unsigned n);
1755 static unsigned tcMSB(const WordType *parts, unsigned n);
1756
1757 /// Negate a bignum in-place.
1758 static void tcNegate(WordType *, unsigned);
1759
1760 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1761 static WordType tcAdd(WordType *, const WordType *, WordType carry, unsigned);
1762 /// DST += RHS. Returns the carry flag.
1763 static WordType tcAddPart(WordType *, WordType, unsigned);
1764
1765 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1766 static WordType tcSubtract(WordType *, const WordType *, WordType carry,
1767 unsigned);
1768 /// DST -= RHS. Returns the carry flag.
1769 static WordType tcSubtractPart(WordType *, WordType, unsigned);
1770
1771 /// DST += SRC * MULTIPLIER + PART if add is true
1772 /// DST = SRC * MULTIPLIER + PART if add is false
1773 ///
1774 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1775 /// start at the same point, i.e. DST == SRC.
1776 ///
1777 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1778 /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1779 /// result, and if all of the omitted higher parts were zero return zero,
1780 /// otherwise overflow occurred and return one.
1781 static int tcMultiplyPart(WordType *dst, const WordType *src,
1782 WordType multiplier, WordType carry,
1783 unsigned srcParts, unsigned dstParts, bool add);
1784
1785 /// DST = LHS * RHS, where DST has the same width as the operands and is
1786 /// filled with the least significant parts of the result. Returns one if
1787 /// overflow occurred, otherwise zero. DST must be disjoint from both
1788 /// operands.
1789 static int tcMultiply(WordType *, const WordType *, const WordType *,
1790 unsigned);
1791
1792 /// DST = LHS * RHS, where DST has width the sum of the widths of the
1793 /// operands. No overflow occurs. DST must be disjoint from both operands.
1794 static void tcFullMultiply(WordType *, const WordType *, const WordType *,
1795 unsigned, unsigned);
1796
1797 /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1798 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1799 /// REMAINDER to the remainder, return zero. i.e.
1800 ///
1801 /// OLD_LHS = RHS * LHS + REMAINDER
1802 ///
1803 /// SCRATCH is a bignum of the same size as the operands and result for use by
1804 /// the routine; its contents need not be initialized and are destroyed. LHS,
1805 /// REMAINDER and SCRATCH must be distinct.
1806 static int tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder,
1807 WordType *scratch, unsigned parts);
1808
1809 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1810 /// restrictions on Count.
1811 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1812
1813 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1814 /// restrictions on Count.
1815 static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1816
1817 /// Comparison (unsigned) of two bignums.
1818 static int tcCompare(const WordType *, const WordType *, unsigned);
1819
1820 /// Increment a bignum in-place. Return the carry flag.
1821 static WordType tcIncrement(WordType *dst, unsigned parts) {
1822 return tcAddPart(dst, 1, parts);
1823 }
1824
1825 /// Decrement a bignum in-place. Return the borrow flag.
1826 static WordType tcDecrement(WordType *dst, unsigned parts) {
1827 return tcSubtractPart(dst, 1, parts);
1828 }
1829
1830 /// Used to insert APInt objects, or objects that contain APInt objects, into
1831 /// FoldingSets.
1832 void Profile(FoldingSetNodeID &id) const;
1833
1834 /// debug method
1835 void dump() const;
1836
1837 /// Returns whether this instance allocated memory.
1838 bool needsCleanup() const { return !isSingleWord(); }
1839
1840private:
1841 /// This union is used to store the integer value. When the
1842 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
1843 union {
1844 uint64_t VAL; ///< Used to store the <= 64 bits integer value.
1845 uint64_t *pVal; ///< Used to store the >64 bits integer value.
1846 } U;
1847
1848 unsigned BitWidth = 1; ///< The number of bits in this APInt.
1849
1850 friend struct DenseMapInfo<APInt, void>;
1851 friend class APSInt;
1852
1853 /// This constructor is used only internally for speed of construction of
1854 /// temporaries. It is unsafe since it takes ownership of the pointer, so it
1855 /// is not public.
1856 APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { U.pVal = val; }
1857
1858 /// Determine which word a bit is in.
1859 ///
1860 /// \returns the word position for the specified bit position.
1861 static unsigned whichWord(unsigned bitPosition) {
1862 return bitPosition / APINT_BITS_PER_WORD;
1863 }
1864
1865 /// Determine which bit in a word the specified bit position is in.
1866 static unsigned whichBit(unsigned bitPosition) {
1867 return bitPosition % APINT_BITS_PER_WORD;
1868 }
1869
1870 /// Get a single bit mask.
1871 ///
1872 /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
1873 /// This method generates and returns a uint64_t (word) mask for a single
1874 /// bit at a specific bit position. This is used to mask the bit in the
1875 /// corresponding word.
1876 static uint64_t maskBit(unsigned bitPosition) {
1877 return 1ULL << whichBit(bitPosition);
1878 }
1879
1880 /// Clear unused high order bits
1881 ///
1882 /// This method is used internally to clear the top "N" bits in the high order
1883 /// word that are not used by the APInt. This is needed after the most
1884 /// significant word is assigned a value to ensure that those bits are
1885 /// zero'd out.
1886 APInt &clearUnusedBits() {
1887 // Compute how many bits are used in the final word.
1888 unsigned WordBits = ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1;
1889
1890 // Mask out the high bits.
1891 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
1892 if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
1893 mask = 0;
1894
1895 if (isSingleWord())
1896 U.VAL &= mask;
1897 else
1898 U.pVal[getNumWords() - 1] &= mask;
1899 return *this;
1900 }
1901
1902 /// Get the word corresponding to a bit position
1903 /// \returns the corresponding word for the specified bit position.
1904 uint64_t getWord(unsigned bitPosition) const {
1905 return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
1906 }
1907
1908 /// Utility method to change the bit width of this APInt to new bit width,
1909 /// allocating and/or deallocating as necessary. There is no guarantee on the
1910 /// value of any bits upon return. Caller should populate the bits after.
1911 void reallocate(unsigned NewBitWidth);
1912
1913 /// Convert a char array into an APInt
1914 ///
1915 /// \param radix 2, 8, 10, 16, or 36
1916 /// Converts a string into a number. The string must be non-empty
1917 /// and well-formed as a number of the given base. The bit-width
1918 /// must be sufficient to hold the result.
1919 ///
1920 /// This is used by the constructors that take string arguments.
1921 ///
1922 /// StringRef::getAsInteger is superficially similar but (1) does
1923 /// not assume that the string is well-formed and (2) grows the
1924 /// result to hold the input.
1925 void fromString(unsigned numBits, StringRef str, uint8_t radix);
1926
1927 /// An internal division function for dividing APInts.
1928 ///
1929 /// This is used by the toString method to divide by the radix. It simply
1930 /// provides a more convenient form of divide for internal use since KnuthDiv
1931 /// has specific constraints on its inputs. If those constraints are not met
1932 /// then it provides a simpler form of divide.
1933 static void divide(const WordType *LHS, unsigned lhsWords,
1934 const WordType *RHS, unsigned rhsWords, WordType *Quotient,
1935 WordType *Remainder);
1936
1937 /// out-of-line slow case for inline constructor
1938 void initSlowCase(uint64_t val, bool isSigned);
1939
1940 /// shared code between two array constructors
1941 void initFromArray(ArrayRef<uint64_t> array);
1942
1943 /// out-of-line slow case for inline copy constructor
1944 void initSlowCase(const APInt &that);
1945
1946 /// out-of-line slow case for shl
1947 void shlSlowCase(unsigned ShiftAmt);
1948
1949 /// out-of-line slow case for lshr.
1950 void lshrSlowCase(unsigned ShiftAmt);
1951
1952 /// out-of-line slow case for ashr.
1953 void ashrSlowCase(unsigned ShiftAmt);
1954
1955 /// out-of-line slow case for operator=
1956 void assignSlowCase(const APInt &RHS);
1957
1958 /// out-of-line slow case for operator==
1959 bool equalSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
1960
1961 /// out-of-line slow case for countLeadingZeros
1962 unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
1963
1964 /// out-of-line slow case for countLeadingOnes.
1965 unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
1966
1967 /// out-of-line slow case for countTrailingZeros.
1968 unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
1969
1970 /// out-of-line slow case for countTrailingOnes
1971 unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
1972
1973 /// out-of-line slow case for countPopulation
1974 unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));
1975
1976 /// out-of-line slow case for intersects.
1977 bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
1978
1979 /// out-of-line slow case for isSubsetOf.
1980 bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
1981
1982 /// out-of-line slow case for setBits.
1983 void setBitsSlowCase(unsigned loBit, unsigned hiBit);
1984
1985 /// out-of-line slow case for flipAllBits.
1986 void flipAllBitsSlowCase();
1987
1988 /// out-of-line slow case for concat.
1989 APInt concatSlowCase(const APInt &NewLSB) const;
1990
1991 /// out-of-line slow case for operator&=.
1992 void andAssignSlowCase(const APInt &RHS);
1993
1994 /// out-of-line slow case for operator|=.
1995 void orAssignSlowCase(const APInt &RHS);
1996
1997 /// out-of-line slow case for operator^=.
1998 void xorAssignSlowCase(const APInt &RHS);
1999
2000 /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
2001 /// to, or greater than RHS.
2002 int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
2003
2004 /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
2005 /// to, or greater than RHS.
2006 int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
2007
2008 /// @}
2009};
2010
2011inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
2012
2013inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
2014
2015/// Unary bitwise complement operator.
2016///
2017/// \returns an APInt that is the bitwise complement of \p v.
2018inline APInt operator~(APInt v) {
2019 v.flipAllBits();
2020 return v;
2021}
2022
2023inline APInt operator&(APInt a, const APInt &b) {
2024 a &= b;
2025 return a;
2026}
2027
2028inline APInt operator&(const APInt &a, APInt &&b) {
2029 b &= a;
2030 return std::move(b);
2031}
2032
2033inline APInt operator&(APInt a, uint64_t RHS) {
2034 a &= RHS;
2035 return a;
2036}
2037
2038inline APInt operator&(uint64_t LHS, APInt b) {
2039 b &= LHS;
2040 return b;
2041}
2042
2043inline APInt operator|(APInt a, const APInt &b) {
2044 a |= b;
2045 return a;
2046}
2047
2048inline APInt operator|(const APInt &a, APInt &&b) {
2049 b |= a;
2050 return std::move(b);
2051}
2052
2053inline APInt operator|(APInt a, uint64_t RHS) {
2054 a |= RHS;
2055 return a;
2056}
2057
2058inline APInt operator|(uint64_t LHS, APInt b) {
2059 b |= LHS;
2060 return b;
2061}
2062
2063inline APInt operator^(APInt a, const APInt &b) {
2064 a ^= b;
2065 return a;
2066}
2067
2068inline APInt operator^(const APInt &a, APInt &&b) {
2069 b ^= a;
2070 return std::move(b);
2071}
2072
2073inline APInt operator^(APInt a, uint64_t RHS) {
2074 a ^= RHS;
2075 return a;
2076}
2077
2078inline APInt operator^(uint64_t LHS, APInt b) {
2079 b ^= LHS;
2080 return b;
2081}
2082
2083inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2084 I.print(OS, true);
2085 return OS;
2086}
2087
2088inline APInt operator-(APInt v) {
2089 v.negate();
2090 return v;
2091}
2092
2093inline APInt operator+(APInt a, const APInt &b) {
2094 a += b;
2095 return a;
2096}
2097
2098inline APInt operator+(const APInt &a, APInt &&b) {
2099 b += a;
2100 return std::move(b);
2101}
2102
2103inline APInt operator+(APInt a, uint64_t RHS) {
2104 a += RHS;
2105 return a;
2106}
2107
2108inline APInt operator+(uint64_t LHS, APInt b) {
2109 b += LHS;
2110 return b;
2111}
2112
2113inline APInt operator-(APInt a, const APInt &b) {
2114 a -= b;
2115 return a;
2116}
2117
2118inline APInt operator-(const APInt &a, APInt &&b) {
2119 b.negate();
2120 b += a;
2121 return std::move(b);
2122}
2123
2124inline APInt operator-(APInt a, uint64_t RHS) {
2125 a -= RHS;
2126 return a;
2127}
2128
2129inline APInt operator-(uint64_t LHS, APInt b) {
2130 b.negate();
2131 b += LHS;
2132 return b;
2133}
2134
2135inline APInt operator*(APInt a, uint64_t RHS) {
2136 a *= RHS;
2137 return a;
2138}
2139
2140inline APInt operator*(uint64_t LHS, APInt b) {
2141 b *= LHS;
2142 return b;
2143}
2144
2145namespace APIntOps {
2146
2147/// Determine the smaller of two APInts considered to be signed.
2148inline const APInt &smin(const APInt &A, const APInt &B) {
2149 return A.slt(B) ? A : B;
2150}
2151
2152/// Determine the larger of two APInts considered to be signed.
2153inline const APInt &smax(const APInt &A, const APInt &B) {
2154 return A.sgt(B) ? A : B;
2155}
2156
2157/// Determine the smaller of two APInts considered to be unsigned.
2158inline const APInt &umin(const APInt &A, const APInt &B) {
2159 return A.ult(B) ? A : B;
2160}
2161
2162/// Determine the larger of two APInts considered to be unsigned.
2163inline const APInt &umax(const APInt &A, const APInt &B) {
2164 return A.ugt(B) ? A : B;
2165}
2166
2167/// Compute GCD of two unsigned APInt values.
2168///
2169/// This function returns the greatest common divisor of the two APInt values
2170/// using Stein's algorithm.
2171///
2172/// \returns the greatest common divisor of A and B.
2173APInt GreatestCommonDivisor(APInt A, APInt B);
2174
2175/// Converts the given APInt to a double value.
2176///
2177/// Treats the APInt as an unsigned value for conversion purposes.
2178inline double RoundAPIntToDouble(const APInt &APIVal) {
2179 return APIVal.roundToDouble();
2180}
2181
2182/// Converts the given APInt to a double value.
2183///
2184/// Treats the APInt as a signed value for conversion purposes.
2185inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2186 return APIVal.signedRoundToDouble();
2187}
2188
2189/// Converts the given APInt to a float value.
2190inline float RoundAPIntToFloat(const APInt &APIVal) {
2191 return float(RoundAPIntToDouble(APIVal));
2192}
2193
2194/// Converts the given APInt to a float value.
2195///
2196/// Treats the APInt as a signed value for conversion purposes.
2197inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2198 return float(APIVal.signedRoundToDouble());
2199}
2200
2201/// Converts the given double value into a APInt.
2202///
2203/// This function convert a double value to an APInt value.
2204APInt RoundDoubleToAPInt(double Double, unsigned width);
2205
2206/// Converts a float value into a APInt.
2207///
2208/// Converts a float value into an APInt value.
2209inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2210 return RoundDoubleToAPInt(double(Float), width);
2211}
2212
2213/// Return A unsign-divided by B, rounded by the given rounding mode.
2214APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2215
2216/// Return A sign-divided by B, rounded by the given rounding mode.
2217APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2218
2219/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2220/// (e.g. 32 for i32).
2221/// This function finds the smallest number n, such that
2222/// (a) n >= 0 and q(n) = 0, or
2223/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2224/// integers, belong to two different intervals [Rk, Rk+R),
2225/// where R = 2^BW, and k is an integer.
2226/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2227/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2228/// subtraction (treated as addition of negated numbers) would always
2229/// count as an overflow, but here we want to allow values to decrease
2230/// and increase as long as they are within the same interval.
2231/// Specifically, adding of two negative numbers should not cause an
2232/// overflow (as long as the magnitude does not exceed the bit width).
2233/// On the other hand, given a positive number, adding a negative
2234/// number to it can give a negative result, which would cause the
2235/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2236/// treated as a special case of an overflow.
2237///
2238/// This function returns std::nullopt if after finding k that minimizes the
2239/// positive solution to q(n) = kR, both solutions are contained between
2240/// two consecutive integers.
2241///
2242/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2243/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2244/// virtue of *signed* overflow. This function will *not* find such an n,
2245/// however it may find a value of n satisfying the inequalities due to
2246/// an *unsigned* overflow (if the values are treated as unsigned).
2247/// To find a solution for a signed overflow, treat it as a problem of
2248/// finding an unsigned overflow with a range with of BW-1.
2249///
2250/// The returned value may have a different bit width from the input
2251/// coefficients.
2252std::optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2253 unsigned RangeWidth);
2254
2255/// Compare two values, and if they are different, return the position of the
2256/// most significant bit that is different in the values.
2257Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
2258 const APInt &B);
2259
2260/// Splat/Merge neighboring bits to widen/narrow the bitmask represented
2261/// by \param A to \param NewBitWidth bits.
2262///
2263/// MatchAnyBits: (Default)
2264/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
2265/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0111
2266///
2267/// MatchAllBits:
2268/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
2269/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0001
2270/// A.getBitwidth() or NewBitWidth must be a whole multiples of the other.
2271APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth,
2272 bool MatchAllBits = false);
2273} // namespace APIntOps
2274
2275// See friend declaration above. This additional declaration is required in
2276// order to compile LLVM with IBM xlC compiler.
2277hash_code hash_value(const APInt &Arg);
2278
2279/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2280/// with the integer held in IntVal.
2281void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);
2282
2283/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2284/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2285void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes);
2286
2287/// Provide DenseMapInfo for APInt.
2288template <> struct DenseMapInfo<APInt, void> {
2289 static inline APInt getEmptyKey() {
2290 APInt V(nullptr, 0);
2291 V.U.VAL = ~0ULL;
2292 return V;
2293 }
2294
2295 static inline APInt getTombstoneKey() {
2296 APInt V(nullptr, 0);
2297 V.U.VAL = ~1ULL;
2298 return V;
2299 }
2300
2301 static unsigned getHashValue(const APInt &Key);
2302
2303 static bool isEqual(const APInt &LHS, const APInt &RHS) {
2304 return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
2305 }
2306};
2307
2308} // namespace llvm
2309
2310#endif