| 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' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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 | ||||
| 41 | using namespace llvm; | |||
| 42 | ||||
| 43 | //===----------------------------------------------------------------------===// | |||
| 44 | // Support for StructLayout | |||
| 45 | //===----------------------------------------------------------------------===// | |||
| 46 | ||||
| 47 | StructLayout::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. | |||
| 82 | unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const { | |||
| 83 | ArrayRef<uint64_t> MemberOffsets = getMemberOffsets(); | |||
| 84 | auto SI = llvm::upper_bound(MemberOffsets, Offset); | |||
| 85 | assert(SI != MemberOffsets.begin() && "Offset not in structure type!")((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 | ||||
| 104 | LayoutAlignElem LayoutAlignElem::get(AlignTypeEnum align_type, Align abi_align, | |||
| 105 | Align pref_align, uint32_t bit_width) { | |||
| 106 | assert(abi_align <= pref_align && "Preferred alignment worse than ABI!")((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 | ||||
| 115 | bool | |||
| 116 | LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const { | |||
| 117 | return (AlignType == rhs.AlignType | |||
| 118 | && ABIAlign == rhs.ABIAlign | |||
| 119 | && PrefAlign == rhs.PrefAlign | |||
| 120 | && TypeBitWidth == rhs.TypeBitWidth); | |||
| 121 | } | |||
| 122 | ||||
| 123 | //===----------------------------------------------------------------------===// | |||
| 124 | // PointerAlignElem, PointerAlign support | |||
| 125 | //===----------------------------------------------------------------------===// | |||
| 126 | ||||
| 127 | PointerAlignElem PointerAlignElem::get(uint32_t AddressSpace, Align ABIAlign, | |||
| 128 | Align PrefAlign, uint32_t TypeByteWidth, | |||
| 129 | uint32_t IndexWidth) { | |||
| 130 | assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!")((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 | ||||
| 140 | bool | |||
| 141 | PointerAlignElem::operator==(const PointerAlignElem &rhs) const { | |||
| 142 | return (ABIAlign == rhs.ABIAlign | |||
| 143 | && AddressSpace == rhs.AddressSpace | |||
| 144 | && PrefAlign == rhs.PrefAlign | |||
| 145 | && TypeByteWidth == rhs.TypeByteWidth | |||
| 146 | && IndexWidth == rhs.IndexWidth); | |||
| 147 | } | |||
| 148 | ||||
| 149 | //===----------------------------------------------------------------------===// | |||
| 150 | // DataLayout Class Implementation | |||
| 151 | //===----------------------------------------------------------------------===// | |||
| 152 | ||||
| 153 | const char *DataLayout::getManglingComponent(const Triple &T) { | |||
| 154 | if (T.isOSBinFormatMachO()) | |||
| 155 | return "-m:o"; | |||
| 156 | if (T.isOSWindows() && T.isOSBinFormatCOFF()) | |||
| 157 | return T.getArch() == Triple::x86 ? "-m:x" : "-m:w"; | |||
| 158 | if (T.isOSBinFormatXCOFF()) | |||
| 159 | return "-m:a"; | |||
| 160 | return "-m:e"; | |||
| 161 | } | |||
| 162 | ||||
| 163 | static const LayoutAlignElem DefaultAlignments[] = { | |||
| 164 | {INTEGER_ALIGN, 1, Align(1), Align(1)}, // 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 | ||||
| 178 | void DataLayout::reset(StringRef Desc) { | |||
| 179 | clear(); | |||
| 180 | ||||
| 181 | LayoutMap = nullptr; | |||
| 182 | BigEndian = false; | |||
| 183 | AllocaAddrSpace = 0; | |||
| 184 | StackNaturalAlign.reset(); | |||
| 185 | ProgramAddrSpace = 0; | |||
| 186 | DefaultGlobalsAddrSpace = 0; | |||
| 187 | FunctionPtrAlign.reset(); | |||
| 188 | TheFunctionPtrAlignType = FunctionPtrAlignType::Independent; | |||
| 189 | ManglingMode = MM_None; | |||
| 190 | NonIntegralAddressSpaces.clear(); | |||
| 191 | ||||
| 192 | // 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 | ||||
| 205 | Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) { | |||
| 206 | DataLayout Layout(""); | |||
| 207 | if (Error Err = Layout.parseSpecifier(LayoutDescription)) | |||
| 208 | return std::move(Err); | |||
| 209 | return Layout; | |||
| 210 | } | |||
| 211 | ||||
| 212 | static Error reportError(const Twine &Message) { | |||
| 213 | return createStringError(inconvertibleErrorCode(), Message); | |||
| 214 | } | |||
| 215 | ||||
| 216 | /// Checked version of split, to ensure mandatory subparts. | |||
| 217 | static Error split(StringRef Str, char Separator, | |||
| 218 | std::pair<StringRef, StringRef> &Split) { | |||
| 219 | assert(!Str.empty() && "parse error, string can't be empty here")((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. | |||
| 229 | template <typename IntTy> static Error getInt(StringRef R, IntTy &Result) { | |||
| 230 | bool error = R.getAsInteger(10, Result); (void)error; | |||
| 231 | if (error) | |||
| 232 | return reportError("not a number, or does not fit in an unsigned int"); | |||
| 233 | return Error::success(); | |||
| 234 | } | |||
| 235 | ||||
| 236 | /// Get an unsigned integer representing the number of bits and convert it into | |||
| 237 | /// bytes. Error out of not a byte width multiple. | |||
| 238 | template <typename IntTy> | |||
| 239 | static Error getIntInBytes(StringRef R, IntTy &Result) { | |||
| 240 | if (Error Err = getInt<IntTy>(R, Result)) | |||
| 241 | return Err; | |||
| 242 | if (Result % 8) | |||
| 243 | return reportError("number of bits must be a byte width multiple"); | |||
| 244 | Result /= 8; | |||
| 245 | return Error::success(); | |||
| 246 | } | |||
| 247 | ||||
| 248 | static Error getAddrSpace(StringRef R, unsigned &AddrSpace) { | |||
| 249 | if (Error Err = getInt(R, AddrSpace)) | |||
| 250 | return Err; | |||
| 251 | if (!isUInt<24>(AddrSpace)) | |||
| 252 | return reportError("Invalid address space, must be a 24-bit integer"); | |||
| 253 | return Error::success(); | |||
| 254 | } | |||
| 255 | ||||
| 256 | Error DataLayout::parseSpecifier(StringRef Desc) { | |||
| 257 | StringRepresentation = std::string(Desc); | |||
| 258 | while (!Desc.empty()) { | |||
| 259 | // 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 | ||||
| 529 | DataLayout::DataLayout(const Module *M) { | |||
| 530 | init(M); | |||
| 531 | } | |||
| 532 | ||||
| 533 | void DataLayout::init(const Module *M) { *this = M->getDataLayout(); } | |||
| 534 | ||||
| 535 | bool DataLayout::operator==(const DataLayout &Other) const { | |||
| 536 | bool Ret = BigEndian == Other.BigEndian && | |||
| 537 | AllocaAddrSpace == Other.AllocaAddrSpace && | |||
| 538 | StackNaturalAlign == Other.StackNaturalAlign && | |||
| 539 | ProgramAddrSpace == Other.ProgramAddrSpace && | |||
| 540 | DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace && | |||
| 541 | FunctionPtrAlign == Other.FunctionPtrAlign && | |||
| 542 | TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType && | |||
| 543 | ManglingMode == Other.ManglingMode && | |||
| 544 | LegalIntWidths == Other.LegalIntWidths && | |||
| 545 | Alignments == Other.Alignments && Pointers == Other.Pointers; | |||
| 546 | // Note: getStringRepresentation() might differs, it is not canonicalized | |||
| 547 | return Ret; | |||
| 548 | } | |||
| 549 | ||||
| 550 | DataLayout::AlignmentsTy::iterator | |||
| 551 | DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType, | |||
| 552 | uint32_t BitWidth) { | |||
| 553 | auto Pair = std::make_pair((unsigned)AlignType, BitWidth); | |||
| 554 | return partition_point(Alignments, [=](const LayoutAlignElem &E) { | |||
| 555 | return std::make_pair(E.AlignType, E.TypeBitWidth) < Pair; | |||
| 556 | }); | |||
| 557 | } | |||
| 558 | ||||
| 559 | Error DataLayout::setAlignment(AlignTypeEnum align_type, Align abi_align, | |||
| 560 | Align pref_align, uint32_t bit_width) { | |||
| 561 | // 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 | ||||
| 586 | const PointerAlignElem & | |||
| 587 | DataLayout::getPointerAlignElem(uint32_t AddressSpace) const { | |||
| 588 | if (AddressSpace != 0) { | |||
| 589 | auto I = lower_bound(Pointers, AddressSpace, | |||
| 590 | [](const PointerAlignElem &A, uint32_t AddressSpace) { | |||
| 591 | return A.AddressSpace < AddressSpace; | |||
| 592 | }); | |||
| 593 | if (I != Pointers.end() && I->AddressSpace == AddressSpace) | |||
| 594 | return *I; | |||
| 595 | } | |||
| 596 | ||||
| 597 | assert(Pointers[0].AddressSpace == 0)((void)0); | |||
| 598 | return Pointers[0]; | |||
| 599 | } | |||
| 600 | ||||
| 601 | Error DataLayout::setPointerAlignment(uint32_t AddrSpace, Align ABIAlign, | |||
| 602 | Align PrefAlign, uint32_t TypeByteWidth, | |||
| 603 | uint32_t IndexWidth) { | |||
| 604 | if (PrefAlign < ABIAlign) | |||
| 605 | return reportError( | |||
| 606 | "Preferred alignment cannot be less than the ABI alignment"); | |||
| 607 | ||||
| 608 | auto I = lower_bound(Pointers, AddrSpace, | |||
| 609 | [](const PointerAlignElem &A, uint32_t AddressSpace) { | |||
| 610 | return A.AddressSpace < AddressSpace; | |||
| 611 | }); | |||
| 612 | if (I == Pointers.end() || I->AddressSpace != AddrSpace) { | |||
| 613 | Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, | |||
| 614 | TypeByteWidth, IndexWidth)); | |||
| 615 | } else { | |||
| 616 | I->ABIAlign = ABIAlign; | |||
| 617 | I->PrefAlign = PrefAlign; | |||
| 618 | I->TypeByteWidth = TypeByteWidth; | |||
| 619 | I->IndexWidth = IndexWidth; | |||
| 620 | } | |||
| 621 | return Error::success(); | |||
| 622 | } | |||
| 623 | ||||
| 624 | Align DataLayout::getIntegerAlignment(uint32_t BitWidth, | |||
| 625 | bool abi_or_pref) const { | |||
| 626 | auto I = findAlignmentLowerBound(INTEGER_ALIGN, BitWidth); | |||
| 627 | // 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 | ||||
| 636 | namespace { | |||
| 637 | ||||
| 638 | class StructLayoutMap { | |||
| 639 | using LayoutInfoTy = DenseMap<StructType*, StructLayout*>; | |||
| 640 | LayoutInfoTy LayoutInfo; | |||
| 641 | ||||
| 642 | public: | |||
| 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 | ||||
| 659 | void DataLayout::clear() { | |||
| 660 | LegalIntWidths.clear(); | |||
| 661 | Alignments.clear(); | |||
| 662 | Pointers.clear(); | |||
| 663 | delete static_cast<StructLayoutMap *>(LayoutMap); | |||
| 664 | LayoutMap = nullptr; | |||
| 665 | } | |||
| 666 | ||||
| 667 | DataLayout::~DataLayout() { | |||
| 668 | clear(); | |||
| 669 | } | |||
| 670 | ||||
| 671 | const StructLayout *DataLayout::getStructLayout(StructType *Ty) const { | |||
| 672 | if (!LayoutMap) | |||
| 673 | LayoutMap = new StructLayoutMap(); | |||
| 674 | ||||
| 675 | StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap); | |||
| 676 | StructLayout *&SL = (*STM)[Ty]; | |||
| 677 | if (SL) return SL; | |||
| 678 | ||||
| 679 | // 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 | ||||
| 693 | Align DataLayout::getPointerABIAlignment(unsigned AS) const { | |||
| 694 | return getPointerAlignElem(AS).ABIAlign; | |||
| 695 | } | |||
| 696 | ||||
| 697 | Align DataLayout::getPointerPrefAlignment(unsigned AS) const { | |||
| 698 | return getPointerAlignElem(AS).PrefAlign; | |||
| 699 | } | |||
| 700 | ||||
| 701 | unsigned DataLayout::getPointerSize(unsigned AS) const { | |||
| 702 | return getPointerAlignElem(AS).TypeByteWidth; | |||
| 703 | } | |||
| 704 | ||||
| 705 | unsigned DataLayout::getMaxPointerSize() const { | |||
| 706 | unsigned MaxPointerSize = 0; | |||
| 707 | for (auto &P : Pointers) | |||
| 708 | MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth); | |||
| 709 | ||||
| 710 | return MaxPointerSize; | |||
| 711 | } | |||
| 712 | ||||
| 713 | unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const { | |||
| 714 | assert(Ty->isPtrOrPtrVectorTy() &&((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 | ||||
| 720 | unsigned DataLayout::getIndexSize(unsigned AS) const { | |||
| 721 | return getPointerAlignElem(AS).IndexWidth; | |||
| 722 | } | |||
| 723 | ||||
| 724 | unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const { | |||
| 725 | assert(Ty->isPtrOrPtrVectorTy() &&((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 | */ | |||
| 739 | Align 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()) { | |||
| 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 && | |||
| 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)); | |||
| 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 && | |||
| 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()); | |||
| 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. | |||
| 821 | unsigned DataLayout::getABITypeAlignment(Type *Ty) const { | |||
| 822 | return getABITypeAlign(Ty).value(); | |||
| 823 | } | |||
| 824 | ||||
| 825 | Align DataLayout::getABITypeAlign(Type *Ty) const { | |||
| 826 | return getAlignment(Ty, true); | |||
| 827 | } | |||
| 828 | ||||
| 829 | /// TODO: Remove this function once the transition to Align is over. | |||
| 830 | unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const { | |||
| 831 | return getPrefTypeAlign(Ty).value(); | |||
| 832 | } | |||
| 833 | ||||
| 834 | Align DataLayout::getPrefTypeAlign(Type *Ty) const { | |||
| 835 | return getAlignment(Ty, false); | |||
| 836 | } | |||
| 837 | ||||
| 838 | IntegerType *DataLayout::getIntPtrType(LLVMContext &C, | |||
| 839 | unsigned AddressSpace) const { | |||
| 840 | return IntegerType::get(C, getPointerSizeInBits(AddressSpace)); | |||
| 841 | } | |||
| 842 | ||||
| 843 | Type *DataLayout::getIntPtrType(Type *Ty) const { | |||
| 844 | assert(Ty->isPtrOrPtrVectorTy() &&((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 | ||||
| 853 | Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const { | |||
| 854 | for (unsigned LegalIntWidth : LegalIntWidths) | |||
| 855 | if (Width <= LegalIntWidth) | |||
| 856 | return Type::getIntNTy(C, LegalIntWidth); | |||
| 857 | return nullptr; | |||
| 858 | } | |||
| 859 | ||||
| 860 | unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const { | |||
| 861 | auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end()); | |||
| 862 | return Max != LegalIntWidths.end() ? *Max : 0; | |||
| 863 | } | |||
| 864 | ||||
| 865 | Type *DataLayout::getIndexType(Type *Ty) const { | |||
| 866 | assert(Ty->isPtrOrPtrVectorTy() &&((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 | ||||
| 875 | int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy, | |||
| 876 | ArrayRef<Value *> Indices) const { | |||
| 877 | int64_t Result = 0; | |||
| 878 | ||||
| 879 | generic_gep_type_iterator<Value* const*> | |||
| 880 | GTI = gep_type_begin(ElemTy, Indices), | |||
| 881 | GTE = gep_type_end(ElemTy, Indices); | |||
| 882 | for (; GTI != GTE; ++GTI) { | |||
| 883 | Value *Idx = GTI.getOperand(); | |||
| 884 | if (StructType *STy = GTI.getStructTypeOrNull()) { | |||
| 885 | assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx")((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). | |||
| 905 | Align 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()) | |||
| ||||
| 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); | |||
| 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 | } |
| 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. |
| 40 | using LLVMTargetDataRef = struct LLVMOpaqueTargetData *; |
| 41 | |
| 42 | namespace llvm { |
| 43 | |
| 44 | class GlobalVariable; |
| 45 | class LLVMContext; |
| 46 | class Module; |
| 47 | class StructLayout; |
| 48 | class Triple; |
| 49 | class Value; |
| 50 | |
| 51 | /// Enum used to categorize the alignment types stored by LayoutAlignElem |
| 52 | enum AlignTypeEnum { |
| 53 | INVALID_ALIGN = 0, |
| 54 | INTEGER_ALIGN = 'i', |
| 55 | VECTOR_ALIGN = 'v', |
| 56 | FLOAT_ALIGN = 'f', |
| 57 | AGGREGATE_ALIGN = 'a' |
| 58 | }; |
| 59 | |
| 60 | // 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. |
| 72 | struct 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. |
| 91 | struct 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. |
| 112 | class DataLayout { |
| 113 | public: |
| 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 | }; |
| 120 | private: |
| 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 | |
| 197 | public: |
| 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)); |
| 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 | |
| 594 | inline DataLayout *unwrap(LLVMTargetDataRef P) { |
| 595 | return reinterpret_cast<DataLayout *>(P); |
| 596 | } |
| 597 | |
| 598 | inline LLVMTargetDataRef wrap(const DataLayout *P) { |
| 599 | return reinterpret_cast<LLVMTargetDataRef>(const_cast<DataLayout *>(P)); |
| 600 | } |
| 601 | |
| 602 | /// Used to lazily calculate structure layout information for a target machine, |
| 603 | /// based on the DataLayout structure. |
| 604 | class StructLayout final : public TrailingObjects<StructLayout, uint64_t> { |
| 605 | uint64_t StructSize; |
| 606 | Align StructAlignment; |
| 607 | unsigned IsPadded : 1; |
| 608 | unsigned NumElements : 31; |
| 609 | |
| 610 | public: |
| 611 | uint64_t getSizeInBytes() const { return StructSize; } |
| 612 | |
| 613 | uint64_t getSizeInBits() const { return 8 * StructSize; } |
| 614 | |
| 615 | Align getAlignment() const { return StructAlignment; } |
| 616 | |
| 617 | /// 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 | |
| 643 | private: |
| 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. |
| 655 | inline 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 |
| 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 | ||||
| 31 | namespace 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. | |||
| 39 | struct Align { | |||
| 40 | private: | |||
| 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 | ||||
| 66 | public: | |||
| 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); | |||
| 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; } | |||
| ||||
| 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. | |||
| 103 | inline 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. | |||
| 109 | struct MaybeAlign : public llvm::Optional<Align> { | |||
| 110 | private: | |||
| 111 | using UP = llvm::Optional<Align>; | |||
| 112 | ||||
| 113 | public: | |||
| 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. | |||
| 138 | inline 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. | |||
| 143 | inline 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. | |||
| 148 | inline 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 | |||
| 173 | inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { | |||
| 174 | const uint64_t Value = A.value(); | |||
| 175 | Skew %= Value; | |||
| 176 | return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew; | |||
| 177 | } | |||
| 178 | ||||
| 179 | /// Returns a multiple of A needed to store `Size` bytes. | |||
| 180 | /// Returns `Size` if current alignment is undefined. | |||
| 181 | inline 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. | |||
| 186 | inline uintptr_t alignAddr(const void *Addr, Align Alignment) { | |||
| 187 | uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr); | |||
| 188 | assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=((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. | |||
| 196 | inline 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. | |||
| 202 | inline 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. | |||
| 207 | inline unsigned Log2(Align A) { return A.ShiftValue; } | |||
| 208 | ||||
| 209 | /// Returns the alignment that satisfies both alignments. | |||
| 210 | /// Same semantic as MinAlign. | |||
| 211 | inline 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. | |||
| 215 | inline 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. | |||
| 221 | inline 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. | |||
| 227 | inline 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. | |||
| 232 | inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } | |||
| 233 | ||||
| 234 | /// Dual operation of the encode function above. | |||
| 235 | inline MaybeAlign decodeMaybeAlign(unsigned Value) { | |||
| 236 | if (Value == 0) | |||
| 237 | return MaybeAlign(); | |||
| 238 | Align Out; | |||
| 239 | Out.ShiftValue = Value - 1; | |||
| 240 | return Out; | |||
| 241 | } | |||
| 242 | ||||
| 243 | /// Returns a representation of the alignment, the encoded value is positive by | |||
| 244 | /// definition. | |||
| 245 | inline unsigned encode(Align A) { return encode(MaybeAlign(A)); } | |||
| 246 | ||||
| 247 | /// Comparisons between Align and scalars. Rhs must be positive. | |||
| 248 | inline bool operator==(Align Lhs, uint64_t Rhs) { | |||
| 249 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
| 250 | return Lhs.value() == Rhs; | |||
| 251 | } | |||
| 252 | inline bool operator!=(Align Lhs, uint64_t Rhs) { | |||
| 253 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
| 254 | return Lhs.value() != Rhs; | |||
| 255 | } | |||
| 256 | inline bool operator<=(Align Lhs, uint64_t Rhs) { | |||
| 257 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
| 258 | return Lhs.value() <= Rhs; | |||
| 259 | } | |||
| 260 | inline bool operator>=(Align Lhs, uint64_t Rhs) { | |||
| 261 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
| 262 | return Lhs.value() >= Rhs; | |||
| 263 | } | |||
| 264 | inline bool operator<(Align Lhs, uint64_t Rhs) { | |||
| 265 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
| 266 | return Lhs.value() < Rhs; | |||
| 267 | } | |||
| 268 | inline bool operator>(Align Lhs, uint64_t Rhs) { | |||
| 269 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
| 270 | return Lhs.value() > Rhs; | |||
| 271 | } | |||
| 272 | ||||
| 273 | /// Comparisons between MaybeAlign and scalars. | |||
| 274 | inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) { | |||
| 275 | return Lhs ? (*Lhs).value() == Rhs : Rhs == 0; | |||
| 276 | } | |||
| 277 | inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) { | |||
| 278 | return Lhs ? (*Lhs).value() != Rhs : Rhs != 0; | |||
| 279 | } | |||
| 280 | ||||
| 281 | /// Comparisons operators between Align. | |||
| 282 | inline bool operator==(Align Lhs, Align Rhs) { | |||
| 283 | return Lhs.ShiftValue == Rhs.ShiftValue; | |||
| 284 | } | |||
| 285 | inline bool operator!=(Align Lhs, Align Rhs) { | |||
| 286 | return Lhs.ShiftValue != Rhs.ShiftValue; | |||
| 287 | } | |||
| 288 | inline bool operator<=(Align Lhs, Align Rhs) { | |||
| 289 | return Lhs.ShiftValue <= Rhs.ShiftValue; | |||
| 290 | } | |||
| 291 | inline bool operator>=(Align Lhs, Align Rhs) { | |||
| 292 | return Lhs.ShiftValue >= Rhs.ShiftValue; | |||
| 293 | } | |||
| 294 | inline bool operator<(Align Lhs, Align Rhs) { | |||
| 295 | return Lhs.ShiftValue < Rhs.ShiftValue; | |||
| 296 | } | |||
| 297 | inline bool operator>(Align Lhs, Align Rhs) { | |||
| 298 | return Lhs.ShiftValue > Rhs.ShiftValue; | |||
| 299 | } | |||
| 300 | ||||
| 301 | // Don't allow relational comparisons with MaybeAlign. | |||
| 302 | bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; | |||
| 303 | bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; | |||
| 304 | bool operator<(Align Lhs, MaybeAlign Rhs) = delete; | |||
| 305 | bool operator>(Align Lhs, MaybeAlign Rhs) = delete; | |||
| 306 | ||||
| 307 | bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; | |||
| 308 | bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; | |||
| 309 | bool operator<(MaybeAlign Lhs, Align Rhs) = delete; | |||
| 310 | bool operator>(MaybeAlign Lhs, Align Rhs) = delete; | |||
| 311 | ||||
| 312 | bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
| 313 | bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
| 314 | bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
| 315 | bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
| 316 | ||||
| 317 | inline Align operator*(Align Lhs, uint64_t Rhs) { | |||
| 318 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
| 319 | return Align(Lhs.value() * Rhs); | |||
| 320 | } | |||
| 321 | ||||
| 322 | inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) { | |||
| 323 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
| 324 | return Lhs ? Lhs.getValue() * Rhs : MaybeAlign(); | |||
| 325 | } | |||
| 326 | ||||
| 327 | inline 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 | ||||
| 334 | inline 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 | ||||
| 340 | inline Align max(MaybeAlign Lhs, Align Rhs) { | |||
| 341 | return Lhs && *Lhs > Rhs ? *Lhs : Rhs; | |||
| 342 | } | |||
| 343 | ||||
| 344 | inline Align max(Align Lhs, MaybeAlign Rhs) { | |||
| 345 | return Rhs && *Rhs > Lhs ? *Rhs : Lhs; | |||
| 346 | } | |||
| 347 | ||||
| 348 | #ifndef NDEBUG1 | |||
| 349 | // For usage in LLVM_DEBUG macros. | |||
| 350 | inline std::string DebugStr(const Align &A) { | |||
| 351 | return std::to_string(A.value()); | |||
| 352 | } | |||
| 353 | // For usage in LLVM_DEBUG macros. | |||
| 354 | inline std::string DebugStr(const MaybeAlign &MA) { | |||
| 355 | if (MA) | |||
| 356 | return std::to_string(MA->value()); | |||
| 357 | return "None"; | |||
| 358 | } | |||
| 359 | #endif // NDEBUG | |||
| 360 | ||||
| 361 | #undef ALIGN_CHECK_ISPOSITIVE | |||
| 362 | ||||
| 363 | } // namespace llvm | |||
| 364 | ||||
| 365 | #endif // LLVM_SUPPORT_ALIGNMENT_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> |
| 33 | extern "C" { |
| 34 | unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); |
| 35 | unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); |
| 36 | unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); |
| 37 | unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); |
| 38 | } |
| 39 | #endif |
| 40 | |
| 41 | namespace llvm { |
| 42 | |
| 43 | /// The behavior an operation has on an input of 0. |
| 44 | enum 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. |
| 54 | namespace numbers { |
| 55 | // TODO: Track C++20 std::numbers. |
| 56 | // TODO: Favor using the hexadecimal FP constants (requires C++17). |
| 57 | constexpr 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 |
| 72 | constexpr 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 | |
| 89 | namespace detail { |
| 90 | template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { |
| 91 | static unsigned count(T Val, ZeroBehavior) { |
| 92 | if (!Val) |
| 93 | return std::numeric_limits<T>::digits; |
| 94 | if (Val & 0x1) |
| 95 | return 0; |
| 96 | |
| 97 | // 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) |
| 114 | template <typename T> struct TrailingZerosCounter<T, 4> { |
| 115 | static unsigned count(T Val, ZeroBehavior ZB) { |
| 116 | if (ZB != ZB_Undefined && Val == 0) |
| 117 | return 32; |
| 118 | |
| 119 | #if __has_builtin(__builtin_ctz)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) |
| 130 | template <typename T> struct TrailingZerosCounter<T, 8> { |
| 131 | static unsigned count(T Val, ZeroBehavior ZB) { |
| 132 | if (ZB != ZB_Undefined && Val == 0) |
| 133 | return 64; |
| 134 | |
| 135 | #if __has_builtin(__builtin_ctzll)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. |
| 155 | template <typename T> |
| 156 | unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { |
| 157 | static_assert(std::numeric_limits<T>::is_integer && |
| 158 | !std::numeric_limits<T>::is_signed, |
| 159 | "Only unsigned integral types are allowed."); |
| 160 | return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB); |
| 161 | } |
| 162 | |
| 163 | namespace detail { |
| 164 | template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { |
| 165 | static unsigned count(T Val, ZeroBehavior) { |
| 166 | if (!Val) |
| 167 | return std::numeric_limits<T>::digits; |
| 168 | |
| 169 | // 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) |
| 183 | template <typename T> struct LeadingZerosCounter<T, 4> { |
| 184 | static unsigned count(T Val, ZeroBehavior ZB) { |
| 185 | if (ZB != ZB_Undefined && Val == 0) |
| 186 | return 32; |
| 187 | |
| 188 | #if __has_builtin(__builtin_clz)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) |
| 199 | template <typename T> struct LeadingZerosCounter<T, 8> { |
| 200 | static unsigned count(T Val, ZeroBehavior ZB) { |
| 201 | if (ZB != ZB_Undefined && Val == 0) |
| 202 | return 64; |
| 203 | |
| 204 | #if __has_builtin(__builtin_clzll)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. |
| 224 | template <typename T> |
| 225 | unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { |
| 226 | static_assert(std::numeric_limits<T>::is_integer && |
| 227 | !std::numeric_limits<T>::is_signed, |
| 228 | "Only unsigned integral types are allowed."); |
| 229 | return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB); |
| 230 | } |
| 231 | |
| 232 | /// 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. |
| 239 | template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { |
| 240 | if (ZB == ZB_Max && Val == 0) |
| 241 | return std::numeric_limits<T>::max(); |
| 242 | |
| 243 | return countTrailingZeros(Val, ZB_Undefined); |
| 244 | } |
| 245 | |
| 246 | /// 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. |
| 248 | template <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. |
| 257 | template <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. |
| 263 | template <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. |
| 269 | template <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. |
| 280 | template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { |
| 281 | if (ZB == ZB_Max && Val == 0) |
| 282 | return std::numeric_limits<T>::max(); |
| 283 | |
| 284 | // 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 |
| 293 | static const unsigned char BitReverseTable256[256] = { |
| 294 | #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 |
| 295 | #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) |
| 296 | #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) |
| 297 | R6(0), R6(2), R6(1), R6(3) |
| 298 | #undef R2 |
| 299 | #undef R4 |
| 300 | #undef R6 |
| 301 | }; |
| 302 | |
| 303 | /// Reverse the bits in \p Val. |
| 304 | template <typename T> |
| 305 | T reverseBits(T Val) { |
| 306 | unsigned char in[sizeof(Val)]; |
| 307 | unsigned char out[sizeof(Val)]; |
| 308 | std::memcpy(in, &Val, sizeof(Val)); |
| 309 | for (unsigned i = 0; i < sizeof(Val); ++i) |
| 310 | out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]]; |
| 311 | std::memcpy(&Val, out, sizeof(Val)); |
| 312 | return Val; |
| 313 | } |
| 314 | |
| 315 | #if __has_builtin(__builtin_bitreverse8)1 |
| 316 | template<> |
| 317 | inline uint8_t reverseBits<uint8_t>(uint8_t Val) { |
| 318 | return __builtin_bitreverse8(Val); |
| 319 | } |
| 320 | #endif |
| 321 | |
| 322 | #if __has_builtin(__builtin_bitreverse16)1 |
| 323 | template<> |
| 324 | inline uint16_t reverseBits<uint16_t>(uint16_t Val) { |
| 325 | return __builtin_bitreverse16(Val); |
| 326 | } |
| 327 | #endif |
| 328 | |
| 329 | #if __has_builtin(__builtin_bitreverse32)1 |
| 330 | template<> |
| 331 | inline uint32_t reverseBits<uint32_t>(uint32_t Val) { |
| 332 | return __builtin_bitreverse32(Val); |
| 333 | } |
| 334 | #endif |
| 335 | |
| 336 | #if __has_builtin(__builtin_bitreverse64)1 |
| 337 | template<> |
| 338 | inline 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. |
| 348 | constexpr 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. |
| 353 | constexpr 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. |
| 358 | constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) { |
| 359 | return ((uint64_t)High << 32) | (uint64_t)Low; |
| 360 | } |
| 361 | |
| 362 | /// Checks if an integer fits into the given bit width. |
| 363 | template <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. |
| 367 | template <> constexpr inline bool isInt<8>(int64_t x) { |
| 368 | return static_cast<int8_t>(x) == x; |
| 369 | } |
| 370 | template <> constexpr inline bool isInt<16>(int64_t x) { |
| 371 | return static_cast<int16_t>(x) == x; |
| 372 | } |
| 373 | template <> constexpr inline bool isInt<32>(int64_t x) { |
| 374 | return static_cast<int32_t>(x) == x; |
| 375 | } |
| 376 | |
| 377 | /// Checks if a signed integer is an N bit number shifted left by S. |
| 378 | template <unsigned N, unsigned S> |
| 379 | constexpr inline bool isShiftedInt(int64_t x) { |
| 380 | static_assert( |
| 381 | N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number."); |
| 382 | static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide."); |
| 383 | return isInt<N + S>(x) && (x % (UINT64_C(1)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. |
| 394 | template <unsigned N> |
| 395 | constexpr inline std::enable_if_t<(N < 64), bool> isUInt(uint64_t X) { |
| 396 | static_assert(N > 0, "isUInt<0> doesn't make sense"); |
| 397 | return X < (UINT64_C(1)1ULL << (N)); |
| 398 | } |
| 399 | template <unsigned N> |
| 400 | constexpr inline std::enable_if_t<N >= 64, bool> isUInt(uint64_t) { |
| 401 | return true; |
| 402 | } |
| 403 | |
| 404 | // Template specializations to get better code for common cases. |
| 405 | template <> constexpr inline bool isUInt<8>(uint64_t x) { |
| 406 | return static_cast<uint8_t>(x) == x; |
| 407 | } |
| 408 | template <> constexpr inline bool isUInt<16>(uint64_t x) { |
| 409 | return static_cast<uint16_t>(x) == x; |
| 410 | } |
| 411 | template <> constexpr inline bool isUInt<32>(uint64_t x) { |
| 412 | return static_cast<uint32_t>(x) == x; |
| 413 | } |
| 414 | |
| 415 | /// Checks if a unsigned integer is an N bit number shifted left by S. |
| 416 | template <unsigned N, unsigned S> |
| 417 | constexpr inline bool isShiftedUInt(uint64_t x) { |
| 418 | static_assert( |
| 419 | N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)"); |
| 420 | static_assert(N + S <= 64, |
| 421 | "isShiftedUInt<N, S> with N + S > 64 is too wide."); |
| 422 | // 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. |
| 428 | inline 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. |
| 439 | inline 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. |
| 446 | inline 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. |
| 455 | inline 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. |
| 460 | inline 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. |
| 467 | constexpr 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). |
| 473 | constexpr 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. |
| 479 | constexpr 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.) |
| 485 | constexpr 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.) |
| 491 | constexpr 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.) |
| 496 | constexpr 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. |
| 508 | template <typename T> |
| 509 | unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) { |
| 510 | static_assert(std::numeric_limits<T>::is_integer && |
| 511 | !std::numeric_limits<T>::is_signed, |
| 512 | "Only unsigned integral types are allowed."); |
| 513 | return countLeadingZeros<T>(~Value, ZB); |
| 514 | } |
| 515 | |
| 516 | /// 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. |
| 524 | template <typename T> |
| 525 | unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) { |
| 526 | static_assert(std::numeric_limits<T>::is_integer && |
| 527 | !std::numeric_limits<T>::is_signed, |
| 528 | "Only unsigned integral types are allowed."); |
| 529 | return countTrailingZeros<T>(~Value, ZB); |
| 530 | } |
| 531 | |
| 532 | namespace detail { |
| 533 | template <typename T, std::size_t SizeOfT> struct PopulationCounter { |
| 534 | static unsigned count(T Value) { |
| 535 | // 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 | |
| 548 | template <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. |
| 566 | template <typename T> |
| 567 | inline unsigned countPopulation(T Value) { |
| 568 | static_assert(std::numeric_limits<T>::is_integer && |
| 569 | !std::numeric_limits<T>::is_signed, |
| 570 | "Only unsigned integral types are allowed."); |
| 571 | return detail::PopulationCounter<T, sizeof(T)>::count(Value); |
| 572 | } |
| 573 | |
| 574 | /// Compile time Log2. |
| 575 | /// Valid only for positive powers of two. |
| 576 | template <size_t kValue> constexpr inline size_t CTLog2() { |
| 577 | static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue), |
| 578 | "Value is not a valid power of 2"); |
| 579 | return 1 + CTLog2<kValue / 2>(); |
| 580 | } |
| 581 | |
| 582 | template <> constexpr inline size_t CTLog2<1>() { return 0; } |
| 583 | |
| 584 | /// Return the log base 2 of the specified value. |
| 585 | inline double Log2(double Value) { |
| 586 | #if defined(__ANDROID_API__) && __ANDROID_API__ < 18 |
| 587 | return __builtin_log(Value) / __builtin_log(2.0); |
| 588 | #else |
| 589 | return log2(Value); |
| 590 | #endif |
| 591 | } |
| 592 | |
| 593 | /// 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 |
| 596 | inline 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.) |
| 602 | inline unsigned Log2_64(uint64_t Value) { |
| 603 | return 63 - countLeadingZeros(Value); |
| 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 |
| 609 | inline 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.) |
| 615 | inline 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. |
| 620 | template <typename T> |
| 621 | inline T greatestCommonDivisor(T A, T B) { |
| 622 | while (B) { |
| 623 | T Tmp = B; |
| 624 | B = A % B; |
| 625 | A = Tmp; |
| 626 | } |
| 627 | return A; |
| 628 | } |
| 629 | |
| 630 | inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { |
| 631 | return greatestCommonDivisor<uint64_t>(A, B); |
| 632 | } |
| 633 | |
| 634 | /// This function takes a 64-bit integer and returns the bit equivalent double. |
| 635 | inline double BitsToDouble(uint64_t Bits) { |
| 636 | double D; |
| 637 | static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes"); |
| 638 | memcpy(&D, &Bits, sizeof(Bits)); |
| 639 | return D; |
| 640 | } |
| 641 | |
| 642 | /// This function takes a 32-bit integer and returns the bit equivalent float. |
| 643 | inline float BitsToFloat(uint32_t Bits) { |
| 644 | float F; |
| 645 | static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes"); |
| 646 | memcpy(&F, &Bits, sizeof(Bits)); |
| 647 | return F; |
| 648 | } |
| 649 | |
| 650 | /// 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. |
| 653 | inline uint64_t DoubleToBits(double Double) { |
| 654 | uint64_t Bits; |
| 655 | static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes"); |
| 656 | memcpy(&Bits, &Double, sizeof(Double)); |
| 657 | return Bits; |
| 658 | } |
| 659 | |
| 660 | /// 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. |
| 663 | inline uint32_t FloatToBits(float Float) { |
| 664 | uint32_t Bits; |
| 665 | static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes"); |
| 666 | memcpy(&Bits, &Float, sizeof(Float)); |
| 667 | return Bits; |
| 668 | } |
| 669 | |
| 670 | /// A and B are either alignments or offsets. Return the minimum alignment that |
| 671 | /// may be assumed after adding the two together. |
| 672 | constexpr 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. |
| 683 | inline uint64_t NextPowerOf2(uint64_t A) { |
| 684 | A |= (A >> 1); |
| 685 | A |= (A >> 2); |
| 686 | A |= (A >> 4); |
| 687 | A |= (A >> 8); |
| 688 | A |= (A >> 16); |
| 689 | A |= (A >> 32); |
| 690 | return A + 1; |
| 691 | } |
| 692 | |
| 693 | /// 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. |
| 695 | inline 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. |
| 702 | inline 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 |
| 728 | inline 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. |
| 736 | template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) { |
| 737 | static_assert(Align != 0u, "Align must be non-zero"); |
| 738 | return (Value + Align - 1) / Align * Align; |
| 739 | } |
| 740 | |
| 741 | /// Returns the integer ceil(Numerator / Denominator). |
| 742 | inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) { |
| 743 | return alignTo(Numerator, Denominator) / Denominator; |
| 744 | } |
| 745 | |
| 746 | /// Returns the integer nearest(Numerator / Denominator). |
| 747 | inline 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 |
| 753 | inline 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. |
| 761 | template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) { |
| 762 | static_assert(B > 0, "Bit width can't be 0."); |
| 763 | static_assert(B <= 32, "Bit width out of range."); |
| 764 | return int32_t(X << (32 - B)) >> (32 - B); |
| 765 | } |
| 766 | |
| 767 | /// Sign-extend the number in the bottom B bits of X to a 32-bit integer. |
| 768 | /// Requires 0 < B <= 32. |
| 769 | inline 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. |
| 777 | template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) { |
| 778 | static_assert(B > 0, "Bit width can't be 0."); |
| 779 | static_assert(B <= 64, "Bit width out of range."); |
| 780 | return int64_t(x << (64 - B)) >> (64 - B); |
| 781 | } |
| 782 | |
| 783 | /// Sign-extend the number in the bottom B bits of X to a 64-bit integer. |
| 784 | /// Requires 0 < B <= 64. |
| 785 | inline 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. |
| 793 | template <typename T> |
| 794 | std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) { |
| 795 | return X > Y ? (X - Y) : (Y - X); |
| 796 | } |
| 797 | |
| 798 | /// 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. |
| 801 | template <typename T> |
| 802 | std::enable_if_t<std::is_unsigned<T>::value, T> |
| 803 | SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) { |
| 804 | bool Dummy; |
| 805 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
| 806 | // 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. |
| 818 | template <typename T> |
| 819 | std::enable_if_t<std::is_unsigned<T>::value, T> |
| 820 | SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) { |
| 821 | bool Dummy; |
| 822 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
| 823 | |
| 824 | // 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. |
| 864 | template <typename T> |
| 865 | std::enable_if_t<std::is_unsigned<T>::value, T> |
| 866 | SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) { |
| 867 | bool Dummy; |
| 868 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
| 869 | |
| 870 | T Product = SaturatingMultiply(X, Y, &Overflowed); |
| 871 | if (Overflowed) |
| 872 | return Product; |
| 873 | |
| 874 | return SaturatingAdd(A, Product, &Overflowed); |
| 875 | } |
| 876 | |
| 877 | /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC. |
| 878 | extern const float huge_valf; |
| 879 | |
| 880 | |
| 881 | /// Add two signed integers, computing the two's complement truncated result, |
| 882 | /// returning true if overflow occured. |
| 883 | template <typename T> |
| 884 | std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) { |
| 885 | #if __has_builtin(__builtin_add_overflow)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. |
| 909 | template <typename T> |
| 910 | std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) { |
| 911 | #if __has_builtin(__builtin_sub_overflow)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. |
| 935 | template <typename T> |
| 936 | std::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 |