clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DataLayout.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/IR/DataLayout.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | #include "llvm/IR/DataLayout.h" |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/ADT/StringRef.h" |
21 | #include "llvm/ADT/Triple.h" |
22 | #include "llvm/IR/Constants.h" |
23 | #include "llvm/IR/DerivedTypes.h" |
24 | #include "llvm/IR/GetElementPtrTypeIterator.h" |
25 | #include "llvm/IR/GlobalVariable.h" |
26 | #include "llvm/IR/Module.h" |
27 | #include "llvm/IR/Type.h" |
28 | #include "llvm/IR/Value.h" |
29 | #include "llvm/Support/Casting.h" |
30 | #include "llvm/Support/Error.h" |
31 | #include "llvm/Support/ErrorHandling.h" |
32 | #include "llvm/Support/MathExtras.h" |
33 | #include "llvm/Support/TypeSize.h" |
34 | #include <algorithm> |
35 | #include <cassert> |
36 | #include <cstdint> |
37 | #include <cstdlib> |
38 | #include <tuple> |
39 | #include <utility> |
40 | |
41 | using namespace llvm; |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | StructLayout::StructLayout(StructType *ST, const DataLayout &DL) { |
48 | assert(!ST->isOpaque() && "Cannot get layout of opaque structs"); |
49 | StructSize = 0; |
50 | IsPadded = false; |
51 | NumElements = ST->getNumElements(); |
52 | |
53 | |
54 | for (unsigned i = 0, e = NumElements; i != e; ++i) { |
55 | Type *Ty = ST->getElementType(i); |
56 | const Align TyAlign = ST->isPacked() ? Align(1) : DL.getABITypeAlign(Ty); |
57 | |
58 | |
59 | if (!isAligned(TyAlign, StructSize)) { |
60 | IsPadded = true; |
61 | StructSize = alignTo(StructSize, TyAlign); |
62 | } |
63 | |
64 | |
65 | StructAlignment = std::max(TyAlign, StructAlignment); |
66 | |
67 | getMemberOffsets()[i] = StructSize; |
68 | |
69 | StructSize += DL.getTypeAllocSize(Ty).getFixedValue(); |
70 | } |
71 | |
72 | |
73 | |
74 | if (!isAligned(StructAlignment, StructSize)) { |
75 | IsPadded = true; |
76 | StructSize = alignTo(StructSize, StructAlignment); |
77 | } |
78 | } |
79 | |
80 | |
81 | |
82 | unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const { |
83 | ArrayRef<uint64_t> MemberOffsets = getMemberOffsets(); |
84 | auto SI = llvm::upper_bound(MemberOffsets, Offset); |
85 | assert(SI != MemberOffsets.begin() && "Offset not in structure type!"); |
86 | --SI; |
87 | assert(*SI <= Offset && "upper_bound didn't work"); |
88 | assert((SI == MemberOffsets.begin() || *(SI - 1) <= Offset) && |
89 | (SI + 1 == MemberOffsets.end() || *(SI + 1) > Offset) && |
90 | "Upper bound didn't work!"); |
91 | |
92 | |
93 | |
94 | |
95 | |
96 | |
97 | return SI - MemberOffsets.begin(); |
98 | } |
99 | |
100 | |
101 | |
102 | |
103 | |
104 | LayoutAlignElem LayoutAlignElem::get(AlignTypeEnum align_type, Align abi_align, |
105 | Align pref_align, uint32_t bit_width) { |
106 | assert(abi_align <= pref_align && "Preferred alignment worse than ABI!"); |
107 | LayoutAlignElem retval; |
108 | retval.AlignType = align_type; |
109 | retval.ABIAlign = abi_align; |
110 | retval.PrefAlign = pref_align; |
111 | retval.TypeBitWidth = bit_width; |
112 | return retval; |
113 | } |
114 | |
115 | bool |
116 | LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const { |
117 | return (AlignType == rhs.AlignType |
118 | && ABIAlign == rhs.ABIAlign |
119 | && PrefAlign == rhs.PrefAlign |
120 | && TypeBitWidth == rhs.TypeBitWidth); |
121 | } |
122 | |
123 | |
124 | |
125 | |
126 | |
127 | PointerAlignElem PointerAlignElem::get(uint32_t AddressSpace, Align ABIAlign, |
128 | Align PrefAlign, uint32_t TypeByteWidth, |
129 | uint32_t IndexWidth) { |
130 | assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!"); |
131 | PointerAlignElem retval; |
132 | retval.AddressSpace = AddressSpace; |
133 | retval.ABIAlign = ABIAlign; |
134 | retval.PrefAlign = PrefAlign; |
135 | retval.TypeByteWidth = TypeByteWidth; |
136 | retval.IndexWidth = IndexWidth; |
137 | return retval; |
138 | } |
139 | |
140 | bool |
141 | PointerAlignElem::operator==(const PointerAlignElem &rhs) const { |
142 | return (ABIAlign == rhs.ABIAlign |
143 | && AddressSpace == rhs.AddressSpace |
144 | && PrefAlign == rhs.PrefAlign |
145 | && TypeByteWidth == rhs.TypeByteWidth |
146 | && IndexWidth == rhs.IndexWidth); |
147 | } |
148 | |
149 | |
150 | |
151 | |
152 | |
153 | const char *DataLayout::getManglingComponent(const Triple &T) { |
154 | if (T.isOSBinFormatMachO()) |
155 | return "-m:o"; |
156 | if (T.isOSWindows() && T.isOSBinFormatCOFF()) |
157 | return T.getArch() == Triple::x86 ? "-m:x" : "-m:w"; |
158 | if (T.isOSBinFormatXCOFF()) |
159 | return "-m:a"; |
160 | return "-m:e"; |
161 | } |
162 | |
163 | static const LayoutAlignElem DefaultAlignments[] = { |
164 | {INTEGER_ALIGN, 1, Align(1), Align(1)}, |
165 | {INTEGER_ALIGN, 8, Align(1), Align(1)}, |
166 | {INTEGER_ALIGN, 16, Align(2), Align(2)}, |
167 | {INTEGER_ALIGN, 32, Align(4), Align(4)}, |
168 | {INTEGER_ALIGN, 64, Align(4), Align(8)}, |
169 | {FLOAT_ALIGN, 16, Align(2), Align(2)}, |
170 | {FLOAT_ALIGN, 32, Align(4), Align(4)}, |
171 | {FLOAT_ALIGN, 64, Align(8), Align(8)}, |
172 | {FLOAT_ALIGN, 128, Align(16), Align(16)}, |
173 | {VECTOR_ALIGN, 64, Align(8), Align(8)}, |
174 | {VECTOR_ALIGN, 128, Align(16), Align(16)}, |
175 | {AGGREGATE_ALIGN, 0, Align(1), Align(8)} |
176 | }; |
177 | |
178 | void DataLayout::reset(StringRef Desc) { |
179 | clear(); |
180 | |
181 | LayoutMap = nullptr; |
182 | BigEndian = false; |
183 | AllocaAddrSpace = 0; |
184 | StackNaturalAlign.reset(); |
185 | ProgramAddrSpace = 0; |
186 | DefaultGlobalsAddrSpace = 0; |
187 | FunctionPtrAlign.reset(); |
188 | TheFunctionPtrAlignType = FunctionPtrAlignType::Independent; |
189 | ManglingMode = MM_None; |
190 | NonIntegralAddressSpaces.clear(); |
191 | |
192 | |
193 | for (const LayoutAlignElem &E : DefaultAlignments) { |
194 | if (Error Err = setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, |
195 | E.PrefAlign, E.TypeBitWidth)) |
196 | return report_fatal_error(std::move(Err)); |
197 | } |
198 | if (Error Err = setPointerAlignment(0, Align(8), Align(8), 8, 8)) |
199 | return report_fatal_error(std::move(Err)); |
200 | |
201 | if (Error Err = parseSpecifier(Desc)) |
202 | return report_fatal_error(std::move(Err)); |
203 | } |
204 | |
205 | Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) { |
206 | DataLayout Layout(""); |
207 | if (Error Err = Layout.parseSpecifier(LayoutDescription)) |
208 | return std::move(Err); |
209 | return Layout; |
210 | } |
211 | |
212 | static Error reportError(const Twine &Message) { |
213 | return createStringError(inconvertibleErrorCode(), Message); |
214 | } |
215 | |
216 | |
217 | static Error split(StringRef Str, char Separator, |
218 | std::pair<StringRef, StringRef> &Split) { |
219 | assert(!Str.empty() && "parse error, string can't be empty here"); |
220 | Split = Str.split(Separator); |
221 | if (Split.second.empty() && Split.first != Str) |
222 | return reportError("Trailing separator in datalayout string"); |
223 | if (!Split.second.empty() && Split.first.empty()) |
224 | return reportError("Expected token before separator in datalayout string"); |
225 | return Error::success(); |
226 | } |
227 | |
228 | |
229 | template <typename IntTy> static Error getInt(StringRef R, IntTy &Result) { |
230 | bool error = R.getAsInteger(10, Result); (void)error; |
231 | if (error) |
232 | return reportError("not a number, or does not fit in an unsigned int"); |
233 | return Error::success(); |
234 | } |
235 | |
236 | |
237 | |
238 | template <typename IntTy> |
239 | static Error getIntInBytes(StringRef R, IntTy &Result) { |
240 | if (Error Err = getInt<IntTy>(R, Result)) |
241 | return Err; |
242 | if (Result % 8) |
243 | return reportError("number of bits must be a byte width multiple"); |
244 | Result /= 8; |
245 | return Error::success(); |
246 | } |
247 | |
248 | static Error getAddrSpace(StringRef R, unsigned &AddrSpace) { |
249 | if (Error Err = getInt(R, AddrSpace)) |
250 | return Err; |
251 | if (!isUInt<24>(AddrSpace)) |
252 | return reportError("Invalid address space, must be a 24-bit integer"); |
253 | return Error::success(); |
254 | } |
255 | |
256 | Error DataLayout::parseSpecifier(StringRef Desc) { |
257 | StringRepresentation = std::string(Desc); |
258 | while (!Desc.empty()) { |
259 | |
260 | std::pair<StringRef, StringRef> Split; |
261 | if (Error Err = split(Desc, '-', Split)) |
262 | return Err; |
263 | Desc = Split.second; |
264 | |
265 | |
266 | if (Error Err = split(Split.first, ':', Split)) |
267 | return Err; |
268 | |
269 | |
270 | StringRef &Tok = Split.first; |
271 | StringRef &Rest = Split.second; |
272 | |
273 | if (Tok == "ni") { |
274 | do { |
275 | if (Error Err = split(Rest, ':', Split)) |
276 | return Err; |
277 | Rest = Split.second; |
278 | unsigned AS; |
279 | if (Error Err = getInt(Split.first, AS)) |
280 | return Err; |
281 | if (AS == 0) |
282 | return reportError("Address space 0 can never be non-integral"); |
283 | NonIntegralAddressSpaces.push_back(AS); |
284 | } while (!Rest.empty()); |
285 | |
286 | continue; |
287 | } |
288 | |
289 | char Specifier = Tok.front(); |
290 | Tok = Tok.substr(1); |
291 | |
292 | switch (Specifier) { |
293 | case 's': |
294 | |
295 | |
296 | break; |
297 | case 'E': |
298 | BigEndian = true; |
299 | break; |
300 | case 'e': |
301 | BigEndian = false; |
302 | break; |
303 | case 'p': { |
304 | |
305 | unsigned AddrSpace = 0; |
306 | if (!Tok.empty()) |
307 | if (Error Err = getInt(Tok, AddrSpace)) |
308 | return Err; |
309 | if (!isUInt<24>(AddrSpace)) |
310 | return reportError("Invalid address space, must be a 24bit integer"); |
311 | |
312 | |
313 | if (Rest.empty()) |
314 | return reportError( |
315 | "Missing size specification for pointer in datalayout string"); |
316 | if (Error Err = split(Rest, ':', Split)) |
317 | return Err; |
318 | unsigned PointerMemSize; |
319 | if (Error Err = getIntInBytes(Tok, PointerMemSize)) |
320 | return Err; |
321 | if (!PointerMemSize) |
322 | return reportError("Invalid pointer size of 0 bytes"); |
323 | |
324 | |
325 | if (Rest.empty()) |
326 | return reportError( |
327 | "Missing alignment specification for pointer in datalayout string"); |
328 | if (Error Err = split(Rest, ':', Split)) |
329 | return Err; |
330 | unsigned PointerABIAlign; |
331 | if (Error Err = getIntInBytes(Tok, PointerABIAlign)) |
332 | return Err; |
333 | if (!isPowerOf2_64(PointerABIAlign)) |
334 | return reportError("Pointer ABI alignment must be a power of 2"); |
335 | |
336 | |
337 | |
338 | unsigned IndexSize = PointerMemSize; |
339 | |
340 | |
341 | unsigned PointerPrefAlign = PointerABIAlign; |
342 | if (!Rest.empty()) { |
343 | if (Error Err = split(Rest, ':', Split)) |
344 | return Err; |
345 | if (Error Err = getIntInBytes(Tok, PointerPrefAlign)) |
346 | return Err; |
347 | if (!isPowerOf2_64(PointerPrefAlign)) |
348 | return reportError( |
349 | "Pointer preferred alignment must be a power of 2"); |
350 | |
351 | |
352 | if (!Rest.empty()) { |
353 | if (Error Err = split(Rest, ':', Split)) |
354 | return Err; |
355 | if (Error Err = getIntInBytes(Tok, IndexSize)) |
356 | return Err; |
357 | if (!IndexSize) |
358 | return reportError("Invalid index size of 0 bytes"); |
359 | } |
360 | } |
361 | if (Error Err = setPointerAlignment( |
362 | AddrSpace, assumeAligned(PointerABIAlign), |
363 | assumeAligned(PointerPrefAlign), PointerMemSize, IndexSize)) |
364 | return Err; |
365 | break; |
366 | } |
367 | case 'i': |
368 | case 'v': |
369 | case 'f': |
370 | case 'a': { |
371 | AlignTypeEnum AlignType; |
372 | switch (Specifier) { |
373 | default: llvm_unreachable("Unexpected specifier!"); |
374 | case 'i': AlignType = INTEGER_ALIGN; break; |
375 | case 'v': AlignType = VECTOR_ALIGN; break; |
376 | case 'f': AlignType = FLOAT_ALIGN; break; |
377 | case 'a': AlignType = AGGREGATE_ALIGN; break; |
378 | } |
379 | |
380 | |
381 | unsigned Size = 0; |
382 | if (!Tok.empty()) |
383 | if (Error Err = getInt(Tok, Size)) |
384 | return Err; |
385 | |
386 | if (AlignType == AGGREGATE_ALIGN && Size != 0) |
387 | return reportError( |
388 | "Sized aggregate specification in datalayout string"); |
389 | |
390 | |
391 | if (Rest.empty()) |
392 | return reportError( |
393 | "Missing alignment specification in datalayout string"); |
394 | if (Error Err = split(Rest, ':', Split)) |
395 | return Err; |
396 | unsigned ABIAlign; |
397 | if (Error Err = getIntInBytes(Tok, ABIAlign)) |
398 | return Err; |
399 | if (AlignType != AGGREGATE_ALIGN && !ABIAlign) |
400 | return reportError( |
401 | "ABI alignment specification must be >0 for non-aggregate types"); |
402 | |
403 | if (!isUInt<16>(ABIAlign)) |
404 | return reportError("Invalid ABI alignment, must be a 16bit integer"); |
405 | if (ABIAlign != 0 && !isPowerOf2_64(ABIAlign)) |
406 | return reportError("Invalid ABI alignment, must be a power of 2"); |
407 | |
408 | |
409 | unsigned PrefAlign = ABIAlign; |
410 | if (!Rest.empty()) { |
411 | if (Error Err = split(Rest, ':', Split)) |
412 | return Err; |
413 | if (Error Err = getIntInBytes(Tok, PrefAlign)) |
414 | return Err; |
415 | } |
416 | |
417 | if (!isUInt<16>(PrefAlign)) |
418 | return reportError( |
419 | "Invalid preferred alignment, must be a 16bit integer"); |
420 | if (PrefAlign != 0 && !isPowerOf2_64(PrefAlign)) |
421 | return reportError("Invalid preferred alignment, must be a power of 2"); |
422 | |
423 | if (Error Err = setAlignment(AlignType, assumeAligned(ABIAlign), |
424 | assumeAligned(PrefAlign), Size)) |
425 | return Err; |
426 | |
427 | break; |
428 | } |
429 | case 'n': |
430 | while (true) { |
431 | unsigned Width; |
432 | if (Error Err = getInt(Tok, Width)) |
433 | return Err; |
434 | if (Width == 0) |
435 | return reportError( |
436 | "Zero width native integer type in datalayout string"); |
437 | LegalIntWidths.push_back(Width); |
438 | if (Rest.empty()) |
439 | break; |
440 | if (Error Err = split(Rest, ':', Split)) |
441 | return Err; |
442 | } |
443 | break; |
444 | case 'S': { |
445 | uint64_t Alignment; |
446 | if (Error Err = getIntInBytes(Tok, Alignment)) |
447 | return Err; |
448 | if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment)) |
449 | return reportError("Alignment is neither 0 nor a power of 2"); |
450 | StackNaturalAlign = MaybeAlign(Alignment); |
451 | break; |
452 | } |
453 | case 'F': { |
454 | switch (Tok.front()) { |
455 | case 'i': |
456 | TheFunctionPtrAlignType = FunctionPtrAlignType::Independent; |
457 | break; |
458 | case 'n': |
459 | TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign; |
460 | break; |
461 | default: |
462 | return reportError("Unknown function pointer alignment type in " |
463 | "datalayout string"); |
464 | } |
465 | Tok = Tok.substr(1); |
466 | uint64_t Alignment; |
467 | if (Error Err = getIntInBytes(Tok, Alignment)) |
468 | return Err; |
469 | if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment)) |
470 | return reportError("Alignment is neither 0 nor a power of 2"); |
471 | FunctionPtrAlign = MaybeAlign(Alignment); |
472 | break; |
473 | } |
474 | case 'P': { |
475 | if (Error Err = getAddrSpace(Tok, ProgramAddrSpace)) |
476 | return Err; |
477 | break; |
478 | } |
479 | case 'A': { |
480 | if (Error Err = getAddrSpace(Tok, AllocaAddrSpace)) |
481 | return Err; |
482 | break; |
483 | } |
484 | case 'G': { |
485 | if (Error Err = getAddrSpace(Tok, DefaultGlobalsAddrSpace)) |
486 | return Err; |
487 | break; |
488 | } |
489 | case 'm': |
490 | if (!Tok.empty()) |
491 | return reportError("Unexpected trailing characters after mangling " |
492 | "specifier in datalayout string"); |
493 | if (Rest.empty()) |
494 | return reportError("Expected mangling specifier in datalayout string"); |
495 | if (Rest.size() > 1) |
496 | return reportError("Unknown mangling specifier in datalayout string"); |
497 | switch(Rest[0]) { |
498 | default: |
499 | return reportError("Unknown mangling in datalayout string"); |
500 | case 'e': |
501 | ManglingMode = MM_ELF; |
502 | break; |
503 | case 'o': |
504 | ManglingMode = MM_MachO; |
505 | break; |
506 | case 'm': |
507 | ManglingMode = MM_Mips; |
508 | break; |
509 | case 'w': |
510 | ManglingMode = MM_WinCOFF; |
511 | break; |
512 | case 'x': |
513 | ManglingMode = MM_WinCOFFX86; |
514 | break; |
515 | case 'a': |
516 | ManglingMode = MM_XCOFF; |
517 | break; |
518 | } |
519 | break; |
520 | default: |
521 | return reportError("Unknown specifier in datalayout string"); |
522 | break; |
523 | } |
524 | } |
525 | |
526 | return Error::success(); |
527 | } |
528 | |
529 | DataLayout::DataLayout(const Module *M) { |
530 | init(M); |
531 | } |
532 | |
533 | void DataLayout::init(const Module *M) { *this = M->getDataLayout(); } |
534 | |
535 | bool DataLayout::operator==(const DataLayout &Other) const { |
536 | bool Ret = BigEndian == Other.BigEndian && |
537 | AllocaAddrSpace == Other.AllocaAddrSpace && |
538 | StackNaturalAlign == Other.StackNaturalAlign && |
539 | ProgramAddrSpace == Other.ProgramAddrSpace && |
540 | DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace && |
541 | FunctionPtrAlign == Other.FunctionPtrAlign && |
542 | TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType && |
543 | ManglingMode == Other.ManglingMode && |
544 | LegalIntWidths == Other.LegalIntWidths && |
545 | Alignments == Other.Alignments && Pointers == Other.Pointers; |
546 | |
547 | return Ret; |
548 | } |
549 | |
550 | DataLayout::AlignmentsTy::iterator |
551 | DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType, |
552 | uint32_t BitWidth) { |
553 | auto Pair = std::make_pair((unsigned)AlignType, BitWidth); |
554 | return partition_point(Alignments, [=](const LayoutAlignElem &E) { |
555 | return std::make_pair(E.AlignType, E.TypeBitWidth) < Pair; |
556 | }); |
557 | } |
558 | |
559 | Error DataLayout::setAlignment(AlignTypeEnum align_type, Align abi_align, |
560 | Align pref_align, uint32_t bit_width) { |
561 | |
562 | |
563 | |
564 | |
565 | assert(Log2(abi_align) < 16 && Log2(pref_align) < 16 && "Alignment too big"); |
566 | if (!isUInt<24>(bit_width)) |
567 | return reportError("Invalid bit width, must be a 24bit integer"); |
568 | if (pref_align < abi_align) |
569 | return reportError( |
570 | "Preferred alignment cannot be less than the ABI alignment"); |
571 | |
572 | AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width); |
573 | if (I != Alignments.end() && |
574 | I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) { |
575 | |
576 | I->ABIAlign = abi_align; |
577 | I->PrefAlign = pref_align; |
578 | } else { |
579 | |
580 | Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align, |
581 | pref_align, bit_width)); |
582 | } |
583 | return Error::success(); |
584 | } |
585 | |
586 | const PointerAlignElem & |
587 | DataLayout::getPointerAlignElem(uint32_t AddressSpace) const { |
588 | if (AddressSpace != 0) { |
589 | auto I = lower_bound(Pointers, AddressSpace, |
590 | [](const PointerAlignElem &A, uint32_t AddressSpace) { |
591 | return A.AddressSpace < AddressSpace; |
592 | }); |
593 | if (I != Pointers.end() && I->AddressSpace == AddressSpace) |
594 | return *I; |
595 | } |
596 | |
597 | assert(Pointers[0].AddressSpace == 0); |
598 | return Pointers[0]; |
599 | } |
600 | |
601 | Error DataLayout::setPointerAlignment(uint32_t AddrSpace, Align ABIAlign, |
602 | Align PrefAlign, uint32_t TypeByteWidth, |
603 | uint32_t IndexWidth) { |
604 | if (PrefAlign < ABIAlign) |
605 | return reportError( |
606 | "Preferred alignment cannot be less than the ABI alignment"); |
607 | |
608 | auto I = lower_bound(Pointers, AddrSpace, |
609 | [](const PointerAlignElem &A, uint32_t AddressSpace) { |
610 | return A.AddressSpace < AddressSpace; |
611 | }); |
612 | if (I == Pointers.end() || I->AddressSpace != AddrSpace) { |
613 | Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, |
614 | TypeByteWidth, IndexWidth)); |
615 | } else { |
616 | I->ABIAlign = ABIAlign; |
617 | I->PrefAlign = PrefAlign; |
618 | I->TypeByteWidth = TypeByteWidth; |
619 | I->IndexWidth = IndexWidth; |
620 | } |
621 | return Error::success(); |
622 | } |
623 | |
624 | Align DataLayout::getIntegerAlignment(uint32_t BitWidth, |
625 | bool abi_or_pref) const { |
626 | auto I = findAlignmentLowerBound(INTEGER_ALIGN, BitWidth); |
627 | |
628 | |
629 | |
630 | if (I == Alignments.end() || I->AlignType != INTEGER_ALIGN) |
631 | --I; |
632 | assert(I->AlignType == INTEGER_ALIGN && "Must be integer alignment"); |
633 | return abi_or_pref ? I->ABIAlign : I->PrefAlign; |
634 | } |
635 | |
636 | namespace { |
637 | |
638 | class StructLayoutMap { |
639 | using LayoutInfoTy = DenseMap<StructType*, StructLayout*>; |
640 | LayoutInfoTy LayoutInfo; |
641 | |
642 | public: |
643 | ~StructLayoutMap() { |
644 | |
645 | for (const auto &I : LayoutInfo) { |
646 | StructLayout *Value = I.second; |
647 | Value->~StructLayout(); |
648 | free(Value); |
649 | } |
650 | } |
651 | |
652 | StructLayout *&operator[](StructType *STy) { |
653 | return LayoutInfo[STy]; |
654 | } |
655 | }; |
656 | |
657 | } |
658 | |
659 | void DataLayout::clear() { |
660 | LegalIntWidths.clear(); |
661 | Alignments.clear(); |
662 | Pointers.clear(); |
663 | delete static_cast<StructLayoutMap *>(LayoutMap); |
664 | LayoutMap = nullptr; |
665 | } |
666 | |
667 | DataLayout::~DataLayout() { |
668 | clear(); |
669 | } |
670 | |
671 | const StructLayout *DataLayout::getStructLayout(StructType *Ty) const { |
672 | if (!LayoutMap) |
673 | LayoutMap = new StructLayoutMap(); |
674 | |
675 | StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap); |
676 | StructLayout *&SL = (*STM)[Ty]; |
677 | if (SL) return SL; |
678 | |
679 | |
680 | |
681 | StructLayout *L = (StructLayout *)safe_malloc( |
682 | StructLayout::totalSizeToAlloc<uint64_t>(Ty->getNumElements())); |
683 | |
684 | |
685 | |
686 | SL = L; |
687 | |
688 | new (L) StructLayout(Ty, *this); |
689 | |
690 | return L; |
691 | } |
692 | |
693 | Align DataLayout::getPointerABIAlignment(unsigned AS) const { |
694 | return getPointerAlignElem(AS).ABIAlign; |
695 | } |
696 | |
697 | Align DataLayout::getPointerPrefAlignment(unsigned AS) const { |
698 | return getPointerAlignElem(AS).PrefAlign; |
699 | } |
700 | |
701 | unsigned DataLayout::getPointerSize(unsigned AS) const { |
702 | return getPointerAlignElem(AS).TypeByteWidth; |
703 | } |
704 | |
705 | unsigned DataLayout::getMaxPointerSize() const { |
706 | unsigned MaxPointerSize = 0; |
707 | for (auto &P : Pointers) |
708 | MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth); |
709 | |
710 | return MaxPointerSize; |
711 | } |
712 | |
713 | unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const { |
714 | assert(Ty->isPtrOrPtrVectorTy() && |
715 | "This should only be called with a pointer or pointer vector type"); |
716 | Ty = Ty->getScalarType(); |
717 | return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace()); |
718 | } |
719 | |
720 | unsigned DataLayout::getIndexSize(unsigned AS) const { |
721 | return getPointerAlignElem(AS).IndexWidth; |
722 | } |
723 | |
724 | unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const { |
725 | assert(Ty->isPtrOrPtrVectorTy() && |
726 | "This should only be called with a pointer or pointer vector type"); |
727 | Ty = Ty->getScalarType(); |
728 | return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace()); |
729 | } |
730 | |
731 | |
732 | |
733 | |
734 | |
735 | |
736 | |
737 | |
738 | |
739 | Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const { |
740 | assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!"); |
741 | switch (Ty->getTypeID()) { |
| 5 | | Control jumps to 'case X86_MMXTyID:' at line 792 | |
|
| 12 | | Control jumps to 'case X86_FP80TyID:' at line 777 | |
|
742 | |
743 | case Type::LabelTyID: |
744 | return abi_or_pref ? getPointerABIAlignment(0) : getPointerPrefAlignment(0); |
745 | case Type::PointerTyID: { |
746 | unsigned AS = cast<PointerType>(Ty)->getAddressSpace(); |
747 | return abi_or_pref ? getPointerABIAlignment(AS) |
748 | : getPointerPrefAlignment(AS); |
749 | } |
750 | case Type::ArrayTyID: |
751 | return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref); |
752 | |
753 | case Type::StructTyID: { |
754 | |
755 | if (cast<StructType>(Ty)->isPacked() && abi_or_pref) |
756 | return Align(1); |
757 | |
758 | |
759 | const StructLayout *Layout = getStructLayout(cast<StructType>(Ty)); |
760 | const LayoutAlignElem &AggregateAlign = Alignments[0]; |
761 | assert(AggregateAlign.AlignType == AGGREGATE_ALIGN && |
762 | "Aggregate alignment must be first alignment entry"); |
763 | const Align Align = |
764 | abi_or_pref ? AggregateAlign.ABIAlign : AggregateAlign.PrefAlign; |
765 | return std::max(Align, Layout->getAlignment()); |
766 | } |
767 | case Type::IntegerTyID: |
768 | return getIntegerAlignment(Ty->getIntegerBitWidth(), abi_or_pref); |
769 | case Type::HalfTyID: |
770 | case Type::BFloatTyID: |
771 | case Type::FloatTyID: |
772 | case Type::DoubleTyID: |
773 | |
774 | |
775 | case Type::PPC_FP128TyID: |
776 | case Type::FP128TyID: |
777 | case Type::X86_FP80TyID: { |
778 | unsigned BitWidth = getTypeSizeInBits(Ty).getFixedSize(); |
779 | auto I = findAlignmentLowerBound(FLOAT_ALIGN, BitWidth); |
780 | if (I != Alignments.end() && I->AlignType == FLOAT_ALIGN && |
| 13 | | Assuming the condition is false | |
|
781 | I->TypeBitWidth == BitWidth) |
782 | return abi_or_pref ? I->ABIAlign : I->PrefAlign; |
783 | |
784 | |
785 | |
786 | |
787 | |
788 | |
789 | |
790 | return Align(PowerOf2Ceil(BitWidth / 8)); |
| 14 | | Calling constructor for 'Align' | |
|
| 19 | | Returning from constructor for 'Align' | |
|
791 | } |
792 | case Type::X86_MMXTyID: |
793 | case Type::FixedVectorTyID: |
794 | case Type::ScalableVectorTyID: { |
795 | unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinSize(); |
796 | auto I = findAlignmentLowerBound(VECTOR_ALIGN, BitWidth); |
797 | if (I != Alignments.end() && I->AlignType == VECTOR_ALIGN && |
| 6 | | Assuming the condition is false | |
|
798 | I->TypeBitWidth == BitWidth) |
799 | return abi_or_pref ? I->ABIAlign : I->PrefAlign; |
800 | |
801 | |
802 | |
803 | |
804 | unsigned Alignment = |
805 | getTypeAllocSize(cast<VectorType>(Ty)->getElementType()); |
| |
| 8 | | Calling 'DataLayout::getTypeAllocSize' | |
|
806 | |
807 | |
808 | |
809 | Alignment *= cast<VectorType>(Ty)->getElementCount().getKnownMinValue(); |
810 | Alignment = PowerOf2Ceil(Alignment); |
811 | return Align(Alignment); |
812 | } |
813 | case Type::X86_AMXTyID: |
814 | return Align(64); |
815 | default: |
816 | llvm_unreachable("Bad type for getAlignment!!!"); |
817 | } |
818 | } |
819 | |
820 | |
821 | unsigned DataLayout::getABITypeAlignment(Type *Ty) const { |
822 | return getABITypeAlign(Ty).value(); |
| 10 | | Calling 'DataLayout::getABITypeAlign' | |
|
| 21 | | Returning from 'DataLayout::getABITypeAlign' | |
|
| |
823 | } |
824 | |
825 | Align DataLayout::getABITypeAlign(Type *Ty) const { |
826 | return getAlignment(Ty, true); |
| 11 | | Calling 'DataLayout::getAlignment' | |
|
| 20 | | Returning from 'DataLayout::getAlignment' | |
|
827 | } |
828 | |
829 | |
830 | unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const { |
831 | return getPrefTypeAlign(Ty).value(); |
832 | } |
833 | |
834 | Align DataLayout::getPrefTypeAlign(Type *Ty) const { |
835 | return getAlignment(Ty, false); |
| 4 | | Calling 'DataLayout::getAlignment' | |
|
836 | } |
837 | |
838 | IntegerType *DataLayout::getIntPtrType(LLVMContext &C, |
839 | unsigned AddressSpace) const { |
840 | return IntegerType::get(C, getPointerSizeInBits(AddressSpace)); |
841 | } |
842 | |
843 | Type *DataLayout::getIntPtrType(Type *Ty) const { |
844 | assert(Ty->isPtrOrPtrVectorTy() && |
845 | "Expected a pointer or pointer vector type."); |
846 | unsigned NumBits = getPointerTypeSizeInBits(Ty); |
847 | IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits); |
848 | if (VectorType *VecTy = dyn_cast<VectorType>(Ty)) |
849 | return VectorType::get(IntTy, VecTy); |
850 | return IntTy; |
851 | } |
852 | |
853 | Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const { |
854 | for (unsigned LegalIntWidth : LegalIntWidths) |
855 | if (Width <= LegalIntWidth) |
856 | return Type::getIntNTy(C, LegalIntWidth); |
857 | return nullptr; |
858 | } |
859 | |
860 | unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const { |
861 | auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end()); |
862 | return Max != LegalIntWidths.end() ? *Max : 0; |
863 | } |
864 | |
865 | Type *DataLayout::getIndexType(Type *Ty) const { |
866 | assert(Ty->isPtrOrPtrVectorTy() && |
867 | "Expected a pointer or pointer vector type."); |
868 | unsigned NumBits = getIndexTypeSizeInBits(Ty); |
869 | IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits); |
870 | if (VectorType *VecTy = dyn_cast<VectorType>(Ty)) |
871 | return VectorType::get(IntTy, VecTy); |
872 | return IntTy; |
873 | } |
874 | |
875 | int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy, |
876 | ArrayRef<Value *> Indices) const { |
877 | int64_t Result = 0; |
878 | |
879 | generic_gep_type_iterator<Value* const*> |
880 | GTI = gep_type_begin(ElemTy, Indices), |
881 | GTE = gep_type_end(ElemTy, Indices); |
882 | for (; GTI != GTE; ++GTI) { |
883 | Value *Idx = GTI.getOperand(); |
884 | if (StructType *STy = GTI.getStructTypeOrNull()) { |
885 | assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx"); |
886 | unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue(); |
887 | |
888 | |
889 | const StructLayout *Layout = getStructLayout(STy); |
890 | |
891 | |
892 | Result += Layout->getElementOffset(FieldNo); |
893 | } else { |
894 | |
895 | if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue()) |
896 | Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType()); |
897 | } |
898 | } |
899 | |
900 | return Result; |
901 | } |
902 | |
903 | |
904 | |
905 | Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const { |
906 | MaybeAlign GVAlignment = GV->getAlign(); |
907 | |
908 | |
909 | if (GVAlignment && GV->hasSection()) |
| 1 | Assuming the condition is false | |
|
| |
910 | return *GVAlignment; |
911 | |
912 | |
913 | |
914 | |
915 | |
916 | |
917 | |
918 | Type *ElemType = GV->getValueType(); |
919 | Align Alignment = getPrefTypeAlign(ElemType); |
| 3 | | Calling 'DataLayout::getPrefTypeAlign' | |
|
920 | if (GVAlignment) { |
921 | if (*GVAlignment >= Alignment) |
922 | Alignment = *GVAlignment; |
923 | else |
924 | Alignment = std::max(*GVAlignment, getABITypeAlign(ElemType)); |
925 | } |
926 | |
927 | |
928 | |
929 | |
930 | if (GV->hasInitializer() && !GVAlignment) { |
931 | if (Alignment < Align(16)) { |
932 | |
933 | |
934 | if (getTypeSizeInBits(ElemType) > 128) |
935 | Alignment = Align(16); |
936 | } |
937 | } |
938 | return Alignment; |
939 | } |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | #ifndef LLVM_IR_DATALAYOUT_H |
20 | #define LLVM_IR_DATALAYOUT_H |
21 | |
22 | #include "llvm/ADT/ArrayRef.h" |
23 | #include "llvm/ADT/STLExtras.h" |
24 | #include "llvm/ADT/SmallVector.h" |
25 | #include "llvm/ADT/StringRef.h" |
26 | #include "llvm/IR/DerivedTypes.h" |
27 | #include "llvm/IR/Type.h" |
28 | #include "llvm/Support/Casting.h" |
29 | #include "llvm/Support/ErrorHandling.h" |
30 | #include "llvm/Support/MathExtras.h" |
31 | #include "llvm/Support/Alignment.h" |
32 | #include "llvm/Support/TrailingObjects.h" |
33 | #include "llvm/Support/TypeSize.h" |
34 | #include <cassert> |
35 | #include <cstdint> |
36 | #include <string> |
37 | |
38 | |
39 | |
40 | using LLVMTargetDataRef = struct LLVMOpaqueTargetData *; |
41 | |
42 | namespace llvm { |
43 | |
44 | class GlobalVariable; |
45 | class LLVMContext; |
46 | class Module; |
47 | class StructLayout; |
48 | class Triple; |
49 | class Value; |
50 | |
51 | |
52 | enum AlignTypeEnum { |
53 | INVALID_ALIGN = 0, |
54 | INTEGER_ALIGN = 'i', |
55 | VECTOR_ALIGN = 'v', |
56 | FLOAT_ALIGN = 'f', |
57 | AGGREGATE_ALIGN = 'a' |
58 | }; |
59 | |
60 | |
61 | |
62 | |
63 | |
64 | |
65 | |
66 | |
67 | |
68 | |
69 | |
70 | |
71 | |
72 | struct LayoutAlignElem { |
73 | |
74 | unsigned AlignType : 8; |
75 | unsigned TypeBitWidth : 24; |
76 | Align ABIAlign; |
77 | Align PrefAlign; |
78 | |
79 | static LayoutAlignElem get(AlignTypeEnum align_type, Align abi_align, |
80 | Align pref_align, uint32_t bit_width); |
81 | |
82 | bool operator==(const LayoutAlignElem &rhs) const; |
83 | }; |
84 | |
85 | |
86 | |
87 | |
88 | |
89 | |
90 | |
91 | struct PointerAlignElem { |
92 | Align ABIAlign; |
93 | Align PrefAlign; |
94 | uint32_t TypeByteWidth; |
95 | uint32_t AddressSpace; |
96 | uint32_t IndexWidth; |
97 | |
98 | |
99 | static PointerAlignElem get(uint32_t AddressSpace, Align ABIAlign, |
100 | Align PrefAlign, uint32_t TypeByteWidth, |
101 | uint32_t IndexWidth); |
102 | |
103 | bool operator==(const PointerAlignElem &rhs) const; |
104 | }; |
105 | |
106 | |
107 | |
108 | |
109 | |
110 | |
111 | |
112 | class DataLayout { |
113 | public: |
114 | enum class FunctionPtrAlignType { |
115 | |
116 | Independent, |
117 | |
118 | MultipleOfFunctionAlign, |
119 | }; |
120 | private: |
121 | |
122 | bool BigEndian; |
123 | |
124 | unsigned AllocaAddrSpace; |
125 | MaybeAlign StackNaturalAlign; |
126 | unsigned ProgramAddrSpace; |
127 | unsigned DefaultGlobalsAddrSpace; |
128 | |
129 | MaybeAlign FunctionPtrAlign; |
130 | FunctionPtrAlignType TheFunctionPtrAlignType; |
131 | |
132 | enum ManglingModeT { |
133 | MM_None, |
134 | MM_ELF, |
135 | MM_MachO, |
136 | MM_WinCOFF, |
137 | MM_WinCOFFX86, |
138 | MM_Mips, |
139 | MM_XCOFF |
140 | }; |
141 | ManglingModeT ManglingMode; |
142 | |
143 | SmallVector<unsigned char, 8> LegalIntWidths; |
144 | |
145 | |
146 | |
147 | using AlignmentsTy = SmallVector<LayoutAlignElem, 16>; |
148 | AlignmentsTy Alignments; |
149 | |
150 | AlignmentsTy::const_iterator |
151 | findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth) const { |
152 | return const_cast<DataLayout *>(this)->findAlignmentLowerBound(AlignType, |
153 | BitWidth); |
154 | } |
155 | |
156 | AlignmentsTy::iterator |
157 | findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth); |
158 | |
159 | |
160 | std::string StringRepresentation; |
161 | |
162 | using PointersTy = SmallVector<PointerAlignElem, 8>; |
163 | PointersTy Pointers; |
164 | |
165 | const PointerAlignElem &getPointerAlignElem(uint32_t AddressSpace) const; |
166 | |
167 | |
168 | mutable void *LayoutMap = nullptr; |
169 | |
170 | |
171 | |
172 | SmallVector<unsigned, 8> NonIntegralAddressSpaces; |
173 | |
174 | |
175 | |
176 | Error setAlignment(AlignTypeEnum align_type, Align abi_align, |
177 | Align pref_align, uint32_t bit_width); |
178 | |
179 | |
180 | |
181 | Error setPointerAlignment(uint32_t AddrSpace, Align ABIAlign, Align PrefAlign, |
182 | uint32_t TypeByteWidth, uint32_t IndexWidth); |
183 | |
184 | |
185 | Align getIntegerAlignment(uint32_t BitWidth, bool abi_or_pref) const; |
186 | |
187 | |
188 | Align getAlignment(Type *Ty, bool abi_or_pref) const; |
189 | |
190 | |
191 | |
192 | Error parseSpecifier(StringRef Desc); |
193 | |
194 | |
195 | void clear(); |
196 | |
197 | public: |
198 | |
199 | explicit DataLayout(StringRef LayoutDescription) { |
200 | reset(LayoutDescription); |
201 | } |
202 | |
203 | |
204 | explicit DataLayout(const Module *M); |
205 | |
206 | DataLayout(const DataLayout &DL) { *this = DL; } |
207 | |
208 | ~DataLayout(); |
209 | |
210 | DataLayout &operator=(const DataLayout &DL) { |
211 | clear(); |
212 | StringRepresentation = DL.StringRepresentation; |
213 | BigEndian = DL.isBigEndian(); |
214 | AllocaAddrSpace = DL.AllocaAddrSpace; |
215 | StackNaturalAlign = DL.StackNaturalAlign; |
216 | FunctionPtrAlign = DL.FunctionPtrAlign; |
217 | TheFunctionPtrAlignType = DL.TheFunctionPtrAlignType; |
218 | ProgramAddrSpace = DL.ProgramAddrSpace; |
219 | DefaultGlobalsAddrSpace = DL.DefaultGlobalsAddrSpace; |
220 | ManglingMode = DL.ManglingMode; |
221 | LegalIntWidths = DL.LegalIntWidths; |
222 | Alignments = DL.Alignments; |
223 | Pointers = DL.Pointers; |
224 | NonIntegralAddressSpaces = DL.NonIntegralAddressSpaces; |
225 | return *this; |
226 | } |
227 | |
228 | bool operator==(const DataLayout &Other) const; |
229 | bool operator!=(const DataLayout &Other) const { return !(*this == Other); } |
230 | |
231 | void init(const Module *M); |
232 | |
233 | |
234 | void reset(StringRef LayoutDescription); |
235 | |
236 | |
237 | |
238 | static Expected<DataLayout> parse(StringRef LayoutDescription); |
239 | |
240 | |
241 | bool isLittleEndian() const { return !BigEndian; } |
242 | bool isBigEndian() const { return BigEndian; } |
243 | |
244 | |
245 | |
246 | |
247 | |
248 | |
249 | const std::string &getStringRepresentation() const { |
250 | return StringRepresentation; |
251 | } |
252 | |
253 | |
254 | bool isDefault() const { return StringRepresentation.empty(); } |
255 | |
256 | |
257 | |
258 | |
259 | |
260 | |
261 | |
262 | |
263 | bool isLegalInteger(uint64_t Width) const { |
264 | return llvm::is_contained(LegalIntWidths, Width); |
265 | } |
266 | |
267 | bool isIllegalInteger(uint64_t Width) const { return !isLegalInteger(Width); } |
268 | |
269 | |
270 | bool exceedsNaturalStackAlignment(Align Alignment) const { |
271 | return StackNaturalAlign && (Alignment > *StackNaturalAlign); |
272 | } |
273 | |
274 | Align getStackAlignment() const { |
275 | assert(StackNaturalAlign && "StackNaturalAlign must be defined"); |
276 | return *StackNaturalAlign; |
277 | } |
278 | |
279 | unsigned getAllocaAddrSpace() const { return AllocaAddrSpace; } |
280 | |
281 | |
282 | |
283 | |
284 | MaybeAlign getFunctionPtrAlign() const { return FunctionPtrAlign; } |
285 | |
286 | |
287 | |
288 | FunctionPtrAlignType getFunctionPtrAlignType() const { |
289 | return TheFunctionPtrAlignType; |
290 | } |
291 | |
292 | unsigned getProgramAddressSpace() const { return ProgramAddrSpace; } |
293 | unsigned getDefaultGlobalsAddressSpace() const { |
294 | return DefaultGlobalsAddrSpace; |
295 | } |
296 | |
297 | bool hasMicrosoftFastStdCallMangling() const { |
298 | return ManglingMode == MM_WinCOFFX86; |
299 | } |
300 | |
301 | |
302 | |
303 | bool doNotMangleLeadingQuestionMark() const { |
304 | return ManglingMode == MM_WinCOFF || ManglingMode == MM_WinCOFFX86; |
305 | } |
306 | |
307 | bool hasLinkerPrivateGlobalPrefix() const { return ManglingMode == MM_MachO; } |
308 | |
309 | StringRef getLinkerPrivateGlobalPrefix() const { |
310 | if (ManglingMode == MM_MachO) |
311 | return "l"; |
312 | return ""; |
313 | } |
314 | |
315 | char getGlobalPrefix() const { |
316 | switch (ManglingMode) { |
317 | case MM_None: |
318 | case MM_ELF: |
319 | case MM_Mips: |
320 | case MM_WinCOFF: |
321 | case MM_XCOFF: |
322 | return '\0'; |
323 | case MM_MachO: |
324 | case MM_WinCOFFX86: |
325 | return '_'; |
326 | } |
327 | llvm_unreachable("invalid mangling mode"); |
328 | } |
329 | |
330 | StringRef getPrivateGlobalPrefix() const { |
331 | switch (ManglingMode) { |
332 | case MM_None: |
333 | return ""; |
334 | case MM_ELF: |
335 | case MM_WinCOFF: |
336 | return ".L"; |
337 | case MM_Mips: |
338 | return "$"; |
339 | case MM_MachO: |
340 | case MM_WinCOFFX86: |
341 | return "L"; |
342 | case MM_XCOFF: |
343 | return "L.."; |
344 | } |
345 | llvm_unreachable("invalid mangling mode"); |
346 | } |
347 | |
348 | static const char *getManglingComponent(const Triple &T); |
349 | |
350 | |
351 | |
352 | |
353 | |
354 | |
355 | bool fitsInLegalInteger(unsigned Width) const { |
356 | for (unsigned LegalIntWidth : LegalIntWidths) |
357 | if (Width <= LegalIntWidth) |
358 | return true; |
359 | return false; |
360 | } |
361 | |
362 | |
363 | Align getPointerABIAlignment(unsigned AS) const; |
364 | |
365 | |
366 | |
367 | |
368 | Align getPointerPrefAlignment(unsigned AS = 0) const; |
369 | |
370 | |
371 | |
372 | |
373 | unsigned getPointerSize(unsigned AS = 0) const; |
374 | |
375 | |
376 | unsigned getMaxPointerSize() const; |
377 | |
378 | |
379 | unsigned getIndexSize(unsigned AS) const; |
380 | |
381 | |
382 | |
383 | ArrayRef<unsigned> getNonIntegralAddressSpaces() const { |
384 | return NonIntegralAddressSpaces; |
385 | } |
386 | |
387 | bool isNonIntegralAddressSpace(unsigned AddrSpace) const { |
388 | ArrayRef<unsigned> NonIntegralSpaces = getNonIntegralAddressSpaces(); |
389 | return is_contained(NonIntegralSpaces, AddrSpace); |
390 | } |
391 | |
392 | bool isNonIntegralPointerType(PointerType *PT) const { |
393 | return isNonIntegralAddressSpace(PT->getAddressSpace()); |
394 | } |
395 | |
396 | bool isNonIntegralPointerType(Type *Ty) const { |
397 | auto *PTy = dyn_cast<PointerType>(Ty); |
398 | return PTy && isNonIntegralPointerType(PTy); |
399 | } |
400 | |
401 | |
402 | |
403 | |
404 | unsigned getPointerSizeInBits(unsigned AS = 0) const { |
405 | return getPointerSize(AS) * 8; |
406 | } |
407 | |
408 | |
409 | unsigned getMaxPointerSizeInBits() const { |
410 | return getMaxPointerSize() * 8; |
411 | } |
412 | |
413 | |
414 | unsigned getIndexSizeInBits(unsigned AS) const { |
415 | return getIndexSize(AS) * 8; |
416 | } |
417 | |
418 | |
419 | |
420 | |
421 | |
422 | |
423 | unsigned getPointerTypeSizeInBits(Type *) const; |
424 | |
425 | |
426 | |
427 | unsigned getIndexTypeSizeInBits(Type *Ty) const; |
428 | |
429 | unsigned getPointerTypeSize(Type *Ty) const { |
430 | return getPointerTypeSizeInBits(Ty) / 8; |
431 | } |
432 | |
433 | |
434 | |
435 | |
436 | |
437 | |
438 | |
439 | |
440 | |
441 | |
442 | |
443 | |
444 | |
445 | |
446 | |
447 | |
448 | |
449 | |
450 | |
451 | |
452 | |
453 | |
454 | |
455 | |
456 | |
457 | TypeSize getTypeSizeInBits(Type *Ty) const; |
458 | |
459 | |
460 | |
461 | |
462 | |
463 | |
464 | |
465 | |
466 | TypeSize getTypeStoreSize(Type *Ty) const { |
467 | TypeSize BaseSize = getTypeSizeInBits(Ty); |
468 | return { (BaseSize.getKnownMinSize() + 7) / 8, BaseSize.isScalable() }; |
469 | } |
470 | |
471 | |
472 | |
473 | |
474 | |
475 | |
476 | |
477 | |
478 | TypeSize getTypeStoreSizeInBits(Type *Ty) const { |
479 | return 8 * getTypeStoreSize(Ty); |
480 | } |
481 | |
482 | |
483 | |
484 | |
485 | |
486 | bool typeSizeEqualsStoreSize(Type *Ty) const { |
487 | return getTypeSizeInBits(Ty) == getTypeStoreSizeInBits(Ty); |
488 | } |
489 | |
490 | |
491 | |
492 | |
493 | |
494 | |
495 | |
496 | |
497 | |
498 | TypeSize getTypeAllocSize(Type *Ty) const { |
499 | |
500 | return alignTo(getTypeStoreSize(Ty), getABITypeAlignment(Ty)); |
| 9 | | Calling 'DataLayout::getABITypeAlignment' | |
|
501 | } |
502 | |
503 | |
504 | |
505 | |
506 | |
507 | |
508 | |
509 | |
510 | |
511 | TypeSize getTypeAllocSizeInBits(Type *Ty) const { |
512 | return 8 * getTypeAllocSize(Ty); |
513 | } |
514 | |
515 | |
516 | |
517 | unsigned getABITypeAlignment(Type *Ty) const; |
518 | |
519 | |
520 | Align getABITypeAlign(Type *Ty) const; |
521 | |
522 | |
523 | |
524 | inline Align getValueOrABITypeAlignment(MaybeAlign Alignment, |
525 | Type *Ty) const { |
526 | return Alignment ? *Alignment : getABITypeAlign(Ty); |
527 | } |
528 | |
529 | |
530 | |
531 | Align getABIIntegerTypeAlignment(unsigned BitWidth) const { |
532 | return getIntegerAlignment(BitWidth, true); |
533 | } |
534 | |
535 | |
536 | |
537 | |
538 | |
539 | |
540 | unsigned getPrefTypeAlignment(Type *Ty) const; |
541 | |
542 | |
543 | |
544 | |
545 | |
546 | Align getPrefTypeAlign(Type *Ty) const; |
547 | |
548 | |
549 | |
550 | IntegerType *getIntPtrType(LLVMContext &C, unsigned AddressSpace = 0) const; |
551 | |
552 | |
553 | |
554 | Type *getIntPtrType(Type *) const; |
555 | |
556 | |
557 | |
558 | Type *getSmallestLegalIntType(LLVMContext &C, unsigned Width = 0) const; |
559 | |
560 | |
561 | Type *getLargestLegalIntType(LLVMContext &C) const { |
562 | unsigned LargestSize = getLargestLegalIntTypeSizeInBits(); |
563 | return (LargestSize == 0) ? nullptr : Type::getIntNTy(C, LargestSize); |
564 | } |
565 | |
566 | |
567 | |
568 | unsigned getLargestLegalIntTypeSizeInBits() const; |
569 | |
570 | |
571 | |
572 | |
573 | Type *getIndexType(Type *PtrTy) const; |
574 | |
575 | |
576 | |
577 | |
578 | |
579 | |
580 | int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef<Value *> Indices) const; |
581 | |
582 | |
583 | |
584 | |
585 | |
586 | const StructLayout *getStructLayout(StructType *Ty) const; |
587 | |
588 | |
589 | |
590 | |
591 | Align getPreferredAlign(const GlobalVariable *GV) const; |
592 | }; |
593 | |
594 | inline DataLayout *unwrap(LLVMTargetDataRef P) { |
595 | return reinterpret_cast<DataLayout *>(P); |
596 | } |
597 | |
598 | inline LLVMTargetDataRef wrap(const DataLayout *P) { |
599 | return reinterpret_cast<LLVMTargetDataRef>(const_cast<DataLayout *>(P)); |
600 | } |
601 | |
602 | |
603 | |
604 | class StructLayout final : public TrailingObjects<StructLayout, uint64_t> { |
605 | uint64_t StructSize; |
606 | Align StructAlignment; |
607 | unsigned IsPadded : 1; |
608 | unsigned NumElements : 31; |
609 | |
610 | public: |
611 | uint64_t getSizeInBytes() const { return StructSize; } |
612 | |
613 | uint64_t getSizeInBits() const { return 8 * StructSize; } |
614 | |
615 | Align getAlignment() const { return StructAlignment; } |
616 | |
617 | |
618 | |
619 | bool hasPadding() const { return IsPadded; } |
620 | |
621 | |
622 | |
623 | unsigned getElementContainingOffset(uint64_t Offset) const; |
624 | |
625 | MutableArrayRef<uint64_t> getMemberOffsets() { |
626 | return llvm::makeMutableArrayRef(getTrailingObjects<uint64_t>(), |
627 | NumElements); |
628 | } |
629 | |
630 | ArrayRef<uint64_t> getMemberOffsets() const { |
631 | return llvm::makeArrayRef(getTrailingObjects<uint64_t>(), NumElements); |
632 | } |
633 | |
634 | uint64_t getElementOffset(unsigned Idx) const { |
635 | assert(Idx < NumElements && "Invalid element idx!"); |
636 | return getMemberOffsets()[Idx]; |
637 | } |
638 | |
639 | uint64_t getElementOffsetInBits(unsigned Idx) const { |
640 | return getElementOffset(Idx) * 8; |
641 | } |
642 | |
643 | private: |
644 | friend class DataLayout; |
645 | |
646 | StructLayout(StructType *ST, const DataLayout &DL); |
647 | |
648 | size_t numTrailingObjects(OverloadToken<uint64_t>) const { |
649 | return NumElements; |
650 | } |
651 | }; |
652 | |
653 | |
654 | |
655 | inline TypeSize DataLayout::getTypeSizeInBits(Type *Ty) const { |
656 | assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!"); |
657 | switch (Ty->getTypeID()) { |
658 | case Type::LabelTyID: |
659 | return TypeSize::Fixed(getPointerSizeInBits(0)); |
660 | case Type::PointerTyID: |
661 | return TypeSize::Fixed(getPointerSizeInBits(Ty->getPointerAddressSpace())); |
662 | case Type::ArrayTyID: { |
663 | ArrayType *ATy = cast<ArrayType>(Ty); |
664 | return ATy->getNumElements() * |
665 | getTypeAllocSizeInBits(ATy->getElementType()); |
666 | } |
667 | case Type::StructTyID: |
668 | |
669 | return TypeSize::Fixed( |
670 | getStructLayout(cast<StructType>(Ty))->getSizeInBits()); |
671 | case Type::IntegerTyID: |
672 | return TypeSize::Fixed(Ty->getIntegerBitWidth()); |
673 | case Type::HalfTyID: |
674 | case Type::BFloatTyID: |
675 | return TypeSize::Fixed(16); |
676 | case Type::FloatTyID: |
677 | return TypeSize::Fixed(32); |
678 | case Type::DoubleTyID: |
679 | case Type::X86_MMXTyID: |
680 | return TypeSize::Fixed(64); |
681 | case Type::PPC_FP128TyID: |
682 | case Type::FP128TyID: |
683 | return TypeSize::Fixed(128); |
684 | case Type::X86_AMXTyID: |
685 | return TypeSize::Fixed(8192); |
686 | |
687 | |
688 | case Type::X86_FP80TyID: |
689 | return TypeSize::Fixed(80); |
690 | case Type::FixedVectorTyID: |
691 | case Type::ScalableVectorTyID: { |
692 | VectorType *VTy = cast<VectorType>(Ty); |
693 | auto EltCnt = VTy->getElementCount(); |
694 | uint64_t MinBits = EltCnt.getKnownMinValue() * |
695 | getTypeSizeInBits(VTy->getElementType()).getFixedSize(); |
696 | return TypeSize(MinBits, EltCnt.isScalable()); |
697 | } |
698 | default: |
699 | llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type"); |
700 | } |
701 | } |
702 | |
703 | } |
704 | |
705 | #endif // LLVM_IR_DATALAYOUT_H |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | #ifndef LLVM_SUPPORT_ALIGNMENT_H_ |
22 | #define LLVM_SUPPORT_ALIGNMENT_H_ |
23 | |
24 | #include "llvm/ADT/Optional.h" |
25 | #include "llvm/Support/MathExtras.h" |
26 | #include <cassert> |
27 | #ifndef NDEBUG |
28 | #include <string> |
29 | #endif // NDEBUG |
30 | |
31 | namespace llvm { |
32 | |
33 | #define ALIGN_CHECK_ISPOSITIVE(decl) \ |
34 | assert(decl > 0 && (#decl " should be defined")) |
35 | |
36 | |
37 | |
38 | |
39 | struct Align { |
40 | private: |
41 | uint8_t ShiftValue = 0; |
42 | |
43 | |
44 | friend struct MaybeAlign; |
45 | friend unsigned Log2(Align); |
46 | friend bool operator==(Align Lhs, Align Rhs); |
47 | friend bool operator!=(Align Lhs, Align Rhs); |
48 | friend bool operator<=(Align Lhs, Align Rhs); |
49 | friend bool operator>=(Align Lhs, Align Rhs); |
50 | friend bool operator<(Align Lhs, Align Rhs); |
51 | friend bool operator>(Align Lhs, Align Rhs); |
52 | friend unsigned encode(struct MaybeAlign A); |
53 | friend struct MaybeAlign decodeMaybeAlign(unsigned Value); |
54 | |
55 | |
56 | |
57 | |
58 | |
59 | |
60 | |
61 | |
62 | struct LogValue { |
63 | uint8_t Log; |
64 | }; |
65 | |
66 | public: |
67 | |
68 | constexpr Align() = default; |
69 | |
70 | |
71 | constexpr Align(const Align &Other) = default; |
72 | constexpr Align(Align &&Other) = default; |
73 | Align &operator=(const Align &Other) = default; |
74 | Align &operator=(Align &&Other) = default; |
75 | |
76 | explicit Align(uint64_t Value) { |
77 | assert(Value > 0 && "Value must not be 0"); |
78 | assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2"); |
79 | ShiftValue = Log2_64(Value); |
| |
| 17 | | Returning from 'Log2_64' | |
|
| 18 | | The value 255 is assigned to field 'ShiftValue' | |
|
80 | assert(ShiftValue < 64 && "Broken invariant"); |
81 | } |
82 | |
83 | |
84 | |
85 | uint64_t value() const { return uint64_t(1) << ShiftValue; } |
| 23 | | The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'uint64_t' |
|
86 | |
87 | |
88 | template <size_t kValue> constexpr static LogValue Constant() { |
89 | return LogValue{static_cast<uint8_t>(CTLog2<kValue>())}; |
90 | } |
91 | |
92 | |
93 | |
94 | template <typename T> constexpr static LogValue Of() { |
95 | return Constant<std::alignment_of<T>::value>(); |
96 | } |
97 | |
98 | |
99 | constexpr Align(LogValue CA) : ShiftValue(CA.Log) {} |
100 | }; |
101 | |
102 | |
103 | inline Align assumeAligned(uint64_t Value) { |
104 | return Value ? Align(Value) : Align(); |
105 | } |
106 | |
107 | |
108 | |
109 | struct MaybeAlign : public llvm::Optional<Align> { |
110 | private: |
111 | using UP = llvm::Optional<Align>; |
112 | |
113 | public: |
114 | |
115 | MaybeAlign() = default; |
116 | |
117 | |
118 | MaybeAlign(const MaybeAlign &Other) = default; |
119 | MaybeAlign &operator=(const MaybeAlign &Other) = default; |
120 | MaybeAlign(MaybeAlign &&Other) = default; |
121 | MaybeAlign &operator=(MaybeAlign &&Other) = default; |
122 | |
123 | |
124 | using UP::UP; |
125 | |
126 | explicit MaybeAlign(uint64_t Value) { |
127 | assert((Value == 0 || llvm::isPowerOf2_64(Value)) && |
128 | "Alignment is neither 0 nor a power of 2"); |
129 | if (Value) |
130 | emplace(Value); |
131 | } |
132 | |
133 | |
134 | Align valueOrOne() const { return hasValue() ? getValue() : Align(); } |
135 | }; |
136 | |
137 | |
138 | inline bool isAligned(Align Lhs, uint64_t SizeInBytes) { |
139 | return SizeInBytes % Lhs.value() == 0; |
140 | } |
141 | |
142 | |
143 | inline bool isAddrAligned(Align Lhs, const void *Addr) { |
144 | return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr)); |
145 | } |
146 | |
147 | |
148 | inline uint64_t alignTo(uint64_t Size, Align A) { |
149 | const uint64_t Value = A.value(); |
150 | |
151 | |
152 | |
153 | |
154 | |
155 | |
156 | |
157 | |
158 | |
159 | return (Size + Value - 1) & ~(Value - 1U); |
160 | } |
161 | |
162 | |
163 | |
164 | |
165 | |
166 | |
167 | |
168 | |
169 | |
170 | |
171 | |
172 | |
173 | inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { |
174 | const uint64_t Value = A.value(); |
175 | Skew %= Value; |
176 | return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew; |
177 | } |
178 | |
179 | |
180 | |
181 | inline uint64_t alignTo(uint64_t Size, MaybeAlign A) { |
182 | return A ? alignTo(Size, A.getValue()) : Size; |
183 | } |
184 | |
185 | |
186 | inline uintptr_t alignAddr(const void *Addr, Align Alignment) { |
187 | uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr); |
188 | assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >= |
189 | ArithAddr && |
190 | "Overflow"); |
191 | return alignTo(ArithAddr, Alignment); |
192 | } |
193 | |
194 | |
195 | |
196 | inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) { |
197 | return alignTo(Value, Alignment) - Value; |
198 | } |
199 | |
200 | |
201 | |
202 | inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) { |
203 | return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment); |
204 | } |
205 | |
206 | |
207 | inline unsigned Log2(Align A) { return A.ShiftValue; } |
208 | |
209 | |
210 | |
211 | inline Align commonAlignment(Align A, Align B) { return std::min(A, B); } |
212 | |
213 | |
214 | |
215 | inline Align commonAlignment(Align A, uint64_t Offset) { |
216 | return Align(MinAlign(A.value(), Offset)); |
217 | } |
218 | |
219 | |
220 | |
221 | inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) { |
222 | return A && B ? commonAlignment(*A, *B) : A ? A : B; |
223 | } |
224 | |
225 | |
226 | |
227 | inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) { |
228 | return MaybeAlign(MinAlign((*A).value(), Offset)); |
229 | } |
230 | |
231 | |
232 | inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } |
233 | |
234 | |
235 | inline MaybeAlign decodeMaybeAlign(unsigned Value) { |
236 | if (Value == 0) |
237 | return MaybeAlign(); |
238 | Align Out; |
239 | Out.ShiftValue = Value - 1; |
240 | return Out; |
241 | } |
242 | |
243 | |
244 | |
245 | inline unsigned encode(Align A) { return encode(MaybeAlign(A)); } |
246 | |
247 | |
248 | inline bool operator==(Align Lhs, uint64_t Rhs) { |
249 | ALIGN_CHECK_ISPOSITIVE(Rhs); |
250 | return Lhs.value() == Rhs; |
251 | } |
252 | inline bool operator!=(Align Lhs, uint64_t Rhs) { |
253 | ALIGN_CHECK_ISPOSITIVE(Rhs); |
254 | return Lhs.value() != Rhs; |
255 | } |
256 | inline bool operator<=(Align Lhs, uint64_t Rhs) { |
257 | ALIGN_CHECK_ISPOSITIVE(Rhs); |
258 | return Lhs.value() <= Rhs; |
259 | } |
260 | inline bool operator>=(Align Lhs, uint64_t Rhs) { |
261 | ALIGN_CHECK_ISPOSITIVE(Rhs); |
262 | return Lhs.value() >= Rhs; |
263 | } |
264 | inline bool operator<(Align Lhs, uint64_t Rhs) { |
265 | ALIGN_CHECK_ISPOSITIVE(Rhs); |
266 | return Lhs.value() < Rhs; |
267 | } |
268 | inline bool operator>(Align Lhs, uint64_t Rhs) { |
269 | ALIGN_CHECK_ISPOSITIVE(Rhs); |
270 | return Lhs.value() > Rhs; |
271 | } |
272 | |
273 | |
274 | inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) { |
275 | return Lhs ? (*Lhs).value() == Rhs : Rhs == 0; |
276 | } |
277 | inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) { |
278 | return Lhs ? (*Lhs).value() != Rhs : Rhs != 0; |
279 | } |
280 | |
281 | |
282 | inline bool operator==(Align Lhs, Align Rhs) { |
283 | return Lhs.ShiftValue == Rhs.ShiftValue; |
284 | } |
285 | inline bool operator!=(Align Lhs, Align Rhs) { |
286 | return Lhs.ShiftValue != Rhs.ShiftValue; |
287 | } |
288 | inline bool operator<=(Align Lhs, Align Rhs) { |
289 | return Lhs.ShiftValue <= Rhs.ShiftValue; |
290 | } |
291 | inline bool operator>=(Align Lhs, Align Rhs) { |
292 | return Lhs.ShiftValue >= Rhs.ShiftValue; |
293 | } |
294 | inline bool operator<(Align Lhs, Align Rhs) { |
295 | return Lhs.ShiftValue < Rhs.ShiftValue; |
296 | } |
297 | inline bool operator>(Align Lhs, Align Rhs) { |
298 | return Lhs.ShiftValue > Rhs.ShiftValue; |
299 | } |
300 | |
301 | |
302 | bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; |
303 | bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; |
304 | bool operator<(Align Lhs, MaybeAlign Rhs) = delete; |
305 | bool operator>(Align Lhs, MaybeAlign Rhs) = delete; |
306 | |
307 | bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; |
308 | bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; |
309 | bool operator<(MaybeAlign Lhs, Align Rhs) = delete; |
310 | bool operator>(MaybeAlign Lhs, Align Rhs) = delete; |
311 | |
312 | bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; |
313 | bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; |
314 | bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; |
315 | bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; |
316 | |
317 | inline Align operator*(Align Lhs, uint64_t Rhs) { |
318 | assert(Rhs > 0 && "Rhs must be positive"); |
319 | return Align(Lhs.value() * Rhs); |
320 | } |
321 | |
322 | inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) { |
323 | assert(Rhs > 0 && "Rhs must be positive"); |
324 | return Lhs ? Lhs.getValue() * Rhs : MaybeAlign(); |
325 | } |
326 | |
327 | inline Align operator/(Align Lhs, uint64_t Divisor) { |
328 | assert(llvm::isPowerOf2_64(Divisor) && |
329 | "Divisor must be positive and a power of 2"); |
330 | assert(Lhs != 1 && "Can't halve byte alignment"); |
331 | return Align(Lhs.value() / Divisor); |
332 | } |
333 | |
334 | inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) { |
335 | assert(llvm::isPowerOf2_64(Divisor) && |
336 | "Divisor must be positive and a power of 2"); |
337 | return Lhs ? Lhs.getValue() / Divisor : MaybeAlign(); |
338 | } |
339 | |
340 | inline Align max(MaybeAlign Lhs, Align Rhs) { |
341 | return Lhs && *Lhs > Rhs ? *Lhs : Rhs; |
342 | } |
343 | |
344 | inline Align max(Align Lhs, MaybeAlign Rhs) { |
345 | return Rhs && *Rhs > Lhs ? *Rhs : Lhs; |
346 | } |
347 | |
348 | #ifndef NDEBUG |
349 | |
350 | inline std::string DebugStr(const Align &A) { |
351 | return std::to_string(A.value()); |
352 | } |
353 | |
354 | inline std::string DebugStr(const MaybeAlign &MA) { |
355 | if (MA) |
356 | return std::to_string(MA->value()); |
357 | return "None"; |
358 | } |
359 | #endif // NDEBUG |
360 | |
361 | #undef ALIGN_CHECK_ISPOSITIVE |
362 | |
363 | } |
364 | |
365 | #endif // LLVM_SUPPORT_ALIGNMENT_H_ |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | #ifndef LLVM_SUPPORT_MATHEXTRAS_H |
14 | #define LLVM_SUPPORT_MATHEXTRAS_H |
15 | |
16 | #include "llvm/Support/Compiler.h" |
17 | #include <cassert> |
18 | #include <climits> |
19 | #include <cmath> |
20 | #include <cstdint> |
21 | #include <cstring> |
22 | #include <limits> |
23 | #include <type_traits> |
24 | |
25 | #ifdef __ANDROID_NDK__ |
26 | #include <android/api-level.h> |
27 | #endif |
28 | |
29 | #ifdef _MSC_VER |
30 | |
31 | |
32 | |
33 | extern "C" { |
34 | unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); |
35 | unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); |
36 | unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); |
37 | unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); |
38 | } |
39 | #endif |
40 | |
41 | namespace llvm { |
42 | |
43 | |
44 | enum ZeroBehavior { |
45 | |
46 | ZB_Undefined, |
47 | |
48 | ZB_Max, |
49 | |
50 | ZB_Width |
51 | }; |
52 | |
53 | |
54 | namespace numbers { |
55 | |
56 | |
57 | constexpr double e = 2.7182818284590452354, |
58 | egamma = .57721566490153286061, |
59 | ln2 = .69314718055994530942, |
60 | ln10 = 2.3025850929940456840, |
61 | log2e = 1.4426950408889634074, |
62 | log10e = .43429448190325182765, |
63 | pi = 3.1415926535897932385, |
64 | inv_pi = .31830988618379067154, |
65 | sqrtpi = 1.7724538509055160273, |
66 | inv_sqrtpi = .56418958354775628695, |
67 | sqrt2 = 1.4142135623730950488, |
68 | inv_sqrt2 = .70710678118654752440, |
69 | sqrt3 = 1.7320508075688772935, |
70 | inv_sqrt3 = .57735026918962576451, |
71 | phi = 1.6180339887498948482; |
72 | constexpr float ef = 2.71828183F, |
73 | egammaf = .577215665F, |
74 | ln2f = .693147181F, |
75 | ln10f = 2.30258509F, |
76 | log2ef = 1.44269504F, |
77 | log10ef = .434294482F, |
78 | pif = 3.14159265F, |
79 | inv_pif = .318309886F, |
80 | sqrtpif = 1.77245385F, |
81 | inv_sqrtpif = .564189584F, |
82 | sqrt2f = 1.41421356F, |
83 | inv_sqrt2f = .707106781F, |
84 | sqrt3f = 1.73205081F, |
85 | inv_sqrt3f = .577350269F, |
86 | phif = 1.61803399F; |
87 | } |
88 | |
89 | namespace detail { |
90 | template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { |
91 | static unsigned count(T Val, ZeroBehavior) { |
92 | if (!Val) |
93 | return std::numeric_limits<T>::digits; |
94 | if (Val & 0x1) |
95 | return 0; |
96 | |
97 | |
98 | unsigned ZeroBits = 0; |
99 | T Shift = std::numeric_limits<T>::digits >> 1; |
100 | T Mask = std::numeric_limits<T>::max() >> Shift; |
101 | while (Shift) { |
102 | if ((Val & Mask) == 0) { |
103 | Val >>= Shift; |
104 | ZeroBits |= Shift; |
105 | } |
106 | Shift >>= 1; |
107 | Mask >>= Shift; |
108 | } |
109 | return ZeroBits; |
110 | } |
111 | }; |
112 | |
113 | #if defined(__GNUC__) || defined(_MSC_VER) |
114 | template <typename T> struct TrailingZerosCounter<T, 4> { |
115 | static unsigned count(T Val, ZeroBehavior ZB) { |
116 | if (ZB != ZB_Undefined && Val == 0) |
117 | return 32; |
118 | |
119 | #if __has_builtin(__builtin_ctz) || defined(__GNUC__) |
120 | return __builtin_ctz(Val); |
121 | #elif defined(_MSC_VER) |
122 | unsigned long Index; |
123 | _BitScanForward(&Index, Val); |
124 | return Index; |
125 | #endif |
126 | } |
127 | }; |
128 | |
129 | #if !defined(_MSC_VER) || defined(_M_X64) |
130 | template <typename T> struct TrailingZerosCounter<T, 8> { |
131 | static unsigned count(T Val, ZeroBehavior ZB) { |
132 | if (ZB != ZB_Undefined && Val == 0) |
133 | return 64; |
134 | |
135 | #if __has_builtin(__builtin_ctzll) || defined(__GNUC__) |
136 | return __builtin_ctzll(Val); |
137 | #elif defined(_MSC_VER) |
138 | unsigned long Index; |
139 | _BitScanForward64(&Index, Val); |
140 | return Index; |
141 | #endif |
142 | } |
143 | }; |
144 | #endif |
145 | #endif |
146 | } |
147 | |
148 | |
149 | |
150 | |
151 | |
152 | |
153 | |
154 | |
155 | template <typename T> |
156 | unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { |
157 | static_assert(std::numeric_limits<T>::is_integer && |
158 | !std::numeric_limits<T>::is_signed, |
159 | "Only unsigned integral types are allowed."); |
160 | return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB); |
161 | } |
162 | |
163 | namespace detail { |
164 | template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { |
165 | static unsigned count(T Val, ZeroBehavior) { |
166 | if (!Val) |
167 | return std::numeric_limits<T>::digits; |
168 | |
169 | |
170 | unsigned ZeroBits = 0; |
171 | for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) { |
172 | T Tmp = Val >> Shift; |
173 | if (Tmp) |
174 | Val = Tmp; |
175 | else |
176 | ZeroBits |= Shift; |
177 | } |
178 | return ZeroBits; |
179 | } |
180 | }; |
181 | |
182 | #if defined(__GNUC__) || defined(_MSC_VER) |
183 | template <typename T> struct LeadingZerosCounter<T, 4> { |
184 | static unsigned count(T Val, ZeroBehavior ZB) { |
185 | if (ZB != ZB_Undefined && Val == 0) |
186 | return 32; |
187 | |
188 | #if __has_builtin(__builtin_clz) || defined(__GNUC__) |
189 | return __builtin_clz(Val); |
190 | #elif defined(_MSC_VER) |
191 | unsigned long Index; |
192 | _BitScanReverse(&Index, Val); |
193 | return Index ^ 31; |
194 | #endif |
195 | } |
196 | }; |
197 | |
198 | #if !defined(_MSC_VER) || defined(_M_X64) |
199 | template <typename T> struct LeadingZerosCounter<T, 8> { |
200 | static unsigned count(T Val, ZeroBehavior ZB) { |
201 | if (ZB != ZB_Undefined && Val == 0) |
202 | return 64; |
203 | |
204 | #if __has_builtin(__builtin_clzll) || defined(__GNUC__) |
205 | return __builtin_clzll(Val); |
206 | #elif defined(_MSC_VER) |
207 | unsigned long Index; |
208 | _BitScanReverse64(&Index, Val); |
209 | return Index ^ 63; |
210 | #endif |
211 | } |
212 | }; |
213 | #endif |
214 | #endif |
215 | } |
216 | |
217 | |
218 | |
219 | |
220 | |
221 | |
222 | |
223 | |
224 | template <typename T> |
225 | unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { |
226 | static_assert(std::numeric_limits<T>::is_integer && |
227 | !std::numeric_limits<T>::is_signed, |
228 | "Only unsigned integral types are allowed."); |
229 | return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB); |
230 | } |
231 | |
232 | |
233 | |
234 | |
235 | |
236 | |
237 | |
238 | |
239 | template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { |
240 | if (ZB == ZB_Max && Val == 0) |
241 | return std::numeric_limits<T>::max(); |
242 | |
243 | return countTrailingZeros(Val, ZB_Undefined); |
244 | } |
245 | |
246 | |
247 | |
248 | template <typename T> T maskTrailingOnes(unsigned N) { |
249 | static_assert(std::is_unsigned<T>::value, "Invalid type!"); |
250 | const unsigned Bits = CHAR_BIT * sizeof(T); |
251 | assert(N <= Bits && "Invalid bit index"); |
252 | return N == 0 ? 0 : (T(-1) >> (Bits - N)); |
253 | } |
254 | |
255 | |
256 | |
257 | template <typename T> T maskLeadingOnes(unsigned N) { |
258 | return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); |
259 | } |
260 | |
261 | |
262 | |
263 | template <typename T> T maskTrailingZeros(unsigned N) { |
264 | return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N); |
265 | } |
266 | |
267 | |
268 | |
269 | template <typename T> T maskLeadingZeros(unsigned N) { |
270 | return maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); |
271 | } |
272 | |
273 | |
274 | |
275 | |
276 | |
277 | |
278 | |
279 | |
280 | template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { |
281 | if (ZB == ZB_Max && Val == 0) |
282 | return std::numeric_limits<T>::max(); |
283 | |
284 | |
285 | |
286 | return countLeadingZeros(Val, ZB_Undefined) ^ |
287 | (std::numeric_limits<T>::digits - 1); |
288 | } |
289 | |
290 | |
291 | |
292 | |
293 | static const unsigned char BitReverseTable256[256] = { |
294 | #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 |
295 | #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) |
296 | #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) |
297 | R6(0), R6(2), R6(1), R6(3) |
298 | #undef R2 |
299 | #undef R4 |
300 | #undef R6 |
301 | }; |
302 | |
303 | |
304 | template <typename T> |
305 | T reverseBits(T Val) { |
306 | unsigned char in[sizeof(Val)]; |
307 | unsigned char out[sizeof(Val)]; |
308 | std::memcpy(in, &Val, sizeof(Val)); |
309 | for (unsigned i = 0; i < sizeof(Val); ++i) |
310 | out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]]; |
311 | std::memcpy(&Val, out, sizeof(Val)); |
312 | return Val; |
313 | } |
314 | |
315 | #if __has_builtin(__builtin_bitreverse8) |
316 | template<> |
317 | inline uint8_t reverseBits<uint8_t>(uint8_t Val) { |
318 | return __builtin_bitreverse8(Val); |
319 | } |
320 | #endif |
321 | |
322 | #if __has_builtin(__builtin_bitreverse16) |
323 | template<> |
324 | inline uint16_t reverseBits<uint16_t>(uint16_t Val) { |
325 | return __builtin_bitreverse16(Val); |
326 | } |
327 | #endif |
328 | |
329 | #if __has_builtin(__builtin_bitreverse32) |
330 | template<> |
331 | inline uint32_t reverseBits<uint32_t>(uint32_t Val) { |
332 | return __builtin_bitreverse32(Val); |
333 | } |
334 | #endif |
335 | |
336 | #if __has_builtin(__builtin_bitreverse64) |
337 | template<> |
338 | inline uint64_t reverseBits<uint64_t>(uint64_t Val) { |
339 | return __builtin_bitreverse64(Val); |
340 | } |
341 | #endif |
342 | |
343 | |
344 | |
345 | |
346 | |
347 | |
348 | constexpr inline uint32_t Hi_32(uint64_t Value) { |
349 | return static_cast<uint32_t>(Value >> 32); |
350 | } |
351 | |
352 | |
353 | constexpr inline uint32_t Lo_32(uint64_t Value) { |
354 | return static_cast<uint32_t>(Value); |
355 | } |
356 | |
357 | |
358 | constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) { |
359 | return ((uint64_t)High << 32) | (uint64_t)Low; |
360 | } |
361 | |
362 | |
363 | template <unsigned N> constexpr inline bool isInt(int64_t x) { |
364 | return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); |
365 | } |
366 | |
367 | template <> constexpr inline bool isInt<8>(int64_t x) { |
368 | return static_cast<int8_t>(x) == x; |
369 | } |
370 | template <> constexpr inline bool isInt<16>(int64_t x) { |
371 | return static_cast<int16_t>(x) == x; |
372 | } |
373 | template <> constexpr inline bool isInt<32>(int64_t x) { |
374 | return static_cast<int32_t>(x) == x; |
375 | } |
376 | |
377 | |
378 | template <unsigned N, unsigned S> |
379 | constexpr inline bool isShiftedInt(int64_t x) { |
380 | static_assert( |
381 | N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number."); |
382 | static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide."); |
383 | return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0); |
384 | } |
385 | |
386 | |
387 | |
388 | |
389 | |
390 | |
391 | |
392 | |
393 | |
394 | template <unsigned N> |
395 | constexpr inline std::enable_if_t<(N < 64), bool> isUInt(uint64_t X) { |
396 | static_assert(N > 0, "isUInt<0> doesn't make sense"); |
397 | return X < (UINT64_C(1) << (N)); |
398 | } |
399 | template <unsigned N> |
400 | constexpr inline std::enable_if_t<N >= 64, bool> isUInt(uint64_t) { |
401 | return true; |
402 | } |
403 | |
404 | |
405 | template <> constexpr inline bool isUInt<8>(uint64_t x) { |
406 | return static_cast<uint8_t>(x) == x; |
407 | } |
408 | template <> constexpr inline bool isUInt<16>(uint64_t x) { |
409 | return static_cast<uint16_t>(x) == x; |
410 | } |
411 | template <> constexpr inline bool isUInt<32>(uint64_t x) { |
412 | return static_cast<uint32_t>(x) == x; |
413 | } |
414 | |
415 | |
416 | template <unsigned N, unsigned S> |
417 | constexpr inline bool isShiftedUInt(uint64_t x) { |
418 | static_assert( |
419 | N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)"); |
420 | static_assert(N + S <= 64, |
421 | "isShiftedUInt<N, S> with N + S > 64 is too wide."); |
422 | |
423 | |
424 | return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0); |
425 | } |
426 | |
427 | |
428 | inline uint64_t maxUIntN(uint64_t N) { |
429 | assert(N > 0 && N <= 64 && "integer width out of range"); |
430 | |
431 | |
432 | |
433 | |
434 | |
435 | return UINT64_MAX >> (64 - N); |
436 | } |
437 | |
438 | |
439 | inline int64_t minIntN(int64_t N) { |
440 | assert(N > 0 && N <= 64 && "integer width out of range"); |
441 | |
442 | return UINT64_C(1) + ~(UINT64_C(1) << (N - 1)); |
443 | } |
444 | |
445 | |
446 | inline int64_t maxIntN(int64_t N) { |
447 | assert(N > 0 && N <= 64 && "integer width out of range"); |
448 | |
449 | |
450 | |
451 | return (UINT64_C(1) << (N - 1)) - 1; |
452 | } |
453 | |
454 | |
455 | inline bool isUIntN(unsigned N, uint64_t x) { |
456 | return N >= 64 || x <= maxUIntN(N); |
457 | } |
458 | |
459 | |
460 | inline bool isIntN(unsigned N, int64_t x) { |
461 | return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N)); |
462 | } |
463 | |
464 | |
465 | |
466 | |
467 | constexpr inline bool isMask_32(uint32_t Value) { |
468 | return Value && ((Value + 1) & Value) == 0; |
469 | } |
470 | |
471 | |
472 | |
473 | constexpr inline bool isMask_64(uint64_t Value) { |
474 | return Value && ((Value + 1) & Value) == 0; |
475 | } |
476 | |
477 | |
478 | |
479 | constexpr inline bool isShiftedMask_32(uint32_t Value) { |
480 | return Value && isMask_32((Value - 1) | Value); |
481 | } |
482 | |
483 | |
484 | |
485 | constexpr inline bool isShiftedMask_64(uint64_t Value) { |
486 | return Value && isMask_64((Value - 1) | Value); |
487 | } |
488 | |
489 | |
490 | |
491 | constexpr inline bool isPowerOf2_32(uint32_t Value) { |
492 | return Value && !(Value & (Value - 1)); |
493 | } |
494 | |
495 | |
496 | constexpr inline bool isPowerOf2_64(uint64_t Value) { |
497 | return Value && !(Value & (Value - 1)); |
498 | } |
499 | |
500 | |
501 | |
502 | |
503 | |
504 | |
505 | |
506 | |
507 | |
508 | template <typename T> |
509 | unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) { |
510 | static_assert(std::numeric_limits<T>::is_integer && |
511 | !std::numeric_limits<T>::is_signed, |
512 | "Only unsigned integral types are allowed."); |
513 | return countLeadingZeros<T>(~Value, ZB); |
514 | } |
515 | |
516 | |
517 | |
518 | |
519 | |
520 | |
521 | |
522 | |
523 | |
524 | template <typename T> |
525 | unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) { |
526 | static_assert(std::numeric_limits<T>::is_integer && |
527 | !std::numeric_limits<T>::is_signed, |
528 | "Only unsigned integral types are allowed."); |
529 | return countTrailingZeros<T>(~Value, ZB); |
530 | } |
531 | |
532 | namespace detail { |
533 | template <typename T, std::size_t SizeOfT> struct PopulationCounter { |
534 | static unsigned count(T Value) { |
535 | |
536 | static_assert(SizeOfT <= 4, "Not implemented!"); |
537 | #if defined(__GNUC__) |
538 | return __builtin_popcount(Value); |
539 | #else |
540 | uint32_t v = Value; |
541 | v = v - ((v >> 1) & 0x55555555); |
542 | v = (v & 0x33333333) + ((v >> 2) & 0x33333333); |
543 | return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; |
544 | #endif |
545 | } |
546 | }; |
547 | |
548 | template <typename T> struct PopulationCounter<T, 8> { |
549 | static unsigned count(T Value) { |
550 | #if defined(__GNUC__) |
551 | return __builtin_popcountll(Value); |
552 | #else |
553 | uint64_t v = Value; |
554 | v = v - ((v >> 1) & 0x5555555555555555ULL); |
555 | v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); |
556 | v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; |
557 | return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); |
558 | #endif |
559 | } |
560 | }; |
561 | } |
562 | |
563 | |
564 | |
565 | |
566 | template <typename T> |
567 | inline unsigned countPopulation(T Value) { |
568 | static_assert(std::numeric_limits<T>::is_integer && |
569 | !std::numeric_limits<T>::is_signed, |
570 | "Only unsigned integral types are allowed."); |
571 | return detail::PopulationCounter<T, sizeof(T)>::count(Value); |
572 | } |
573 | |
574 | |
575 | |
576 | template <size_t kValue> constexpr inline size_t CTLog2() { |
577 | static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue), |
578 | "Value is not a valid power of 2"); |
579 | return 1 + CTLog2<kValue / 2>(); |
580 | } |
581 | |
582 | template <> constexpr inline size_t CTLog2<1>() { return 0; } |
583 | |
584 | |
585 | inline double Log2(double Value) { |
586 | #if defined(__ANDROID_API__) && __ANDROID_API__ < 18 |
587 | return __builtin_log(Value) / __builtin_log(2.0); |
588 | #else |
589 | return log2(Value); |
590 | #endif |
591 | } |
592 | |
593 | |
594 | |
595 | |
596 | inline unsigned Log2_32(uint32_t Value) { |
597 | return 31 - countLeadingZeros(Value); |
598 | } |
599 | |
600 | |
601 | |
602 | inline unsigned Log2_64(uint64_t Value) { |
603 | return 63 - countLeadingZeros(Value); |
| 16 | | Returning the value 4294967295 | |
|
604 | } |
605 | |
606 | |
607 | |
608 | |
609 | inline unsigned Log2_32_Ceil(uint32_t Value) { |
610 | return 32 - countLeadingZeros(Value - 1); |
611 | } |
612 | |
613 | |
614 | |
615 | inline unsigned Log2_64_Ceil(uint64_t Value) { |
616 | return 64 - countLeadingZeros(Value - 1); |
617 | } |
618 | |
619 | |
620 | template <typename T> |
621 | inline T greatestCommonDivisor(T A, T B) { |
622 | while (B) { |
623 | T Tmp = B; |
624 | B = A % B; |
625 | A = Tmp; |
626 | } |
627 | return A; |
628 | } |
629 | |
630 | inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { |
631 | return greatestCommonDivisor<uint64_t>(A, B); |
632 | } |
633 | |
634 | |
635 | inline double BitsToDouble(uint64_t Bits) { |
636 | double D; |
637 | static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes"); |
638 | memcpy(&D, &Bits, sizeof(Bits)); |
639 | return D; |
640 | } |
641 | |
642 | |
643 | inline float BitsToFloat(uint32_t Bits) { |
644 | float F; |
645 | static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes"); |
646 | memcpy(&F, &Bits, sizeof(Bits)); |
647 | return F; |
648 | } |
649 | |
650 | |
651 | |
652 | |
653 | inline uint64_t DoubleToBits(double Double) { |
654 | uint64_t Bits; |
655 | static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes"); |
656 | memcpy(&Bits, &Double, sizeof(Double)); |
657 | return Bits; |
658 | } |
659 | |
660 | |
661 | |
662 | |
663 | inline uint32_t FloatToBits(float Float) { |
664 | uint32_t Bits; |
665 | static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes"); |
666 | memcpy(&Bits, &Float, sizeof(Float)); |
667 | return Bits; |
668 | } |
669 | |
670 | |
671 | |
672 | constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) { |
673 | |
674 | |
675 | |
676 | |
677 | |
678 | return (A | B) & (1 + ~(A | B)); |
679 | } |
680 | |
681 | |
682 | |
683 | inline uint64_t NextPowerOf2(uint64_t A) { |
684 | A |= (A >> 1); |
685 | A |= (A >> 2); |
686 | A |= (A >> 4); |
687 | A |= (A >> 8); |
688 | A |= (A >> 16); |
689 | A |= (A >> 32); |
690 | return A + 1; |
691 | } |
692 | |
693 | |
694 | |
695 | inline uint64_t PowerOf2Floor(uint64_t A) { |
696 | if (!A) return 0; |
697 | return 1ull << (63 - countLeadingZeros(A, ZB_Undefined)); |
698 | } |
699 | |
700 | |
701 | |
702 | inline uint64_t PowerOf2Ceil(uint64_t A) { |
703 | if (!A) |
704 | return 0; |
705 | return NextPowerOf2(A - 1); |
706 | } |
707 | |
708 | |
709 | |
710 | |
711 | |
712 | |
713 | |
714 | |
715 | |
716 | |
717 | |
718 | |
719 | |
720 | |
721 | |
722 | |
723 | |
724 | |
725 | |
726 | |
727 | |
728 | inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { |
729 | assert(Align != 0u && "Align can't be 0."); |
730 | Skew %= Align; |
731 | return (Value + Align - 1 - Skew) / Align * Align + Skew; |
732 | } |
733 | |
734 | |
735 | |
736 | template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) { |
737 | static_assert(Align != 0u, "Align must be non-zero"); |
738 | return (Value + Align - 1) / Align * Align; |
739 | } |
740 | |
741 | |
742 | inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) { |
743 | return alignTo(Numerator, Denominator) / Denominator; |
744 | } |
745 | |
746 | |
747 | inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) { |
748 | return (Numerator + (Denominator / 2)) / Denominator; |
749 | } |
750 | |
751 | |
752 | |
753 | inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { |
754 | assert(Align != 0u && "Align can't be 0."); |
755 | Skew %= Align; |
756 | return (Value - Skew) / Align * Align + Skew; |
757 | } |
758 | |
759 | |
760 | |
761 | template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) { |
762 | static_assert(B > 0, "Bit width can't be 0."); |
763 | static_assert(B <= 32, "Bit width out of range."); |
764 | return int32_t(X << (32 - B)) >> (32 - B); |
765 | } |
766 | |
767 | |
768 | |
769 | inline int32_t SignExtend32(uint32_t X, unsigned B) { |
770 | assert(B > 0 && "Bit width can't be 0."); |
771 | assert(B <= 32 && "Bit width out of range."); |
772 | return int32_t(X << (32 - B)) >> (32 - B); |
773 | } |
774 | |
775 | |
776 | |
777 | template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) { |
778 | static_assert(B > 0, "Bit width can't be 0."); |
779 | static_assert(B <= 64, "Bit width out of range."); |
780 | return int64_t(x << (64 - B)) >> (64 - B); |
781 | } |
782 | |
783 | |
784 | |
785 | inline int64_t SignExtend64(uint64_t X, unsigned B) { |
786 | assert(B > 0 && "Bit width can't be 0."); |
787 | assert(B <= 64 && "Bit width out of range."); |
788 | return int64_t(X << (64 - B)) >> (64 - B); |
789 | } |
790 | |
791 | |
792 | |
793 | template <typename T> |
794 | std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) { |
795 | return X > Y ? (X - Y) : (Y - X); |
796 | } |
797 | |
798 | |
799 | |
800 | |
801 | template <typename T> |
802 | std::enable_if_t<std::is_unsigned<T>::value, T> |
803 | SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) { |
804 | bool Dummy; |
805 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
806 | |
807 | T Z = X + Y; |
808 | Overflowed = (Z < X || Z < Y); |
809 | if (Overflowed) |
810 | return std::numeric_limits<T>::max(); |
811 | else |
812 | return Z; |
813 | } |
814 | |
815 | |
816 | |
817 | |
818 | template <typename T> |
819 | std::enable_if_t<std::is_unsigned<T>::value, T> |
820 | SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) { |
821 | bool Dummy; |
822 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
823 | |
824 | |
825 | |
826 | |
827 | |
828 | |
829 | Overflowed = false; |
830 | |
831 | |
832 | |
833 | |
834 | int Log2Z = Log2_64(X) + Log2_64(Y); |
835 | const T Max = std::numeric_limits<T>::max(); |
836 | int Log2Max = Log2_64(Max); |
837 | if (Log2Z < Log2Max) { |
838 | return X * Y; |
839 | } |
840 | if (Log2Z > Log2Max) { |
841 | Overflowed = true; |
842 | return Max; |
843 | } |
844 | |
845 | |
846 | |
847 | |
848 | T Z = (X >> 1) * Y; |
849 | if (Z & ~(Max >> 1)) { |
850 | Overflowed = true; |
851 | return Max; |
852 | } |
853 | Z <<= 1; |
854 | if (X & 1) |
855 | return SaturatingAdd(Z, Y, ResultOverflowed); |
856 | |
857 | return Z; |
858 | } |
859 | |
860 | |
861 | |
862 | |
863 | |
864 | template <typename T> |
865 | std::enable_if_t<std::is_unsigned<T>::value, T> |
866 | SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) { |
867 | bool Dummy; |
868 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
869 | |
870 | T Product = SaturatingMultiply(X, Y, &Overflowed); |
871 | if (Overflowed) |
872 | return Product; |
873 | |
874 | return SaturatingAdd(A, Product, &Overflowed); |
875 | } |
876 | |
877 | |
878 | extern const float huge_valf; |
879 | |
880 | |
881 | |
882 | |
883 | template <typename T> |
884 | std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) { |
885 | #if __has_builtin(__builtin_add_overflow) |
886 | return __builtin_add_overflow(X, Y, &Result); |
887 | #else |
888 | |
889 | using U = std::make_unsigned_t<T>; |
890 | const U UX = static_cast<U>(X); |
891 | const U UY = static_cast<U>(Y); |
892 | const U UResult = UX + UY; |
893 | |
894 | |
895 | Result = static_cast<T>(UResult); |
896 | |
897 | |
898 | if (X > 0 && Y > 0) |
899 | return Result <= 0; |
900 | |
901 | if (X < 0 && Y < 0) |
902 | return Result >= 0; |
903 | return false; |
904 | #endif |
905 | } |
906 | |
907 | |
908 | |
909 | template <typename T> |
910 | std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) { |
911 | #if __has_builtin(__builtin_sub_overflow) |
912 | return __builtin_sub_overflow(X, Y, &Result); |
913 | #else |
914 | |
915 | using U = std::make_unsigned_t<T>; |
916 | const U UX = static_cast<U>(X); |
917 | const U UY = static_cast<U>(Y); |
918 | const U UResult = UX - UY; |
919 | |
920 | |
921 | Result = static_cast<T>(UResult); |
922 | |
923 | |
924 | if (X <= 0 && Y > 0) |
925 | return Result >= 0; |
926 | |
927 | if (X >= 0 && Y < 0) |
928 | return Result <= 0; |
929 | return false; |
930 | #endif |
931 | } |
932 | |
933 | |
934 | |
935 | template <typename T> |
936 | std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) { |
937 | |
938 | using U = std::make_unsigned_t<T>; |
939 | const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X); |
940 | const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y); |
941 | const U UResult = UX * UY; |
942 | |
943 | |
944 | const bool IsNegative = (X < 0) ^ (Y < 0); |
945 | Result = IsNegative ? (0 - UResult) : UResult; |
946 | |
947 | |
948 | if (UX == 0 || UY == 0) |
949 | return false; |
950 | |
951 | |
952 | |
953 | |
954 | if (IsNegative) |
955 | return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY; |
956 | else |
957 | return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY; |
958 | } |
959 | |
960 | } |
961 | |
962 | #endif |