Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Alignment.h
Warning:line 85, column 47
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'

Annotated Source Code

Press '?' to see keyboard shortcuts

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 static -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" -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 -stack-protector 2 -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

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/IR/DataLayout.cpp

→
1//===- DataLayout.cpp - Data size & alignment routines ---------------------==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines layout properties related to datatype size/offset/alignment
10// information.
11//
12// This structure should be created once, filled in if the defaults are not
13// correct and then passed around by const&. None of the members functions
14// require modification to the object.
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
41using namespace llvm;
42
43//===----------------------------------------------------------------------===//
44// Support for StructLayout
45//===----------------------------------------------------------------------===//
46
47StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
48 assert(!ST->isOpaque() && "Cannot get layout of opaque structs")((void)0);
49 StructSize = 0;
50 IsPadded = false;
51 NumElements = ST->getNumElements();
52
53 // Loop over each of the elements, placing them in memory.
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 // Add padding if necessary to align the data element properly.
59 if (!isAligned(TyAlign, StructSize)) {
60 IsPadded = true;
61 StructSize = alignTo(StructSize, TyAlign);
62 }
63
64 // Keep track of maximum alignment constraint.
65 StructAlignment = std::max(TyAlign, StructAlignment);
66
67 getMemberOffsets()[i] = StructSize;
68 // Consume space for this data item
69 StructSize += DL.getTypeAllocSize(Ty).getFixedValue();
70 }
71
72 // Add padding to the end of the struct so that it could be put in an array
73 // and all array elements would be aligned correctly.
74 if (!isAligned(StructAlignment, StructSize)) {
75 IsPadded = true;
76 StructSize = alignTo(StructSize, StructAlignment);
77 }
78}
79
80/// getElementContainingOffset - Given a valid offset into the structure,
81/// return the structure index that contains it.
82unsigned 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!")((void)0);
86 --SI;
87 assert(*SI <= Offset && "upper_bound didn't work")((void)0);
88 assert((SI == MemberOffsets.begin() || *(SI - 1) <= Offset) &&((void)0)
89 (SI + 1 == MemberOffsets.end() || *(SI + 1) > Offset) &&((void)0)
90 "Upper bound didn't work!")((void)0);
91
92 // Multiple fields can have the same offset if any of them are zero sized.
93 // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
94 // at the i32 element, because it is the last element at that offset. This is
95 // the right one to return, because anything after it will have a higher
96 // offset, implying that this element is non-empty.
97 return SI - MemberOffsets.begin();
98}
99
100//===----------------------------------------------------------------------===//
101// LayoutAlignElem, LayoutAlign support
102//===----------------------------------------------------------------------===//
103
104LayoutAlignElem 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!")((void)0);
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
115bool
116LayoutAlignElem::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// PointerAlignElem, PointerAlign support
125//===----------------------------------------------------------------------===//
126
127PointerAlignElem 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!")((void)0);
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
140bool
141PointerAlignElem::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// DataLayout Class Implementation
151//===----------------------------------------------------------------------===//
152
153const 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
163static const LayoutAlignElem DefaultAlignments[] = {
164 {INTEGER_ALIGN, 1, Align(1), Align(1)}, // i1
165 {INTEGER_ALIGN, 8, Align(1), Align(1)}, // i8
166 {INTEGER_ALIGN, 16, Align(2), Align(2)}, // i16
167 {INTEGER_ALIGN, 32, Align(4), Align(4)}, // i32
168 {INTEGER_ALIGN, 64, Align(4), Align(8)}, // i64
169 {FLOAT_ALIGN, 16, Align(2), Align(2)}, // half, bfloat
170 {FLOAT_ALIGN, 32, Align(4), Align(4)}, // float
171 {FLOAT_ALIGN, 64, Align(8), Align(8)}, // double
172 {FLOAT_ALIGN, 128, Align(16), Align(16)}, // ppcf128, quad, ...
173 {VECTOR_ALIGN, 64, Align(8), Align(8)}, // v2i32, v1i64, ...
174 {VECTOR_ALIGN, 128, Align(16), Align(16)}, // v16i8, v8i16, v4i32, ...
175 {AGGREGATE_ALIGN, 0, Align(1), Align(8)} // struct
176};
177
178void 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 // Default alignments
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
205Expected<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
212static Error reportError(const Twine &Message) {
213 return createStringError(inconvertibleErrorCode(), Message);
214}
215
216/// Checked version of split, to ensure mandatory subparts.
217static Error split(StringRef Str, char Separator,
218 std::pair<StringRef, StringRef> &Split) {
219 assert(!Str.empty() && "parse error, string can't be empty here")((void)0);
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/// Get an unsigned integer, including error checks.
229template <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/// Get an unsigned integer representing the number of bits and convert it into
237/// bytes. Error out of not a byte width multiple.
238template <typename IntTy>
239static 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
248static 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
256Error DataLayout::parseSpecifier(StringRef Desc) {
257 StringRepresentation = std::string(Desc);
258 while (!Desc.empty()) {
259 // Split at '-'.
260 std::pair<StringRef, StringRef> Split;
261 if (Error Err = split(Desc, '-', Split))
262 return Err;
263 Desc = Split.second;
264
265 // Split at ':'.
266 if (Error Err = split(Split.first, ':', Split))
267 return Err;
268
269 // Aliases used below.
270 StringRef &Tok = Split.first; // Current token.
271 StringRef &Rest = Split.second; // The rest of the string.
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 // Deprecated, but ignoring here to preserve loading older textual llvm
295 // ASM file
296 break;
297 case 'E':
298 BigEndian = true;
299 break;
300 case 'e':
301 BigEndian = false;
302 break;
303 case 'p': {
304 // Address space.
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 // Size.
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 // ABI alignment.
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 // Size of index used in GEP for address calculation.
337 // The parameter is optional. By default it is equal to size of pointer.
338 unsigned IndexSize = PointerMemSize;
339
340 // Preferred alignment.
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 // Now read the index. It is the second optional parameter here.
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!")__builtin_unreachable();
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 // Bit size.
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 // ABI alignment.
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 // Preferred alignment.
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': // Native integer types.
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': { // Stack natural alignment.
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': { // Function address space.
475 if (Error Err = getAddrSpace(Tok, ProgramAddrSpace))
476 return Err;
477 break;
478 }
479 case 'A': { // Default stack/alloca address space.
480 if (Error Err = getAddrSpace(Tok, AllocaAddrSpace))
481 return Err;
482 break;
483 }
484 case 'G': { // Default address space for global variables.
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
529DataLayout::DataLayout(const Module *M) {
530 init(M);
531}
532
533void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
534
535bool 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 // Note: getStringRepresentation() might differs, it is not canonicalized
547 return Ret;
548}
549
550DataLayout::AlignmentsTy::iterator
551DataLayout::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
559Error DataLayout::setAlignment(AlignTypeEnum align_type, Align abi_align,
560 Align pref_align, uint32_t bit_width) {
561 // AlignmentsTy::ABIAlign and AlignmentsTy::PrefAlign were once stored as
562 // uint16_t, it is unclear if there are requirements for alignment to be less
563 // than 2^16 other than storage. In the meantime we leave the restriction as
564 // an assert. See D67400 for context.
565 assert(Log2(abi_align) < 16 && Log2(pref_align) < 16 && "Alignment too big")((void)0);
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 // Update the abi, preferred alignments.
576 I->ABIAlign = abi_align;
577 I->PrefAlign = pref_align;
578 } else {
579 // Insert before I to keep the vector sorted.
580 Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
581 pref_align, bit_width));
582 }
583 return Error::success();
584}
585
586const PointerAlignElem &
587DataLayout::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)((void)0);
598 return Pointers[0];
599}
600
601Error 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
624Align DataLayout::getIntegerAlignment(uint32_t BitWidth,
625 bool abi_or_pref) const {
626 auto I = findAlignmentLowerBound(INTEGER_ALIGN, BitWidth);
627 // If we don't have an exact match, use alignment of next larger integer
628 // type. If there is none, use alignment of largest integer type by going
629 // back one element.
630 if (I == Alignments.end() || I->AlignType != INTEGER_ALIGN)
631 --I;
632 assert(I->AlignType == INTEGER_ALIGN && "Must be integer alignment")((void)0);
633 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
634}
635
636namespace {
637
638class StructLayoutMap {
639 using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
640 LayoutInfoTy LayoutInfo;
641
642public:
643 ~StructLayoutMap() {
644 // Remove any layouts.
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} // end anonymous namespace
658
659void DataLayout::clear() {
660 LegalIntWidths.clear();
661 Alignments.clear();
662 Pointers.clear();
663 delete static_cast<StructLayoutMap *>(LayoutMap);
664 LayoutMap = nullptr;
665}
666
667DataLayout::~DataLayout() {
668 clear();
669}
670
671const 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 // Otherwise, create the struct layout. Because it is variable length, we
680 // malloc it, then use placement new.
681 StructLayout *L = (StructLayout *)safe_malloc(
682 StructLayout::totalSizeToAlloc<uint64_t>(Ty->getNumElements()));
683
684 // Set SL before calling StructLayout's ctor. The ctor could cause other
685 // entries to be added to TheMap, invalidating our reference.
686 SL = L;
687
688 new (L) StructLayout(Ty, *this);
689
690 return L;
691}
692
693Align DataLayout::getPointerABIAlignment(unsigned AS) const {
694 return getPointerAlignElem(AS).ABIAlign;
695}
696
697Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
698 return getPointerAlignElem(AS).PrefAlign;
699}
700
701unsigned DataLayout::getPointerSize(unsigned AS) const {
702 return getPointerAlignElem(AS).TypeByteWidth;
703}
704
705unsigned 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
713unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
714 assert(Ty->isPtrOrPtrVectorTy() &&((void)0)
715 "This should only be called with a pointer or pointer vector type")((void)0);
716 Ty = Ty->getScalarType();
717 return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
718}
719
720unsigned DataLayout::getIndexSize(unsigned AS) const {
721 return getPointerAlignElem(AS).IndexWidth;
722}
723
724unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
725 assert(Ty->isPtrOrPtrVectorTy() &&((void)0)
726 "This should only be called with a pointer or pointer vector type")((void)0);
727 Ty = Ty->getScalarType();
728 return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
729}
730
731/*!
732 \param abi_or_pref Flag that determines which alignment is returned. true
733 returns the ABI alignment, false returns the preferred alignment.
734 \param Ty The underlying type for which alignment is determined.
735
736 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
737 == false) for the requested type \a Ty.
738 */
739Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
740 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!")((void)0);
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 // Early escape for the non-numeric types.
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 // Packed structure types always have an ABI alignment of one.
755 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
756 return Align(1);
757
758 // Get the layout annotation... which is lazily created on demand.
759 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
760 const LayoutAlignElem &AggregateAlign = Alignments[0];
761 assert(AggregateAlign.AlignType == AGGREGATE_ALIGN &&((void)0)
762 "Aggregate alignment must be first alignment entry")((void)0);
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 // PPC_FP128TyID and FP128TyID have different data contents, but the
774 // same size and alignment, so they look the same here.
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 // If we still couldn't find a reasonable default alignment, fall back
785 // to a simple heuristic that the alignment is the first power of two
786 // greater-or-equal to the store size of the type. This is a reasonable
787 // approximation of reality, and if the user wanted something less
788 // less conservative, they should have specified it explicitly in the data
789 // layout.
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 // By default, use natural alignment for vector types. This is consistent
802 // with what clang and llvm-gcc do.
803 // TODO: This should probably not be using the alloc size.
804 unsigned Alignment =
805 getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
7
←
'Ty' is a 'VectorType'
→
8
←
Calling 'DataLayout::getTypeAllocSize'
→
806 // We're only calculating a natural alignment, so it doesn't have to be
807 // based on the full size for scalable vectors. Using the minimum element
808 // count should be enough here.
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!!!")__builtin_unreachable();
817 }
818}
819
820/// TODO: Remove this function once the transition to Align is over.
821unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
822 return getABITypeAlign(Ty).value();
10
←
Calling 'DataLayout::getABITypeAlign'
→
21
←
Returning from 'DataLayout::getABITypeAlign'
→
22
←
Calling 'Align::value'
→
823}
824
825Align DataLayout::getABITypeAlign(Type *Ty) const {
826 return getAlignment(Ty, true);
11
←
Calling 'DataLayout::getAlignment'
→
20
←
Returning from 'DataLayout::getAlignment'
→
827}
828
829/// TODO: Remove this function once the transition to Align is over.
830unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
831 return getPrefTypeAlign(Ty).value();
832}
833
834Align DataLayout::getPrefTypeAlign(Type *Ty) const {
835 return getAlignment(Ty, false);
4
←
Calling 'DataLayout::getAlignment'
→
836}
837
838IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
839 unsigned AddressSpace) const {
840 return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
841}
842
843Type *DataLayout::getIntPtrType(Type *Ty) const {
844 assert(Ty->isPtrOrPtrVectorTy() &&((void)0)
845 "Expected a pointer or pointer vector type.")((void)0);
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
853Type *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
860unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
861 auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
862 return Max != LegalIntWidths.end() ? *Max : 0;
863}
864
865Type *DataLayout::getIndexType(Type *Ty) const {
866 assert(Ty->isPtrOrPtrVectorTy() &&((void)0)
867 "Expected a pointer or pointer vector type.")((void)0);
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
875int64_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")((void)0);
886 unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
887
888 // Get structure layout information...
889 const StructLayout *Layout = getStructLayout(STy);
890
891 // Add in the offset, as calculated by the structure layout info...
892 Result += Layout->getElementOffset(FieldNo);
893 } else {
894 // Get the array index and the size of each array element.
895 if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
896 Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
897 }
898 }
899
900 return Result;
901}
902
903/// getPreferredAlign - Return the preferred alignment of the specified global.
904/// This includes an explicitly requested alignment (if the global has one).
905Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {
906 MaybeAlign GVAlignment = GV->getAlign();
907 // If a section is specified, always precisely honor explicit alignment,
908 // so we don't insert padding into a section we don't control.
909 if (GVAlignment && GV->hasSection())
1
Assuming the condition is false
→
2
←
Taking false branch
→
910 return *GVAlignment;
911
912 // If no explicit alignment is specified, compute the alignment based on
913 // the IR type. If an alignment is specified, increase it to match the ABI
914 // alignment of the IR type.
915 //
916 // FIXME: Not sure it makes sense to use the alignment of the type if
917 // there's already an explicit alignment specification.
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 // If no explicit alignment is specified, and the global is large, increase
928 // the alignment to 16.
929 // FIXME: Why 16, specifically?
930 if (GV->hasInitializer() && !GVAlignment) {
931 if (Alignment < Align(16)) {
932 // If the global is not external, see if it is large. If so, give it a
933 // larger alignment.
934 if (getTypeSizeInBits(ElemType) > 128)
935 Alignment = Align(16); // 16-byte alignment.
936 }
937 }
938 return Alignment;
939}
←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR/DataLayout.h

