Bug Summary

File:build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include/llvm/ADT/APInt.h
Warning:line 161, 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/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Analysis -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Analysis -I include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include -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.0.0/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/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -O3 -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/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -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-09-04-125545-48738-1 -x c++ /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Analysis/LazyValueInfo.cpp

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

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/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 None.
337 Optional<ConstantRange> exactIntersectWith(const ConstantRange &CR) const;
338
339 /// Union the two ranges and return the result if it can be represented
340 /// exactly, otherwise return None.
341 Optional<ConstantRange> exactUnionWith(const ConstantRange &CR) const;
342
343 /// Return a new range representing the possible values resulting
344 /// from an application of the specified cast operator to this range. \p
345 /// BitWidth is the target bitwidth of the cast. For casts which don't
346 /// change bitwidth, it must be the same as the source bitwidth. For casts
347 /// which do change bitwidth, the bitwidth must be consistent with the
348 /// requested cast and source bitwidth.
349 ConstantRange castOp(Instruction::CastOps CastOp,
350 uint32_t BitWidth) const;
351
352 /// Return a new range in the specified integer type, which must
353 /// be strictly larger than the current type. The returned range will
354 /// correspond to the possible range of values if the source range had been
355 /// zero extended to BitWidth.
356 ConstantRange zeroExtend(uint32_t BitWidth) const;
357
358 /// Return a new range in the specified integer type, which must
359 /// be strictly larger than the current type. The returned range will
360 /// correspond to the possible range of values if the source range had been
361 /// sign extended to BitWidth.
362 ConstantRange signExtend(uint32_t BitWidth) const;
363
364 /// Return a new range in the specified integer type, which must be
365 /// strictly smaller than the current type. The returned range will
366 /// correspond to the possible range of values if the source range had been
367 /// truncated to the specified type.
368 ConstantRange truncate(uint32_t BitWidth) const;
369
370 /// Make this range have the bit width given by \p BitWidth. The
371 /// value is zero extended, truncated, or left alone to make it that width.
372 ConstantRange zextOrTrunc(uint32_t BitWidth) const;
373
374 /// Make this range have the bit width given by \p BitWidth. The
375 /// value is sign extended, truncated, or left alone to make it that width.
376 ConstantRange sextOrTrunc(uint32_t BitWidth) const;
377
378 /// Return a new range representing the possible values resulting
379 /// from an application of the specified binary operator to an left hand side
380 /// of this range and a right hand side of \p Other.
381 ConstantRange binaryOp(Instruction::BinaryOps BinOp,
382 const ConstantRange &Other) const;
383
384 /// Return a new range representing the possible values resulting
385 /// from an application of the specified overflowing binary operator to a
386 /// left hand side of this range and a right hand side of \p Other given
387 /// the provided knowledge about lack of wrapping \p NoWrapKind.
388 ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp,
389 const ConstantRange &Other,
390 unsigned NoWrapKind) const;
391
392 /// Return a new range representing the possible values resulting
393 /// from an addition of a value in this range and a value in \p Other.
394 ConstantRange add(const ConstantRange &Other) const;
395
396 /// Return a new range representing the possible values resulting
397 /// from an addition with wrap type \p NoWrapKind of a value in this
398 /// range and a value in \p Other.
399 /// If the result range is disjoint, the preferred range is determined by the
400 /// \p PreferredRangeType.
401 ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
402 PreferredRangeType RangeType = Smallest) const;
403
404 /// Return a new range representing the possible values resulting
405 /// from a subtraction of a value in this range and a value in \p Other.
406 ConstantRange sub(const ConstantRange &Other) const;
407
408 /// Return a new range representing the possible values resulting
409 /// from an subtraction with wrap type \p NoWrapKind of a value in this
410 /// range and a value in \p Other.
411 /// If the result range is disjoint, the preferred range is determined by the
412 /// \p PreferredRangeType.
413 ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
414 PreferredRangeType RangeType = Smallest) const;
415
416 /// Return a new range representing the possible values resulting
417 /// from a multiplication of a value in this range and a value in \p Other,
418 /// treating both this and \p Other as unsigned ranges.
419 ConstantRange multiply(const ConstantRange &Other) const;
420
421 /// Return range of possible values for a signed multiplication of this and
422 /// \p Other. However, if overflow is possible always return a full range
423 /// rather than trying to determine a more precise result.
424 ConstantRange smul_fast(const ConstantRange &Other) const;
425
426 /// Return a new range representing the possible values resulting
427 /// from a signed maximum of a value in this range and a value in \p Other.
428 ConstantRange smax(const ConstantRange &Other) const;
429
430 /// Return a new range representing the possible values resulting
431 /// from an unsigned maximum of a value in this range and a value in \p Other.
432 ConstantRange umax(const ConstantRange &Other) const;
433
434 /// Return a new range representing the possible values resulting
435 /// from a signed minimum of a value in this range and a value in \p Other.
436 ConstantRange smin(const ConstantRange &Other) const;
437
438 /// Return a new range representing the possible values resulting
439 /// from an unsigned minimum of a value in this range and a value in \p Other.
440 ConstantRange umin(const ConstantRange &Other) const;
441
442 /// Return a new range representing the possible values resulting
443 /// from an unsigned division of a value in this range and a value in
444 /// \p Other.
445 ConstantRange udiv(const ConstantRange &Other) const;
446
447 /// Return a new range representing the possible values resulting
448 /// from a signed division of a value in this range and a value in
449 /// \p Other. Division by zero and division of SignedMin by -1 are considered
450 /// undefined behavior, in line with IR, and do not contribute towards the
451 /// result.
452 ConstantRange sdiv(const ConstantRange &Other) const;
453
454 /// Return a new range representing the possible values resulting
455 /// from an unsigned remainder operation of a value in this range and a
456 /// value in \p Other.
457 ConstantRange urem(const ConstantRange &Other) const;
458
459 /// Return a new range representing the possible values resulting
460 /// from a signed remainder operation of a value in this range and a
461 /// value in \p Other.
462 ConstantRange srem(const ConstantRange &Other) const;
463
464 /// Return a new range representing the possible values resulting from
465 /// a binary-xor of a value in this range by an all-one value,
466 /// aka bitwise complement operation.
467 ConstantRange binaryNot() const;
468
469 /// Return a new range representing the possible values resulting
470 /// from a binary-and of a value in this range by a value in \p Other.
471 ConstantRange binaryAnd(const ConstantRange &Other) const;
472
473 /// Return a new range representing the possible values resulting
474 /// from a binary-or of a value in this range by a value in \p Other.
475 ConstantRange binaryOr(const ConstantRange &Other) const;
476
477 /// Return a new range representing the possible values resulting
478 /// from a binary-xor of a value in this range by a value in \p Other.
479 ConstantRange binaryXor(const ConstantRange &Other) const;
480
481 /// Return a new range representing the possible values resulting
482 /// from a left shift of a value in this range by a value in \p Other.
483 /// TODO: This isn't fully implemented yet.
484 ConstantRange shl(const ConstantRange &Other) const;
485
486 /// Return a new range representing the possible values resulting from a
487 /// logical right shift of a value in this range and a value in \p Other.
488 ConstantRange lshr(const ConstantRange &Other) const;
489
490 /// Return a new range representing the possible values resulting from a
491 /// arithmetic right shift of a value in this range and a value in \p Other.
492 ConstantRange ashr(const ConstantRange &Other) const;
493
494 /// Perform an unsigned saturating addition of two constant ranges.
495 ConstantRange uadd_sat(const ConstantRange &Other) const;
496
497 /// Perform a signed saturating addition of two constant ranges.
498 ConstantRange sadd_sat(const ConstantRange &Other) const;
499
500 /// Perform an unsigned saturating subtraction of two constant ranges.
501 ConstantRange usub_sat(const ConstantRange &Other) const;
502
503 /// Perform a signed saturating subtraction of two constant ranges.
504 ConstantRange ssub_sat(const ConstantRange &Other) const;
505
506 /// Perform an unsigned saturating multiplication of two constant ranges.
507 ConstantRange umul_sat(const ConstantRange &Other) const;
508
509 /// Perform a signed saturating multiplication of two constant ranges.
510 ConstantRange smul_sat(const ConstantRange &Other) const;
511
512 /// Perform an unsigned saturating left shift of this constant range by a
513 /// value in \p Other.
514 ConstantRange ushl_sat(const ConstantRange &Other) const;
515
516 /// Perform a signed saturating left shift of this constant range by a
517 /// value in \p Other.
518 ConstantRange sshl_sat(const ConstantRange &Other) const;
519
520 /// Return a new range that is the logical not of the current set.
521 ConstantRange inverse() const;
522
523 /// Calculate absolute value range. If the original range contains signed
524 /// min, then the resulting range will contain signed min if and only if
525 /// \p IntMinIsPoison is false.
526 ConstantRange abs(bool IntMinIsPoison = false) const;
527
528 /// Represents whether an operation on the given constant range is known to
529 /// always or never overflow.
530 enum class OverflowResult {
531 /// Always overflows in the direction of signed/unsigned min value.
532 AlwaysOverflowsLow,
533 /// Always overflows in the direction of signed/unsigned max value.
534 AlwaysOverflowsHigh,
535 /// May or may not overflow.
536 MayOverflow,
537 /// Never overflows.
538 NeverOverflows,
539 };
540
541 /// Return whether unsigned add of the two ranges always/never overflows.
542 OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const;
543
544 /// Return whether signed add of the two ranges always/never overflows.
545 OverflowResult signedAddMayOverflow(const ConstantRange &Other) const;
546
547 /// Return whether unsigned sub of the two ranges always/never overflows.
548 OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const;
549
550 /// Return whether signed sub of the two ranges always/never overflows.
551 OverflowResult signedSubMayOverflow(const ConstantRange &Other) const;
552
553 /// Return whether unsigned mul of the two ranges always/never overflows.
554 OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const;
555
556 /// Return known bits for values in this range.
557 KnownBits toKnownBits() const;
558
559 /// Print out the bounds to a stream.
560 void print(raw_ostream &OS) const;
561
562 /// Allow printing from a debugger easily.
563 void dump() const;
564};
565
566inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
567 CR.print(OS);
568 return OS;
569}
570
571/// Parse out a conservative ConstantRange from !range metadata.
572///
573/// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
574ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD);
575
576} // end namespace llvm
577
578#endif // LLVM_IR_CONSTANTRANGE_H

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