clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name BasicAliasAnalysis.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/BasicAliasAnalysis.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
16 | #include "llvm/ADT/APInt.h" |
17 | #include "llvm/ADT/ScopeExit.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/ADT/Statistic.h" |
21 | #include "llvm/Analysis/AliasAnalysis.h" |
22 | #include "llvm/Analysis/AssumptionCache.h" |
23 | #include "llvm/Analysis/CFG.h" |
24 | #include "llvm/Analysis/CaptureTracking.h" |
25 | #include "llvm/Analysis/InstructionSimplify.h" |
26 | #include "llvm/Analysis/MemoryBuiltins.h" |
27 | #include "llvm/Analysis/MemoryLocation.h" |
28 | #include "llvm/Analysis/PhiValues.h" |
29 | #include "llvm/Analysis/TargetLibraryInfo.h" |
30 | #include "llvm/Analysis/ValueTracking.h" |
31 | #include "llvm/IR/Argument.h" |
32 | #include "llvm/IR/Attributes.h" |
33 | #include "llvm/IR/Constant.h" |
34 | #include "llvm/IR/Constants.h" |
35 | #include "llvm/IR/DataLayout.h" |
36 | #include "llvm/IR/DerivedTypes.h" |
37 | #include "llvm/IR/Dominators.h" |
38 | #include "llvm/IR/Function.h" |
39 | #include "llvm/IR/GetElementPtrTypeIterator.h" |
40 | #include "llvm/IR/GlobalAlias.h" |
41 | #include "llvm/IR/GlobalVariable.h" |
42 | #include "llvm/IR/InstrTypes.h" |
43 | #include "llvm/IR/Instruction.h" |
44 | #include "llvm/IR/Instructions.h" |
45 | #include "llvm/IR/IntrinsicInst.h" |
46 | #include "llvm/IR/Intrinsics.h" |
47 | #include "llvm/IR/Metadata.h" |
48 | #include "llvm/IR/Operator.h" |
49 | #include "llvm/IR/Type.h" |
50 | #include "llvm/IR/User.h" |
51 | #include "llvm/IR/Value.h" |
52 | #include "llvm/InitializePasses.h" |
53 | #include "llvm/Pass.h" |
54 | #include "llvm/Support/Casting.h" |
55 | #include "llvm/Support/CommandLine.h" |
56 | #include "llvm/Support/Compiler.h" |
57 | #include "llvm/Support/KnownBits.h" |
58 | #include <cassert> |
59 | #include <cstdint> |
60 | #include <cstdlib> |
61 | #include <utility> |
62 | |
63 | #define DEBUG_TYPE "basicaa" |
64 | |
65 | using namespace llvm; |
66 | |
67 | |
68 | static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden, |
69 | cl::init(true)); |
70 | |
71 | |
72 | |
73 | |
74 | |
75 | static cl::opt<bool> ForceAtLeast64Bits("basic-aa-force-at-least-64b", |
76 | cl::Hidden, cl::init(true)); |
77 | static cl::opt<bool> DoubleCalcBits("basic-aa-double-calc-bits", |
78 | cl::Hidden, cl::init(false)); |
79 | |
80 | |
81 | |
82 | |
83 | STATISTIC(SearchLimitReached, "Number of times the limit to " |
84 | "decompose GEPs is reached"); |
85 | STATISTIC(SearchTimes, "Number of times a GEP is decomposed"); |
86 | |
87 | |
88 | |
89 | |
90 | |
91 | const unsigned MaxNumPhiBBsValueReachabilityCheck = 20; |
92 | |
93 | |
94 | |
95 | |
96 | static const unsigned MaxLookupSearchDepth = 6; |
97 | |
98 | bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA, |
99 | FunctionAnalysisManager::Invalidator &Inv) { |
100 | |
101 | |
102 | |
103 | |
104 | if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) || |
105 | (DT && Inv.invalidate<DominatorTreeAnalysis>(Fn, PA)) || |
106 | (PV && Inv.invalidate<PhiValuesAnalysis>(Fn, PA))) |
107 | return true; |
108 | |
109 | |
110 | return false; |
111 | } |
112 | |
113 | |
114 | |
115 | |
116 | |
117 | |
118 | |
119 | static bool isEscapeSource(const Value *V) { |
120 | if (isa<CallBase>(V)) |
121 | return true; |
122 | |
123 | if (isa<Argument>(V)) |
124 | return true; |
125 | |
126 | |
127 | |
128 | |
129 | if (isa<LoadInst>(V)) |
130 | return true; |
131 | |
132 | |
133 | |
134 | |
135 | |
136 | |
137 | if (isa<IntToPtrInst>(V)) |
138 | return true; |
139 | |
140 | return false; |
141 | } |
142 | |
143 | |
144 | static uint64_t getObjectSize(const Value *V, const DataLayout &DL, |
145 | const TargetLibraryInfo &TLI, |
146 | bool NullIsValidLoc, |
147 | bool RoundToAlign = false) { |
148 | uint64_t Size; |
149 | ObjectSizeOpts Opts; |
150 | Opts.RoundToAlign = RoundToAlign; |
151 | Opts.NullIsUnknownSize = NullIsValidLoc; |
152 | if (getObjectSize(V, Size, DL, &TLI, Opts)) |
153 | return Size; |
154 | return MemoryLocation::UnknownSize; |
155 | } |
156 | |
157 | |
158 | |
159 | static bool isObjectSmallerThan(const Value *V, uint64_t Size, |
160 | const DataLayout &DL, |
161 | const TargetLibraryInfo &TLI, |
162 | bool NullIsValidLoc) { |
163 | |
164 | |
165 | |
166 | |
167 | |
168 | |
169 | |
170 | |
171 | |
172 | |
173 | |
174 | |
175 | |
176 | |
177 | |
178 | |
179 | |
180 | |
181 | |
182 | |
183 | |
184 | |
185 | |
186 | |
187 | |
188 | |
189 | if (!isIdentifiedObject(V)) |
190 | return false; |
191 | |
192 | |
193 | |
194 | uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc, |
195 | true); |
196 | |
197 | return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size; |
198 | } |
199 | |
200 | |
201 | |
202 | |
203 | static uint64_t getMinimalExtentFrom(const Value &V, |
204 | const LocationSize &LocSize, |
205 | const DataLayout &DL, |
206 | bool NullIsValidLoc) { |
207 | |
208 | |
209 | |
210 | bool CanBeNull, CanBeFreed; |
211 | uint64_t DerefBytes = |
212 | V.getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed); |
213 | DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes; |
214 | DerefBytes = CanBeFreed ? 0 : DerefBytes; |
215 | |
216 | |
217 | if (LocSize.isPrecise()) |
218 | DerefBytes = std::max(DerefBytes, LocSize.getValue()); |
219 | return DerefBytes; |
220 | } |
221 | |
222 | |
223 | static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL, |
224 | const TargetLibraryInfo &TLI, bool NullIsValidLoc) { |
225 | uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc); |
226 | return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size; |
227 | } |
228 | |
229 | |
230 | |
231 | |
232 | |
233 | namespace { |
234 | |
235 | struct ExtendedValue { |
236 | const Value *V; |
237 | unsigned ZExtBits; |
238 | unsigned SExtBits; |
239 | |
240 | explicit ExtendedValue(const Value *V, unsigned ZExtBits = 0, |
241 | unsigned SExtBits = 0) |
242 | : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits) {} |
243 | |
244 | unsigned getBitWidth() const { |
245 | return V->getType()->getPrimitiveSizeInBits() + ZExtBits + SExtBits; |
246 | } |
247 | |
248 | ExtendedValue withValue(const Value *NewV) const { |
249 | return ExtendedValue(NewV, ZExtBits, SExtBits); |
250 | } |
251 | |
252 | ExtendedValue withZExtOfValue(const Value *NewV) const { |
253 | unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - |
254 | NewV->getType()->getPrimitiveSizeInBits(); |
255 | |
256 | return ExtendedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0); |
257 | } |
258 | |
259 | ExtendedValue withSExtOfValue(const Value *NewV) const { |
260 | unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - |
261 | NewV->getType()->getPrimitiveSizeInBits(); |
262 | |
263 | return ExtendedValue(NewV, ZExtBits, SExtBits + ExtendBy); |
264 | } |
265 | |
266 | APInt evaluateWith(APInt N) const { |
267 | assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && |
268 | "Incompatible bit width"); |
269 | if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits); |
270 | if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits); |
271 | return N; |
272 | } |
273 | |
274 | bool canDistributeOver(bool NUW, bool NSW) const { |
275 | |
276 | |
277 | return (!ZExtBits || NUW) && (!SExtBits || NSW); |
| 44 | | Returning the value 1, which participates in a condition later | |
|
278 | } |
279 | }; |
280 | |
281 | |
282 | struct LinearExpression { |
283 | ExtendedValue Val; |
284 | APInt Scale; |
285 | APInt Offset; |
286 | |
287 | |
288 | bool IsNSW; |
289 | |
290 | LinearExpression(const ExtendedValue &Val, const APInt &Scale, |
291 | const APInt &Offset, bool IsNSW) |
292 | : Val(Val), Scale(Scale), Offset(Offset), IsNSW(IsNSW) {} |
293 | |
294 | LinearExpression(const ExtendedValue &Val) : Val(Val), IsNSW(true) { |
295 | unsigned BitWidth = Val.getBitWidth(); |
296 | Scale = APInt(BitWidth, 1); |
297 | Offset = APInt(BitWidth, 0); |
298 | } |
299 | }; |
300 | } |
301 | |
302 | |
303 | |
304 | static LinearExpression GetLinearExpression( |
305 | const ExtendedValue &Val, const DataLayout &DL, unsigned Depth, |
306 | AssumptionCache *AC, DominatorTree *DT) { |
307 | |
308 | if (Depth == 6) |
| |
| |
309 | return Val; |
310 | |
311 | if (const ConstantInt *Const = dyn_cast<ConstantInt>(Val.V)) |
| 24 | | Field 'V' is not a 'ConstantInt' | |
|
| |
| 35 | | Assuming field 'V' is not a 'ConstantInt' | |
|
| |
312 | return LinearExpression(Val, APInt(Val.getBitWidth(), 0), |
313 | Val.evaluateWith(Const->getValue()), true); |
314 | |
315 | if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val.V)) { |
| 26 | | Assuming field 'V' is not a 'BinaryOperator' | |
|
| |
| 37 | | Assuming field 'V' is a 'BinaryOperator' | |
|
| |
316 | if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { |
| 39 | | Assuming 'RHSC' is non-null | |
|
| |
317 | APInt RHS = Val.evaluateWith(RHSC->getValue()); |
318 | |
319 | |
320 | bool NUW = true, NSW = true; |
321 | if (isa<OverflowingBinaryOperator>(BOp)) { |
| 41 | | Assuming 'BOp' is not a 'OverflowingBinaryOperator' | |
|
| |
322 | NUW &= BOp->hasNoUnsignedWrap(); |
323 | NSW &= BOp->hasNoSignedWrap(); |
324 | } |
325 | if (!Val.canDistributeOver(NUW, NSW)) |
| 43 | | Calling 'ExtendedValue::canDistributeOver' | |
|
| 45 | | Returning from 'ExtendedValue::canDistributeOver' | |
|
| |
326 | return Val; |
327 | |
328 | LinearExpression E(Val); |
329 | switch (BOp->getOpcode()) { |
| 47 | | Control jumps to 'case Shl:' at line 364 | |
|
330 | default: |
331 | |
332 | |
333 | return Val; |
334 | case Instruction::Or: |
335 | |
336 | |
337 | if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC, |
338 | BOp, DT)) |
339 | return Val; |
340 | |
341 | LLVM_FALLTHROUGH; |
342 | case Instruction::Add: { |
343 | E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, |
344 | Depth + 1, AC, DT); |
345 | E.Offset += RHS; |
346 | E.IsNSW &= NSW; |
347 | break; |
348 | } |
349 | case Instruction::Sub: { |
350 | E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, |
351 | Depth + 1, AC, DT); |
352 | E.Offset -= RHS; |
353 | E.IsNSW &= NSW; |
354 | break; |
355 | } |
356 | case Instruction::Mul: { |
357 | E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, |
358 | Depth + 1, AC, DT); |
359 | E.Offset *= RHS; |
360 | E.Scale *= RHS; |
361 | E.IsNSW &= NSW; |
362 | break; |
363 | } |
364 | case Instruction::Shl: |
365 | |
366 | |
367 | |
368 | |
369 | |
370 | if (RHS.getLimitedValue() > Val.getBitWidth()) |
| 48 | | Assuming the condition is false | |
|
| |
371 | return Val; |
372 | |
373 | E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, |
374 | Depth + 1, AC, DT); |
375 | E.Offset <<= RHS.getLimitedValue(); |
| 50 | | Passing the value 18446744073709551615 via 1st parameter 'Limit' | |
|
| 51 | | Calling 'APInt::getLimitedValue' | |
|
| 55 | | Returning from 'APInt::getLimitedValue' | |
|
| 56 | | Passing the value 4294967295 via 1st parameter 'ShiftAmt' | |
|
| 57 | | Calling 'APInt::operator<<=' | |
|
376 | E.Scale <<= RHS.getLimitedValue(); |
377 | E.IsNSW &= NSW; |
378 | break; |
379 | } |
380 | return E; |
381 | } |
382 | } |
383 | |
384 | if (isa<ZExtInst>(Val.V)) |
| 28 | | Assuming field 'V' is not a 'ZExtInst' | |
|
| |
385 | return GetLinearExpression( |
386 | Val.withZExtOfValue(cast<CastInst>(Val.V)->getOperand(0)), |
387 | DL, Depth + 1, AC, DT); |
388 | |
389 | if (isa<SExtInst>(Val.V)) |
| 30 | | Assuming field 'V' is a 'SExtInst' | |
|
| |
390 | return GetLinearExpression( |
| 33 | | Calling 'GetLinearExpression' | |
|
391 | Val.withSExtOfValue(cast<CastInst>(Val.V)->getOperand(0)), |
| 32 | | Field 'V' is a 'CastInst' | |
|
392 | DL, Depth + 1, AC, DT); |
393 | |
394 | return Val; |
395 | } |
396 | |
397 | |
398 | |
399 | |
400 | |
401 | |
402 | static APInt adjustToPointerSize(const APInt &Offset, unsigned PointerSize) { |
403 | assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!"); |
404 | unsigned ShiftBits = Offset.getBitWidth() - PointerSize; |
405 | return (Offset << ShiftBits).ashr(ShiftBits); |
406 | } |
407 | |
408 | static unsigned getMaxPointerSize(const DataLayout &DL) { |
409 | unsigned MaxPointerSize = DL.getMaxPointerSizeInBits(); |
410 | if (MaxPointerSize < 64 && ForceAtLeast64Bits) MaxPointerSize = 64; |
411 | if (DoubleCalcBits) MaxPointerSize *= 2; |
412 | |
413 | return MaxPointerSize; |
414 | } |
415 | |
416 | |
417 | |
418 | |
419 | |
420 | |
421 | |
422 | |
423 | |
424 | |
425 | |
426 | |
427 | |
428 | BasicAAResult::DecomposedGEP |
429 | BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, |
430 | AssumptionCache *AC, DominatorTree *DT) { |
431 | |
432 | unsigned MaxLookup = MaxLookupSearchDepth; |
433 | SearchTimes++; |
434 | const Instruction *CxtI = dyn_cast<Instruction>(V); |
| 2 | | Assuming 'V' is not a 'Instruction' | |
|
435 | |
436 | unsigned MaxPointerSize = getMaxPointerSize(DL); |
437 | DecomposedGEP Decomposed; |
438 | Decomposed.Offset = APInt(MaxPointerSize, 0); |
439 | Decomposed.HasCompileTimeConstantScale = true; |
440 | do { |
441 | |
442 | const Operator *Op = dyn_cast<Operator>(V); |
| 3 | | Assuming 'V' is a 'Operator' | |
|
443 | if (!Op) { |
| |
444 | |
445 | if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { |
446 | if (!GA->isInterposable()) { |
447 | V = GA->getAliasee(); |
448 | continue; |
449 | } |
450 | } |
451 | Decomposed.Base = V; |
452 | return Decomposed; |
453 | } |
454 | |
455 | if (Op->getOpcode() == Instruction::BitCast || |
| 5 | | Assuming the condition is false | |
|
| |
456 | Op->getOpcode() == Instruction::AddrSpaceCast) { |
| 6 | | Assuming the condition is false | |
|
457 | V = Op->getOperand(0); |
458 | continue; |
459 | } |
460 | |
461 | const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); |
| 8 | | Assuming 'Op' is a 'GEPOperator' | |
|
462 | if (!GEPOp) { |
| |
463 | if (const auto *PHI = dyn_cast<PHINode>(V)) { |
464 | |
465 | if (PHI->getNumIncomingValues() == 1) { |
466 | V = PHI->getIncomingValue(0); |
467 | continue; |
468 | } |
469 | } else if (const auto *Call = dyn_cast<CallBase>(V)) { |
470 | |
471 | |
472 | |
473 | |
474 | |
475 | |
476 | |
477 | |
478 | |
479 | if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) { |
480 | V = RP; |
481 | continue; |
482 | } |
483 | } |
484 | |
485 | Decomposed.Base = V; |
486 | return Decomposed; |
487 | } |
488 | |
489 | |
490 | |
491 | if (Decomposed.InBounds == None) |
| |
492 | Decomposed.InBounds = GEPOp->isInBounds(); |
493 | else if (!GEPOp->isInBounds()) |
494 | Decomposed.InBounds = false; |
495 | |
496 | |
497 | if (!GEPOp->getSourceElementType()->isSized()) { |
| |
498 | Decomposed.Base = V; |
499 | return Decomposed; |
500 | } |
501 | |
502 | |
503 | |
504 | if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) { |
| 12 | | Assuming the object is not a 'ScalableVectorType' | |
|
| |
505 | Decomposed.Base = V; |
506 | Decomposed.HasCompileTimeConstantScale = false; |
507 | return Decomposed; |
508 | } |
509 | |
510 | unsigned AS = GEPOp->getPointerAddressSpace(); |
511 | |
512 | gep_type_iterator GTI = gep_type_begin(GEPOp); |
513 | unsigned PointerSize = DL.getPointerSizeInBits(AS); |
514 | |
515 | bool GepHasConstantOffset = true; |
516 | for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end(); |
| 15 | | Loop condition is true. Entering loop body | |
|
517 | I != E; ++I, ++GTI) { |
| 14 | | Assuming 'I' is not equal to 'E' | |
|
518 | const Value *Index = *I; |
519 | |
520 | if (StructType *STy = GTI.getStructTypeOrNull()) { |
| |
| |
521 | |
522 | unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); |
523 | if (FieldNo == 0) |
524 | continue; |
525 | |
526 | Decomposed.Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo); |
527 | continue; |
528 | } |
529 | |
530 | |
531 | if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { |
| 18 | | Assuming 'Index' is not a 'ConstantInt' | |
|
| |
532 | if (CIdx->isZero()) |
533 | continue; |
534 | Decomposed.Offset += |
535 | DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() * |
536 | CIdx->getValue().sextOrTrunc(MaxPointerSize); |
537 | continue; |
538 | } |
539 | |
540 | GepHasConstantOffset = false; |
541 | |
542 | APInt Scale(MaxPointerSize, |
543 | DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize()); |
544 | |
545 | |
546 | unsigned Width = Index->getType()->getIntegerBitWidth(); |
547 | unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0; |
| 20 | | Assuming 'PointerSize' is <= 'Width' | |
|
| |
548 | LinearExpression LE = GetLinearExpression( |
| 22 | | Calling 'GetLinearExpression' | |
|
549 | ExtendedValue(Index, 0, SExtBits), DL, 0, AC, DT); |
550 | |
551 | |
552 | |
553 | |
554 | |
555 | |
556 | |
557 | |
558 | |
559 | |
560 | |
561 | bool Overflow; |
562 | APInt ScaledOffset = LE.Offset.sextOrTrunc(MaxPointerSize) |
563 | .smul_ov(Scale, Overflow); |
564 | if (Overflow) { |
565 | LE = LinearExpression(ExtendedValue(Index, 0, SExtBits)); |
566 | } else { |
567 | Decomposed.Offset += ScaledOffset; |
568 | Scale *= LE.Scale.sextOrTrunc(MaxPointerSize); |
569 | } |
570 | |
571 | |
572 | |
573 | |
574 | |
575 | for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) { |
576 | if (Decomposed.VarIndices[i].V == LE.Val.V && |
577 | Decomposed.VarIndices[i].ZExtBits == LE.Val.ZExtBits && |
578 | Decomposed.VarIndices[i].SExtBits == LE.Val.SExtBits) { |
579 | Scale += Decomposed.VarIndices[i].Scale; |
580 | Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i); |
581 | break; |
582 | } |
583 | } |
584 | |
585 | |
586 | |
587 | Scale = adjustToPointerSize(Scale, PointerSize); |
588 | |
589 | if (!!Scale) { |
590 | VariableGEPIndex Entry = { |
591 | LE.Val.V, LE.Val.ZExtBits, LE.Val.SExtBits, Scale, CxtI, LE.IsNSW}; |
592 | Decomposed.VarIndices.push_back(Entry); |
593 | } |
594 | } |
595 | |
596 | |
597 | if (GepHasConstantOffset) |
598 | Decomposed.Offset = adjustToPointerSize(Decomposed.Offset, PointerSize); |
599 | |
600 | |
601 | V = GEPOp->getOperand(0); |
602 | } while (--MaxLookup); |
603 | |
604 | |
605 | Decomposed.Base = V; |
606 | SearchLimitReached++; |
607 | return Decomposed; |
608 | } |
609 | |
610 | |
611 | |
612 | |
613 | bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, |
614 | AAQueryInfo &AAQI, bool OrLocal) { |
615 | assert(Visited.empty() && "Visited must be cleared after use!"); |
616 | |
617 | unsigned MaxLookup = 8; |
618 | SmallVector<const Value *, 16> Worklist; |
619 | Worklist.push_back(Loc.Ptr); |
620 | do { |
621 | const Value *V = getUnderlyingObject(Worklist.pop_back_val()); |
622 | if (!Visited.insert(V).second) { |
623 | Visited.clear(); |
624 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); |
625 | } |
626 | |
627 | |
628 | if (OrLocal && isa<AllocaInst>(V)) |
629 | continue; |
630 | |
631 | |
632 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { |
633 | |
634 | |
635 | |
636 | if (!GV->isConstant()) { |
637 | Visited.clear(); |
638 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); |
639 | } |
640 | continue; |
641 | } |
642 | |
643 | |
644 | if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { |
645 | Worklist.push_back(SI->getTrueValue()); |
646 | Worklist.push_back(SI->getFalseValue()); |
647 | continue; |
648 | } |
649 | |
650 | |
651 | |
652 | if (const PHINode *PN = dyn_cast<PHINode>(V)) { |
653 | |
654 | if (PN->getNumIncomingValues() > MaxLookup) { |
655 | Visited.clear(); |
656 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); |
657 | } |
658 | append_range(Worklist, PN->incoming_values()); |
659 | continue; |
660 | } |
661 | |
662 | |
663 | Visited.clear(); |
664 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); |
665 | } while (!Worklist.empty() && --MaxLookup); |
666 | |
667 | Visited.clear(); |
668 | return Worklist.empty(); |
669 | } |
670 | |
671 | static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) { |
672 | const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call); |
673 | return II && II->getIntrinsicID() == IID; |
674 | } |
675 | |
676 | |
677 | FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) { |
678 | if (Call->doesNotAccessMemory()) |
679 | |
680 | return FMRB_DoesNotAccessMemory; |
681 | |
682 | FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; |
683 | |
684 | |
685 | |
686 | if (Call->onlyReadsMemory()) |
687 | Min = FMRB_OnlyReadsMemory; |
688 | else if (Call->doesNotReadMemory()) |
689 | Min = FMRB_OnlyWritesMemory; |
690 | |
691 | if (Call->onlyAccessesArgMemory()) |
692 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); |
693 | else if (Call->onlyAccessesInaccessibleMemory()) |
694 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem); |
695 | else if (Call->onlyAccessesInaccessibleMemOrArgMem()) |
696 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem); |
697 | |
698 | |
699 | |
700 | |
701 | if (!Call->hasOperandBundles()) |
702 | if (const Function *F = Call->getCalledFunction()) |
703 | Min = |
704 | FunctionModRefBehavior(Min & getBestAAResults().getModRefBehavior(F)); |
705 | |
706 | return Min; |
707 | } |
708 | |
709 | |
710 | |
711 | FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) { |
712 | |
713 | if (F->doesNotAccessMemory()) |
714 | return FMRB_DoesNotAccessMemory; |
715 | |
716 | FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; |
717 | |
718 | |
719 | if (F->onlyReadsMemory()) |
720 | Min = FMRB_OnlyReadsMemory; |
721 | else if (F->doesNotReadMemory()) |
722 | Min = FMRB_OnlyWritesMemory; |
723 | |
724 | if (F->onlyAccessesArgMemory()) |
725 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); |
726 | else if (F->onlyAccessesInaccessibleMemory()) |
727 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem); |
728 | else if (F->onlyAccessesInaccessibleMemOrArgMem()) |
729 | Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem); |
730 | |
731 | return Min; |
732 | } |
733 | |
734 | |
735 | static bool isWriteOnlyParam(const CallBase *Call, unsigned ArgIdx, |
736 | const TargetLibraryInfo &TLI) { |
737 | if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly)) |
738 | return true; |
739 | |
740 | |
741 | |
742 | |
743 | |
744 | |
745 | |
746 | LibFunc F; |
747 | if (Call->getCalledFunction() && |
748 | TLI.getLibFunc(*Call->getCalledFunction(), F) && |
749 | F == LibFunc_memset_pattern16 && TLI.has(F)) |
750 | if (ArgIdx == 0) |
751 | return true; |
752 | |
753 | |
754 | |
755 | |
756 | |
757 | return false; |
758 | } |
759 | |
760 | ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call, |
761 | unsigned ArgIdx) { |
762 | |
763 | if (isWriteOnlyParam(Call, ArgIdx, TLI)) |
764 | return ModRefInfo::Mod; |
765 | |
766 | if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly)) |
767 | return ModRefInfo::Ref; |
768 | |
769 | if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone)) |
770 | return ModRefInfo::NoModRef; |
771 | |
772 | return AAResultBase::getArgModRefInfo(Call, ArgIdx); |
773 | } |
774 | |
775 | #ifndef NDEBUG |
776 | static const Function *getParent(const Value *V) { |
777 | if (const Instruction *inst = dyn_cast<Instruction>(V)) { |
778 | if (!inst->getParent()) |
779 | return nullptr; |
780 | return inst->getParent()->getParent(); |
781 | } |
782 | |
783 | if (const Argument *arg = dyn_cast<Argument>(V)) |
784 | return arg->getParent(); |
785 | |
786 | return nullptr; |
787 | } |
788 | |
789 | static bool notDifferentParent(const Value *O1, const Value *O2) { |
790 | |
791 | const Function *F1 = getParent(O1); |
792 | const Function *F2 = getParent(O2); |
793 | |
794 | return !F1 || !F2 || F1 == F2; |
795 | } |
796 | #endif |
797 | |
798 | AliasResult BasicAAResult::alias(const MemoryLocation &LocA, |
799 | const MemoryLocation &LocB, |
800 | AAQueryInfo &AAQI) { |
801 | assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && |
802 | "BasicAliasAnalysis doesn't support interprocedural queries."); |
803 | return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI); |
804 | } |
805 | |
806 | |
807 | |
808 | |
809 | |
810 | |
811 | |
812 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, |
813 | const MemoryLocation &Loc, |
814 | AAQueryInfo &AAQI) { |
815 | assert(notDifferentParent(Call, Loc.Ptr) && |
816 | "AliasAnalysis query involving multiple functions!"); |
817 | |
818 | const Value *Object = getUnderlyingObject(Loc.Ptr); |
819 | |
820 | |
821 | |
822 | |
823 | |
824 | |
825 | if (isa<AllocaInst>(Object)) |
826 | if (const CallInst *CI = dyn_cast<CallInst>(Call)) |
827 | if (CI->isTailCall() && |
828 | !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal)) |
829 | return ModRefInfo::NoModRef; |
830 | |
831 | |
832 | |
833 | if (auto *AI = dyn_cast<AllocaInst>(Object)) |
834 | if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore)) |
835 | return ModRefInfo::Mod; |
836 | |
837 | |
838 | |
839 | |
840 | if (!isa<Constant>(Object) && Call != Object && |
841 | isNonEscapingLocalObject(Object, &AAQI.IsCapturedCache)) { |
842 | |
843 | |
844 | |
845 | ModRefInfo Result = ModRefInfo::NoModRef; |
846 | bool IsMustAlias = true; |
847 | |
848 | unsigned OperandNo = 0; |
849 | for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end(); |
850 | CI != CE; ++CI, ++OperandNo) { |
851 | |
852 | |
853 | |
854 | if (!(*CI)->getType()->isPointerTy() || |
855 | (!Call->doesNotCapture(OperandNo) && |
856 | OperandNo < Call->getNumArgOperands() && |
857 | !Call->isByValArgument(OperandNo))) |
858 | continue; |
859 | |
860 | |
861 | |
862 | if (Call->doesNotAccessMemory(OperandNo)) |
863 | continue; |
864 | |
865 | |
866 | |
867 | AliasResult AR = getBestAAResults().alias( |
868 | MemoryLocation::getBeforeOrAfter(*CI), |
869 | MemoryLocation::getBeforeOrAfter(Object), AAQI); |
870 | if (AR != AliasResult::MustAlias) |
871 | IsMustAlias = false; |
872 | |
873 | if (AR == AliasResult::NoAlias) |
874 | continue; |
875 | |
876 | |
877 | if (Call->onlyReadsMemory(OperandNo)) { |
878 | Result = setRef(Result); |
879 | continue; |
880 | } |
881 | |
882 | if (Call->doesNotReadMemory(OperandNo)) { |
883 | Result = setMod(Result); |
884 | continue; |
885 | } |
886 | |
887 | |
888 | |
889 | Result = ModRefInfo::ModRef; |
890 | break; |
891 | } |
892 | |
893 | |
894 | |
895 | if (isNoModRef(Result)) |
896 | IsMustAlias = false; |
897 | |
898 | |
899 | if (!isModAndRefSet(Result)) { |
900 | if (isNoModRef(Result)) |
901 | return ModRefInfo::NoModRef; |
902 | return IsMustAlias ? setMust(Result) : clearMust(Result); |
903 | } |
904 | } |
905 | |
906 | |
907 | |
908 | |
909 | |
910 | |
911 | |
912 | if (isMallocOrCallocLikeFn(Call, &TLI)) { |
913 | |
914 | |
915 | if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), Loc, |
916 | AAQI) == AliasResult::NoAlias) |
917 | return ModRefInfo::NoModRef; |
918 | } |
919 | |
920 | |
921 | |
922 | |
923 | if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) { |
924 | AliasResult SrcAA = |
925 | getBestAAResults().alias(MemoryLocation::getForSource(Inst), Loc, AAQI); |
926 | AliasResult DestAA = |
927 | getBestAAResults().alias(MemoryLocation::getForDest(Inst), Loc, AAQI); |
928 | |
929 | ModRefInfo rv = ModRefInfo::NoModRef; |
930 | if (SrcAA != AliasResult::NoAlias) |
931 | rv = setRef(rv); |
932 | if (DestAA != AliasResult::NoAlias) |
933 | rv = setMod(rv); |
934 | return rv; |
935 | } |
936 | |
937 | |
938 | |
939 | |
940 | |
941 | |
942 | |
943 | |
944 | if (isIntrinsicCall(Call, Intrinsic::experimental_guard)) |
945 | return ModRefInfo::Ref; |
946 | |
947 | if (isIntrinsicCall(Call, Intrinsic::experimental_deoptimize)) |
948 | return ModRefInfo::Ref; |
949 | |
950 | |
951 | |
952 | |
953 | |
954 | |
955 | |
956 | |
957 | |
958 | |
959 | |
960 | |
961 | |
962 | |
963 | |
964 | |
965 | |
966 | |
967 | |
968 | |
969 | |
970 | |
971 | |
972 | |
973 | if (isIntrinsicCall(Call, Intrinsic::invariant_start)) |
974 | return ModRefInfo::Ref; |
975 | |
976 | |
977 | return AAResultBase::getModRefInfo(Call, Loc, AAQI); |
978 | } |
979 | |
980 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, |
981 | const CallBase *Call2, |
982 | AAQueryInfo &AAQI) { |
983 | |
984 | |
985 | |
986 | |
987 | |
988 | |
989 | |
990 | |
991 | |
992 | |
993 | |
994 | if (isIntrinsicCall(Call1, Intrinsic::experimental_guard)) |
995 | return isModSet(createModRefInfo(getModRefBehavior(Call2))) |
996 | ? ModRefInfo::Ref |
997 | : ModRefInfo::NoModRef; |
998 | |
999 | if (isIntrinsicCall(Call2, Intrinsic::experimental_guard)) |
1000 | return isModSet(createModRefInfo(getModRefBehavior(Call1))) |
1001 | ? ModRefInfo::Mod |
1002 | : ModRefInfo::NoModRef; |
1003 | |
1004 | |
1005 | return AAResultBase::getModRefInfo(Call1, Call2, AAQI); |
1006 | } |
1007 | |
1008 | |
1009 | |
1010 | |
1011 | |
1012 | |
1013 | static bool isBaseOfObject(const Value *V) { |
1014 | |
1015 | |
1016 | |
1017 | |
1018 | return (isa<AllocaInst>(V) || isa<GlobalVariable>(V)); |
1019 | } |
1020 | |
1021 | |
1022 | |
1023 | |
1024 | |
1025 | |
1026 | |
1027 | AliasResult BasicAAResult::aliasGEP( |
1028 | const GEPOperator *GEP1, LocationSize V1Size, |
1029 | const Value *V2, LocationSize V2Size, |
1030 | const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) { |
1031 | if (!V1Size.hasValue() && !V2Size.hasValue()) { |
1032 | |
1033 | |
1034 | if (!isa<GEPOperator>(V2)) |
1035 | return AliasResult::MayAlias; |
1036 | |
1037 | |
1038 | |
1039 | AliasResult BaseAlias = getBestAAResults().alias( |
1040 | MemoryLocation::getBeforeOrAfter(UnderlyingV1), |
1041 | MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); |
1042 | return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias |
1043 | : AliasResult::MayAlias; |
1044 | } |
1045 | |
1046 | DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT); |
| 1 | Calling 'BasicAAResult::DecomposeGEPExpression' | |
|
1047 | DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT); |
1048 | |
1049 | |
1050 | |
1051 | if (!DecompGEP1.HasCompileTimeConstantScale || |
1052 | !DecompGEP2.HasCompileTimeConstantScale) |
1053 | return AliasResult::MayAlias; |
1054 | |
1055 | assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 && |
1056 | "DecomposeGEPExpression returned a result different from " |
1057 | "getUnderlyingObject"); |
1058 | |
1059 | |
1060 | |
1061 | DecompGEP1.Offset -= DecompGEP2.Offset; |
1062 | GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices); |
1063 | |
1064 | |
1065 | |
1066 | if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() && |
1067 | V2Size.hasValue() && DecompGEP1.Offset.sge(V2Size.getValue()) && |
1068 | isBaseOfObject(DecompGEP2.Base)) |
1069 | return AliasResult::NoAlias; |
1070 | |
1071 | if (isa<GEPOperator>(V2)) { |
1072 | |
1073 | if (*DecompGEP2.InBounds && DecompGEP1.VarIndices.empty() && |
1074 | V1Size.hasValue() && DecompGEP1.Offset.sle(-V1Size.getValue()) && |
1075 | isBaseOfObject(DecompGEP1.Base)) |
1076 | return AliasResult::NoAlias; |
1077 | } |
1078 | |
1079 | |
1080 | |
1081 | if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) |
1082 | return getBestAAResults().alias( |
1083 | MemoryLocation(UnderlyingV1, V1Size), |
1084 | MemoryLocation(UnderlyingV2, V2Size), AAQI); |
1085 | |
1086 | |
1087 | AliasResult BaseAlias = getBestAAResults().alias( |
1088 | MemoryLocation::getBeforeOrAfter(UnderlyingV1), |
1089 | MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); |
1090 | |
1091 | |
1092 | |
1093 | if (BaseAlias != AliasResult::MustAlias) { |
1094 | assert(BaseAlias == AliasResult::NoAlias || |
1095 | BaseAlias == AliasResult::MayAlias); |
1096 | return BaseAlias; |
1097 | } |
1098 | |
1099 | |
1100 | |
1101 | |
1102 | |
1103 | if (DecompGEP1.Offset != 0 && DecompGEP1.VarIndices.empty()) { |
1104 | APInt &Off = DecompGEP1.Offset; |
1105 | |
1106 | |
1107 | const Value *LeftPtr = V2; |
1108 | const Value *RightPtr = GEP1; |
1109 | LocationSize VLeftSize = V2Size; |
1110 | LocationSize VRightSize = V1Size; |
1111 | const bool Swapped = Off.isNegative(); |
1112 | |
1113 | if (Swapped) { |
1114 | |
1115 | |
1116 | |
1117 | |
1118 | |
1119 | |
1120 | std::swap(LeftPtr, RightPtr); |
1121 | std::swap(VLeftSize, VRightSize); |
1122 | Off = -Off; |
1123 | } |
1124 | |
1125 | if (VLeftSize.hasValue()) { |
1126 | const uint64_t LSize = VLeftSize.getValue(); |
1127 | if (Off.ult(LSize)) { |
1128 | |
1129 | |
1130 | AliasResult AR = AliasResult::PartialAlias; |
1131 | if (VRightSize.hasValue() && Off.ule(INT32_MAX) && |
1132 | (Off + VRightSize.getValue()).ule(LSize)) { |
1133 | |
1134 | |
1135 | |
1136 | AR.setOffset(-Off.getSExtValue()); |
1137 | AR.swap(Swapped); |
1138 | } |
1139 | return AR; |
1140 | } |
1141 | return AliasResult::NoAlias; |
1142 | } |
1143 | } |
1144 | |
1145 | if (!DecompGEP1.VarIndices.empty()) { |
1146 | APInt GCD; |
1147 | bool AllNonNegative = DecompGEP1.Offset.isNonNegative(); |
1148 | bool AllNonPositive = DecompGEP1.Offset.isNonPositive(); |
1149 | for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { |
1150 | APInt Scale = DecompGEP1.VarIndices[i].Scale; |
1151 | APInt ScaleForGCD = DecompGEP1.VarIndices[i].Scale; |
1152 | if (!DecompGEP1.VarIndices[i].IsNSW) |
1153 | ScaleForGCD = APInt::getOneBitSet(Scale.getBitWidth(), |
1154 | Scale.countTrailingZeros()); |
1155 | |
1156 | if (i == 0) |
1157 | GCD = ScaleForGCD.abs(); |
1158 | else |
1159 | GCD = APIntOps::GreatestCommonDivisor(GCD, ScaleForGCD.abs()); |
1160 | |
1161 | if (AllNonNegative || AllNonPositive) { |
1162 | |
1163 | |
1164 | |
1165 | const Value *V = DecompGEP1.VarIndices[i].V; |
1166 | const Instruction *CxtI = DecompGEP1.VarIndices[i].CxtI; |
1167 | |
1168 | KnownBits Known = computeKnownBits(V, DL, 0, &AC, CxtI, DT); |
1169 | bool SignKnownZero = Known.isNonNegative(); |
1170 | bool SignKnownOne = Known.isNegative(); |
1171 | |
1172 | |
1173 | |
1174 | bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V); |
1175 | SignKnownZero |= IsZExt; |
1176 | SignKnownOne &= !IsZExt; |
1177 | |
1178 | AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) || |
1179 | (SignKnownOne && Scale.isNonPositive()); |
1180 | AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) || |
1181 | (SignKnownOne && Scale.isNonNegative()); |
1182 | } |
1183 | } |
1184 | |
1185 | |
1186 | |
1187 | |
1188 | |
1189 | |
1190 | |
1191 | APInt ModOffset = DecompGEP1.Offset.srem(GCD); |
1192 | if (ModOffset.isNegative()) |
1193 | ModOffset += GCD; |
1194 | if (V1Size.hasValue() && V2Size.hasValue() && |
1195 | ModOffset.uge(V2Size.getValue()) && |
1196 | (GCD - ModOffset).uge(V1Size.getValue())) |
1197 | return AliasResult::NoAlias; |
1198 | |
1199 | |
1200 | |
1201 | |
1202 | |
1203 | if (AllNonNegative && V2Size.hasValue() && |
1204 | DecompGEP1.Offset.uge(V2Size.getValue())) |
1205 | return AliasResult::NoAlias; |
1206 | |
1207 | |
1208 | |
1209 | |
1210 | if (AllNonPositive && V1Size.hasValue() && |
1211 | (-DecompGEP1.Offset).uge(V1Size.getValue())) |
1212 | return AliasResult::NoAlias; |
1213 | |
1214 | if (V1Size.hasValue() && V2Size.hasValue()) { |
1215 | |
1216 | Optional<APInt> MinAbsVarIndex; |
1217 | if (DecompGEP1.VarIndices.size() == 1) { |
1218 | |
1219 | const VariableGEPIndex &Var = DecompGEP1.VarIndices[0]; |
1220 | if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT)) |
1221 | MinAbsVarIndex = Var.Scale.abs(); |
1222 | } else if (DecompGEP1.VarIndices.size() == 2) { |
1223 | |
1224 | |
1225 | |
1226 | |
1227 | const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0]; |
1228 | const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1]; |
1229 | if (Var0.Scale == -Var1.Scale && Var0.ZExtBits == Var1.ZExtBits && |
1230 | Var0.SExtBits == Var1.SExtBits && VisitedPhiBBs.empty() && |
1231 | isKnownNonEqual(Var0.V, Var1.V, DL, &AC, nullptr, DT)) |
1232 | MinAbsVarIndex = Var0.Scale.abs(); |
1233 | } |
1234 | |
1235 | if (MinAbsVarIndex) { |
1236 | |
1237 | APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex; |
1238 | APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex; |
1239 | |
1240 | |
1241 | if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) && |
1242 | OffsetHi.isNonNegative() && OffsetHi.uge(V2Size.getValue())) |
1243 | return AliasResult::NoAlias; |
1244 | } |
1245 | } |
1246 | |
1247 | if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size, |
1248 | DecompGEP1.Offset, &AC, DT)) |
1249 | return AliasResult::NoAlias; |
1250 | } |
1251 | |
1252 | |
1253 | |
1254 | |
1255 | return AliasResult::MayAlias; |
1256 | } |
1257 | |
1258 | static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { |
1259 | |
1260 | if (A == B) |
1261 | return A; |
1262 | |
1263 | if ((A == AliasResult::PartialAlias && B == AliasResult::MustAlias) || |
1264 | (B == AliasResult::PartialAlias && A == AliasResult::MustAlias)) |
1265 | return AliasResult::PartialAlias; |
1266 | |
1267 | return AliasResult::MayAlias; |
1268 | } |
1269 | |
1270 | |
1271 | |
1272 | AliasResult |
1273 | BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize, |
1274 | const Value *V2, LocationSize V2Size, |
1275 | AAQueryInfo &AAQI) { |
1276 | |
1277 | |
1278 | if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) |
1279 | if (SI->getCondition() == SI2->getCondition()) { |
1280 | AliasResult Alias = getBestAAResults().alias( |
1281 | MemoryLocation(SI->getTrueValue(), SISize), |
1282 | MemoryLocation(SI2->getTrueValue(), V2Size), AAQI); |
1283 | if (Alias == AliasResult::MayAlias) |
1284 | return AliasResult::MayAlias; |
1285 | AliasResult ThisAlias = getBestAAResults().alias( |
1286 | MemoryLocation(SI->getFalseValue(), SISize), |
1287 | MemoryLocation(SI2->getFalseValue(), V2Size), AAQI); |
1288 | return MergeAliasResults(ThisAlias, Alias); |
1289 | } |
1290 | |
1291 | |
1292 | |
1293 | AliasResult Alias = getBestAAResults().alias( |
1294 | MemoryLocation(V2, V2Size), |
1295 | MemoryLocation(SI->getTrueValue(), SISize), AAQI); |
1296 | if (Alias == AliasResult::MayAlias) |
1297 | return AliasResult::MayAlias; |
1298 | |
1299 | AliasResult ThisAlias = getBestAAResults().alias( |
1300 | MemoryLocation(V2, V2Size), |
1301 | MemoryLocation(SI->getFalseValue(), SISize), AAQI); |
1302 | return MergeAliasResults(ThisAlias, Alias); |
1303 | } |
1304 | |
1305 | |
1306 | |
1307 | AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, |
1308 | const Value *V2, LocationSize V2Size, |
1309 | AAQueryInfo &AAQI) { |
1310 | if (!PN->getNumIncomingValues()) |
1311 | return AliasResult::NoAlias; |
1312 | |
1313 | |
1314 | |
1315 | if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) |
1316 | if (PN2->getParent() == PN->getParent()) { |
1317 | Optional<AliasResult> Alias; |
1318 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
1319 | AliasResult ThisAlias = getBestAAResults().alias( |
1320 | MemoryLocation(PN->getIncomingValue(i), PNSize), |
1321 | MemoryLocation( |
1322 | PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size), |
1323 | AAQI); |
1324 | if (Alias) |
1325 | *Alias = MergeAliasResults(*Alias, ThisAlias); |
1326 | else |
1327 | Alias = ThisAlias; |
1328 | if (*Alias == AliasResult::MayAlias) |
1329 | break; |
1330 | } |
1331 | return *Alias; |
1332 | } |
1333 | |
1334 | SmallVector<Value *, 4> V1Srcs; |
1335 | |
1336 | |
1337 | |
1338 | bool isRecursive = false; |
1339 | auto CheckForRecPhi = [&](Value *PV) { |
1340 | if (!EnableRecPhiAnalysis) |
1341 | return false; |
1342 | if (getUnderlyingObject(PV) == PN) { |
1343 | isRecursive = true; |
1344 | return true; |
1345 | } |
1346 | return false; |
1347 | }; |
1348 | |
1349 | if (PV) { |
1350 | |
1351 | const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN); |
1352 | |
1353 | |
1354 | |
1355 | |
1356 | if (PhiValueSet.size() > MaxLookupSearchDepth) |
1357 | return AliasResult::MayAlias; |
1358 | |
1359 | for (Value *PV1 : PhiValueSet) { |
1360 | if (CheckForRecPhi(PV1)) |
1361 | continue; |
1362 | V1Srcs.push_back(PV1); |
1363 | } |
1364 | } else { |
1365 | |
1366 | |
1367 | SmallPtrSet<Value *, 4> UniqueSrc; |
1368 | Value *OnePhi = nullptr; |
1369 | for (Value *PV1 : PN->incoming_values()) { |
1370 | if (isa<PHINode>(PV1)) { |
1371 | if (OnePhi && OnePhi != PV1) { |
1372 | |
1373 | |
1374 | |
1375 | |
1376 | |
1377 | return AliasResult::MayAlias; |
1378 | } |
1379 | OnePhi = PV1; |
1380 | } |
1381 | |
1382 | if (CheckForRecPhi(PV1)) |
1383 | continue; |
1384 | |
1385 | if (UniqueSrc.insert(PV1).second) |
1386 | V1Srcs.push_back(PV1); |
1387 | } |
1388 | |
1389 | if (OnePhi && UniqueSrc.size() > 1) |
1390 | |
1391 | |
1392 | return AliasResult::MayAlias; |
1393 | } |
1394 | |
1395 | |
1396 | |
1397 | |
1398 | if (V1Srcs.empty()) |
1399 | return AliasResult::MayAlias; |
1400 | |
1401 | |
1402 | |
1403 | |
1404 | if (isRecursive) |
1405 | PNSize = LocationSize::beforeOrAfterPointer(); |
1406 | |
1407 | |
1408 | |
1409 | |
1410 | bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second; |
1411 | auto _ = make_scope_exit([&]() { |
1412 | if (BlockInserted) |
1413 | VisitedPhiBBs.erase(PN->getParent()); |
1414 | }); |
1415 | |
1416 | |
1417 | |
1418 | |
1419 | AAQueryInfo NewAAQI = AAQI.withEmptyCache(); |
1420 | AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI; |
1421 | |
1422 | AliasResult Alias = getBestAAResults().alias( |
1423 | MemoryLocation(V2, V2Size), |
1424 | MemoryLocation(V1Srcs[0], PNSize), *UseAAQI); |
1425 | |
1426 | |
1427 | |
1428 | if (Alias == AliasResult::MayAlias) |
1429 | return AliasResult::MayAlias; |
1430 | |
1431 | |
1432 | if (isRecursive && Alias != AliasResult::NoAlias) |
1433 | return AliasResult::MayAlias; |
1434 | |
1435 | |
1436 | |
1437 | for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { |
1438 | Value *V = V1Srcs[i]; |
1439 | |
1440 | AliasResult ThisAlias = getBestAAResults().alias( |
1441 | MemoryLocation(V2, V2Size), MemoryLocation(V, PNSize), *UseAAQI); |
1442 | Alias = MergeAliasResults(ThisAlias, Alias); |
1443 | if (Alias == AliasResult::MayAlias) |
1444 | break; |
1445 | } |
1446 | |
1447 | return Alias; |
1448 | } |
1449 | |
1450 | |
1451 | |
1452 | AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, |
1453 | const Value *V2, LocationSize V2Size, |
1454 | AAQueryInfo &AAQI) { |
1455 | |
1456 | |
1457 | if (V1Size.isZero() || V2Size.isZero()) |
1458 | return AliasResult::NoAlias; |
1459 | |
1460 | |
1461 | V1 = V1->stripPointerCastsForAliasAnalysis(); |
1462 | V2 = V2->stripPointerCastsForAliasAnalysis(); |
1463 | |
1464 | |
1465 | |
1466 | if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) |
1467 | return AliasResult::NoAlias; |
1468 | |
1469 | |
1470 | |
1471 | |
1472 | |
1473 | |
1474 | |
1475 | if (isValueEqualInPotentialCycles(V1, V2)) |
1476 | return AliasResult::MustAlias; |
1477 | |
1478 | if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) |
1479 | return AliasResult::NoAlias; |
1480 | |
1481 | |
1482 | const Value *O1 = getUnderlyingObject(V1, MaxLookupSearchDepth); |
1483 | const Value *O2 = getUnderlyingObject(V2, MaxLookupSearchDepth); |
1484 | |
1485 | |
1486 | |
1487 | if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) |
1488 | if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) |
1489 | return AliasResult::NoAlias; |
1490 | if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) |
1491 | if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) |
1492 | return AliasResult::NoAlias; |
1493 | |
1494 | if (O1 != O2) { |
1495 | |
1496 | if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) |
1497 | return AliasResult::NoAlias; |
1498 | |
1499 | |
1500 | if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || |
1501 | (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) |
1502 | return AliasResult::NoAlias; |
1503 | |
1504 | |
1505 | |
1506 | if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || |
1507 | (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) |
1508 | return AliasResult::NoAlias; |
1509 | |
1510 | |
1511 | |
1512 | |
1513 | |
1514 | |
1515 | |
1516 | |
1517 | |
1518 | |
1519 | if (isEscapeSource(O1) && |
1520 | isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache)) |
1521 | return AliasResult::NoAlias; |
1522 | if (isEscapeSource(O2) && |
1523 | isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache)) |
1524 | return AliasResult::NoAlias; |
1525 | } |
1526 | |
1527 | |
1528 | |
1529 | bool NullIsValidLocation = NullPointerIsDefined(&F); |
1530 | if ((isObjectSmallerThan( |
1531 | O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL, |
1532 | TLI, NullIsValidLocation)) || |
1533 | (isObjectSmallerThan( |
1534 | O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL, |
1535 | TLI, NullIsValidLocation))) |
1536 | return AliasResult::NoAlias; |
1537 | |
1538 | |
1539 | |
1540 | |
1541 | |
1542 | |
1543 | |
1544 | |
1545 | if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) { |
1546 | V1Size = LocationSize::afterPointer(); |
1547 | V2Size = LocationSize::afterPointer(); |
1548 | } |
1549 | |
1550 | |
1551 | |
1552 | |
1553 | |
1554 | if (AAQI.Depth >= 512) |
1555 | return AliasResult::MayAlias; |
1556 | |
1557 | |
1558 | |
1559 | AAQueryInfo::LocPair Locs({V1, V1Size}, {V2, V2Size}); |
1560 | const bool Swapped = V1 > V2; |
1561 | if (Swapped) |
1562 | std::swap(Locs.first, Locs.second); |
1563 | const auto &Pair = AAQI.AliasCache.try_emplace( |
1564 | Locs, AAQueryInfo::CacheEntry{AliasResult::NoAlias, 0}); |
1565 | if (!Pair.second) { |
1566 | auto &Entry = Pair.first->second; |
1567 | if (!Entry.isDefinitive()) { |
1568 | |
1569 | ++Entry.NumAssumptionUses; |
1570 | ++AAQI.NumAssumptionUses; |
1571 | } |
1572 | |
1573 | auto Result = Entry.Result; |
1574 | Result.swap(Swapped); |
1575 | return Result; |
1576 | } |
1577 | |
1578 | int OrigNumAssumptionUses = AAQI.NumAssumptionUses; |
1579 | unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size(); |
1580 | AliasResult Result = |
1581 | aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2); |
1582 | |
1583 | auto It = AAQI.AliasCache.find(Locs); |
1584 | assert(It != AAQI.AliasCache.end() && "Must be in cache"); |
1585 | auto &Entry = It->second; |
1586 | |
1587 | |
1588 | bool AssumptionDisproven = |
1589 | Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias; |
1590 | if (AssumptionDisproven) |
1591 | Result = AliasResult::MayAlias; |
1592 | |
1593 | |
1594 | AAQI.NumAssumptionUses -= Entry.NumAssumptionUses; |
1595 | Entry.Result = Result; |
1596 | |
1597 | Entry.Result.swap(Swapped); |
1598 | Entry.NumAssumptionUses = -1; |
1599 | |
1600 | |
1601 | |
1602 | |
1603 | if (AssumptionDisproven) |
1604 | while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults) |
1605 | AAQI.AliasCache.erase(AAQI.AssumptionBasedResults.pop_back_val()); |
1606 | |
1607 | |
1608 | |
1609 | if (OrigNumAssumptionUses != AAQI.NumAssumptionUses && |
1610 | Result != AliasResult::MayAlias) |
1611 | AAQI.AssumptionBasedResults.push_back(Locs); |
1612 | return Result; |
1613 | } |
1614 | |
1615 | AliasResult BasicAAResult::aliasCheckRecursive( |
1616 | const Value *V1, LocationSize V1Size, |
1617 | const Value *V2, LocationSize V2Size, |
1618 | AAQueryInfo &AAQI, const Value *O1, const Value *O2) { |
1619 | if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { |
1620 | AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, O1, O2, AAQI); |
1621 | if (Result != AliasResult::MayAlias) |
1622 | return Result; |
1623 | } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) { |
1624 | AliasResult Result = aliasGEP(GV2, V2Size, V1, V1Size, O2, O1, AAQI); |
1625 | if (Result != AliasResult::MayAlias) |
1626 | return Result; |
1627 | } |
1628 | |
1629 | if (const PHINode *PN = dyn_cast<PHINode>(V1)) { |
1630 | AliasResult Result = aliasPHI(PN, V1Size, V2, V2Size, AAQI); |
1631 | if (Result != AliasResult::MayAlias) |
1632 | return Result; |
1633 | } else if (const PHINode *PN = dyn_cast<PHINode>(V2)) { |
1634 | AliasResult Result = aliasPHI(PN, V2Size, V1, V1Size, AAQI); |
1635 | if (Result != AliasResult::MayAlias) |
1636 | return Result; |
1637 | } |
1638 | |
1639 | if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { |
1640 | AliasResult Result = aliasSelect(S1, V1Size, V2, V2Size, AAQI); |
1641 | if (Result != AliasResult::MayAlias) |
1642 | return Result; |
1643 | } else if (const SelectInst *S2 = dyn_cast<SelectInst>(V2)) { |
1644 | AliasResult Result = aliasSelect(S2, V2Size, V1, V1Size, AAQI); |
1645 | if (Result != AliasResult::MayAlias) |
1646 | return Result; |
1647 | } |
1648 | |
1649 | |
1650 | |
1651 | if (O1 == O2) { |
1652 | bool NullIsValidLocation = NullPointerIsDefined(&F); |
1653 | if (V1Size.isPrecise() && V2Size.isPrecise() && |
1654 | (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || |
1655 | isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) |
1656 | return AliasResult::PartialAlias; |
1657 | } |
1658 | |
1659 | return AliasResult::MayAlias; |
1660 | } |
1661 | |
1662 | |
1663 | |
1664 | |
1665 | |
1666 | |
1667 | |
1668 | |
1669 | bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V, |
1670 | const Value *V2) { |
1671 | if (V != V2) |
1672 | return false; |
1673 | |
1674 | const Instruction *Inst = dyn_cast<Instruction>(V); |
1675 | if (!Inst) |
1676 | return true; |
1677 | |
1678 | if (VisitedPhiBBs.empty()) |
1679 | return true; |
1680 | |
1681 | if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck) |
1682 | return false; |
1683 | |
1684 | |
1685 | |
1686 | |
1687 | for (auto *P : VisitedPhiBBs) |
1688 | if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT)) |
1689 | return false; |
1690 | |
1691 | return true; |
1692 | } |
1693 | |
1694 | |
1695 | |
1696 | |
1697 | |
1698 | void BasicAAResult::GetIndexDifference( |
1699 | SmallVectorImpl<VariableGEPIndex> &Dest, |
1700 | const SmallVectorImpl<VariableGEPIndex> &Src) { |
1701 | if (Src.empty()) |
1702 | return; |
1703 | |
1704 | for (unsigned i = 0, e = Src.size(); i != e; ++i) { |
1705 | const Value *V = Src[i].V; |
1706 | unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits; |
1707 | APInt Scale = Src[i].Scale; |
1708 | |
1709 | |
1710 | |
1711 | for (unsigned j = 0, e = Dest.size(); j != e; ++j) { |
1712 | if (!isValueEqualInPotentialCycles(Dest[j].V, V) || |
1713 | Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits) |
1714 | continue; |
1715 | |
1716 | |
1717 | |
1718 | if (Dest[j].Scale != Scale) { |
1719 | Dest[j].Scale -= Scale; |
1720 | Dest[j].IsNSW = false; |
1721 | } else |
1722 | Dest.erase(Dest.begin() + j); |
1723 | Scale = 0; |
1724 | break; |
1725 | } |
1726 | |
1727 | |
1728 | if (!!Scale) { |
1729 | VariableGEPIndex Entry = {V, ZExtBits, SExtBits, |
1730 | -Scale, Src[i].CxtI, Src[i].IsNSW}; |
1731 | Dest.push_back(Entry); |
1732 | } |
1733 | } |
1734 | } |
1735 | |
1736 | bool BasicAAResult::constantOffsetHeuristic( |
1737 | const SmallVectorImpl<VariableGEPIndex> &VarIndices, |
1738 | LocationSize MaybeV1Size, LocationSize MaybeV2Size, const APInt &BaseOffset, |
1739 | AssumptionCache *AC, DominatorTree *DT) { |
1740 | if (VarIndices.size() != 2 || !MaybeV1Size.hasValue() || |
1741 | !MaybeV2Size.hasValue()) |
1742 | return false; |
1743 | |
1744 | const uint64_t V1Size = MaybeV1Size.getValue(); |
1745 | const uint64_t V2Size = MaybeV2Size.getValue(); |
1746 | |
1747 | const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1]; |
1748 | |
1749 | if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits || |
1750 | Var0.Scale != -Var1.Scale || Var0.V->getType() != Var1.V->getType()) |
1751 | return false; |
1752 | |
1753 | |
1754 | |
1755 | |
1756 | |
1757 | LinearExpression E0 = |
1758 | GetLinearExpression(ExtendedValue(Var0.V), DL, 0, AC, DT); |
1759 | LinearExpression E1 = |
1760 | GetLinearExpression(ExtendedValue(Var1.V), DL, 0, AC, DT); |
1761 | if (E0.Scale != E1.Scale || E0.Val.ZExtBits != E1.Val.ZExtBits || |
1762 | E0.Val.SExtBits != E1.Val.SExtBits || |
1763 | !isValueEqualInPotentialCycles(E0.Val.V, E1.Val.V)) |
1764 | return false; |
1765 | |
1766 | |
1767 | |
1768 | |
1769 | |
1770 | |
1771 | |
1772 | |
1773 | APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff; |
1774 | MinDiff = APIntOps::umin(MinDiff, Wrapped); |
1775 | APInt MinDiffBytes = |
1776 | MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs(); |
1777 | |
1778 | |
1779 | |
1780 | |
1781 | |
1782 | return MinDiffBytes.uge(V1Size + BaseOffset.abs()) && |
1783 | MinDiffBytes.uge(V2Size + BaseOffset.abs()); |
1784 | } |
1785 | |
1786 | |
1787 | |
1788 | |
1789 | |
1790 | AnalysisKey BasicAA::Key; |
1791 | |
1792 | BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) { |
1793 | auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); |
1794 | auto &AC = AM.getResult<AssumptionAnalysis>(F); |
1795 | auto *DT = &AM.getResult<DominatorTreeAnalysis>(F); |
1796 | auto *PV = AM.getCachedResult<PhiValuesAnalysis>(F); |
1797 | return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT, PV); |
1798 | } |
1799 | |
1800 | BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { |
1801 | initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); |
1802 | } |
1803 | |
1804 | char BasicAAWrapperPass::ID = 0; |
1805 | |
1806 | void BasicAAWrapperPass::anchor() {} |
1807 | |
1808 | INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa", |
1809 | "Basic Alias Analysis (stateless AA impl)", true, true) |
1810 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) |
1811 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
1812 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
1813 | INITIALIZE_PASS_DEPENDENCY(PhiValuesWrapperPass) |
1814 | INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa", |
1815 | "Basic Alias Analysis (stateless AA impl)", true, true) |
1816 | |
1817 | FunctionPass *llvm::createBasicAAWrapperPass() { |
1818 | return new BasicAAWrapperPass(); |
1819 | } |
1820 | |
1821 | bool BasicAAWrapperPass::runOnFunction(Function &F) { |
1822 | auto &ACT = getAnalysis<AssumptionCacheTracker>(); |
1823 | auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); |
1824 | auto &DTWP = getAnalysis<DominatorTreeWrapperPass>(); |
1825 | auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>(); |
1826 | |
1827 | Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, |
1828 | TLIWP.getTLI(F), ACT.getAssumptionCache(F), |
1829 | &DTWP.getDomTree(), |
1830 | PVWP ? &PVWP->getResult() : nullptr)); |
1831 | |
1832 | return false; |
1833 | } |
1834 | |
1835 | void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
1836 | AU.setPreservesAll(); |
1837 | AU.addRequiredTransitive<AssumptionCacheTracker>(); |
1838 | AU.addRequiredTransitive<DominatorTreeWrapperPass>(); |
1839 | AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>(); |
1840 | AU.addUsedIfAvailable<PhiValuesWrapperPass>(); |
1841 | } |
1842 | |
1843 | BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) { |
1844 | return BasicAAResult( |
1845 | F.getParent()->getDataLayout(), F, |
1846 | P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F), |
1847 | P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F)); |
1848 | } |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
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 | |
25 | namespace llvm { |
26 | class FoldingSetNodeID; |
27 | class StringRef; |
28 | class hash_code; |
29 | class raw_ostream; |
30 | |
31 | template <typename T> class SmallVectorImpl; |
32 | template <typename T> class ArrayRef; |
33 | template <typename T> class Optional; |
34 | template <typename T> struct DenseMapInfo; |
35 | |
36 | class APInt; |
37 | |
38 | inline APInt operator-(APInt); |
39 | |
40 | |
41 | |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 | |
51 | |
52 | |
53 | |
54 | |
55 | |
56 | |
57 | |
58 | |
59 | |
60 | |
61 | |
62 | |
63 | |
64 | |
65 | |
66 | |
67 | |
68 | |
69 | |
70 | class LLVM_NODISCARD APInt { |
71 | public: |
72 | typedef uint64_t WordType; |
73 | |
74 | |
75 | enum : unsigned { |
76 | |
77 | APINT_WORD_SIZE = sizeof(WordType), |
78 | |
79 | APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT |
80 | }; |
81 | |
82 | enum class Rounding { |
83 | DOWN, |
84 | TOWARD_ZERO, |
85 | UP, |
86 | }; |
87 | |
88 | static constexpr WordType WORDTYPE_MAX = ~WordType(0); |
89 | |
90 | private: |
91 | |
92 | |
93 | union { |
94 | uint64_t VAL; |
95 | uint64_t *pVal; |
96 | } U; |
97 | |
98 | unsigned BitWidth; |
99 | |
100 | friend struct DenseMapInfo<APInt>; |
101 | |
102 | friend class APSInt; |
103 | |
104 | |
105 | |
106 | |
107 | |
108 | APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { |
109 | U.pVal = val; |
110 | } |
111 | |
112 | |
113 | |
114 | |
115 | static unsigned whichWord(unsigned bitPosition) { |
116 | return bitPosition / APINT_BITS_PER_WORD; |
117 | } |
118 | |
119 | |
120 | |
121 | |
122 | |
123 | static unsigned whichBit(unsigned bitPosition) { |
124 | return bitPosition % APINT_BITS_PER_WORD; |
125 | } |
126 | |
127 | |
128 | |
129 | |
130 | |
131 | |
132 | |
133 | static uint64_t maskBit(unsigned bitPosition) { |
134 | return 1ULL << whichBit(bitPosition); |
135 | } |
136 | |
137 | |
138 | |
139 | |
140 | |
141 | |
142 | |
143 | APInt &clearUnusedBits() { |
144 | |
145 | unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1; |
146 | |
147 | |
148 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits); |
149 | if (isSingleWord()) |
150 | U.VAL &= mask; |
151 | else |
152 | U.pVal[getNumWords() - 1] &= mask; |
153 | return *this; |
154 | } |
155 | |
156 | |
157 | |
158 | uint64_t getWord(unsigned bitPosition) const { |
159 | return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)]; |
160 | } |
161 | |
162 | |
163 | |
164 | |
165 | void reallocate(unsigned NewBitWidth); |
166 | |
167 | |
168 | |
169 | |
170 | |
171 | |
172 | |
173 | |
174 | |
175 | |
176 | |
177 | |
178 | |
179 | void fromString(unsigned numBits, StringRef str, uint8_t radix); |
180 | |
181 | |
182 | |
183 | |
184 | |
185 | |
186 | |
187 | static void divide(const WordType *LHS, unsigned lhsWords, |
188 | const WordType *RHS, unsigned rhsWords, WordType *Quotient, |
189 | WordType *Remainder); |
190 | |
191 | |
192 | void initSlowCase(uint64_t val, bool isSigned); |
193 | |
194 | |
195 | void initFromArray(ArrayRef<uint64_t> array); |
196 | |
197 | |
198 | void initSlowCase(const APInt &that); |
199 | |
200 | |
201 | void shlSlowCase(unsigned ShiftAmt); |
202 | |
203 | |
204 | void lshrSlowCase(unsigned ShiftAmt); |
205 | |
206 | |
207 | void ashrSlowCase(unsigned ShiftAmt); |
208 | |
209 | |
210 | void AssignSlowCase(const APInt &RHS); |
211 | |
212 | |
213 | bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY; |
214 | |
215 | |
216 | unsigned countLeadingZerosSlowCase() const LLVM_READONLY; |
217 | |
218 | |
219 | unsigned countLeadingOnesSlowCase() const LLVM_READONLY; |
220 | |
221 | |
222 | unsigned countTrailingZerosSlowCase() const LLVM_READONLY; |
223 | |
224 | |
225 | unsigned countTrailingOnesSlowCase() const LLVM_READONLY; |
226 | |
227 | |
228 | unsigned countPopulationSlowCase() const LLVM_READONLY; |
229 | |
230 | |
231 | bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY; |
232 | |
233 | |
234 | bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY; |
235 | |
236 | |
237 | void setBitsSlowCase(unsigned loBit, unsigned hiBit); |
238 | |
239 | |
240 | void flipAllBitsSlowCase(); |
241 | |
242 | |
243 | void AndAssignSlowCase(const APInt& RHS); |
244 | |
245 | |
246 | void OrAssignSlowCase(const APInt& RHS); |
247 | |
248 | |
249 | void XorAssignSlowCase(const APInt& RHS); |
250 | |
251 | |
252 | |
253 | int compare(const APInt &RHS) const LLVM_READONLY; |
254 | |
255 | |
256 | |
257 | int compareSigned(const APInt &RHS) const LLVM_READONLY; |
258 | |
259 | public: |
260 | |
261 | |
262 | |
263 | |
264 | |
265 | |
266 | |
267 | |
268 | |
269 | |
270 | |
271 | |
272 | |
273 | APInt(unsigned numBits, uint64_t val, bool isSigned = false) |
274 | : BitWidth(numBits) { |
275 | assert(BitWidth && "bitwidth too small"); |
276 | if (isSingleWord()) { |
277 | U.VAL = val; |
278 | clearUnusedBits(); |
279 | } else { |
280 | initSlowCase(val, isSigned); |
281 | } |
282 | } |
283 | |
284 | |
285 | |
286 | |
287 | |
288 | |
289 | |
290 | |
291 | APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); |
292 | |
293 | |
294 | |
295 | |
296 | |
297 | |
298 | |
299 | |
300 | APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); |
301 | |
302 | |
303 | |
304 | |
305 | |
306 | |
307 | |
308 | |
309 | |
310 | |
311 | |
312 | |
313 | APInt(unsigned numBits, StringRef str, uint8_t radix); |
314 | |
315 | |
316 | |
317 | APInt(const APInt &that) : BitWidth(that.BitWidth) { |
318 | if (isSingleWord()) |
319 | U.VAL = that.U.VAL; |
320 | else |
321 | initSlowCase(that); |
322 | } |
323 | |
324 | |
325 | APInt(APInt &&that) : BitWidth(that.BitWidth) { |
326 | memcpy(&U, &that.U, sizeof(U)); |
327 | that.BitWidth = 0; |
328 | } |
329 | |
330 | |
331 | ~APInt() { |
332 | if (needsCleanup()) |
333 | delete[] U.pVal; |
334 | } |
335 | |
336 | |
337 | |
338 | |
339 | |
340 | |
341 | explicit APInt() : BitWidth(1) { U.VAL = 0; } |
342 | |
343 | |
344 | bool needsCleanup() const { return !isSingleWord(); } |
345 | |
346 | |
347 | |
348 | void Profile(FoldingSetNodeID &id) const; |
349 | |
350 | |
351 | |
352 | |
353 | |
354 | |
355 | |
356 | |
357 | bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } |
| 59 | | Assuming field 'BitWidth' is <= APINT_BITS_PER_WORD | |
|
| 60 | | Returning the value 1, which participates in a condition later | |
|
358 | |
359 | |
360 | |
361 | |
362 | |
363 | |
364 | bool isNegative() const { return (*this)[BitWidth - 1]; } |
365 | |
366 | |
367 | |
368 | |
369 | bool isNonNegative() const { return !isNegative(); } |
370 | |
371 | |
372 | |
373 | |
374 | |
375 | |
376 | bool isSignBitSet() const { return (*this)[BitWidth-1]; } |
377 | |
378 | |
379 | |
380 | |
381 | |
382 | |
383 | bool isSignBitClear() const { return !isSignBitSet(); } |
384 | |
385 | |
386 | |
387 | |
388 | |
389 | |
390 | |
391 | bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); } |
392 | |
393 | |
394 | |
395 | |
396 | bool isNonPositive() const { return !isStrictlyPositive(); } |
397 | |
398 | |
399 | |
400 | |
401 | bool isAllOnesValue() const { |
402 | if (isSingleWord()) |
403 | return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth); |
404 | return countTrailingOnesSlowCase() == BitWidth; |
405 | } |
406 | |
407 | |
408 | |
409 | |
410 | |
411 | bool isNullValue() const { return !*this; } |
412 | |
413 | |
414 | |
415 | |
416 | bool isOneValue() const { |
417 | if (isSingleWord()) |
418 | return U.VAL == 1; |
419 | return countLeadingZerosSlowCase() == BitWidth - 1; |
420 | } |
421 | |
422 | |
423 | |
424 | |
425 | |
426 | bool isMaxValue() const { return isAllOnesValue(); } |
427 | |
428 | |
429 | |
430 | |
431 | |
432 | bool isMaxSignedValue() const { |
433 | if (isSingleWord()) |
434 | return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1); |
435 | return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1; |
436 | } |
437 | |
438 | |
439 | |
440 | |
441 | |
442 | bool isMinValue() const { return isNullValue(); } |
443 | |
444 | |
445 | |
446 | |
447 | |
448 | bool isMinSignedValue() const { |
449 | if (isSingleWord()) |
450 | return U.VAL == (WordType(1) << (BitWidth - 1)); |
451 | return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1; |
452 | } |
453 | |
454 | |
455 | bool isIntN(unsigned N) const { |
456 | assert(N && "N == 0 ???"); |
457 | return getActiveBits() <= N; |
458 | } |
459 | |
460 | |
461 | bool isSignedIntN(unsigned N) const { |
462 | assert(N && "N == 0 ???"); |
463 | return getMinSignedBits() <= N; |
464 | } |
465 | |
466 | |
467 | |
468 | |
469 | bool isPowerOf2() const { |
470 | if (isSingleWord()) |
471 | return isPowerOf2_64(U.VAL); |
472 | return countPopulationSlowCase() == 1; |
473 | } |
474 | |
475 | |
476 | |
477 | |
478 | bool isSignMask() const { return isMinSignedValue(); } |
479 | |
480 | |
481 | |
482 | |
483 | bool getBoolValue() const { return !!*this; } |
484 | |
485 | |
486 | |
487 | uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const { |
488 | return ugt(Limit) ? Limit : getZExtValue(); |
| 52 | | Assuming the condition is true | |
|
| |
| 54 | | Returning the value 18446744073709551615 | |
|
489 | } |
490 | |
491 | |
492 | |
493 | |
494 | |
495 | |
496 | bool isSplat(unsigned SplatSizeInBits) const; |
497 | |
498 | |
499 | |
500 | bool isMask(unsigned numBits) const { |
501 | assert(numBits != 0 && "numBits must be non-zero"); |
502 | assert(numBits <= BitWidth && "numBits out of range"); |
503 | if (isSingleWord()) |
504 | return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits)); |
505 | unsigned Ones = countTrailingOnesSlowCase(); |
506 | return (numBits == Ones) && |
507 | ((Ones + countLeadingZerosSlowCase()) == BitWidth); |
508 | } |
509 | |
510 | |
511 | |
512 | |
513 | bool isMask() const { |
514 | if (isSingleWord()) |
515 | return isMask_64(U.VAL); |
516 | unsigned Ones = countTrailingOnesSlowCase(); |
517 | return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth); |
518 | } |
519 | |
520 | |
521 | |
522 | bool isShiftedMask() const { |
523 | if (isSingleWord()) |
524 | return isShiftedMask_64(U.VAL); |
525 | unsigned Ones = countPopulationSlowCase(); |
526 | unsigned LeadZ = countLeadingZerosSlowCase(); |
527 | return (Ones + LeadZ + countTrailingZeros()) == BitWidth; |
528 | } |
529 | |
530 | |
531 | |
532 | |
533 | |
534 | |
535 | static APInt getMaxValue(unsigned numBits) { |
536 | return getAllOnesValue(numBits); |
537 | } |
538 | |
539 | |
540 | static APInt getSignedMaxValue(unsigned numBits) { |
541 | APInt API = getAllOnesValue(numBits); |
542 | API.clearBit(numBits - 1); |
543 | return API; |
544 | } |
545 | |
546 | |
547 | static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); } |
548 | |
549 | |
550 | static APInt getSignedMinValue(unsigned numBits) { |
551 | APInt API(numBits, 0); |
552 | API.setBit(numBits - 1); |
553 | return API; |
554 | } |
555 | |
556 | |
557 | |
558 | |
559 | |
560 | static APInt getSignMask(unsigned BitWidth) { |
561 | return getSignedMinValue(BitWidth); |
562 | } |
563 | |
564 | |
565 | |
566 | |
567 | static APInt getAllOnesValue(unsigned numBits) { |
568 | return APInt(numBits, WORDTYPE_MAX, true); |
569 | } |
570 | |
571 | |
572 | |
573 | |
574 | static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); } |
575 | |
576 | |
577 | |
578 | |
579 | |
580 | |
581 | |
582 | APInt getHiBits(unsigned numBits) const; |
583 | |
584 | |
585 | |
586 | |
587 | |
588 | |
589 | |
590 | APInt getLoBits(unsigned numBits) const; |
591 | |
592 | |
593 | static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { |
594 | APInt Res(numBits, 0); |
595 | Res.setBit(BitNo); |
596 | return Res; |
597 | } |
598 | |
599 | |
600 | |
601 | |
602 | |
603 | |
604 | |
605 | |
606 | |
607 | |
608 | |
609 | |
610 | |
611 | |
612 | static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { |
613 | assert(loBit <= hiBit && "loBit greater than hiBit"); |
614 | APInt Res(numBits, 0); |
615 | Res.setBits(loBit, hiBit); |
616 | return Res; |
617 | } |
618 | |
619 | |
620 | |
621 | |
622 | |
623 | |
624 | |
625 | static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit, |
626 | unsigned hiBit) { |
627 | APInt Res(numBits, 0); |
628 | Res.setBitsWithWrap(loBit, hiBit); |
629 | return Res; |
630 | } |
631 | |
632 | |
633 | |
634 | |
635 | |
636 | |
637 | |
638 | |
639 | |
640 | |
641 | |
642 | |
643 | static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { |
644 | APInt Res(numBits, 0); |
645 | Res.setBitsFrom(loBit); |
646 | return Res; |
647 | } |
648 | |
649 | |
650 | |
651 | |
652 | |
653 | |
654 | |
655 | static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { |
656 | APInt Res(numBits, 0); |
657 | Res.setHighBits(hiBitsSet); |
658 | return Res; |
659 | } |
660 | |
661 | |
662 | |
663 | |
664 | |
665 | |
666 | |
667 | static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { |
668 | APInt Res(numBits, 0); |
669 | Res.setLowBits(loBitsSet); |
670 | return Res; |
671 | } |
672 | |
673 | |
674 | static APInt getSplat(unsigned NewLen, const APInt &V); |
675 | |
676 | |
677 | |
678 | static bool isSameValue(const APInt &I1, const APInt &I2) { |
679 | if (I1.getBitWidth() == I2.getBitWidth()) |
680 | return I1 == I2; |
681 | |
682 | if (I1.getBitWidth() > I2.getBitWidth()) |
683 | return I1 == I2.zext(I1.getBitWidth()); |
684 | |
685 | return I1.zext(I2.getBitWidth()) == I2; |
686 | } |
687 | |
688 | |
689 | friend hash_code hash_value(const APInt &Arg); |
690 | |
691 | |
692 | |
693 | |
694 | const uint64_t *getRawData() const { |
695 | if (isSingleWord()) |
696 | return &U.VAL; |
697 | return &U.pVal[0]; |
698 | } |
699 | |
700 | |
701 | |
702 | |
703 | |
704 | |
705 | |
706 | |
707 | |
708 | |
709 | const APInt operator++(int) { |
710 | APInt API(*this); |
711 | ++(*this); |
712 | return API; |
713 | } |
714 | |
715 | |
716 | |
717 | |
718 | APInt &operator++(); |
719 | |
720 | |
721 | |
722 | |
723 | |
724 | |
725 | const APInt operator--(int) { |
726 | APInt API(*this); |
727 | --(*this); |
728 | return API; |
729 | } |
730 | |
731 | |
732 | |
733 | |
734 | APInt &operator--(); |
735 | |
736 | |
737 | |
738 | |
739 | |
740 | |
741 | bool operator!() const { |
742 | if (isSingleWord()) |
743 | return U.VAL == 0; |
744 | return countLeadingZerosSlowCase() == BitWidth; |
745 | } |
746 | |
747 | |
748 | |
749 | |
750 | |
751 | |
752 | |
753 | |
754 | APInt &operator=(const APInt &RHS) { |
755 | |
756 | if (isSingleWord() && RHS.isSingleWord()) { |
757 | U.VAL = RHS.U.VAL; |
758 | BitWidth = RHS.BitWidth; |
759 | return clearUnusedBits(); |
760 | } |
761 | |
762 | AssignSlowCase(RHS); |
763 | return *this; |
764 | } |
765 | |
766 | |
767 | APInt &operator=(APInt &&that) { |
768 | #ifdef EXPENSIVE_CHECKS |
769 | |
770 | if (this == &that) |
771 | return *this; |
772 | #endif |
773 | assert(this != &that && "Self-move not supported"); |
774 | if (!isSingleWord()) |
775 | delete[] U.pVal; |
776 | |
777 | |
778 | |
779 | memcpy(&U, &that.U, sizeof(U)); |
780 | |
781 | BitWidth = that.BitWidth; |
782 | that.BitWidth = 0; |
783 | |
784 | return *this; |
785 | } |
786 | |
787 | |
788 | |
789 | |
790 | |
791 | |
792 | |
793 | |
794 | APInt &operator=(uint64_t RHS) { |
795 | if (isSingleWord()) { |
796 | U.VAL = RHS; |
797 | return clearUnusedBits(); |
798 | } |
799 | U.pVal[0] = RHS; |
800 | memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); |
801 | return *this; |
802 | } |
803 | |
804 | |
805 | |
806 | |
807 | |
808 | |
809 | |
810 | APInt &operator&=(const APInt &RHS) { |
811 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
812 | if (isSingleWord()) |
813 | U.VAL &= RHS.U.VAL; |
814 | else |
815 | AndAssignSlowCase(RHS); |
816 | return *this; |
817 | } |
818 | |
819 | |
820 | |
821 | |
822 | |
823 | |
824 | APInt &operator&=(uint64_t RHS) { |
825 | if (isSingleWord()) { |
826 | U.VAL &= RHS; |
827 | return *this; |
828 | } |
829 | U.pVal[0] &= RHS; |
830 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); |
831 | return *this; |
832 | } |
833 | |
834 | |
835 | |
836 | |
837 | |
838 | |
839 | |
840 | APInt &operator|=(const APInt &RHS) { |
841 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
842 | if (isSingleWord()) |
843 | U.VAL |= RHS.U.VAL; |
844 | else |
845 | OrAssignSlowCase(RHS); |
846 | return *this; |
847 | } |
848 | |
849 | |
850 | |
851 | |
852 | |
853 | |
854 | APInt &operator|=(uint64_t RHS) { |
855 | if (isSingleWord()) { |
856 | U.VAL |= RHS; |
857 | return clearUnusedBits(); |
858 | } |
859 | U.pVal[0] |= RHS; |
860 | return *this; |
861 | } |
862 | |
863 | |
864 | |
865 | |
866 | |
867 | |
868 | |
869 | APInt &operator^=(const APInt &RHS) { |
870 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
871 | if (isSingleWord()) |
872 | U.VAL ^= RHS.U.VAL; |
873 | else |
874 | XorAssignSlowCase(RHS); |
875 | return *this; |
876 | } |
877 | |
878 | |
879 | |
880 | |
881 | |
882 | |
883 | APInt &operator^=(uint64_t RHS) { |
884 | if (isSingleWord()) { |
885 | U.VAL ^= RHS; |
886 | return clearUnusedBits(); |
887 | } |
888 | U.pVal[0] ^= RHS; |
889 | return *this; |
890 | } |
891 | |
892 | |
893 | |
894 | |
895 | |
896 | |
897 | APInt &operator*=(const APInt &RHS); |
898 | APInt &operator*=(uint64_t RHS); |
899 | |
900 | |
901 | |
902 | |
903 | |
904 | |
905 | APInt &operator+=(const APInt &RHS); |
906 | APInt &operator+=(uint64_t RHS); |
907 | |
908 | |
909 | |
910 | |
911 | |
912 | |
913 | APInt &operator-=(const APInt &RHS); |
914 | APInt &operator-=(uint64_t RHS); |
915 | |
916 | |
917 | |
918 | |
919 | |
920 | |
921 | APInt &operator<<=(unsigned ShiftAmt) { |
922 | assert(ShiftAmt <= BitWidth && "Invalid shift amount"); |
923 | if (isSingleWord()) { |
| 58 | | Calling 'APInt::isSingleWord' | |
|
| 61 | | Returning from 'APInt::isSingleWord' | |
|
| |
924 | if (ShiftAmt == BitWidth) |
| |
925 | U.VAL = 0; |
926 | else |
927 | U.VAL <<= ShiftAmt; |
| 64 | | Assigned value is garbage or undefined |
|
928 | return clearUnusedBits(); |
929 | } |
930 | shlSlowCase(ShiftAmt); |
931 | return *this; |
932 | } |
933 | |
934 | |
935 | |
936 | |
937 | |
938 | |
939 | APInt &operator<<=(const APInt &ShiftAmt); |
940 | |
941 | |
942 | |
943 | |
944 | |
945 | |
946 | |
947 | |
948 | APInt operator*(const APInt &RHS) const; |
949 | |
950 | |
951 | |
952 | |
953 | APInt operator<<(unsigned Bits) const { return shl(Bits); } |
954 | |
955 | |
956 | |
957 | |
958 | APInt operator<<(const APInt &Bits) const { return shl(Bits); } |
959 | |
960 | |
961 | |
962 | |
963 | APInt ashr(unsigned ShiftAmt) const { |
964 | APInt R(*this); |
965 | R.ashrInPlace(ShiftAmt); |
966 | return R; |
967 | } |
968 | |
969 | |
970 | void ashrInPlace(unsigned ShiftAmt) { |
971 | assert(ShiftAmt <= BitWidth && "Invalid shift amount"); |
972 | if (isSingleWord()) { |
973 | int64_t SExtVAL = SignExtend64(U.VAL, BitWidth); |
974 | if (ShiftAmt == BitWidth) |
975 | U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); |
976 | else |
977 | U.VAL = SExtVAL >> ShiftAmt; |
978 | clearUnusedBits(); |
979 | return; |
980 | } |
981 | ashrSlowCase(ShiftAmt); |
982 | } |
983 | |
984 | |
985 | |
986 | |
987 | APInt lshr(unsigned shiftAmt) const { |
988 | APInt R(*this); |
989 | R.lshrInPlace(shiftAmt); |
990 | return R; |
991 | } |
992 | |
993 | |
994 | void lshrInPlace(unsigned ShiftAmt) { |
995 | assert(ShiftAmt <= BitWidth && "Invalid shift amount"); |
996 | if (isSingleWord()) { |
997 | if (ShiftAmt == BitWidth) |
998 | U.VAL = 0; |
999 | else |
1000 | U.VAL >>= ShiftAmt; |
1001 | return; |
1002 | } |
1003 | lshrSlowCase(ShiftAmt); |
1004 | } |
1005 | |
1006 | |
1007 | |
1008 | |
1009 | APInt shl(unsigned shiftAmt) const { |
1010 | APInt R(*this); |
1011 | R <<= shiftAmt; |
1012 | return R; |
1013 | } |
1014 | |
1015 | |
1016 | APInt rotl(unsigned rotateAmt) const; |
1017 | |
1018 | |
1019 | APInt rotr(unsigned rotateAmt) const; |
1020 | |
1021 | |
1022 | |
1023 | |
1024 | APInt ashr(const APInt &ShiftAmt) const { |
1025 | APInt R(*this); |
1026 | R.ashrInPlace(ShiftAmt); |
1027 | return R; |
1028 | } |
1029 | |
1030 | |
1031 | void ashrInPlace(const APInt &shiftAmt); |
1032 | |
1033 | |
1034 | |
1035 | |
1036 | APInt lshr(const APInt &ShiftAmt) const { |
1037 | APInt R(*this); |
1038 | R.lshrInPlace(ShiftAmt); |
1039 | return R; |
1040 | } |
1041 | |
1042 | |
1043 | void lshrInPlace(const APInt &ShiftAmt); |
1044 | |
1045 | |
1046 | |
1047 | |
1048 | APInt shl(const APInt &ShiftAmt) const { |
1049 | APInt R(*this); |
1050 | R <<= ShiftAmt; |
1051 | return R; |
1052 | } |
1053 | |
1054 | |
1055 | APInt rotl(const APInt &rotateAmt) const; |
1056 | |
1057 | |
1058 | APInt rotr(const APInt &rotateAmt) const; |
1059 | |
1060 | |
1061 | |
1062 | |
1063 | |
1064 | |
1065 | |
1066 | |
1067 | APInt udiv(const APInt &RHS) const; |
1068 | APInt udiv(uint64_t RHS) const; |
1069 | |
1070 | |
1071 | |
1072 | |
1073 | |
1074 | |
1075 | APInt sdiv(const APInt &RHS) const; |
1076 | APInt sdiv(int64_t RHS) const; |
1077 | |
1078 | |
1079 | |
1080 | |
1081 | |
1082 | |
1083 | |
1084 | |
1085 | |
1086 | |
1087 | APInt urem(const APInt &RHS) const; |
1088 | uint64_t urem(uint64_t RHS) const; |
1089 | |
1090 | |
1091 | |
1092 | |
1093 | APInt srem(const APInt &RHS) const; |
1094 | int64_t srem(int64_t RHS) const; |
1095 | |
1096 | |
1097 | |
1098 | |
1099 | |
1100 | |
1101 | |
1102 | |
1103 | static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, |
1104 | APInt &Remainder); |
1105 | static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, |
1106 | uint64_t &Remainder); |
1107 | |
1108 | static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, |
1109 | APInt &Remainder); |
1110 | static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, |
1111 | int64_t &Remainder); |
1112 | |
1113 | |
1114 | APInt sadd_ov(const APInt &RHS, bool &Overflow) const; |
1115 | APInt uadd_ov(const APInt &RHS, bool &Overflow) const; |
1116 | APInt ssub_ov(const APInt &RHS, bool &Overflow) const; |
1117 | APInt usub_ov(const APInt &RHS, bool &Overflow) const; |
1118 | APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; |
1119 | APInt smul_ov(const APInt &RHS, bool &Overflow) const; |
1120 | APInt umul_ov(const APInt &RHS, bool &Overflow) const; |
1121 | APInt sshl_ov(const APInt &Amt, bool &Overflow) const; |
1122 | APInt ushl_ov(const APInt &Amt, bool &Overflow) const; |
1123 | |
1124 | |
1125 | APInt sadd_sat(const APInt &RHS) const; |
1126 | APInt uadd_sat(const APInt &RHS) const; |
1127 | APInt ssub_sat(const APInt &RHS) const; |
1128 | APInt usub_sat(const APInt &RHS) const; |
1129 | APInt smul_sat(const APInt &RHS) const; |
1130 | APInt umul_sat(const APInt &RHS) const; |
1131 | APInt sshl_sat(const APInt &RHS) const; |
1132 | APInt ushl_sat(const APInt &RHS) const; |
1133 | |
1134 | |
1135 | |
1136 | |
1137 | bool operator[](unsigned bitPosition) const { |
1138 | assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); |
1139 | return (maskBit(bitPosition) & getWord(bitPosition)) != 0; |
1140 | } |
1141 | |
1142 | |
1143 | |
1144 | |
1145 | |
1146 | |
1147 | |
1148 | |
1149 | |
1150 | bool operator==(const APInt &RHS) const { |
1151 | assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"); |
1152 | if (isSingleWord()) |
1153 | return U.VAL == RHS.U.VAL; |
1154 | return EqualSlowCase(RHS); |
1155 | } |
1156 | |
1157 | |
1158 | |
1159 | |
1160 | |
1161 | |
1162 | |
1163 | bool operator==(uint64_t Val) const { |
1164 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val; |
1165 | } |
1166 | |
1167 | |
1168 | |
1169 | |
1170 | |
1171 | |
1172 | |
1173 | bool eq(const APInt &RHS) const { return (*this) == RHS; } |
1174 | |
1175 | |
1176 | |
1177 | |
1178 | |
1179 | |
1180 | |
1181 | bool operator!=(const APInt &RHS) const { return !((*this) == RHS); } |
1182 | |
1183 | |
1184 | |
1185 | |
1186 | |
1187 | |
1188 | |
1189 | bool operator!=(uint64_t Val) const { return !((*this) == Val); } |
1190 | |
1191 | |
1192 | |
1193 | |
1194 | |
1195 | |
1196 | |
1197 | bool ne(const APInt &RHS) const { return !((*this) == RHS); } |
1198 | |
1199 | |
1200 | |
1201 | |
1202 | |
1203 | |
1204 | |
1205 | bool ult(const APInt &RHS) const { return compare(RHS) < 0; } |
1206 | |
1207 | |
1208 | |
1209 | |
1210 | |
1211 | |
1212 | |
1213 | bool ult(uint64_t RHS) const { |
1214 | |
1215 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS; |
1216 | } |
1217 | |
1218 | |
1219 | |
1220 | |
1221 | |
1222 | |
1223 | |
1224 | bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; } |
1225 | |
1226 | |
1227 | |
1228 | |
1229 | |
1230 | |
1231 | |
1232 | bool slt(int64_t RHS) const { |
1233 | return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative() |
1234 | : getSExtValue() < RHS; |
1235 | } |
1236 | |
1237 | |
1238 | |
1239 | |
1240 | |
1241 | |
1242 | |
1243 | bool ule(const APInt &RHS) const { return compare(RHS) <= 0; } |
1244 | |
1245 | |
1246 | |
1247 | |
1248 | |
1249 | |
1250 | |
1251 | bool ule(uint64_t RHS) const { return !ugt(RHS); } |
1252 | |
1253 | |
1254 | |
1255 | |
1256 | |
1257 | |
1258 | |
1259 | bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; } |
1260 | |
1261 | |
1262 | |
1263 | |
1264 | |
1265 | |
1266 | |
1267 | bool sle(uint64_t RHS) const { return !sgt(RHS); } |
1268 | |
1269 | |
1270 | |
1271 | |
1272 | |
1273 | |
1274 | |
1275 | bool ugt(const APInt &RHS) const { return !ule(RHS); } |
1276 | |
1277 | |
1278 | |
1279 | |
1280 | |
1281 | |
1282 | |
1283 | bool ugt(uint64_t RHS) const { |
1284 | |
1285 | return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS; |
1286 | } |
1287 | |
1288 | |
1289 | |
1290 | |
1291 | |
1292 | |
1293 | |
1294 | bool sgt(const APInt &RHS) const { return !sle(RHS); } |
1295 | |
1296 | |
1297 | |
1298 | |
1299 | |
1300 | |
1301 | |
1302 | bool sgt(int64_t RHS) const { |
1303 | return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative() |
1304 | : getSExtValue() > RHS; |
1305 | } |
1306 | |
1307 | |
1308 | |
1309 | |
1310 | |
1311 | |
1312 | |
1313 | bool uge(const APInt &RHS) const { return !ult(RHS); } |
1314 | |
1315 | |
1316 | |
1317 | |
1318 | |
1319 | |
1320 | |
1321 | bool uge(uint64_t RHS) const { return !ult(RHS); } |
1322 | |
1323 | |
1324 | |
1325 | |
1326 | |
1327 | |
1328 | |
1329 | bool sge(const APInt &RHS) const { return !slt(RHS); } |
1330 | |
1331 | |
1332 | |
1333 | |
1334 | |
1335 | |
1336 | |
1337 | bool sge(int64_t RHS) const { return !slt(RHS); } |
1338 | |
1339 | |
1340 | |
1341 | bool intersects(const APInt &RHS) const { |
1342 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
1343 | if (isSingleWord()) |
1344 | return (U.VAL & RHS.U.VAL) != 0; |
1345 | return intersectsSlowCase(RHS); |
1346 | } |
1347 | |
1348 | |
1349 | bool isSubsetOf(const APInt &RHS) const { |
1350 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
1351 | if (isSingleWord()) |
1352 | return (U.VAL & ~RHS.U.VAL) == 0; |
1353 | return isSubsetOfSlowCase(RHS); |
1354 | } |
1355 | |
1356 | |
1357 | |
1358 | |
1359 | |
1360 | |
1361 | |
1362 | |
1363 | |
1364 | APInt trunc(unsigned width) const; |
1365 | |
1366 | |
1367 | |
1368 | |
1369 | |
1370 | APInt truncUSat(unsigned width) const; |
1371 | |
1372 | |
1373 | |
1374 | |
1375 | |
1376 | |
1377 | APInt truncSSat(unsigned width) const; |
1378 | |
1379 | |
1380 | |
1381 | |
1382 | |
1383 | |
1384 | |
1385 | APInt sext(unsigned width) const; |
1386 | |
1387 | |
1388 | |
1389 | |
1390 | |
1391 | |
1392 | APInt zext(unsigned width) const; |
1393 | |
1394 | |
1395 | |
1396 | |
1397 | |
1398 | APInt sextOrTrunc(unsigned width) const; |
1399 | |
1400 | |
1401 | |
1402 | |
1403 | |
1404 | APInt zextOrTrunc(unsigned width) const; |
1405 | |
1406 | |
1407 | |
1408 | |
1409 | |
1410 | APInt truncOrSelf(unsigned width) const; |
1411 | |
1412 | |
1413 | |
1414 | |
1415 | |
1416 | APInt sextOrSelf(unsigned width) const; |
1417 | |
1418 | |
1419 | |
1420 | |
1421 | |
1422 | APInt zextOrSelf(unsigned width) const; |
1423 | |
1424 | |
1425 | |
1426 | |
1427 | |
1428 | |
1429 | void setAllBits() { |
1430 | if (isSingleWord()) |
1431 | U.VAL = WORDTYPE_MAX; |
1432 | else |
1433 | |
1434 | memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE); |
1435 | |
1436 | clearUnusedBits(); |
1437 | } |
1438 | |
1439 | |
1440 | |
1441 | |
1442 | void setBit(unsigned BitPosition) { |
1443 | assert(BitPosition < BitWidth && "BitPosition out of range"); |
1444 | WordType Mask = maskBit(BitPosition); |
1445 | if (isSingleWord()) |
1446 | U.VAL |= Mask; |
1447 | else |
1448 | U.pVal[whichWord(BitPosition)] |= Mask; |
1449 | } |
1450 | |
1451 | |
1452 | void setSignBit() { |
1453 | setBit(BitWidth - 1); |
1454 | } |
1455 | |
1456 | |
1457 | void setBitVal(unsigned BitPosition, bool BitValue) { |
1458 | if (BitValue) |
1459 | setBit(BitPosition); |
1460 | else |
1461 | clearBit(BitPosition); |
1462 | } |
1463 | |
1464 | |
1465 | |
1466 | |
1467 | |
1468 | void setBitsWithWrap(unsigned loBit, unsigned hiBit) { |
1469 | assert(hiBit <= BitWidth && "hiBit out of range"); |
1470 | assert(loBit <= BitWidth && "loBit out of range"); |
1471 | if (loBit < hiBit) { |
1472 | setBits(loBit, hiBit); |
1473 | return; |
1474 | } |
1475 | setLowBits(hiBit); |
1476 | setHighBits(BitWidth - loBit); |
1477 | } |
1478 | |
1479 | |
1480 | |
1481 | void setBits(unsigned loBit, unsigned hiBit) { |
1482 | assert(hiBit <= BitWidth && "hiBit out of range"); |
1483 | assert(loBit <= BitWidth && "loBit out of range"); |
1484 | assert(loBit <= hiBit && "loBit greater than hiBit"); |
1485 | if (loBit == hiBit) |
1486 | return; |
1487 | if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { |
1488 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); |
1489 | mask <<= loBit; |
1490 | if (isSingleWord()) |
1491 | U.VAL |= mask; |
1492 | else |
1493 | U.pVal[0] |= mask; |
1494 | } else { |
1495 | setBitsSlowCase(loBit, hiBit); |
1496 | } |
1497 | } |
1498 | |
1499 | |
1500 | void setBitsFrom(unsigned loBit) { |
1501 | return setBits(loBit, BitWidth); |
1502 | } |
1503 | |
1504 | |
1505 | void setLowBits(unsigned loBits) { |
1506 | return setBits(0, loBits); |
1507 | } |
1508 | |
1509 | |
1510 | void setHighBits(unsigned hiBits) { |
1511 | return setBits(BitWidth - hiBits, BitWidth); |
1512 | } |
1513 | |
1514 | |
1515 | void clearAllBits() { |
1516 | if (isSingleWord()) |
1517 | U.VAL = 0; |
1518 | else |
1519 | memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE); |
1520 | } |
1521 | |
1522 | |
1523 | |
1524 | |
1525 | void clearBit(unsigned BitPosition) { |
1526 | assert(BitPosition < BitWidth && "BitPosition out of range"); |
1527 | WordType Mask = ~maskBit(BitPosition); |
1528 | if (isSingleWord()) |
1529 | U.VAL &= Mask; |
1530 | else |
1531 | U.pVal[whichWord(BitPosition)] &= Mask; |
1532 | } |
1533 | |
1534 | |
1535 | void clearLowBits(unsigned loBits) { |
1536 | assert(loBits <= BitWidth && "More bits than bitwidth"); |
1537 | APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits); |
1538 | *this &= Keep; |
1539 | } |
1540 | |
1541 | |
1542 | void clearSignBit() { |
1543 | clearBit(BitWidth - 1); |
1544 | } |
1545 | |
1546 | |
1547 | void flipAllBits() { |
1548 | if (isSingleWord()) { |
1549 | U.VAL ^= WORDTYPE_MAX; |
1550 | clearUnusedBits(); |
1551 | } else { |
1552 | flipAllBitsSlowCase(); |
1553 | } |
1554 | } |
1555 | |
1556 | |
1557 | |
1558 | |
1559 | |
1560 | void flipBit(unsigned bitPosition); |
1561 | |
1562 | |
1563 | void negate() { |
1564 | flipAllBits(); |
1565 | ++(*this); |
1566 | } |
1567 | |
1568 | |
1569 | void insertBits(const APInt &SubBits, unsigned bitPosition); |
1570 | void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits); |
1571 | |
1572 | |
1573 | APInt extractBits(unsigned numBits, unsigned bitPosition) const; |
1574 | uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const; |
1575 | |
1576 | |
1577 | |
1578 | |
1579 | |
1580 | |
1581 | unsigned getBitWidth() const { return BitWidth; } |
1582 | |
1583 | |
1584 | |
1585 | |
1586 | |
1587 | |
1588 | unsigned getNumWords() const { return getNumWords(BitWidth); } |
1589 | |
1590 | |
1591 | |
1592 | |
1593 | |
1594 | |
1595 | |
1596 | static unsigned getNumWords(unsigned BitWidth) { |
1597 | return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; |
1598 | } |
1599 | |
1600 | |
1601 | |
1602 | |
1603 | |
1604 | |
1605 | unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); } |
1606 | |
1607 | |
1608 | |
1609 | |
1610 | |
1611 | unsigned getActiveWords() const { |
1612 | unsigned numActiveBits = getActiveBits(); |
1613 | return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; |
1614 | } |
1615 | |
1616 | |
1617 | |
1618 | |
1619 | |
1620 | |
1621 | |
1622 | |
1623 | |
1624 | unsigned getMinSignedBits() const { return BitWidth - getNumSignBits() + 1; } |
1625 | |
1626 | |
1627 | |
1628 | |
1629 | |
1630 | |
1631 | uint64_t getZExtValue() const { |
1632 | if (isSingleWord()) |
1633 | return U.VAL; |
1634 | assert(getActiveBits() <= 64 && "Too many bits for uint64_t"); |
1635 | return U.pVal[0]; |
1636 | } |
1637 | |
1638 | |
1639 | |
1640 | |
1641 | |
1642 | |
1643 | int64_t getSExtValue() const { |
1644 | if (isSingleWord()) |
1645 | return SignExtend64(U.VAL, BitWidth); |
1646 | assert(getMinSignedBits() <= 64 && "Too many bits for int64_t"); |
1647 | return int64_t(U.pVal[0]); |
1648 | } |
1649 | |
1650 | |
1651 | |
1652 | |
1653 | |
1654 | static unsigned getBitsNeeded(StringRef str, uint8_t radix); |
1655 | |
1656 | |
1657 | |
1658 | |
1659 | |
1660 | |
1661 | |
1662 | |
1663 | |
1664 | unsigned countLeadingZeros() const { |
1665 | if (isSingleWord()) { |
1666 | unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; |
1667 | return llvm::countLeadingZeros(U.VAL) - unusedBits; |
1668 | } |
1669 | return countLeadingZerosSlowCase(); |
1670 | } |
1671 | |
1672 | |
1673 | |
1674 | |
1675 | |
1676 | |
1677 | |
1678 | |
1679 | |
1680 | unsigned countLeadingOnes() const { |
1681 | if (isSingleWord()) |
1682 | return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth)); |
1683 | return countLeadingOnesSlowCase(); |
1684 | } |
1685 | |
1686 | |
1687 | |
1688 | unsigned getNumSignBits() const { |
1689 | return isNegative() ? countLeadingOnes() : countLeadingZeros(); |
1690 | } |
1691 | |
1692 | |
1693 | |
1694 | |
1695 | |
1696 | |
1697 | |
1698 | |
1699 | |
1700 | unsigned countTrailingZeros() const { |
1701 | if (isSingleWord()) { |
1702 | unsigned TrailingZeros = llvm::countTrailingZeros(U.VAL); |
1703 | return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros); |
1704 | } |
1705 | return countTrailingZerosSlowCase(); |
1706 | } |
1707 | |
1708 | |
1709 | |
1710 | |
1711 | |
1712 | |
1713 | |
1714 | |
1715 | |
1716 | unsigned countTrailingOnes() const { |
1717 | if (isSingleWord()) |
1718 | return llvm::countTrailingOnes(U.VAL); |
1719 | return countTrailingOnesSlowCase(); |
1720 | } |
1721 | |
1722 | |
1723 | |
1724 | |
1725 | |
1726 | |
1727 | |
1728 | unsigned countPopulation() const { |
1729 | if (isSingleWord()) |
1730 | return llvm::countPopulation(U.VAL); |
1731 | return countPopulationSlowCase(); |
1732 | } |
1733 | |
1734 | |
1735 | |
1736 | |
1737 | void print(raw_ostream &OS, bool isSigned) const; |
1738 | |
1739 | |
1740 | |
1741 | void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, |
1742 | bool formatAsCLiteral = false) const; |
1743 | |
1744 | |
1745 | |
1746 | void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { |
1747 | toString(Str, Radix, false, false); |
1748 | } |
1749 | |
1750 | |
1751 | |
1752 | void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { |
1753 | toString(Str, Radix, true, false); |
1754 | } |
1755 | |
1756 | |
1757 | APInt byteSwap() const; |
1758 | |
1759 | |
1760 | |
1761 | APInt reverseBits() const; |
1762 | |
1763 | |
1764 | double roundToDouble(bool isSigned) const; |
1765 | |
1766 | |
1767 | double roundToDouble() const { return roundToDouble(false); } |
1768 | |
1769 | |
1770 | double signedRoundToDouble() const { return roundToDouble(true); } |
1771 | |
1772 | |
1773 | |
1774 | |
1775 | |
1776 | |
1777 | double bitsToDouble() const { |
1778 | return BitsToDouble(getWord(0)); |
1779 | } |
1780 | |
1781 | |
1782 | |
1783 | |
1784 | |
1785 | |
1786 | float bitsToFloat() const { |
1787 | return BitsToFloat(static_cast<uint32_t>(getWord(0))); |
1788 | } |
1789 | |
1790 | |
1791 | |
1792 | |
1793 | |
1794 | static APInt doubleToBits(double V) { |
1795 | return APInt(sizeof(double) * CHAR_BIT, DoubleToBits(V)); |
1796 | } |
1797 | |
1798 | |
1799 | |
1800 | |
1801 | |
1802 | static APInt floatToBits(float V) { |
1803 | return APInt(sizeof(float) * CHAR_BIT, FloatToBits(V)); |
1804 | } |
1805 | |
1806 | |
1807 | |
1808 | |
1809 | |
1810 | |
1811 | unsigned logBase2() const { return getActiveBits() - 1; } |
1812 | |
1813 | |
1814 | unsigned ceilLogBase2() const { |
1815 | APInt temp(*this); |
1816 | --temp; |
1817 | return temp.getActiveBits(); |
1818 | } |
1819 | |
1820 | |
1821 | |
1822 | |
1823 | |
1824 | |
1825 | |
1826 | |
1827 | |
1828 | |
1829 | unsigned nearestLogBase2() const { |
1830 | |
1831 | |
1832 | |
1833 | if (BitWidth == 1) |
1834 | return U.VAL - 1; |
1835 | |
1836 | |
1837 | if (isNullValue()) |
1838 | return UINT32_MAX; |
1839 | |
1840 | |
1841 | |
1842 | |
1843 | |
1844 | |
1845 | unsigned lg = logBase2(); |
1846 | return lg + unsigned((*this)[lg - 1]); |
1847 | } |
1848 | |
1849 | |
1850 | |
1851 | int32_t exactLogBase2() const { |
1852 | if (!isPowerOf2()) |
1853 | return -1; |
1854 | return logBase2(); |
1855 | } |
1856 | |
1857 | |
1858 | APInt sqrt() const; |
1859 | |
1860 | |
1861 | |
1862 | |
1863 | APInt abs() const { |
1864 | if (isNegative()) |
1865 | return -(*this); |
1866 | return *this; |
1867 | } |
1868 | |
1869 | |
1870 | APInt multiplicativeInverse(const APInt &modulo) const; |
1871 | |
1872 | |
1873 | |
1874 | |
1875 | |
1876 | |
1877 | struct ms; |
1878 | ms magic() const; |
1879 | |
1880 | |
1881 | struct mu; |
1882 | mu magicu(unsigned LeadingZeros = 0) const; |
1883 | |
1884 | |
1885 | |
1886 | |
1887 | |
1888 | |
1889 | |
1890 | |
1891 | |
1892 | |
1893 | |
1894 | |
1895 | |
1896 | static void tcSet(WordType *, WordType, unsigned); |
1897 | |
1898 | |
1899 | static void tcAssign(WordType *, const WordType *, unsigned); |
1900 | |
1901 | |
1902 | static bool tcIsZero(const WordType *, unsigned); |
1903 | |
1904 | |
1905 | static int tcExtractBit(const WordType *, unsigned bit); |
1906 | |
1907 | |
1908 | |
1909 | |
1910 | |
1911 | static void tcExtract(WordType *, unsigned dstCount, |
1912 | const WordType *, unsigned srcBits, |
1913 | unsigned srcLSB); |
1914 | |
1915 | |
1916 | static void tcSetBit(WordType *, unsigned bit); |
1917 | |
1918 | |
1919 | static void tcClearBit(WordType *, unsigned bit); |
1920 | |
1921 | |
1922 | |
1923 | static unsigned tcLSB(const WordType *, unsigned n); |
1924 | static unsigned tcMSB(const WordType *parts, unsigned n); |
1925 | |
1926 | |
1927 | static void tcNegate(WordType *, unsigned); |
1928 | |
1929 | |
1930 | static WordType tcAdd(WordType *, const WordType *, |
1931 | WordType carry, unsigned); |
1932 | |
1933 | static WordType tcAddPart(WordType *, WordType, unsigned); |
1934 | |
1935 | |
1936 | static WordType tcSubtract(WordType *, const WordType *, |
1937 | WordType carry, unsigned); |
1938 | |
1939 | static WordType tcSubtractPart(WordType *, WordType, unsigned); |
1940 | |
1941 | |
1942 | |
1943 | |
1944 | |
1945 | |
1946 | |
1947 | |
1948 | |
1949 | |
1950 | |
1951 | static int tcMultiplyPart(WordType *dst, const WordType *src, |
1952 | WordType multiplier, WordType carry, |
1953 | unsigned srcParts, unsigned dstParts, |
1954 | bool add); |
1955 | |
1956 | |
1957 | |
1958 | |
1959 | |
1960 | static int tcMultiply(WordType *, const WordType *, const WordType *, |
1961 | unsigned); |
1962 | |
1963 | |
1964 | |
1965 | static void tcFullMultiply(WordType *, const WordType *, |
1966 | const WordType *, unsigned, unsigned); |
1967 | |
1968 | |
1969 | |
1970 | |
1971 | |
1972 | |
1973 | |
1974 | |
1975 | |
1976 | |
1977 | static int tcDivide(WordType *lhs, const WordType *rhs, |
1978 | WordType *remainder, WordType *scratch, |
1979 | unsigned parts); |
1980 | |
1981 | |
1982 | |
1983 | static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); |
1984 | |
1985 | |
1986 | |
1987 | static void tcShiftRight(WordType *, unsigned Words, unsigned Count); |
1988 | |
1989 | |
1990 | static void tcAnd(WordType *, const WordType *, unsigned); |
1991 | static void tcOr(WordType *, const WordType *, unsigned); |
1992 | static void tcXor(WordType *, const WordType *, unsigned); |
1993 | static void tcComplement(WordType *, unsigned); |
1994 | |
1995 | |
1996 | static int tcCompare(const WordType *, const WordType *, unsigned); |
1997 | |
1998 | |
1999 | static WordType tcIncrement(WordType *dst, unsigned parts) { |
2000 | return tcAddPart(dst, 1, parts); |
2001 | } |
2002 | |
2003 | |
2004 | static WordType tcDecrement(WordType *dst, unsigned parts) { |
2005 | return tcSubtractPart(dst, 1, parts); |
2006 | } |
2007 | |
2008 | |
2009 | static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); |
2010 | |
2011 | |
2012 | void dump() const; |
2013 | |
2014 | |
2015 | }; |
2016 | |
2017 | |
2018 | struct APInt::ms { |
2019 | APInt m; |
2020 | unsigned s; |
2021 | }; |
2022 | |
2023 | |
2024 | struct APInt::mu { |
2025 | APInt m; |
2026 | bool a; |
2027 | unsigned s; |
2028 | }; |
2029 | |
2030 | inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } |
2031 | |
2032 | inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } |
2033 | |
2034 | |
2035 | |
2036 | |
2037 | inline APInt operator~(APInt v) { |
2038 | v.flipAllBits(); |
2039 | return v; |
2040 | } |
2041 | |
2042 | inline APInt operator&(APInt a, const APInt &b) { |
2043 | a &= b; |
2044 | return a; |
2045 | } |
2046 | |
2047 | inline APInt operator&(const APInt &a, APInt &&b) { |
2048 | b &= a; |
2049 | return std::move(b); |
2050 | } |
2051 | |
2052 | inline APInt operator&(APInt a, uint64_t RHS) { |
2053 | a &= RHS; |
2054 | return a; |
2055 | } |
2056 | |
2057 | inline APInt operator&(uint64_t LHS, APInt b) { |
2058 | b &= LHS; |
2059 | return b; |
2060 | } |
2061 | |
2062 | inline APInt operator|(APInt a, const APInt &b) { |
2063 | a |= b; |
2064 | return a; |
2065 | } |
2066 | |
2067 | inline APInt operator|(const APInt &a, APInt &&b) { |
2068 | b |= a; |
2069 | return std::move(b); |
2070 | } |
2071 | |
2072 | inline APInt operator|(APInt a, uint64_t RHS) { |
2073 | a |= RHS; |
2074 | return a; |
2075 | } |
2076 | |
2077 | inline APInt operator|(uint64_t LHS, APInt b) { |
2078 | b |= LHS; |
2079 | return b; |
2080 | } |
2081 | |
2082 | inline APInt operator^(APInt a, const APInt &b) { |
2083 | a ^= b; |
2084 | return a; |
2085 | } |
2086 | |
2087 | inline APInt operator^(const APInt &a, APInt &&b) { |
2088 | b ^= a; |
2089 | return std::move(b); |
2090 | } |
2091 | |
2092 | inline APInt operator^(APInt a, uint64_t RHS) { |
2093 | a ^= RHS; |
2094 | return a; |
2095 | } |
2096 | |
2097 | inline APInt operator^(uint64_t LHS, APInt b) { |
2098 | b ^= LHS; |
2099 | return b; |
2100 | } |
2101 | |
2102 | inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { |
2103 | I.print(OS, true); |
2104 | return OS; |
2105 | } |
2106 | |
2107 | inline APInt operator-(APInt v) { |
2108 | v.negate(); |
2109 | return v; |
2110 | } |
2111 | |
2112 | inline APInt operator+(APInt a, const APInt &b) { |
2113 | a += b; |
2114 | return a; |
2115 | } |
2116 | |
2117 | inline APInt operator+(const APInt &a, APInt &&b) { |
2118 | b += a; |
2119 | return std::move(b); |
2120 | } |
2121 | |
2122 | inline APInt operator+(APInt a, uint64_t RHS) { |
2123 | a += RHS; |
2124 | return a; |
2125 | } |
2126 | |
2127 | inline APInt operator+(uint64_t LHS, APInt b) { |
2128 | b += LHS; |
2129 | return b; |
2130 | } |
2131 | |
2132 | inline APInt operator-(APInt a, const APInt &b) { |
2133 | a -= b; |
2134 | return a; |
2135 | } |
2136 | |
2137 | inline APInt operator-(const APInt &a, APInt &&b) { |
2138 | b.negate(); |
2139 | b += a; |
2140 | return std::move(b); |
2141 | } |
2142 | |
2143 | inline APInt operator-(APInt a, uint64_t RHS) { |
2144 | a -= RHS; |
2145 | return a; |
2146 | } |
2147 | |
2148 | inline APInt operator-(uint64_t LHS, APInt b) { |
2149 | b.negate(); |
2150 | b += LHS; |
2151 | return b; |
2152 | } |
2153 | |
2154 | inline APInt operator*(APInt a, uint64_t RHS) { |
2155 | a *= RHS; |
2156 | return a; |
2157 | } |
2158 | |
2159 | inline APInt operator*(uint64_t LHS, APInt b) { |
2160 | b *= LHS; |
2161 | return b; |
2162 | } |
2163 | |
2164 | |
2165 | namespace APIntOps { |
2166 | |
2167 | |
2168 | inline const APInt &smin(const APInt &A, const APInt &B) { |
2169 | return A.slt(B) ? A : B; |
2170 | } |
2171 | |
2172 | |
2173 | inline const APInt &smax(const APInt &A, const APInt &B) { |
2174 | return A.sgt(B) ? A : B; |
2175 | } |
2176 | |
2177 | |
2178 | inline const APInt &umin(const APInt &A, const APInt &B) { |
2179 | return A.ult(B) ? A : B; |
2180 | } |
2181 | |
2182 | |
2183 | inline const APInt &umax(const APInt &A, const APInt &B) { |
2184 | return A.ugt(B) ? A : B; |
2185 | } |
2186 | |
2187 | |
2188 | |
2189 | |
2190 | |
2191 | |
2192 | |
2193 | APInt GreatestCommonDivisor(APInt A, APInt B); |
2194 | |
2195 | |
2196 | |
2197 | |
2198 | inline double RoundAPIntToDouble(const APInt &APIVal) { |
2199 | return APIVal.roundToDouble(); |
2200 | } |
2201 | |
2202 | |
2203 | |
2204 | |
2205 | inline double RoundSignedAPIntToDouble(const APInt &APIVal) { |
2206 | return APIVal.signedRoundToDouble(); |
2207 | } |
2208 | |
2209 | |
2210 | inline float RoundAPIntToFloat(const APInt &APIVal) { |
2211 | return float(RoundAPIntToDouble(APIVal)); |
2212 | } |
2213 | |
2214 | |
2215 | |
2216 | |
2217 | inline float RoundSignedAPIntToFloat(const APInt &APIVal) { |
2218 | return float(APIVal.signedRoundToDouble()); |
2219 | } |
2220 | |
2221 | |
2222 | |
2223 | |
2224 | APInt RoundDoubleToAPInt(double Double, unsigned width); |
2225 | |
2226 | |
2227 | |
2228 | |
2229 | inline APInt RoundFloatToAPInt(float Float, unsigned width) { |
2230 | return RoundDoubleToAPInt(double(Float), width); |
2231 | } |
2232 | |
2233 | |
2234 | APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM); |
2235 | |
2236 | |
2237 | APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); |
2238 | |
2239 | |
2240 | |
2241 | |
2242 | |
2243 | |
2244 | |
2245 | |
2246 | |
2247 | |
2248 | |
2249 | |
2250 | |
2251 | |
2252 | |
2253 | |
2254 | |
2255 | |
2256 | |
2257 | |
2258 | |
2259 | |
2260 | |
2261 | |
2262 | |
2263 | |
2264 | |
2265 | |
2266 | |
2267 | |
2268 | |
2269 | |
2270 | |
2271 | |
2272 | Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, |
2273 | unsigned RangeWidth); |
2274 | |
2275 | |
2276 | |
2277 | Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A, |
2278 | const APInt &B); |
2279 | |
2280 | } |
2281 | |
2282 | |
2283 | |
2284 | hash_code hash_value(const APInt &Arg); |
2285 | |
2286 | |
2287 | |
2288 | void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes); |
2289 | |
2290 | |
2291 | |
2292 | void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes); |
2293 | |
2294 | |
2295 | template <> struct DenseMapInfo<APInt> { |
2296 | static inline APInt getEmptyKey() { |
2297 | APInt V(nullptr, 0); |
2298 | V.U.VAL = 0; |
2299 | return V; |
2300 | } |
2301 | |
2302 | static inline APInt getTombstoneKey() { |
2303 | APInt V(nullptr, 0); |
2304 | V.U.VAL = 1; |
2305 | return V; |
2306 | } |
2307 | |
2308 | static unsigned getHashValue(const APInt &Key); |
2309 | |
2310 | static bool isEqual(const APInt &LHS, const APInt &RHS) { |
2311 | return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; |
2312 | } |
2313 | }; |
2314 | |
2315 | } |
2316 | |
2317 | #endif |