→
1//===- llvm/DataLayout.h - Data size & alignment info -----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines layout properties related to datatype size/offset/alignment
10// information. It uses lazy annotations to cache information about how
11// structure types are laid out and used.
12//
13// This structure should be created once, filled in if the defaults are not
14// correct and then passed around by const&. None of the members functions
15// require modification to the object.
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// This needs to be outside of the namespace, to avoid conflict with llvm-c
39// decl.
40using LLVMTargetDataRef = struct LLVMOpaqueTargetData *;
41
42namespace llvm {
43
44class GlobalVariable;
45class LLVMContext;
46class Module;
47class StructLayout;
48class Triple;
49class Value;
50
51/// Enum used to categorize the alignment types stored by LayoutAlignElem
52enum AlignTypeEnum {
53 INVALID_ALIGN = 0,
54 INTEGER_ALIGN = 'i',
55 VECTOR_ALIGN = 'v',
56 FLOAT_ALIGN = 'f',
57 AGGREGATE_ALIGN = 'a'
58};
59
60// FIXME: Currently the DataLayout string carries a "preferred alignment"
61// for types. As the DataLayout is module/global, this should likely be
62// sunk down to an FTTI element that is queried rather than a global
63// preference.
64
65/// Layout alignment element.
66///
67/// Stores the alignment data associated with a given alignment type (integer,
68/// vector, float) and type bit width.
69///
70/// \note The unusual order of elements in the structure attempts to reduce
71/// padding and make the structure slightly more cache friendly.
72struct LayoutAlignElem {
73 /// Alignment type from \c AlignTypeEnum
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/// Layout pointer alignment element.
86///
87/// Stores the alignment data associated with a given pointer and address space.
88///
89/// \note The unusual order of elements in the structure attempts to reduce
90/// padding and make the structure slightly more cache friendly.
91struct PointerAlignElem {
92 Align ABIAlign;
93 Align PrefAlign;
94 uint32_t TypeByteWidth;
95 uint32_t AddressSpace;
96 uint32_t IndexWidth;
97
98 /// Initializer
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/// A parsed version of the target data layout string in and methods for
107/// querying it.
108///
109/// The target data layout string is specified *by the target* - a frontend
110/// generating LLVM IR is required to generate the right target data for the
111/// target being codegen'd to.
112class DataLayout {
113public:
114 enum class FunctionPtrAlignType {
115 /// The function pointer alignment is independent of the function alignment.
116 Independent,
117 /// The function pointer alignment is a multiple of the function alignment.
118 MultipleOfFunctionAlign,
119 };
120private:
121 /// Defaults to false.
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 /// Primitive type alignment data. This is sorted by type and bit
146 /// width during construction.
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 /// The string representation used to create this DataLayout
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 // The StructType -> StructLayout map.
168 mutable void *LayoutMap = nullptr;
169
170 /// Pointers in these address spaces are non-integral, and don't have a
171 /// well-defined bitwise representation.
172 SmallVector<unsigned, 8> NonIntegralAddressSpaces;
173
174 /// Attempts to set the alignment of the given type. Returns an error
175 /// description on failure.
176 Error setAlignment(AlignTypeEnum align_type, Align abi_align,
177 Align pref_align, uint32_t bit_width);
178
179 /// Attempts to set the alignment of a pointer in the given address space.
180 /// Returns an error description on failure.
181 Error setPointerAlignment(uint32_t AddrSpace, Align ABIAlign, Align PrefAlign,
182 uint32_t TypeByteWidth, uint32_t IndexWidth);
183
184 /// Internal helper to get alignment for integer of given bitwidth.
185 Align getIntegerAlignment(uint32_t BitWidth, bool abi_or_pref) const;
186
187 /// Internal helper method that returns requested alignment for type.
188 Align getAlignment(Type *Ty, bool abi_or_pref) const;
189
190 /// Attempts to parse a target data specification string and reports an error
191 /// if the string is malformed.
192 Error parseSpecifier(StringRef Desc);
193
194 // Free all internal data structures.
195 void clear();
196
197public:
198 /// Constructs a DataLayout from a specification string. See reset().
199 explicit DataLayout(StringRef LayoutDescription) {
200 reset(LayoutDescription);
201 }
202
203 /// Initialize target data from properties stored in the module.
204 explicit DataLayout(const Module *M);
205
206 DataLayout(const DataLayout &DL) { *this = DL; }
207
208 ~DataLayout(); // Not virtual, do not subclass this class
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 /// Parse a data layout string (with fallback to default values).
234 void reset(StringRef LayoutDescription);
235
236 /// Parse a data layout string and return the layout. Return an error
237 /// description on failure.
238 static Expected<DataLayout> parse(StringRef LayoutDescription);
239
240 /// Layout endianness...
241 bool isLittleEndian() const { return !BigEndian; }
242 bool isBigEndian() const { return BigEndian; }
243
244 /// Returns the string representation of the DataLayout.
245 ///
246 /// This representation is in the same format accepted by the string
247 /// constructor above. This should not be used to compare two DataLayout as
248 /// different string can represent the same layout.
249 const std::string &getStringRepresentation() const {
250 return StringRepresentation;
251 }
252
253 /// Test if the DataLayout was constructed from an empty string.
254 bool isDefault() const { return StringRepresentation.empty(); }
255
256 /// Returns true if the specified type is known to be a native integer
257 /// type supported by the CPU.
258 ///
259 /// For example, i64 is not native on most 32-bit CPUs and i37 is not native
260 /// on any known one. This returns false if the integer width is not legal.
261 ///
262 /// The width is specified in bits.
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 /// Returns true if the given alignment exceeds the natural stack alignment.
270 bool exceedsNaturalStackAlignment(Align Alignment) const {
271 return StackNaturalAlign && (Alignment > *StackNaturalAlign);
272 }
273
274 Align getStackAlignment() const {
275 assert(StackNaturalAlign && "StackNaturalAlign must be defined")((void)0);
276 return *StackNaturalAlign;
277 }
278
279 unsigned getAllocaAddrSpace() const { return AllocaAddrSpace; }
280
281 /// Returns the alignment of function pointers, which may or may not be
282 /// related to the alignment of functions.
283 /// \see getFunctionPtrAlignType
284 MaybeAlign getFunctionPtrAlign() const { return FunctionPtrAlign; }
285
286 /// Return the type of function pointer alignment.
287 /// \see getFunctionPtrAlign
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 /// Returns true if symbols with leading question marks should not receive IR
302 /// mangling. True for Windows mangling modes.
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")__builtin_unreachable();
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")__builtin_unreachable();
346 }
347
348 static const char *getManglingComponent(const Triple &T);
349
350 /// Returns true if the specified type fits in a native integer type
351 /// supported by the CPU.
352 ///
353 /// For example, if the CPU only supports i32 as a native integer type, then
354 /// i27 fits in a legal integer type but i45 does not.
355 bool fitsInLegalInteger(unsigned Width) const {
356 for (unsigned LegalIntWidth : LegalIntWidths)
357 if (Width <= LegalIntWidth)
358 return true;
359 return false;
360 }
361
362 /// Layout pointer alignment
363 Align getPointerABIAlignment(unsigned AS) const;
364
365 /// Return target's alignment for stack-based pointers
366 /// FIXME: The defaults need to be removed once all of
367 /// the backends/clients are updated.
368 Align getPointerPrefAlignment(unsigned AS = 0) const;
369
370 /// Layout pointer size
371 /// FIXME: The defaults need to be removed once all of
372 /// the backends/clients are updated.
373 unsigned getPointerSize(unsigned AS = 0) const;
374
375 /// Returns the maximum pointer size over all address spaces.
376 unsigned getMaxPointerSize() const;
377
378 // Index size used for address calculation.
379 unsigned getIndexSize(unsigned AS) const;
380
381 /// Return the address spaces containing non-integral pointers. Pointers in
382 /// this address space don't have a well-defined bitwise representation.
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 /// Layout pointer size, in bits
402 /// FIXME: The defaults need to be removed once all of
403 /// the backends/clients are updated.
404 unsigned getPointerSizeInBits(unsigned AS = 0) const {
405 return getPointerSize(AS) * 8;
406 }
407
408 /// Returns the maximum pointer size over all address spaces.
409 unsigned getMaxPointerSizeInBits() const {
410 return getMaxPointerSize() * 8;
411 }
412
413 /// Size in bits of index used for address calculation in getelementptr.
414 unsigned getIndexSizeInBits(unsigned AS) const {
415 return getIndexSize(AS) * 8;
416 }
417
418 /// Layout pointer size, in bits, based on the type. If this function is
419 /// called with a pointer type, then the type size of the pointer is returned.
420 /// If this function is called with a vector of pointers, then the type size
421 /// of the pointer is returned. This should only be called with a pointer or
422 /// vector of pointers.
423 unsigned getPointerTypeSizeInBits(Type *) const;
424
425 /// Layout size of the index used in GEP calculation.
426 /// The function should be called with pointer or vector of pointers type.
427 unsigned getIndexTypeSizeInBits(Type *Ty) const;
428
429 unsigned getPointerTypeSize(Type *Ty) const {
430 return getPointerTypeSizeInBits(Ty) / 8;
431 }
432
433 /// Size examples:
434 ///
435 /// Type SizeInBits StoreSizeInBits AllocSizeInBits[*]
436 /// ---- ---------- --------------- ---------------
437 /// i1 1 8 8
438 /// i8 8 8 8
439 /// i19 19 24 32
440 /// i32 32 32 32
441 /// i100 100 104 128
442 /// i128 128 128 128
443 /// Float 32 32 32
444 /// Double 64 64 64
445 /// X86_FP80 80 80 96
446 ///
447 /// [*] The alloc size depends on the alignment, and thus on the target.
448 /// These values are for x86-32 linux.
449
450 /// Returns the number of bits necessary to hold the specified type.
451 ///
452 /// If Ty is a scalable vector type, the scalable property will be set and
453 /// the runtime size will be a positive integer multiple of the base size.
454 ///
455 /// For example, returns 36 for i36 and 80 for x86_fp80. The type passed must
456 /// have a size (Type::isSized() must return true).
457 TypeSize getTypeSizeInBits(Type *Ty) const;
458
459 /// Returns the maximum number of bytes that may be overwritten by
460 /// storing the specified type.
461 ///
462 /// If Ty is a scalable vector type, the scalable property will be set and
463 /// the runtime size will be a positive integer multiple of the base size.
464 ///
465 /// For example, returns 5 for i36 and 10 for x86_fp80.
466 TypeSize getTypeStoreSize(Type *Ty) const {
467 TypeSize BaseSize = getTypeSizeInBits(Ty);
468 return { (BaseSize.getKnownMinSize() + 7) / 8, BaseSize.isScalable() };
469 }
470
471 /// Returns the maximum number of bits that may be overwritten by
472 /// storing the specified type; always a multiple of 8.
473 ///
474 /// If Ty is a scalable vector type, the scalable property will be set and
475 /// the runtime size will be a positive integer multiple of the base size.
476 ///
477 /// For example, returns 40 for i36 and 80 for x86_fp80.
478 TypeSize getTypeStoreSizeInBits(Type *Ty) const {
479 return 8 * getTypeStoreSize(Ty);
480 }
481
482 /// Returns true if no extra padding bits are needed when storing the
483 /// specified type.
484 ///
485 /// For example, returns false for i19 that has a 24-bit store size.
486 bool typeSizeEqualsStoreSize(Type *Ty) const {
487 return getTypeSizeInBits(Ty) == getTypeStoreSizeInBits(Ty);
488 }
489
490 /// Returns the offset in bytes between successive objects of the
491 /// specified type, including alignment padding.
492 ///
493 /// If Ty is a scalable vector type, the scalable property will be set and
494 /// the runtime size will be a positive integer multiple of the base size.
495 ///
496 /// This is the amount that alloca reserves for this type. For example,
497 /// returns 12 or 16 for x86_fp80, depending on alignment.
498 TypeSize getTypeAllocSize(Type *Ty) const {
499 // Round up to the next alignment boundary.
500 return alignTo(getTypeStoreSize(Ty), getABITypeAlignment(Ty));
9
←
Calling 'DataLayout::getABITypeAlignment'
→
501 }
502
503 /// Returns the offset in bits between successive objects of the
504 /// specified type, including alignment padding; always a multiple of 8.
505 ///
506 /// If Ty is a scalable vector type, the scalable property will be set and
507 /// the runtime size will be a positive integer multiple of the base size.
508 ///
509 /// This is the amount that alloca reserves for this type. For example,
510 /// returns 96 or 128 for x86_fp80, depending on alignment.
511 TypeSize getTypeAllocSizeInBits(Type *Ty) const {
512 return 8 * getTypeAllocSize(Ty);
513 }
514
515 /// Returns the minimum ABI-required alignment for the specified type.
516 /// FIXME: Deprecate this function once migration to Align is over.
517 unsigned getABITypeAlignment(Type *Ty) const;
518
519 /// Returns the minimum ABI-required alignment for the specified type.
520 Align getABITypeAlign(Type *Ty) const;
521
522 /// Helper function to return `Alignment` if it's set or the result of
523 /// `getABITypeAlignment(Ty)`, in any case the result is a valid alignment.
524 inline Align getValueOrABITypeAlignment(MaybeAlign Alignment,
525 Type *Ty) const {
526 return Alignment ? *Alignment : getABITypeAlign(Ty);
527 }
528
529 /// Returns the minimum ABI-required alignment for an integer type of
530 /// the specified bitwidth.
531 Align getABIIntegerTypeAlignment(unsigned BitWidth) const {
532 return getIntegerAlignment(BitWidth, /* abi_or_pref */ true);
533 }
534
535 /// Returns the preferred stack/global alignment for the specified
536 /// type.
537 ///
538 /// This is always at least as good as the ABI alignment.
539 /// FIXME: Deprecate this function once migration to Align is over.
540 unsigned getPrefTypeAlignment(Type *Ty) const;
541
542 /// Returns the preferred stack/global alignment for the specified
543 /// type.
544 ///
545 /// This is always at least as good as the ABI alignment.
546 Align getPrefTypeAlign(Type *Ty) const;
547
548 /// Returns an integer type with size at least as big as that of a
549 /// pointer in the given address space.
550 IntegerType *getIntPtrType(LLVMContext &C, unsigned AddressSpace = 0) const;
551
552 /// Returns an integer (vector of integer) type with size at least as
553 /// big as that of a pointer of the given pointer (vector of pointer) type.
554 Type *getIntPtrType(Type *) const;
555
556 /// Returns the smallest integer type with size at least as big as
557 /// Width bits.
558 Type *getSmallestLegalIntType(LLVMContext &C, unsigned Width = 0) const;
559
560 /// Returns the largest legal integer type, or null if none are set.
561 Type *getLargestLegalIntType(LLVMContext &C) const {
562 unsigned LargestSize = getLargestLegalIntTypeSizeInBits();
563 return (LargestSize == 0) ? nullptr : Type::getIntNTy(C, LargestSize);
564 }
565
566 /// Returns the size of largest legal integer type size, or 0 if none
567 /// are set.
568 unsigned getLargestLegalIntTypeSizeInBits() const;
569
570 /// Returns the type of a GEP index.
571 /// If it was not specified explicitly, it will be the integer type of the
572 /// pointer width - IntPtrType.
573 Type *getIndexType(Type *PtrTy) const;
574
575 /// Returns the offset from the beginning of the type for the specified
576 /// indices.
577 ///
578 /// Note that this takes the element type, not the pointer type.
579 /// This is used to implement getelementptr.
580 int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef<Value *> Indices) const;
581
582 /// Returns a StructLayout object, indicating the alignment of the
583 /// struct, its size, and the offsets of its fields.
584 ///
585 /// Note that this information is lazily cached.
586 const StructLayout *getStructLayout(StructType *Ty) const;
587
588 /// Returns the preferred alignment of the specified global.
589 ///
590 /// This includes an explicitly requested alignment (if the global has one).
591 Align getPreferredAlign(const GlobalVariable *GV) const;
592};
593
594inline DataLayout *unwrap(LLVMTargetDataRef P) {
595 return reinterpret_cast<DataLayout *>(P);
596}
597
598inline LLVMTargetDataRef wrap(const DataLayout *P) {
599 return reinterpret_cast<LLVMTargetDataRef>(const_cast<DataLayout *>(P));
600}
601
602/// Used to lazily calculate structure layout information for a target machine,
603/// based on the DataLayout structure.
604class StructLayout final : public TrailingObjects<StructLayout, uint64_t> {
605 uint64_t StructSize;
606 Align StructAlignment;
607 unsigned IsPadded : 1;
608 unsigned NumElements : 31;
609
610public:
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 /// Returns whether the struct has padding or not between its fields.
618 /// NB: Padding in nested element is not taken into account.
619 bool hasPadding() const { return IsPadded; }
620
621 /// Given a valid byte offset into the structure, returns the structure
622 /// index that contains it.
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!")((void)0);
636 return getMemberOffsets()[Idx];
637 }
638
639 uint64_t getElementOffsetInBits(unsigned Idx) const {
640 return getElementOffset(Idx) * 8;
641 }
642
643private:
644 friend class DataLayout; // Only DataLayout can create this class
645
646 StructLayout(StructType *ST, const DataLayout &DL);
647
648 size_t numTrailingObjects(OverloadToken<uint64_t>) const {
649 return NumElements;
650 }
651};
652
653// The implementation of this method is provided inline as it is particularly
654// well suited to constant folding when called on a specific Type subclass.
655inline TypeSize DataLayout::getTypeSizeInBits(Type *Ty) const {
656 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!")((void)0);
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 // Get the layout annotation... which is lazily created on demand.
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 // In memory objects this is always aligned to a higher boundary, but
687 // only 80 bits contain information.
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")__builtin_unreachable();
700 }
701}
702
703} // end namespace llvm
704
705#endif // LLVM_IR_DATALAYOUT_H
←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Alignment.h

