1077 lines · cpp
1//===- DataLayout.cpp - Data size & alignment routines ---------------------==//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines layout properties related to datatype size/offset/alignment10// information.11//12// This structure should be created once, filled in if the defaults are not13// correct and then passed around by const&. None of the members functions14// require modification to the object.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/IR/DataLayout.h"19#include "llvm/ADT/DenseMap.h"20#include "llvm/ADT/StringExtras.h"21#include "llvm/ADT/StringRef.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/Type.h"27#include "llvm/IR/Value.h"28#include "llvm/Support/Casting.h"29#include "llvm/Support/Error.h"30#include "llvm/Support/ErrorHandling.h"31#include "llvm/Support/MathExtras.h"32#include "llvm/Support/MemAlloc.h"33#include "llvm/Support/TypeSize.h"34#include "llvm/TargetParser/Triple.h"35#include <algorithm>36#include <cassert>37#include <cstdint>38#include <cstdlib>39#include <new>40#include <utility>41 42using namespace llvm;43 44//===----------------------------------------------------------------------===//45// Support for StructLayout46//===----------------------------------------------------------------------===//47 48StructLayout::StructLayout(StructType *ST, const DataLayout &DL)49 : StructSize(TypeSize::getFixed(0)) {50 assert(!ST->isOpaque() && "Cannot get layout of opaque structs");51 IsPadded = false;52 NumElements = ST->getNumElements();53 54 // Loop over each of the elements, placing them in memory.55 for (unsigned i = 0, e = NumElements; i != e; ++i) {56 Type *Ty = ST->getElementType(i);57 if (i == 0 && Ty->isScalableTy())58 StructSize = TypeSize::getScalable(0);59 60 const Align TyAlign = ST->isPacked() ? Align(1) : DL.getABITypeAlign(Ty);61 62 // Add padding if necessary to align the data element properly.63 // Currently the only structure with scalable size will be the homogeneous64 // scalable vector types. Homogeneous scalable vector types have members of65 // the same data type so no alignment issue will happen. The condition here66 // assumes so and needs to be adjusted if this assumption changes (e.g. we67 // support structures with arbitrary scalable data type, or structure that68 // contains both fixed size and scalable size data type members).69 if (!StructSize.isScalable() && !isAligned(TyAlign, StructSize)) {70 IsPadded = true;71 StructSize = TypeSize::getFixed(alignTo(StructSize, TyAlign));72 }73 74 // Keep track of maximum alignment constraint.75 StructAlignment = std::max(TyAlign, StructAlignment);76 77 getMemberOffsets()[i] = StructSize;78 // Consume space for this data item79 StructSize += DL.getTypeAllocSize(Ty);80 }81 82 // Add padding to the end of the struct so that it could be put in an array83 // and all array elements would be aligned correctly.84 if (!StructSize.isScalable() && !isAligned(StructAlignment, StructSize)) {85 IsPadded = true;86 StructSize = TypeSize::getFixed(alignTo(StructSize, StructAlignment));87 }88}89 90/// getElementContainingOffset - Given a valid offset into the structure,91/// return the structure index that contains it.92unsigned StructLayout::getElementContainingOffset(uint64_t FixedOffset) const {93 assert(!StructSize.isScalable() &&94 "Cannot get element at offset for structure containing scalable "95 "vector types");96 TypeSize Offset = TypeSize::getFixed(FixedOffset);97 ArrayRef<TypeSize> MemberOffsets = getMemberOffsets();98 99 const auto *SI = llvm::upper_bound(MemberOffsets, Offset,100 [](TypeSize LHS, TypeSize RHS) -> bool {101 return TypeSize::isKnownLT(LHS, RHS);102 });103 assert(SI != MemberOffsets.begin() && "Offset not in structure type!");104 --SI;105 assert(TypeSize::isKnownLE(*SI, Offset) && "upper_bound didn't work");106 assert(107 (SI == MemberOffsets.begin() || TypeSize::isKnownLE(*(SI - 1), Offset)) &&108 (SI + 1 == MemberOffsets.end() ||109 TypeSize::isKnownGT(*(SI + 1), Offset)) &&110 "Upper bound didn't work!");111 112 // Multiple fields can have the same offset if any of them are zero sized.113 // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop114 // at the i32 element, because it is the last element at that offset. This is115 // the right one to return, because anything after it will have a higher116 // offset, implying that this element is non-empty.117 return SI - MemberOffsets.begin();118}119 120namespace {121 122class StructLayoutMap {123 using LayoutInfoTy = DenseMap<StructType *, StructLayout *>;124 LayoutInfoTy LayoutInfo;125 126public:127 ~StructLayoutMap() {128 // Remove any layouts.129 for (const auto &I : LayoutInfo) {130 StructLayout *Value = I.second;131 Value->~StructLayout();132 free(Value);133 }134 }135 136 StructLayout *&operator[](StructType *STy) { return LayoutInfo[STy]; }137};138 139} // end anonymous namespace140 141//===----------------------------------------------------------------------===//142// DataLayout Class Implementation143//===----------------------------------------------------------------------===//144 145bool DataLayout::PrimitiveSpec::operator==(const PrimitiveSpec &Other) const {146 return BitWidth == Other.BitWidth && ABIAlign == Other.ABIAlign &&147 PrefAlign == Other.PrefAlign;148}149 150bool DataLayout::PointerSpec::operator==(const PointerSpec &Other) const {151 return AddrSpace == Other.AddrSpace && BitWidth == Other.BitWidth &&152 ABIAlign == Other.ABIAlign && PrefAlign == Other.PrefAlign &&153 IndexBitWidth == Other.IndexBitWidth &&154 HasUnstableRepresentation == Other.HasUnstableRepresentation &&155 HasExternalState == Other.HasExternalState;156}157 158namespace {159/// Predicate to sort primitive specs by bit width.160struct LessPrimitiveBitWidth {161 bool operator()(const DataLayout::PrimitiveSpec &LHS,162 unsigned RHSBitWidth) const {163 return LHS.BitWidth < RHSBitWidth;164 }165};166 167/// Predicate to sort pointer specs by address space number.168struct LessPointerAddrSpace {169 bool operator()(const DataLayout::PointerSpec &LHS,170 unsigned RHSAddrSpace) const {171 return LHS.AddrSpace < RHSAddrSpace;172 }173};174} // namespace175 176// Default primitive type specifications.177// NOTE: These arrays must be sorted by type bit width.178constexpr DataLayout::PrimitiveSpec DefaultIntSpecs[] = {179 {8, Align::Constant<1>(), Align::Constant<1>()}, // i8:8:8180 {16, Align::Constant<2>(), Align::Constant<2>()}, // i16:16:16181 {32, Align::Constant<4>(), Align::Constant<4>()}, // i32:32:32182 {64, Align::Constant<4>(), Align::Constant<8>()}, // i64:32:64183};184constexpr DataLayout::PrimitiveSpec DefaultFloatSpecs[] = {185 {16, Align::Constant<2>(), Align::Constant<2>()}, // f16:16:16186 {32, Align::Constant<4>(), Align::Constant<4>()}, // f32:32:32187 {64, Align::Constant<8>(), Align::Constant<8>()}, // f64:64:64188 {128, Align::Constant<16>(), Align::Constant<16>()}, // f128:128:128189};190constexpr DataLayout::PrimitiveSpec DefaultVectorSpecs[] = {191 {64, Align::Constant<8>(), Align::Constant<8>()}, // v64:64:64192 {128, Align::Constant<16>(), Align::Constant<16>()}, // v128:128:128193};194 195// Default pointer type specifications.196constexpr DataLayout::PointerSpec DefaultPointerSpecs[] = {197 // p0:64:64:64:64198 {0, 64, Align::Constant<8>(), Align::Constant<8>(), 64, false, false},199};200 201DataLayout::DataLayout()202 : IntSpecs(ArrayRef(DefaultIntSpecs)),203 FloatSpecs(ArrayRef(DefaultFloatSpecs)),204 VectorSpecs(ArrayRef(DefaultVectorSpecs)),205 PointerSpecs(ArrayRef(DefaultPointerSpecs)) {}206 207DataLayout::DataLayout(StringRef LayoutString) : DataLayout() {208 if (Error Err = parseLayoutString(LayoutString))209 report_fatal_error(std::move(Err));210}211 212DataLayout &DataLayout::operator=(const DataLayout &Other) {213 delete static_cast<StructLayoutMap *>(LayoutMap);214 LayoutMap = nullptr;215 StringRepresentation = Other.StringRepresentation;216 BigEndian = Other.BigEndian;217 AllocaAddrSpace = Other.AllocaAddrSpace;218 ProgramAddrSpace = Other.ProgramAddrSpace;219 DefaultGlobalsAddrSpace = Other.DefaultGlobalsAddrSpace;220 StackNaturalAlign = Other.StackNaturalAlign;221 FunctionPtrAlign = Other.FunctionPtrAlign;222 TheFunctionPtrAlignType = Other.TheFunctionPtrAlignType;223 ManglingMode = Other.ManglingMode;224 LegalIntWidths = Other.LegalIntWidths;225 IntSpecs = Other.IntSpecs;226 FloatSpecs = Other.FloatSpecs;227 VectorSpecs = Other.VectorSpecs;228 PointerSpecs = Other.PointerSpecs;229 StructABIAlignment = Other.StructABIAlignment;230 StructPrefAlignment = Other.StructPrefAlignment;231 return *this;232}233 234bool DataLayout::operator==(const DataLayout &Other) const {235 // NOTE: StringRepresentation might differ, it is not canonicalized.236 return BigEndian == Other.BigEndian &&237 AllocaAddrSpace == Other.AllocaAddrSpace &&238 ProgramAddrSpace == Other.ProgramAddrSpace &&239 DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace &&240 StackNaturalAlign == Other.StackNaturalAlign &&241 FunctionPtrAlign == Other.FunctionPtrAlign &&242 TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&243 ManglingMode == Other.ManglingMode &&244 LegalIntWidths == Other.LegalIntWidths && IntSpecs == Other.IntSpecs &&245 FloatSpecs == Other.FloatSpecs && VectorSpecs == Other.VectorSpecs &&246 PointerSpecs == Other.PointerSpecs &&247 StructABIAlignment == Other.StructABIAlignment &&248 StructPrefAlignment == Other.StructPrefAlignment;249}250 251Expected<DataLayout> DataLayout::parse(StringRef LayoutString) {252 DataLayout Layout;253 if (Error Err = Layout.parseLayoutString(LayoutString))254 return std::move(Err);255 return Layout;256}257 258static Error createSpecFormatError(Twine Format) {259 return createStringError("malformed specification, must be of the form \"" +260 Format + "\"");261}262 263/// Attempts to parse an address space component of a specification.264static Error parseAddrSpace(StringRef Str, unsigned &AddrSpace) {265 if (Str.empty())266 return createStringError("address space component cannot be empty");267 268 if (!to_integer(Str, AddrSpace, 10) || !isUInt<24>(AddrSpace))269 return createStringError("address space must be a 24-bit integer");270 271 return Error::success();272}273 274/// Attempts to parse a size component of a specification.275static Error parseSize(StringRef Str, unsigned &BitWidth,276 StringRef Name = "size") {277 if (Str.empty())278 return createStringError(Name + " component cannot be empty");279 280 if (!to_integer(Str, BitWidth, 10) || BitWidth == 0 || !isUInt<24>(BitWidth))281 return createStringError(Name + " must be a non-zero 24-bit integer");282 283 return Error::success();284}285 286/// Attempts to parse an alignment component of a specification.287///288/// On success, returns the value converted to byte amount in \p Alignment.289/// If the value is zero and \p AllowZero is true, \p Alignment is set to one.290///291/// Return an error in a number of cases:292/// - \p Str is empty or contains characters other than decimal digits;293/// - the value is zero and \p AllowZero is false;294/// - the value is too large;295/// - the value is not a multiple of the byte width;296/// - the value converted to byte amount is not not a power of two.297static Error parseAlignment(StringRef Str, Align &Alignment, StringRef Name,298 bool AllowZero = false) {299 if (Str.empty())300 return createStringError(Name + " alignment component cannot be empty");301 302 unsigned Value;303 if (!to_integer(Str, Value, 10) || !isUInt<16>(Value))304 return createStringError(Name + " alignment must be a 16-bit integer");305 306 if (Value == 0) {307 if (!AllowZero)308 return createStringError(Name + " alignment must be non-zero");309 Alignment = Align(1);310 return Error::success();311 }312 313 constexpr unsigned ByteWidth = 8;314 if (Value % ByteWidth || !isPowerOf2_32(Value / ByteWidth))315 return createStringError(316 Name + " alignment must be a power of two times the byte width");317 318 Alignment = Align(Value / ByteWidth);319 return Error::success();320}321 322Error DataLayout::parsePrimitiveSpec(StringRef Spec) {323 // [ifv]<size>:<abi>[:<pref>]324 SmallVector<StringRef, 3> Components;325 char Specifier = Spec.front();326 assert(Specifier == 'i' || Specifier == 'f' || Specifier == 'v');327 Spec.drop_front().split(Components, ':');328 329 if (Components.size() < 2 || Components.size() > 3)330 return createSpecFormatError(Twine(Specifier) + "<size>:<abi>[:<pref>]");331 332 // Size. Required, cannot be zero.333 unsigned BitWidth;334 if (Error Err = parseSize(Components[0], BitWidth))335 return Err;336 337 // ABI alignment.338 Align ABIAlign;339 if (Error Err = parseAlignment(Components[1], ABIAlign, "ABI"))340 return Err;341 342 if (Specifier == 'i' && BitWidth == 8 && ABIAlign != 1)343 return createStringError("i8 must be 8-bit aligned");344 345 // Preferred alignment. Optional, defaults to the ABI alignment.346 Align PrefAlign = ABIAlign;347 if (Components.size() > 2)348 if (Error Err = parseAlignment(Components[2], PrefAlign, "preferred"))349 return Err;350 351 if (PrefAlign < ABIAlign)352 return createStringError(353 "preferred alignment cannot be less than the ABI alignment");354 355 setPrimitiveSpec(Specifier, BitWidth, ABIAlign, PrefAlign);356 return Error::success();357}358 359Error DataLayout::parseAggregateSpec(StringRef Spec) {360 // a<size>:<abi>[:<pref>]361 SmallVector<StringRef, 3> Components;362 assert(Spec.front() == 'a');363 Spec.drop_front().split(Components, ':');364 365 if (Components.size() < 2 || Components.size() > 3)366 return createSpecFormatError("a:<abi>[:<pref>]");367 368 // According to LangRef, <size> component must be absent altogether.369 // For backward compatibility, allow it to be specified, but require370 // it to be zero.371 if (!Components[0].empty()) {372 unsigned BitWidth;373 if (!to_integer(Components[0], BitWidth, 10) || BitWidth != 0)374 return createStringError("size must be zero");375 }376 377 // ABI alignment. Required. Can be zero, meaning use one byte alignment.378 Align ABIAlign;379 if (Error Err =380 parseAlignment(Components[1], ABIAlign, "ABI", /*AllowZero=*/true))381 return Err;382 383 // Preferred alignment. Optional, defaults to the ABI alignment.384 Align PrefAlign = ABIAlign;385 if (Components.size() > 2)386 if (Error Err = parseAlignment(Components[2], PrefAlign, "preferred"))387 return Err;388 389 if (PrefAlign < ABIAlign)390 return createStringError(391 "preferred alignment cannot be less than the ABI alignment");392 393 StructABIAlignment = ABIAlign;394 StructPrefAlignment = PrefAlign;395 return Error::success();396}397 398Error DataLayout::parsePointerSpec(StringRef Spec) {399 // p[<n>]:<size>:<abi>[:<pref>[:<idx>]]400 SmallVector<StringRef, 5> Components;401 assert(Spec.front() == 'p');402 Spec.drop_front().split(Components, ':');403 404 if (Components.size() < 3 || Components.size() > 5)405 return createSpecFormatError("p[<n>]:<size>:<abi>[:<pref>[:<idx>]]");406 407 // Address space. Optional, defaults to 0.408 unsigned AddrSpace = 0;409 bool ExternalState = false;410 bool UnstableRepr = false;411 StringRef AddrSpaceStr = Components[0];412 while (!AddrSpaceStr.empty()) {413 char C = AddrSpaceStr.front();414 if (C == 'e') {415 ExternalState = true;416 } else if (C == 'u') {417 UnstableRepr = true;418 } else if (isAlpha(C)) {419 return createStringError("'%c' is not a valid pointer specification flag",420 C);421 } else {422 break; // not a valid flag, remaining must be the address space number.423 }424 AddrSpaceStr = AddrSpaceStr.drop_front(1);425 }426 if (!AddrSpaceStr.empty())427 if (Error Err = parseAddrSpace(AddrSpaceStr, AddrSpace))428 return Err; // Failed to parse the remaining characters as a number429 if (AddrSpace == 0 && (ExternalState || UnstableRepr))430 return createStringError(431 "address space 0 cannot be unstable or have external state");432 433 // Size. Required, cannot be zero.434 unsigned BitWidth;435 if (Error Err = parseSize(Components[1], BitWidth, "pointer size"))436 return Err;437 438 // ABI alignment. Required, cannot be zero.439 Align ABIAlign;440 if (Error Err = parseAlignment(Components[2], ABIAlign, "ABI"))441 return Err;442 443 // Preferred alignment. Optional, defaults to the ABI alignment.444 // Cannot be zero.445 Align PrefAlign = ABIAlign;446 if (Components.size() > 3)447 if (Error Err = parseAlignment(Components[3], PrefAlign, "preferred"))448 return Err;449 450 if (PrefAlign < ABIAlign)451 return createStringError(452 "preferred alignment cannot be less than the ABI alignment");453 454 // Index size. Optional, defaults to pointer size. Cannot be zero.455 unsigned IndexBitWidth = BitWidth;456 if (Components.size() > 4)457 if (Error Err = parseSize(Components[4], IndexBitWidth, "index size"))458 return Err;459 460 if (IndexBitWidth > BitWidth)461 return createStringError(462 "index size cannot be larger than the pointer size");463 464 setPointerSpec(AddrSpace, BitWidth, ABIAlign, PrefAlign, IndexBitWidth,465 UnstableRepr, ExternalState);466 return Error::success();467}468 469Error DataLayout::parseSpecification(470 StringRef Spec, SmallVectorImpl<unsigned> &NonIntegralAddressSpaces) {471 // The "ni" specifier is the only two-character specifier. Handle it first.472 if (Spec.starts_with("ni")) {473 // ni:<address space>[:<address space>]...474 StringRef Rest = Spec.drop_front(2);475 476 // Drop the first ':', then split the rest of the string the usual way.477 if (!Rest.consume_front(":"))478 return createSpecFormatError("ni:<address space>[:<address space>]...");479 480 for (StringRef Str : split(Rest, ':')) {481 unsigned AddrSpace;482 if (Error Err = parseAddrSpace(Str, AddrSpace))483 return Err;484 if (AddrSpace == 0)485 return createStringError("address space 0 cannot be non-integral");486 NonIntegralAddressSpaces.push_back(AddrSpace);487 }488 return Error::success();489 }490 491 // The rest of the specifiers are single-character.492 assert(!Spec.empty() && "Empty specification is handled by the caller");493 char Specifier = Spec.front();494 495 if (Specifier == 'i' || Specifier == 'f' || Specifier == 'v')496 return parsePrimitiveSpec(Spec);497 498 if (Specifier == 'a')499 return parseAggregateSpec(Spec);500 501 if (Specifier == 'p')502 return parsePointerSpec(Spec);503 504 StringRef Rest = Spec.drop_front();505 switch (Specifier) {506 case 's':507 // Deprecated, but ignoring here to preserve loading older textual llvm508 // ASM file509 break;510 case 'e':511 case 'E':512 if (!Rest.empty())513 return createStringError(514 "malformed specification, must be just 'e' or 'E'");515 BigEndian = Specifier == 'E';516 break;517 case 'n': // Native integer types.518 // n<size>[:<size>]...519 for (StringRef Str : split(Rest, ':')) {520 unsigned BitWidth;521 if (Error Err = parseSize(Str, BitWidth))522 return Err;523 LegalIntWidths.push_back(BitWidth);524 }525 break;526 case 'S': { // Stack natural alignment.527 // S<size>528 if (Rest.empty())529 return createSpecFormatError("S<size>");530 Align Alignment;531 if (Error Err = parseAlignment(Rest, Alignment, "stack natural"))532 return Err;533 StackNaturalAlign = Alignment;534 break;535 }536 case 'F': {537 // F<type><abi>538 if (Rest.empty())539 return createSpecFormatError("F<type><abi>");540 char Type = Rest.front();541 Rest = Rest.drop_front();542 switch (Type) {543 case 'i':544 TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;545 break;546 case 'n':547 TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;548 break;549 default:550 return createStringError("unknown function pointer alignment type '" +551 Twine(Type) + "'");552 }553 Align Alignment;554 if (Error Err = parseAlignment(Rest, Alignment, "ABI"))555 return Err;556 FunctionPtrAlign = Alignment;557 break;558 }559 case 'P': { // Function address space.560 if (Rest.empty())561 return createSpecFormatError("P<address space>");562 if (Error Err = parseAddrSpace(Rest, ProgramAddrSpace))563 return Err;564 break;565 }566 case 'A': { // Default stack/alloca address space.567 if (Rest.empty())568 return createSpecFormatError("A<address space>");569 if (Error Err = parseAddrSpace(Rest, AllocaAddrSpace))570 return Err;571 break;572 }573 case 'G': { // Default address space for global variables.574 if (Rest.empty())575 return createSpecFormatError("G<address space>");576 if (Error Err = parseAddrSpace(Rest, DefaultGlobalsAddrSpace))577 return Err;578 break;579 }580 case 'm':581 if (!Rest.consume_front(":") || Rest.empty())582 return createSpecFormatError("m:<mangling>");583 if (Rest.size() > 1)584 return createStringError("unknown mangling mode");585 switch (Rest[0]) {586 default:587 return createStringError("unknown mangling mode");588 case 'e':589 ManglingMode = MM_ELF;590 break;591 case 'l':592 ManglingMode = MM_GOFF;593 break;594 case 'o':595 ManglingMode = MM_MachO;596 break;597 case 'm':598 ManglingMode = MM_Mips;599 break;600 case 'w':601 ManglingMode = MM_WinCOFF;602 break;603 case 'x':604 ManglingMode = MM_WinCOFFX86;605 break;606 case 'a':607 ManglingMode = MM_XCOFF;608 break;609 }610 break;611 default:612 return createStringError("unknown specifier '" + Twine(Specifier) + "'");613 }614 615 return Error::success();616}617 618Error DataLayout::parseLayoutString(StringRef LayoutString) {619 StringRepresentation = std::string(LayoutString);620 621 if (LayoutString.empty())622 return Error::success();623 624 // Split the data layout string into specifications separated by '-' and625 // parse each specification individually, updating internal data structures.626 SmallVector<unsigned, 8> NonIntegralAddressSpaces;627 for (StringRef Spec : split(LayoutString, '-')) {628 if (Spec.empty())629 return createStringError("empty specification is not allowed");630 if (Error Err = parseSpecification(Spec, NonIntegralAddressSpaces))631 return Err;632 }633 // Mark all address spaces that were qualified as non-integral now. This has634 // to be done later since the non-integral property is not part of the data635 // layout pointer specification.636 for (unsigned AS : NonIntegralAddressSpaces) {637 // If there is no special spec for a given AS, getPointerSpec(AS) returns638 // the spec for AS0, and we then update that to mark it non-integral.639 const PointerSpec &PS = getPointerSpec(AS);640 setPointerSpec(AS, PS.BitWidth, PS.ABIAlign, PS.PrefAlign, PS.IndexBitWidth,641 /*HasUnstableRepr=*/true, /*HasExternalState=*/false);642 }643 644 return Error::success();645}646 647void DataLayout::setPrimitiveSpec(char Specifier, uint32_t BitWidth,648 Align ABIAlign, Align PrefAlign) {649 SmallVectorImpl<PrimitiveSpec> *Specs;650 switch (Specifier) {651 default:652 llvm_unreachable("Unexpected specifier");653 case 'i':654 Specs = &IntSpecs;655 break;656 case 'f':657 Specs = &FloatSpecs;658 break;659 case 'v':660 Specs = &VectorSpecs;661 break;662 }663 664 auto I = lower_bound(*Specs, BitWidth, LessPrimitiveBitWidth());665 if (I != Specs->end() && I->BitWidth == BitWidth) {666 // Update the abi, preferred alignments.667 I->ABIAlign = ABIAlign;668 I->PrefAlign = PrefAlign;669 } else {670 // Insert before I to keep the vector sorted.671 Specs->insert(I, PrimitiveSpec{BitWidth, ABIAlign, PrefAlign});672 }673}674 675const DataLayout::PointerSpec &676DataLayout::getPointerSpec(uint32_t AddrSpace) const {677 if (AddrSpace != 0) {678 auto I = lower_bound(PointerSpecs, AddrSpace, LessPointerAddrSpace());679 if (I != PointerSpecs.end() && I->AddrSpace == AddrSpace)680 return *I;681 }682 683 assert(PointerSpecs[0].AddrSpace == 0);684 return PointerSpecs[0];685}686 687void DataLayout::setPointerSpec(uint32_t AddrSpace, uint32_t BitWidth,688 Align ABIAlign, Align PrefAlign,689 uint32_t IndexBitWidth, bool HasUnstableRepr,690 bool HasExternalState) {691 auto I = lower_bound(PointerSpecs, AddrSpace, LessPointerAddrSpace());692 if (I == PointerSpecs.end() || I->AddrSpace != AddrSpace) {693 PointerSpecs.insert(I, PointerSpec{AddrSpace, BitWidth, ABIAlign, PrefAlign,694 IndexBitWidth, HasUnstableRepr,695 HasExternalState});696 } else {697 I->BitWidth = BitWidth;698 I->ABIAlign = ABIAlign;699 I->PrefAlign = PrefAlign;700 I->IndexBitWidth = IndexBitWidth;701 I->HasUnstableRepresentation = HasUnstableRepr;702 I->HasExternalState = HasExternalState;703 }704}705 706Align DataLayout::getIntegerAlignment(uint32_t BitWidth,707 bool abi_or_pref) const {708 auto I = IntSpecs.begin();709 for (; I != IntSpecs.end(); ++I) {710 if (I->BitWidth >= BitWidth)711 break;712 }713 714 // If we don't have an exact match, use alignment of next larger integer715 // type. If there is none, use alignment of largest integer type by going716 // back one element.717 if (I == IntSpecs.end())718 --I;719 return abi_or_pref ? I->ABIAlign : I->PrefAlign;720}721 722DataLayout::~DataLayout() { delete static_cast<StructLayoutMap *>(LayoutMap); }723 724const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {725 if (!LayoutMap)726 LayoutMap = new StructLayoutMap();727 728 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);729 StructLayout *&SL = (*STM)[Ty];730 if (SL) return SL;731 732 // Otherwise, create the struct layout. Because it is variable length, we733 // malloc it, then use placement new.734 StructLayout *L = (StructLayout *)safe_malloc(735 StructLayout::totalSizeToAlloc<TypeSize>(Ty->getNumElements()));736 737 // Set SL before calling StructLayout's ctor. The ctor could cause other738 // entries to be added to TheMap, invalidating our reference.739 SL = L;740 741 new (L) StructLayout(Ty, *this);742 743 return L;744}745 746Align DataLayout::getPointerABIAlignment(unsigned AS) const {747 return getPointerSpec(AS).ABIAlign;748}749 750Align DataLayout::getPointerPrefAlignment(unsigned AS) const {751 return getPointerSpec(AS).PrefAlign;752}753 754unsigned DataLayout::getPointerSize(unsigned AS) const {755 return divideCeil(getPointerSpec(AS).BitWidth, 8);756}757 758unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {759 assert(Ty->isPtrOrPtrVectorTy() &&760 "This should only be called with a pointer or pointer vector type");761 Ty = Ty->getScalarType();762 return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());763}764 765unsigned DataLayout::getIndexSize(unsigned AS) const {766 return divideCeil(getPointerSpec(AS).IndexBitWidth, 8);767}768 769unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {770 assert(Ty->isPtrOrPtrVectorTy() &&771 "This should only be called with a pointer or pointer vector type");772 Ty = Ty->getScalarType();773 return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());774}775 776/*!777 \param abi_or_pref Flag that determines which alignment is returned. true778 returns the ABI alignment, false returns the preferred alignment.779 \param Ty The underlying type for which alignment is determined.780 781 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref782 == false) for the requested type \a Ty.783 */784Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {785 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");786 switch (Ty->getTypeID()) {787 // Early escape for the non-numeric types.788 case Type::LabelTyID:789 return abi_or_pref ? getPointerABIAlignment(0) : getPointerPrefAlignment(0);790 case Type::PointerTyID: {791 unsigned AS = cast<PointerType>(Ty)->getAddressSpace();792 return abi_or_pref ? getPointerABIAlignment(AS)793 : getPointerPrefAlignment(AS);794 }795 case Type::ArrayTyID:796 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);797 798 case Type::StructTyID: {799 // Packed structure types always have an ABI alignment of one.800 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)801 return Align(1);802 803 // Get the layout annotation... which is lazily created on demand.804 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));805 const Align Align = abi_or_pref ? StructABIAlignment : StructPrefAlignment;806 return std::max(Align, Layout->getAlignment());807 }808 case Type::IntegerTyID:809 return getIntegerAlignment(Ty->getIntegerBitWidth(), abi_or_pref);810 case Type::HalfTyID:811 case Type::BFloatTyID:812 case Type::FloatTyID:813 case Type::DoubleTyID:814 // PPC_FP128TyID and FP128TyID have different data contents, but the815 // same size and alignment, so they look the same here.816 case Type::PPC_FP128TyID:817 case Type::FP128TyID:818 case Type::X86_FP80TyID: {819 unsigned BitWidth = getTypeSizeInBits(Ty).getFixedValue();820 auto I = lower_bound(FloatSpecs, BitWidth, LessPrimitiveBitWidth());821 if (I != FloatSpecs.end() && I->BitWidth == BitWidth)822 return abi_or_pref ? I->ABIAlign : I->PrefAlign;823 824 // If we still couldn't find a reasonable default alignment, fall back825 // to a simple heuristic that the alignment is the first power of two826 // greater-or-equal to the store size of the type. This is a reasonable827 // approximation of reality, and if the user wanted something less828 // less conservative, they should have specified it explicitly in the data829 // layout.830 return Align(PowerOf2Ceil(BitWidth / 8));831 }832 case Type::FixedVectorTyID:833 case Type::ScalableVectorTyID: {834 unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinValue();835 auto I = lower_bound(VectorSpecs, BitWidth, LessPrimitiveBitWidth());836 if (I != VectorSpecs.end() && I->BitWidth == BitWidth)837 return abi_or_pref ? I->ABIAlign : I->PrefAlign;838 839 // By default, use natural alignment for vector types. This is consistent840 // with what clang and llvm-gcc do.841 //842 // We're only calculating a natural alignment, so it doesn't have to be843 // based on the full size for scalable vectors. Using the minimum element844 // count should be enough here.845 return Align(PowerOf2Ceil(getTypeStoreSize(Ty).getKnownMinValue()));846 }847 case Type::X86_AMXTyID:848 return Align(64);849 case Type::TargetExtTyID: {850 Type *LayoutTy = cast<TargetExtType>(Ty)->getLayoutType();851 return getAlignment(LayoutTy, abi_or_pref);852 }853 default:854 llvm_unreachable("Bad type for getAlignment!!!");855 }856}857 858TypeSize DataLayout::getTypeAllocSize(Type *Ty) const {859 switch (Ty->getTypeID()) {860 case Type::ArrayTyID: {861 // The alignment of the array is the alignment of the element, so there862 // is no need for further adjustment.863 auto *ATy = cast<ArrayType>(Ty);864 return ATy->getNumElements() * getTypeAllocSize(ATy->getElementType());865 }866 case Type::StructTyID: {867 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));868 TypeSize Size = Layout->getSizeInBytes();869 870 if (cast<StructType>(Ty)->isPacked())871 return Size;872 873 Align A = std::max(StructABIAlignment, Layout->getAlignment());874 return alignTo(Size, A.value());875 }876 case Type::IntegerTyID: {877 unsigned BitWidth = Ty->getIntegerBitWidth();878 TypeSize Size = TypeSize::getFixed(divideCeil(BitWidth, 8));879 Align A = getIntegerAlignment(BitWidth, /*ABI=*/true);880 return alignTo(Size, A.value());881 }882 case Type::PointerTyID: {883 unsigned AS = Ty->getPointerAddressSpace();884 TypeSize Size = TypeSize::getFixed(getPointerSize(AS));885 return alignTo(Size, getPointerABIAlignment(AS).value());886 }887 case Type::TargetExtTyID: {888 Type *LayoutTy = cast<TargetExtType>(Ty)->getLayoutType();889 return getTypeAllocSize(LayoutTy);890 }891 default:892 return alignTo(getTypeStoreSize(Ty), getABITypeAlign(Ty).value());893 }894}895 896Align DataLayout::getABITypeAlign(Type *Ty) const {897 return getAlignment(Ty, true);898}899 900Align DataLayout::getPrefTypeAlign(Type *Ty) const {901 return getAlignment(Ty, false);902}903 904IntegerType *DataLayout::getIntPtrType(LLVMContext &C,905 unsigned AddressSpace) const {906 return IntegerType::get(C, getPointerSizeInBits(AddressSpace));907}908 909Type *DataLayout::getIntPtrType(Type *Ty) const {910 assert(Ty->isPtrOrPtrVectorTy() &&911 "Expected a pointer or pointer vector type.");912 unsigned NumBits = getPointerTypeSizeInBits(Ty);913 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);914 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))915 return VectorType::get(IntTy, VecTy);916 return IntTy;917}918 919Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {920 for (unsigned LegalIntWidth : LegalIntWidths)921 if (Width <= LegalIntWidth)922 return Type::getIntNTy(C, LegalIntWidth);923 return nullptr;924}925 926unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {927 auto Max = llvm::max_element(LegalIntWidths);928 return Max != LegalIntWidths.end() ? *Max : 0;929}930 931IntegerType *DataLayout::getIndexType(LLVMContext &C,932 unsigned AddressSpace) const {933 return IntegerType::get(C, getIndexSizeInBits(AddressSpace));934}935 936Type *DataLayout::getIndexType(Type *Ty) const {937 assert(Ty->isPtrOrPtrVectorTy() &&938 "Expected a pointer or pointer vector type.");939 unsigned NumBits = getIndexTypeSizeInBits(Ty);940 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);941 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))942 return VectorType::get(IntTy, VecTy);943 return IntTy;944}945 946int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,947 ArrayRef<Value *> Indices) const {948 int64_t Result = 0;949 950 generic_gep_type_iterator<Value* const*>951 GTI = gep_type_begin(ElemTy, Indices),952 GTE = gep_type_end(ElemTy, Indices);953 for (; GTI != GTE; ++GTI) {954 Value *Idx = GTI.getOperand();955 if (StructType *STy = GTI.getStructTypeOrNull()) {956 assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");957 unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();958 959 // Get structure layout information...960 const StructLayout *Layout = getStructLayout(STy);961 962 // Add in the offset, as calculated by the structure layout info...963 Result += Layout->getElementOffset(FieldNo);964 } else {965 if (int64_t ArrayIdx = cast<ConstantInt>(Idx)->getSExtValue())966 Result += ArrayIdx * GTI.getSequentialElementStride(*this);967 }968 }969 970 return Result;971}972 973static APInt getElementIndex(TypeSize ElemSize, APInt &Offset) {974 // Skip over scalable or zero size elements. Also skip element sizes larger975 // than the positive index space, because the arithmetic below may not be976 // correct in that case.977 unsigned BitWidth = Offset.getBitWidth();978 if (ElemSize.isScalable() || ElemSize == 0 ||979 !isUIntN(BitWidth - 1, ElemSize)) {980 return APInt::getZero(BitWidth);981 }982 983 uint64_t FixedElemSize = ElemSize.getFixedValue();984 APInt Index = Offset.sdiv(FixedElemSize);985 Offset -= Index * FixedElemSize;986 if (Offset.isNegative()) {987 // Prefer a positive remaining offset to allow struct indexing.988 --Index;989 Offset += FixedElemSize;990 assert(Offset.isNonNegative() && "Remaining offset shouldn't be negative");991 }992 return Index;993}994 995std::optional<APInt> DataLayout::getGEPIndexForOffset(Type *&ElemTy,996 APInt &Offset) const {997 if (auto *ArrTy = dyn_cast<ArrayType>(ElemTy)) {998 ElemTy = ArrTy->getElementType();999 return getElementIndex(getTypeAllocSize(ElemTy), Offset);1000 }1001 1002 if (isa<VectorType>(ElemTy)) {1003 // Vector GEPs are partially broken (e.g. for overaligned element types),1004 // and may be forbidden in the future, so avoid generating GEPs into1005 // vectors. See https://discourse.llvm.org/t/674971006 return std::nullopt;1007 }1008 1009 if (auto *STy = dyn_cast<StructType>(ElemTy)) {1010 const StructLayout *SL = getStructLayout(STy);1011 uint64_t IntOffset = Offset.getZExtValue();1012 if (IntOffset >= SL->getSizeInBytes())1013 return std::nullopt;1014 1015 unsigned Index = SL->getElementContainingOffset(IntOffset);1016 Offset -= SL->getElementOffset(Index);1017 ElemTy = STy->getElementType(Index);1018 return APInt(32, Index);1019 }1020 1021 // Non-aggregate type.1022 return std::nullopt;1023}1024 1025SmallVector<APInt> DataLayout::getGEPIndicesForOffset(Type *&ElemTy,1026 APInt &Offset) const {1027 assert(ElemTy->isSized() && "Element type must be sized");1028 SmallVector<APInt> Indices;1029 Indices.push_back(getElementIndex(getTypeAllocSize(ElemTy), Offset));1030 while (Offset != 0) {1031 std::optional<APInt> Index = getGEPIndexForOffset(ElemTy, Offset);1032 if (!Index)1033 break;1034 Indices.push_back(*Index);1035 }1036 1037 return Indices;1038}1039 1040/// getPreferredAlign - Return the preferred alignment of the specified global.1041/// This includes an explicitly requested alignment (if the global has one).1042Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {1043 MaybeAlign GVAlignment = GV->getAlign();1044 // If a section is specified, always precisely honor explicit alignment,1045 // so we don't insert padding into a section we don't control.1046 if (GVAlignment && GV->hasSection())1047 return *GVAlignment;1048 1049 // If no explicit alignment is specified, compute the alignment based on1050 // the IR type. If an alignment is specified, increase it to match the ABI1051 // alignment of the IR type.1052 //1053 // FIXME: Not sure it makes sense to use the alignment of the type if1054 // there's already an explicit alignment specification.1055 Type *ElemType = GV->getValueType();1056 Align Alignment = getPrefTypeAlign(ElemType);1057 if (GVAlignment) {1058 if (*GVAlignment >= Alignment)1059 Alignment = *GVAlignment;1060 else1061 Alignment = std::max(*GVAlignment, getABITypeAlign(ElemType));1062 }1063 1064 // If no explicit alignment is specified, and the global is large, increase1065 // the alignment to 16.1066 // FIXME: Why 16, specifically?1067 if (GV->hasInitializer() && !GVAlignment) {1068 if (Alignment < Align(16)) {1069 // If the global is not external, see if it is large. If so, give it a1070 // larger alignment.1071 if (getTypeSizeInBits(ElemType) > 128)1072 Alignment = Align(16); // 16-byte alignment.1073 }1074 }1075 return Alignment;1076}1077