→
1//===-- llvm/Support/Alignment.h - Useful alignment functions ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains types to represent alignments.
10// They are instrumented to guarantee some invariants are preserved and prevent
11// invalid manipulations.
12//
13// - Align represents an alignment in bytes, it is always set and always a valid
14// power of two, its minimum value is 1 which means no alignment requirements.
15//
16// - MaybeAlign is an optional type, it may be undefined or set. When it's set
17// you can get the underlying Align type by using the getValue() method.
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 NDEBUG1
28#include <string>
29#endif // NDEBUG
30
31namespace llvm {
32
33#define ALIGN_CHECK_ISPOSITIVE(decl) \
34 assert(decl > 0 && (#decl " should be defined"))((void)0)
35
36/// This struct is a compact representation of a valid (non-zero power of two)
37/// alignment.
38/// It is suitable for use as static global constants.
39struct Align {
40private:
41 uint8_t ShiftValue = 0; /// The log2 of the required alignment.
42 /// ShiftValue is less than 64 by construction.
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 /// A trivial type to allow construction of constexpr Align.
56 /// This is currently needed to workaround a bug in GCC 5.3 which prevents
57 /// definition of constexpr assign operators.
58 /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic
59 /// FIXME: Remove this, make all assign operators constexpr and introduce user
60 /// defined literals when we don't have to support GCC 5.3 anymore.
61 /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain
62 struct LogValue {
63 uint8_t Log;
64 };
65
66public:
67 /// Default is byte-aligned.
68 constexpr Align() = default;
69 /// Do not perform checks in case of copy/move construct/assign, because the
70 /// checks have been performed when building `Other`.
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")((void)0);
78 assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2")((void)0);
79 ShiftValue = Log2_64(Value);
15
←
Calling 'Log2_64'
→
17
←
Returning from 'Log2_64'
→
18
←
The value 255 is assigned to field 'ShiftValue'
→
80 assert(ShiftValue < 64 && "Broken invariant")((void)0);
81 }
82
83 /// This is a hole in the type system and should not be abused.
84 /// Needed to interact with C for instance.
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 /// Allow constructions of constexpr Align.
88 template <size_t kValue> constexpr static LogValue Constant() {
89 return LogValue{static_cast<uint8_t>(CTLog2<kValue>())};
90 }
91
92 /// Allow constructions of constexpr Align from types.
93 /// Compile time equivalent to Align(alignof(T)).
94 template <typename T> constexpr static LogValue Of() {
95 return Constant<std::alignment_of<T>::value>();
96 }
97
98 /// Constexpr constructor from LogValue type.
99 constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
100};
101
102/// Treats the value 0 as a 1, so Align is always at least 1.
103inline Align assumeAligned(uint64_t Value) {
104 return Value ? Align(Value) : Align();
105}
106
107/// This struct is a compact representation of a valid (power of two) or
108/// undefined (0) alignment.
109struct MaybeAlign : public llvm::Optional<Align> {
110private:
111 using UP = llvm::Optional<Align>;
112
113public:
114 /// Default is undefined.
115 MaybeAlign() = default;
116 /// Do not perform checks in case of copy/move construct/assign, because the
117 /// checks have been performed when building `Other`.
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 /// Use llvm::Optional<Align> constructor.
124 using UP::UP;
125
126 explicit MaybeAlign(uint64_t Value) {
127 assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&((void)0)
128 "Alignment is neither 0 nor a power of 2")((void)0);
129 if (Value)
130 emplace(Value);
131 }
132
133 /// For convenience, returns a valid alignment or 1 if undefined.
134 Align valueOrOne() const { return hasValue() ? getValue() : Align(); }
135};
136
137/// Checks that SizeInBytes is a multiple of the alignment.
138inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
139 return SizeInBytes % Lhs.value() == 0;
140}
141
142/// Checks that Addr is a multiple of the alignment.
143inline bool isAddrAligned(Align Lhs, const void *Addr) {
144 return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
145}
146
147/// Returns a multiple of A needed to store `Size` bytes.
148inline uint64_t alignTo(uint64_t Size, Align A) {
149 const uint64_t Value = A.value();
150 // The following line is equivalent to `(Size + Value - 1) / Value * Value`.
151
152 // The division followed by a multiplication can be thought of as a right
153 // shift followed by a left shift which zeros out the extra bits produced in
154 // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out
155 // are just zero.
156
157 // Most compilers can generate this code but the pattern may be missed when
158 // multiple functions gets inlined.
159 return (Size + Value - 1) & ~(Value - 1U);
160}
161
162/// If non-zero \p Skew is specified, the return value will be a minimal integer
163/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
164/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
165/// Skew mod \p A'.
166///
167/// Examples:
168/// \code
169/// alignTo(5, Align(8), 7) = 7
170/// alignTo(17, Align(8), 1) = 17
171/// alignTo(~0LL, Align(8), 3) = 3
172/// \endcode
173inline 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/// Returns a multiple of A needed to store `Size` bytes.
180/// Returns `Size` if current alignment is undefined.
181inline uint64_t alignTo(uint64_t Size, MaybeAlign A) {
182 return A ? alignTo(Size, A.getValue()) : Size;
183}
184
185/// Aligns `Addr` to `Alignment` bytes, rounding up.
186inline 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) >=((void)0)
189 ArithAddr &&((void)0)
190 "Overflow")((void)0);
191 return alignTo(ArithAddr, Alignment);
192}
193
194/// Returns the offset to the next integer (mod 2**64) that is greater than
195/// or equal to \p Value and is a multiple of \p Align.
196inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
197 return alignTo(Value, Alignment) - Value;
198}
199
200/// Returns the necessary adjustment for aligning `Addr` to `Alignment`
201/// bytes, rounding up.
202inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
203 return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
204}
205
206/// Returns the log2 of the alignment.
207inline unsigned Log2(Align A) { return A.ShiftValue; }
208
209/// Returns the alignment that satisfies both alignments.
210/// Same semantic as MinAlign.
211inline Align commonAlignment(Align A, Align B) { return std::min(A, B); }
212
213/// Returns the alignment that satisfies both alignments.
214/// Same semantic as MinAlign.
215inline Align commonAlignment(Align A, uint64_t Offset) {
216 return Align(MinAlign(A.value(), Offset));
217}
218
219/// Returns the alignment that satisfies both alignments.
220/// Same semantic as MinAlign.
221inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) {
222 return A && B ? commonAlignment(*A, *B) : A ? A : B;
223}
224
225/// Returns the alignment that satisfies both alignments.
226/// Same semantic as MinAlign.
227inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) {
228 return MaybeAlign(MinAlign((*A).value(), Offset));
229}
230
231/// Returns a representation of the alignment that encodes undefined as 0.
232inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
233
234/// Dual operation of the encode function above.
235inline 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/// Returns a representation of the alignment, the encoded value is positive by
244/// definition.
245inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
246
247/// Comparisons between Align and scalars. Rhs must be positive.
248inline bool operator==(Align Lhs, uint64_t Rhs) {
249 ALIGN_CHECK_ISPOSITIVE(Rhs);
250 return Lhs.value() == Rhs;
251}
252inline bool operator!=(Align Lhs, uint64_t Rhs) {
253 ALIGN_CHECK_ISPOSITIVE(Rhs);
254 return Lhs.value() != Rhs;
255}
256inline bool operator<=(Align Lhs, uint64_t Rhs) {
257 ALIGN_CHECK_ISPOSITIVE(Rhs);
258 return Lhs.value() <= Rhs;
259}
260inline bool operator>=(Align Lhs, uint64_t Rhs) {
261 ALIGN_CHECK_ISPOSITIVE(Rhs);
262 return Lhs.value() >= Rhs;
263}
264inline bool operator<(Align Lhs, uint64_t Rhs) {
265 ALIGN_CHECK_ISPOSITIVE(Rhs);
266 return Lhs.value() < Rhs;
267}
268inline bool operator>(Align Lhs, uint64_t Rhs) {
269 ALIGN_CHECK_ISPOSITIVE(Rhs);
270 return Lhs.value() > Rhs;
271}
272
273/// Comparisons between MaybeAlign and scalars.
274inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
275 return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
276}
277inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
278 return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
279}
280
281/// Comparisons operators between Align.
282inline bool operator==(Align Lhs, Align Rhs) {
283 return Lhs.ShiftValue == Rhs.ShiftValue;
284}
285inline bool operator!=(Align Lhs, Align Rhs) {
286 return Lhs.ShiftValue != Rhs.ShiftValue;
287}
288inline bool operator<=(Align Lhs, Align Rhs) {
289 return Lhs.ShiftValue <= Rhs.ShiftValue;
290}
291inline bool operator>=(Align Lhs, Align Rhs) {
292 return Lhs.ShiftValue >= Rhs.ShiftValue;
293}
294inline bool operator<(Align Lhs, Align Rhs) {
295 return Lhs.ShiftValue < Rhs.ShiftValue;
296}
297inline bool operator>(Align Lhs, Align Rhs) {
298 return Lhs.ShiftValue > Rhs.ShiftValue;
299}
300
301// Don't allow relational comparisons with MaybeAlign.
302bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
303bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
304bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
305bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
306
307bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
308bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
309bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
310bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
311
312bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
313bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
314bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
315bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
316
317inline Align operator*(Align Lhs, uint64_t Rhs) {
318 assert(Rhs > 0 && "Rhs must be positive")((void)0);
319 return Align(Lhs.value() * Rhs);
320}
321
322inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) {
323 assert(Rhs > 0 && "Rhs must be positive")((void)0);
324 return Lhs ? Lhs.getValue() * Rhs : MaybeAlign();
325}
326
327inline Align operator/(Align Lhs, uint64_t Divisor) {
328 assert(llvm::isPowerOf2_64(Divisor) &&((void)0)
329 "Divisor must be positive and a power of 2")((void)0);
330 assert(Lhs != 1 && "Can't halve byte alignment")((void)0);
331 return Align(Lhs.value() / Divisor);
332}
333
334inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) {
335 assert(llvm::isPowerOf2_64(Divisor) &&((void)0)
336 "Divisor must be positive and a power of 2")((void)0);
337 return Lhs ? Lhs.getValue() / Divisor : MaybeAlign();
338}
339
340inline Align max(MaybeAlign Lhs, Align Rhs) {
341 return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
342}
343
344inline Align max(Align Lhs, MaybeAlign Rhs) {
345 return Rhs && *Rhs > Lhs ? *Rhs : Lhs;
346}
347
348#ifndef NDEBUG1
349// For usage in LLVM_DEBUG macros.
350inline std::string DebugStr(const Align &A) {
351 return std::to_string(A.value());
352}
353// For usage in LLVM_DEBUG macros.
354inline 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} // namespace llvm
364
365#endif // LLVM_SUPPORT_ALIGNMENT_H_
←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some functions that are useful for math stuff.
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// Declare these intrinsics manually rather including intrin.h. It's very
31// expensive, and MathExtras.h is popular.
32// #include <intrin.h>
33extern "C" {
34unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
35unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
36unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
37unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
38}
39#endif
40
41namespace llvm {
42
43/// The behavior an operation has on an input of 0.
44enum ZeroBehavior {
45 /// The returned value is undefined.
46 ZB_Undefined,
47 /// The returned value is numeric_limits<T>::max()
48 ZB_Max,
49 /// The returned value is numeric_limits<T>::digits
50 ZB_Width
51};
52
53/// Mathematical constants.
54namespace numbers {
55// TODO: Track C++20 std::numbers.
56// TODO: Favor using the hexadecimal FP constants (requires C++17).
57constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
58 egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
59 ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
60 ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
61 log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0)
62 log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
63 pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
64 inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
65 sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
66 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
67 sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
68 inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
69 sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
70 inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1)
71 phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
72constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
73 egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
74 ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
75 ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
76 log2ef = 1.44269504F, // (0x1.715476P+0)
77 log10ef = .434294482F, // (0x1.bcb7b2P-2)
78 pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
79 inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
80 sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
81 inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
82 sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
83 inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1)
84 sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
85 inv_sqrt3f = .577350269F, // (0x1.279a74P-1)
86 phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
87} // namespace numbers
88
89namespace detail {
90template <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 // Bisection method.
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__4) || defined(_MSC_VER)
114template <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)1 || defined(__GNUC__4)
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)
130template <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)1 || defined(__GNUC__4)
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} // namespace detail
147
148/// Count number of 0's from the least significant bit to the most
149/// stopping at the first 1.
150///
151/// Only unsigned integral types are allowed.
152///
153/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
154/// valid arguments.
155template <typename T>
156unsigned 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
163namespace detail {
164template <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 // Bisection method.
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__4) || defined(_MSC_VER)
183template <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)1 || defined(__GNUC__4)
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)
199template <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)1 || defined(__GNUC__4)
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} // namespace detail
216
217/// Count number of 0's from the most significant bit to the least
218/// stopping at the first 1.
219///
220/// Only unsigned integral types are allowed.
221///
222/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
223/// valid arguments.
224template <typename T>
225unsigned 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/// Get the index of the first set bit starting from the least
233/// significant bit.
234///
235/// Only unsigned integral types are allowed.
236///
237/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
238/// valid arguments.
239template <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/// Create a bitmask with the N right-most bits set to 1, and all other
247/// bits set to 0. Only unsigned types are allowed.
248template <typename T> T maskTrailingOnes(unsigned N) {
249 static_assert(std::is_unsigned<T>::value, "Invalid type!");
250 const unsigned Bits = CHAR_BIT8 * sizeof(T);
251 assert(N <= Bits && "Invalid bit index")((void)0);
252 return N == 0 ? 0 : (T(-1) >> (Bits - N));
253}
254
255/// Create a bitmask with the N left-most bits set to 1, and all other
256/// bits set to 0. Only unsigned types are allowed.
257template <typename T> T maskLeadingOnes(unsigned N) {
258 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
259}
260
261/// Create a bitmask with the N right-most bits set to 0, and all other
262/// bits set to 1. Only unsigned types are allowed.
263template <typename T> T maskTrailingZeros(unsigned N) {
264 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
265}
266
267/// Create a bitmask with the N left-most bits set to 0, and all other
268/// bits set to 1. Only unsigned types are allowed.
269template <typename T> T maskLeadingZeros(unsigned N) {
270 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
271}
272
273/// Get the index of the last set bit starting from the least
274/// significant bit.
275///
276/// Only unsigned integral types are allowed.
277///
278/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
279/// valid arguments.
280template <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 // Use ^ instead of - because both gcc and llvm can remove the associated ^
285 // in the __builtin_clz intrinsic on x86.
286 return countLeadingZeros(Val, ZB_Undefined) ^
287 (std::numeric_limits<T>::digits - 1);
288}
289
290/// Macro compressed bit reversal table for 256 bits.
291///
292/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
293static 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/// Reverse the bits in \p Val.
304template <typename T>
305T 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)1
316template<>
317inline uint8_t reverseBits<uint8_t>(uint8_t Val) {
318 return __builtin_bitreverse8(Val);
319}
320#endif
321
322#if __has_builtin(__builtin_bitreverse16)1
323template<>
324inline uint16_t reverseBits<uint16_t>(uint16_t Val) {
325 return __builtin_bitreverse16(Val);
326}
327#endif
328
329#if __has_builtin(__builtin_bitreverse32)1
330template<>
331inline uint32_t reverseBits<uint32_t>(uint32_t Val) {
332 return __builtin_bitreverse32(Val);
333}
334#endif
335
336#if __has_builtin(__builtin_bitreverse64)1
337template<>
338inline uint64_t reverseBits<uint64_t>(uint64_t Val) {
339 return __builtin_bitreverse64(Val);
340}
341#endif
342
343// NOTE: The following support functions use the _32/_64 extensions instead of
344// type overloading so that signed and unsigned integers can be used without
345// ambiguity.
346
347/// Return the high 32 bits of a 64 bit value.
348constexpr inline uint32_t Hi_32(uint64_t Value) {
349 return static_cast<uint32_t>(Value >> 32);
350}
351
352/// Return the low 32 bits of a 64 bit value.
353constexpr inline uint32_t Lo_32(uint64_t Value) {
354 return static_cast<uint32_t>(Value);
355}
356
357/// Make a 64-bit integer from a high / low pair of 32-bit integers.
358constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
359 return ((uint64_t)High << 32) | (uint64_t)Low;
360}
361
362/// Checks if an integer fits into the given bit width.
363template <unsigned N> constexpr inline bool isInt(int64_t x) {
364 return N >= 64 || (-(INT64_C(1)1LL<<(N-1)) <= x && x < (INT64_C(1)1LL<<(N-1)));
365}
366// Template specializations to get better code for common cases.
367template <> constexpr inline bool isInt<8>(int64_t x) {
368 return static_cast<int8_t>(x) == x;
369}
370template <> constexpr inline bool isInt<16>(int64_t x) {
371 return static_cast<int16_t>(x) == x;
372}
373template <> constexpr inline bool isInt<32>(int64_t x) {
374 return static_cast<int32_t>(x) == x;
375}
376
377/// Checks if a signed integer is an N bit number shifted left by S.
378template <unsigned N, unsigned S>
379constexpr 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)1ULL << S) == 0);
384}
385
386/// Checks if an unsigned integer fits into the given bit width.
387///
388/// This is written as two functions rather than as simply
389///
390/// return N >= 64 || X < (UINT64_C(1) << N);
391///
392/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
393/// left too many places.
394template <unsigned N>
395constexpr 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)1ULL << (N));
398}
399template <unsigned N>
400constexpr inline std::enable_if_t<N >= 64, bool> isUInt(uint64_t) {
401 return true;
402}
403
404// Template specializations to get better code for common cases.
405template <> constexpr inline bool isUInt<8>(uint64_t x) {
406 return static_cast<uint8_t>(x) == x;
407}
408template <> constexpr inline bool isUInt<16>(uint64_t x) {
409 return static_cast<uint16_t>(x) == x;
410}
411template <> constexpr inline bool isUInt<32>(uint64_t x) {
412 return static_cast<uint32_t>(x) == x;
413}
414
415/// Checks if a unsigned integer is an N bit number shifted left by S.
416template <unsigned N, unsigned S>
417constexpr 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 // Per the two static_asserts above, S must be strictly less than 64. So
423 // 1 << S is not undefined behavior.
424 return isUInt<N + S>(x) && (x % (UINT64_C(1)1ULL << S) == 0);
425}
426
427/// Gets the maximum value for a N-bit unsigned integer.
428inline uint64_t maxUIntN(uint64_t N) {
429 assert(N > 0 && N <= 64 && "integer width out of range")((void)0);
430
431 // uint64_t(1) << 64 is undefined behavior, so we can't do
432 // (uint64_t(1) << N) - 1
433 // without checking first that N != 64. But this works and doesn't have a
434 // branch.
435 return UINT64_MAX0xffffffffffffffffULL >> (64 - N);
436}
437
438/// Gets the minimum value for a N-bit signed integer.
439inline int64_t minIntN(int64_t N) {
440 assert(N > 0 && N <= 64 && "integer width out of range")((void)0);
441
442 return UINT64_C(1)1ULL + ~(UINT64_C(1)1ULL << (N - 1));
443}
444
445/// Gets the maximum value for a N-bit signed integer.
446inline int64_t maxIntN(int64_t N) {
447 assert(N > 0 && N <= 64 && "integer width out of range")((void)0);
448
449 // This relies on two's complement wraparound when N == 64, so we convert to
450 // int64_t only at the very end to avoid UB.
451 return (UINT64_C(1)1ULL << (N - 1)) - 1;
452}
453
454/// Checks if an unsigned integer fits into the given (dynamic) bit width.
455inline bool isUIntN(unsigned N, uint64_t x) {
456 return N >= 64 || x <= maxUIntN(N);
457}
458
459/// Checks if an signed integer fits into the given (dynamic) bit width.
460inline bool isIntN(unsigned N, int64_t x) {
461 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
462}
463
464/// Return true if the argument is a non-empty sequence of ones starting at the
465/// least significant bit with the remainder zero (32 bit version).
466/// Ex. isMask_32(0x0000FFFFU) == true.
467constexpr inline bool isMask_32(uint32_t Value) {
468 return Value && ((Value + 1) & Value) == 0;
469}
470
471/// Return true if the argument is a non-empty sequence of ones starting at the
472/// least significant bit with the remainder zero (64 bit version).
473constexpr inline bool isMask_64(uint64_t Value) {
474 return Value && ((Value + 1) & Value) == 0;
475}
476
477/// Return true if the argument contains a non-empty sequence of ones with the
478/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
479constexpr inline bool isShiftedMask_32(uint32_t Value) {
480 return Value && isMask_32((Value - 1) | Value);
481}
482
483/// Return true if the argument contains a non-empty sequence of ones with the
484/// remainder zero (64 bit version.)
485constexpr inline bool isShiftedMask_64(uint64_t Value) {
486 return Value && isMask_64((Value - 1) | Value);
487}
488
489/// Return true if the argument is a power of two > 0.
490/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
491constexpr inline bool isPowerOf2_32(uint32_t Value) {
492 return Value && !(Value & (Value - 1));
493}
494
495/// Return true if the argument is a power of two > 0 (64 bit edition.)
496constexpr inline bool isPowerOf2_64(uint64_t Value) {
497 return Value && !(Value & (Value - 1));
498}
499
500/// Count the number of ones from the most significant bit to the first
501/// zero bit.
502///
503/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
504/// Only unsigned integral types are allowed.
505///
506/// \param ZB the behavior on an input of all ones. Only ZB_Width and
507/// ZB_Undefined are valid arguments.
508template <typename T>
509unsigned 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/// Count the number of ones from the least significant bit to the first
517/// zero bit.
518///
519/// Ex. countTrailingOnes(0x00FF00FF) == 8.
520/// Only unsigned integral types are allowed.
521///
522/// \param ZB the behavior on an input of all ones. Only ZB_Width and
523/// ZB_Undefined are valid arguments.
524template <typename T>
525unsigned 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
532namespace detail {
533template <typename T, std::size_t SizeOfT> struct PopulationCounter {
534 static unsigned count(T Value) {
535 // Generic version, forward to 32 bits.
536 static_assert(SizeOfT <= 4, "Not implemented!");
537#if defined(__GNUC__4)
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
548template <typename T> struct PopulationCounter<T, 8> {
549 static unsigned count(T Value) {
550#if defined(__GNUC__4)
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} // namespace detail
562
563/// Count the number of set bits in a value.
564/// Ex. countPopulation(0xF000F000) = 8
565/// Returns 0 if the word is zero.
566template <typename T>
567inline 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/// Compile time Log2.
575/// Valid only for positive powers of two.
576template <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
582template <> constexpr inline size_t CTLog2<1>() { return 0; }
583
584/// Return the log base 2 of the specified value.
585inline 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/// Return the floor log base 2 of the specified value, -1 if the value is zero.
594/// (32 bit edition.)
595/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
596inline unsigned Log2_32(uint32_t Value) {
597 return 31 - countLeadingZeros(Value);
598}
599
600/// Return the floor log base 2 of the specified value, -1 if the value is zero.
601/// (64 bit edition.)
602inline unsigned Log2_64(uint64_t Value) {
603 return 63 - countLeadingZeros(Value);
16
←
Returning the value 4294967295
→
604}
605
606/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
607/// (32 bit edition).
608/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
609inline unsigned Log2_32_Ceil(uint32_t Value) {
610 return 32 - countLeadingZeros(Value - 1);
611}
612
613/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
614/// (64 bit edition.)
615inline unsigned Log2_64_Ceil(uint64_t Value) {
616 return 64 - countLeadingZeros(Value - 1);
617}
618
619/// Return the greatest common divisor of the values using Euclid's algorithm.
620template <typename T>
621inline 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
630inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
631 return greatestCommonDivisor<uint64_t>(A, B);
632}
633
634/// This function takes a 64-bit integer and returns the bit equivalent double.
635inline 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/// This function takes a 32-bit integer and returns the bit equivalent float.
643inline 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/// This function takes a double and returns the bit equivalent 64-bit integer.
651/// Note that copying doubles around changes the bits of NaNs on some hosts,
652/// notably x86, so this routine cannot be used if these bits are needed.
653inline 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/// This function takes a float and returns the bit equivalent 32-bit integer.
661/// Note that copying floats around changes the bits of NaNs on some hosts,
662/// notably x86, so this routine cannot be used if these bits are needed.
663inline 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/// A and B are either alignments or offsets. Return the minimum alignment that
671/// may be assumed after adding the two together.
672constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
673 // The largest power of 2 that divides both A and B.
674 //
675 // Replace "-Value" by "1+~Value" in the following commented code to avoid
676 // MSVC warning C4146
677 // return (A | B) & -(A | B);
678 return (A | B) & (1 + ~(A | B));
679}
680
681/// Returns the next power of two (in 64-bits) that is strictly greater than A.
682/// Returns zero on overflow.
683inline 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/// Returns the power of two which is less than or equal to the given value.
694/// Essentially, it is a floor operation across the domain of powers of two.
695inline uint64_t PowerOf2Floor(uint64_t A) {
696 if (!A) return 0;
697 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
698}
699
700/// Returns the power of two which is greater than or equal to the given value.
701/// Essentially, it is a ceil operation across the domain of powers of two.
702inline uint64_t PowerOf2Ceil(uint64_t A) {
703 if (!A)
704 return 0;
705 return NextPowerOf2(A - 1);
706}
707
708/// Returns the next integer (mod 2**64) that is greater than or equal to
709/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
710///
711/// If non-zero \p Skew is specified, the return value will be a minimal
712/// integer that is greater than or equal to \p Value and equal to
713/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
714/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
715///
716/// Examples:
717/// \code
718/// alignTo(5, 8) = 8
719/// alignTo(17, 8) = 24
720/// alignTo(~0LL, 8) = 0
721/// alignTo(321, 255) = 510
722///
723/// alignTo(5, 8, 7) = 7
724/// alignTo(17, 8, 1) = 17
725/// alignTo(~0LL, 8, 3) = 3
726/// alignTo(321, 255, 42) = 552
727/// \endcode
728inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
729 assert(Align != 0u && "Align can't be 0.")((void)0);
730 Skew %= Align;
731 return (Value + Align - 1 - Skew) / Align * Align + Skew;
732}
733
734/// Returns the next integer (mod 2**64) that is greater than or equal to
735/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
736template <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/// Returns the integer ceil(Numerator / Denominator).
742inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
743 return alignTo(Numerator, Denominator) / Denominator;
744}
745
746/// Returns the integer nearest(Numerator / Denominator).
747inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) {
748 return (Numerator + (Denominator / 2)) / Denominator;
749}
750
751/// Returns the largest uint64_t less than or equal to \p Value and is
752/// \p Skew mod \p Align. \p Align must be non-zero
753inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
754 assert(Align != 0u && "Align can't be 0.")((void)0);
755 Skew %= Align;
756 return (Value - Skew) / Align * Align + Skew;
757}
758
759/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
760/// Requires 0 < B <= 32.
761template <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/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
768/// Requires 0 < B <= 32.
769inline int32_t SignExtend32(uint32_t X, unsigned B) {
770 assert(B > 0 && "Bit width can't be 0.")((void)0);
771 assert(B <= 32 && "Bit width out of range.")((void)0);
772 return int32_t(X << (32 - B)) >> (32 - B);
773}
774
775/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
776/// Requires 0 < B <= 64.
777template <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/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
784/// Requires 0 < B <= 64.
785inline int64_t SignExtend64(uint64_t X, unsigned B) {
786 assert(B > 0 && "Bit width can't be 0.")((void)0);
787 assert(B <= 64 && "Bit width out of range.")((void)0);
788 return int64_t(X << (64 - B)) >> (64 - B);
789}
790
791/// Subtract two unsigned integers, X and Y, of type T and return the absolute
792/// value of the result.
793template <typename T>
794std::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/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
799/// maximum representable value of T on overflow. ResultOverflowed indicates if
800/// the result is larger than the maximum representable value of type T.
801template <typename T>
802std::enable_if_t<std::is_unsigned<T>::value, T>
803SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
804 bool Dummy;
805 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
806 // Hacker's Delight, p. 29
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/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
816/// maximum representable value of T on overflow. ResultOverflowed indicates if
817/// the result is larger than the maximum representable value of type T.
818template <typename T>
819std::enable_if_t<std::is_unsigned<T>::value, T>
820SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
821 bool Dummy;
822 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
823
824 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
825 // because it fails for uint16_t (where multiplication can have undefined
826 // behavior due to promotion to int), and requires a division in addition
827 // to the multiplication.
828
829 Overflowed = false;
830
831 // Log2(Z) would be either Log2Z or Log2Z + 1.
832 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
833 // will necessarily be less than Log2Max as desired.
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 // We're going to use the top bit, and maybe overflow one
846 // bit past it. Multiply all but the bottom bit then add
847 // that on at the end.
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/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
861/// the product. Clamp the result to the maximum representable value of T on
862/// overflow. ResultOverflowed indicates if the result is larger than the
863/// maximum representable value of type T.
864template <typename T>
865std::enable_if_t<std::is_unsigned<T>::value, T>
866SaturatingMultiplyAdd(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/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
878extern const float huge_valf;
879
880
881/// Add two signed integers, computing the two's complement truncated result,
882/// returning true if overflow occured.
883template <typename T>
884std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) {
885#if __has_builtin(__builtin_add_overflow)1
886 return __builtin_add_overflow(X, Y, &Result);
887#else
888 // Perform the unsigned addition.
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 // Convert to signed.
895 Result = static_cast<T>(UResult);
896
897 // Adding two positive numbers should result in a positive number.
898 if (X > 0 && Y > 0)
899 return Result <= 0;
900 // Adding two negatives should result in a negative number.
901 if (X < 0 && Y < 0)
902 return Result >= 0;
903 return false;
904#endif
905}
906
907/// Subtract two signed integers, computing the two's complement truncated
908/// result, returning true if an overflow ocurred.
909template <typename T>
910std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) {
911#if __has_builtin(__builtin_sub_overflow)1
912 return __builtin_sub_overflow(X, Y, &Result);
913#else
914 // Perform the unsigned addition.
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 // Convert to signed.
921 Result = static_cast<T>(UResult);
922
923 // Subtracting a positive number from a negative results in a negative number.
924 if (X <= 0 && Y > 0)
925 return Result >= 0;
926 // Subtracting a negative number from a positive results in a positive number.
927 if (X >= 0 && Y < 0)
928 return Result <= 0;
929 return false;
930#endif
931}
932
933/// Multiply two signed integers, computing the two's complement truncated
934/// result, returning true if an overflow ocurred.
935template <typename T>
936std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) {
937 // Perform the unsigned multiplication on absolute values.
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 // Convert to signed.
944 const bool IsNegative = (X < 0) ^ (Y < 0);
945 Result = IsNegative ? (0 - UResult) : UResult;
946
947 // If any of the args was 0, result is 0 and no overflow occurs.
948 if (UX == 0 || UY == 0)
949 return false;
950
951 // UX and UY are in [1, 2^n], where n is the number of digits.
952 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
953 // positive) divided by an argument compares to the other.
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} // End llvm namespace
961
962#endif