llvm/lib/IR/DataLayout.cpp

   1 //===- DataLayout.cpp - Data size & alignment routines ---------------------==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines layout properties related to datatype size/offset/alignment
  10 // information.
  11 //
  12 // This structure should be created once, filled in if the defaults are not
  13 // correct and then passed around by const&.  None of the members functions
  14 // require modification to the object.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/IR/DataLayout.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/IR/Constants.h"
  22 #include "llvm/IR/DerivedTypes.h"
  23 #include "llvm/IR/GetElementPtrTypeIterator.h"
  24 #include "llvm/IR/GlobalVariable.h"
  25 #include "llvm/IR/Module.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
  42 using namespace llvm;
  43
  44 //===----------------------------------------------------------------------===//
  45 // Support for StructLayout
  46 //===----------------------------------------------------------------------===//
  47
  48 StructLayout::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 homogeneous
  64     // scalable vector types. Homogeneous scalable vector types have members of
  65     // the same data type so no alignment issue will happen. The condition here
  66     // assumes so and needs to be adjusted if this assumption changes (e.g. we
  67     // support structures with arbitrary scalable data type, or structure that
  68     // 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 item
  79     StructSize += DL.getTypeAllocSize(Ty);
  80   }
  81
  82   // Add padding to the end of the struct so that it could be put in an array
  83   // 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.
  92 unsigned 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 =
 100       std::upper_bound(MemberOffsets.begin(), MemberOffsets.end(), Offset,
 101                        [](TypeSize LHS, TypeSize RHS) -> bool {
 102                          return TypeSize::isKnownLT(LHS, RHS);
 103                        });
 104   assert(SI != MemberOffsets.begin() && "Offset not in structure type!");
 105   --SI;
 106   assert(TypeSize::isKnownLE(*SI, Offset) && "upper_bound didn't work");
 107   assert(
 108       (SI == MemberOffsets.begin() || TypeSize::isKnownLE(*(SI - 1), Offset)) &&
 109       (SI + 1 == MemberOffsets.end() ||
 110        TypeSize::isKnownGT(*(SI + 1), Offset)) &&
 111       "Upper bound didn't work!");
 112
 113   // Multiple fields can have the same offset if any of them are zero sized.
 114   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
 115   // at the i32 element, because it is the last element at that offset.  This is
 116   // the right one to return, because anything after it will have a higher
 117   // offset, implying that this element is non-empty.
 118   return SI - MemberOffsets.begin();
 119 }
 120
 121 //===----------------------------------------------------------------------===//
 122 // LayoutAlignElem, LayoutAlign support
 123 //===----------------------------------------------------------------------===//
 124
 125 LayoutAlignElem LayoutAlignElem::get(Align ABIAlign, Align PrefAlign,
 126                                      uint32_t BitWidth) {
 127   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 128   LayoutAlignElem retval;
 129   retval.ABIAlign = ABIAlign;
 130   retval.PrefAlign = PrefAlign;
 131   retval.TypeBitWidth = BitWidth;
 132   return retval;
 133 }
 134
 135 bool LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 136   return ABIAlign == rhs.ABIAlign && PrefAlign == rhs.PrefAlign &&
 137          TypeBitWidth == rhs.TypeBitWidth;
 138 }
 139
 140 //===----------------------------------------------------------------------===//
 141 // PointerAlignElem, PointerAlign support
 142 //===----------------------------------------------------------------------===//
 143
 144 PointerAlignElem PointerAlignElem::getInBits(uint32_t AddressSpace,
 145                                              Align ABIAlign, Align PrefAlign,
 146                                              uint32_t TypeBitWidth,
 147                                              uint32_t IndexBitWidth) {
 148   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 149   PointerAlignElem retval;
 150   retval.AddressSpace = AddressSpace;
 151   retval.ABIAlign = ABIAlign;
 152   retval.PrefAlign = PrefAlign;
 153   retval.TypeBitWidth = TypeBitWidth;
 154   retval.IndexBitWidth = IndexBitWidth;
 155   return retval;
 156 }
 157
 158 bool
 159 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
 160   return (ABIAlign == rhs.ABIAlign && AddressSpace == rhs.AddressSpace &&
 161           PrefAlign == rhs.PrefAlign && TypeBitWidth == rhs.TypeBitWidth &&
 162           IndexBitWidth == rhs.IndexBitWidth);
 163 }
 164
 165 //===----------------------------------------------------------------------===//
 166 //                       DataLayout Class Implementation
 167 //===----------------------------------------------------------------------===//
 168
 169 const char *DataLayout::getManglingComponent(const Triple &T) {
 170   if (T.isOSBinFormatGOFF())
 171     return "-m:l";
 172   if (T.isOSBinFormatMachO())
 173     return "-m:o";
 174   if ((T.isOSWindows() || T.isUEFI()) && T.isOSBinFormatCOFF())
 175     return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
 176   if (T.isOSBinFormatXCOFF())
 177     return "-m:a";
 178   return "-m:e";
 179 }
 180
 181 static const std::pair<AlignTypeEnum, LayoutAlignElem> DefaultAlignments[] = {
 182     {INTEGER_ALIGN, {1, Align(1), Align(1)}},    // i1
 183     {INTEGER_ALIGN, {8, Align(1), Align(1)}},    // i8
 184     {INTEGER_ALIGN, {16, Align(2), Align(2)}},   // i16
 185     {INTEGER_ALIGN, {32, Align(4), Align(4)}},   // i32
 186     {INTEGER_ALIGN, {64, Align(4), Align(8)}},   // i64
 187     {FLOAT_ALIGN, {16, Align(2), Align(2)}},     // half, bfloat
 188     {FLOAT_ALIGN, {32, Align(4), Align(4)}},     // float
 189     {FLOAT_ALIGN, {64, Align(8), Align(8)}},     // double
 190     {FLOAT_ALIGN, {128, Align(16), Align(16)}},  // ppcf128, quad, ...
 191     {VECTOR_ALIGN, {64, Align(8), Align(8)}},    // v2i32, v1i64, ...
 192     {VECTOR_ALIGN, {128, Align(16), Align(16)}}, // v16i8, v8i16, v4i32, ...
 193 };
 194
 195 void DataLayout::reset(StringRef Desc) {
 196   clear();
 197
 198   LayoutMap = nullptr;
 199   BigEndian = false;
 200   AllocaAddrSpace = 0;
 201   StackNaturalAlign.reset();
 202   ProgramAddrSpace = 0;
 203   DefaultGlobalsAddrSpace = 0;
 204   FunctionPtrAlign.reset();
 205   TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
 206   ManglingMode = MM_None;
 207   NonIntegralAddressSpaces.clear();
 208   StructAlignment = LayoutAlignElem::get(Align(1), Align(8), 0);
 209
 210   // Default alignments
 211   for (const auto &[Kind, Layout] : DefaultAlignments) {
 212     if (Error Err = setAlignment(Kind, Layout.ABIAlign, Layout.PrefAlign,
 213                                  Layout.TypeBitWidth))
 214       return report_fatal_error(std::move(Err));
 215   }
 216   if (Error Err = setPointerAlignmentInBits(0, Align(8), Align(8), 64, 64))
 217     return report_fatal_error(std::move(Err));
 218
 219   if (Error Err = parseSpecifier(Desc))
 220     return report_fatal_error(std::move(Err));
 221 }
 222
 223 Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) {
 224   DataLayout Layout("");
 225   if (Error Err = Layout.parseSpecifier(LayoutDescription))
 226     return std::move(Err);
 227   return Layout;
 228 }
 229
 230 static Error reportError(const Twine &Message) {
 231   return createStringError(inconvertibleErrorCode(), Message);
 232 }
 233
 234 /// Checked version of split, to ensure mandatory subparts.
 235 static Error split(StringRef Str, char Separator,
 236                    std::pair<StringRef, StringRef> &Split) {
 237   assert(!Str.empty() && "parse error, string can't be empty here");
 238   Split = Str.split(Separator);
 239   if (Split.second.empty() && Split.first != Str)
 240     return reportError("Trailing separator in datalayout string");
 241   if (!Split.second.empty() && Split.first.empty())
 242     return reportError("Expected token before separator in datalayout string");
 243   return Error::success();
 244 }
 245
 246 /// Get an unsigned integer, including error checks.
 247 template <typename IntTy> static Error getInt(StringRef R, IntTy &Result) {
 248   bool error = R.getAsInteger(10, Result); (void)error;
 249   if (error)
 250     return reportError("not a number, or does not fit in an unsigned int");
 251   return Error::success();
 252 }
 253
 254 /// Get an unsigned integer representing the number of bits and convert it into
 255 /// bytes. Error out of not a byte width multiple.
 256 template <typename IntTy>
 257 static Error getIntInBytes(StringRef R, IntTy &Result) {
 258   if (Error Err = getInt<IntTy>(R, Result))
 259     return Err;
 260   if (Result % 8)
 261     return reportError("number of bits must be a byte width multiple");
 262   Result /= 8;
 263   return Error::success();
 264 }
 265
 266 static Error getAddrSpace(StringRef R, unsigned &AddrSpace) {
 267   if (Error Err = getInt(R, AddrSpace))
 268     return Err;
 269   if (!isUInt<24>(AddrSpace))
 270     return reportError("Invalid address space, must be a 24-bit integer");
 271   return Error::success();
 272 }
 273
 274 Error DataLayout::parseSpecifier(StringRef Desc) {
 275   StringRepresentation = std::string(Desc);
 276   while (!Desc.empty()) {
 277     // Split at '-'.
 278     std::pair<StringRef, StringRef> Split;
 279     if (Error Err = ::split(Desc, '-', Split))
 280       return Err;
 281     Desc = Split.second;
 282
 283     // Split at ':'.
 284     if (Error Err = ::split(Split.first, ':', Split))
 285       return Err;
 286
 287     // Aliases used below.
 288     StringRef &Tok  = Split.first;  // Current token.
 289     StringRef &Rest = Split.second; // The rest of the string.
 290
 291     if (Tok == "ni") {
 292       do {
 293         if (Error Err = ::split(Rest, ':', Split))
 294           return Err;
 295         Rest = Split.second;
 296         unsigned AS;
 297         if (Error Err = getInt(Split.first, AS))
 298           return Err;
 299         if (AS == 0)
 300           return reportError("Address space 0 can never be non-integral");
 301         NonIntegralAddressSpaces.push_back(AS);
 302       } while (!Rest.empty());
 303
 304       continue;
 305     }
 306
 307     char Specifier = Tok.front();
 308     Tok = Tok.substr(1);
 309
 310     switch (Specifier) {
 311     case 's':
 312       // Deprecated, but ignoring here to preserve loading older textual llvm
 313       // ASM file
 314       break;
 315     case 'E':
 316       BigEndian = true;
 317       break;
 318     case 'e':
 319       BigEndian = false;
 320       break;
 321     case 'p': {
 322       // Address space.
 323       unsigned AddrSpace = 0;
 324       if (!Tok.empty())
 325         if (Error Err = getInt(Tok, AddrSpace))
 326           return Err;
 327       if (!isUInt<24>(AddrSpace))
 328         return reportError("Invalid address space, must be a 24-bit integer");
 329
 330       // Size.
 331       if (Rest.empty())
 332         return reportError(
 333             "Missing size specification for pointer in datalayout string");
 334       if (Error Err = ::split(Rest, ':', Split))
 335         return Err;
 336       unsigned PointerMemSize;
 337       if (Error Err = getInt(Tok, PointerMemSize))
 338         return Err;
 339       if (!PointerMemSize)
 340         return reportError("Invalid pointer size of 0 bytes");
 341
 342       // ABI alignment.
 343       if (Rest.empty())
 344         return reportError(
 345             "Missing alignment specification for pointer in datalayout string");
 346       if (Error Err = ::split(Rest, ':', Split))
 347         return Err;
 348       unsigned PointerABIAlign;
 349       if (Error Err = getIntInBytes(Tok, PointerABIAlign))
 350         return Err;
 351       if (!isPowerOf2_64(PointerABIAlign))
 352         return reportError("Pointer ABI alignment must be a power of 2");
 353
 354       // Size of index used in GEP for address calculation.
 355       // The parameter is optional. By default it is equal to size of pointer.
 356       unsigned IndexSize = PointerMemSize;
 357
 358       // Preferred alignment.
 359       unsigned PointerPrefAlign = PointerABIAlign;
 360       if (!Rest.empty()) {
 361         if (Error Err = ::split(Rest, ':', Split))
 362           return Err;
 363         if (Error Err = getIntInBytes(Tok, PointerPrefAlign))
 364           return Err;
 365         if (!isPowerOf2_64(PointerPrefAlign))
 366           return reportError(
 367               "Pointer preferred alignment must be a power of 2");
 368
 369         // Now read the index. It is the second optional parameter here.
 370         if (!Rest.empty()) {
 371           if (Error Err = ::split(Rest, ':', Split))
 372             return Err;
 373           if (Error Err = getInt(Tok, IndexSize))
 374             return Err;
 375           if (!IndexSize)
 376             return reportError("Invalid index size of 0 bytes");
 377         }
 378       }
 379       if (Error Err = setPointerAlignmentInBits(
 380               AddrSpace, assumeAligned(PointerABIAlign),
 381               assumeAligned(PointerPrefAlign), PointerMemSize, IndexSize))
 382         return Err;
 383       break;
 384     }
 385     case 'i':
 386     case 'v':
 387     case 'f':
 388     case 'a': {
 389       AlignTypeEnum AlignType;
 390       switch (Specifier) {
 391       default: llvm_unreachable("Unexpected specifier!");
 392       case 'i': AlignType = INTEGER_ALIGN; break;
 393       case 'v': AlignType = VECTOR_ALIGN; break;
 394       case 'f': AlignType = FLOAT_ALIGN; break;
 395       case 'a': AlignType = AGGREGATE_ALIGN; break;
 396       }
 397
 398       // Bit size.
 399       unsigned Size = 0;
 400       if (!Tok.empty())
 401         if (Error Err = getInt(Tok, Size))
 402           return Err;
 403
 404       if (AlignType == AGGREGATE_ALIGN && Size != 0)
 405         return reportError(
 406             "Sized aggregate specification in datalayout string");
 407
 408       // ABI alignment.
 409       if (Rest.empty())
 410         return reportError(
 411             "Missing alignment specification in datalayout string");
 412       if (Error Err = ::split(Rest, ':', Split))
 413         return Err;
 414       unsigned ABIAlign;
 415       if (Error Err = getIntInBytes(Tok, ABIAlign))
 416         return Err;
 417       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
 418         return reportError(
 419             "ABI alignment specification must be >0 for non-aggregate types");
 420
 421       if (!isUInt<16>(ABIAlign))
 422         return reportError("Invalid ABI alignment, must be a 16bit integer");
 423       if (ABIAlign != 0 && !isPowerOf2_64(ABIAlign))
 424         return reportError("Invalid ABI alignment, must be a power of 2");
 425       if (AlignType == INTEGER_ALIGN && Size == 8 && ABIAlign != 1)
 426         return reportError(
 427             "Invalid ABI alignment, i8 must be naturally aligned");
 428
 429       // Preferred alignment.
 430       unsigned PrefAlign = ABIAlign;
 431       if (!Rest.empty()) {
 432         if (Error Err = ::split(Rest, ':', Split))
 433           return Err;
 434         if (Error Err = getIntInBytes(Tok, PrefAlign))
 435           return Err;
 436       }
 437
 438       if (!isUInt<16>(PrefAlign))
 439         return reportError(
 440             "Invalid preferred alignment, must be a 16bit integer");
 441       if (PrefAlign != 0 && !isPowerOf2_64(PrefAlign))
 442         return reportError("Invalid preferred alignment, must be a power of 2");
 443
 444       if (Error Err = setAlignment(AlignType, assumeAligned(ABIAlign),
 445                                    assumeAligned(PrefAlign), Size))
 446         return Err;
 447
 448       break;
 449     }
 450     case 'n':  // Native integer types.
 451       while (true) {
 452         unsigned Width;
 453         if (Error Err = getInt(Tok, Width))
 454           return Err;
 455         if (Width == 0)
 456           return reportError(
 457               "Zero width native integer type in datalayout string");
 458         LegalIntWidths.push_back(Width);
 459         if (Rest.empty())
 460           break;
 461         if (Error Err = ::split(Rest, ':', Split))
 462           return Err;
 463       }
 464       break;
 465     case 'S': { // Stack natural alignment.
 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       StackNaturalAlign = MaybeAlign(Alignment);
 472       break;
 473     }
 474     case 'F': {
 475       switch (Tok.front()) {
 476       case 'i':
 477         TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
 478         break;
 479       case 'n':
 480         TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;
 481         break;
 482       default:
 483         return reportError("Unknown function pointer alignment type in "
 484                            "datalayout string");
 485       }
 486       Tok = Tok.substr(1);
 487       uint64_t Alignment;
 488       if (Error Err = getIntInBytes(Tok, Alignment))
 489         return Err;
 490       if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
 491         return reportError("Alignment is neither 0 nor a power of 2");
 492       FunctionPtrAlign = MaybeAlign(Alignment);
 493       break;
 494     }
 495     case 'P': { // Function address space.
 496       if (Error Err = getAddrSpace(Tok, ProgramAddrSpace))
 497         return Err;
 498       break;
 499     }
 500     case 'A': { // Default stack/alloca address space.
 501       if (Error Err = getAddrSpace(Tok, AllocaAddrSpace))
 502         return Err;
 503       break;
 504     }
 505     case 'G': { // Default address space for global variables.
 506       if (Error Err = getAddrSpace(Tok, DefaultGlobalsAddrSpace))
 507         return Err;
 508       break;
 509     }
 510     case 'm':
 511       if (!Tok.empty())
 512         return reportError("Unexpected trailing characters after mangling "
 513                            "specifier in datalayout string");
 514       if (Rest.empty())
 515         return reportError("Expected mangling specifier in datalayout string");
 516       if (Rest.size() > 1)
 517         return reportError("Unknown mangling specifier in datalayout string");
 518       switch(Rest[0]) {
 519       default:
 520         return reportError("Unknown mangling in datalayout string");
 521       case 'e':
 522         ManglingMode = MM_ELF;
 523         break;
 524       case 'l':
 525         ManglingMode = MM_GOFF;
 526         break;
 527       case 'o':
 528         ManglingMode = MM_MachO;
 529         break;
 530       case 'm':
 531         ManglingMode = MM_Mips;
 532         break;
 533       case 'w':
 534         ManglingMode = MM_WinCOFF;
 535         break;
 536       case 'x':
 537         ManglingMode = MM_WinCOFFX86;
 538         break;
 539       case 'a':
 540         ManglingMode = MM_XCOFF;
 541         break;
 542       }
 543       break;
 544     default:
 545       return reportError("Unknown specifier in datalayout string");
 546       break;
 547     }
 548   }
 549
 550   return Error::success();
 551 }
 552
 553 DataLayout::DataLayout(const Module *M) {
 554   init(M);
 555 }
 556
 557 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 558
 559 bool DataLayout::operator==(const DataLayout &Other) const {
 560   bool Ret = BigEndian == Other.BigEndian &&
 561              AllocaAddrSpace == Other.AllocaAddrSpace &&
 562              StackNaturalAlign == Other.StackNaturalAlign &&
 563              ProgramAddrSpace == Other.ProgramAddrSpace &&
 564              DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace &&
 565              FunctionPtrAlign == Other.FunctionPtrAlign &&
 566              TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&
 567              ManglingMode == Other.ManglingMode &&
 568              LegalIntWidths == Other.LegalIntWidths &&
 569              IntAlignments == Other.IntAlignments &&
 570              FloatAlignments == Other.FloatAlignments &&
 571              VectorAlignments == Other.VectorAlignments &&
 572              StructAlignment == Other.StructAlignment &&
 573              Pointers == Other.Pointers;
 574   // Note: getStringRepresentation() might differs, it is not canonicalized
 575   return Ret;
 576 }
 577
 578 static SmallVectorImpl<LayoutAlignElem>::const_iterator
 579 findAlignmentLowerBound(const SmallVectorImpl<LayoutAlignElem> &Alignments,
 580                         uint32_t BitWidth) {
 581   return partition_point(Alignments, [BitWidth](const LayoutAlignElem &E) {
 582     return E.TypeBitWidth < BitWidth;
 583   });
 584 }
 585
 586 Error DataLayout::setAlignment(AlignTypeEnum AlignType, Align ABIAlign,
 587                                Align PrefAlign, uint32_t BitWidth) {
 588   // AlignmentsTy::ABIAlign and AlignmentsTy::PrefAlign were once stored as
 589   // uint16_t, it is unclear if there are requirements for alignment to be less
 590   // than 2^16 other than storage. In the meantime we leave the restriction as
 591   // an assert. See D67400 for context.
 592   assert(Log2(ABIAlign) < 16 && Log2(PrefAlign) < 16 && "Alignment too big");
 593   if (!isUInt<24>(BitWidth))
 594     return reportError("Invalid bit width, must be a 24-bit integer");
 595   if (PrefAlign < ABIAlign)
 596     return reportError(
 597         "Preferred alignment cannot be less than the ABI alignment");
 598
 599   SmallVectorImpl<LayoutAlignElem> *Alignments;
 600   switch (AlignType) {
 601   case AGGREGATE_ALIGN:
 602     StructAlignment.ABIAlign = ABIAlign;
 603     StructAlignment.PrefAlign = PrefAlign;
 604     return Error::success();
 605   case INTEGER_ALIGN:
 606     Alignments = &IntAlignments;
 607     break;
 608   case FLOAT_ALIGN:
 609     Alignments = &FloatAlignments;
 610     break;
 611   case VECTOR_ALIGN:
 612     Alignments = &VectorAlignments;
 613     break;
 614   }
 615
 616   auto I = partition_point(*Alignments, [BitWidth](const LayoutAlignElem &E) {
 617     return E.TypeBitWidth < BitWidth;
 618   });
 619   if (I != Alignments->end() && I->TypeBitWidth == BitWidth) {
 620     // Update the abi, preferred alignments.
 621     I->ABIAlign = ABIAlign;
 622     I->PrefAlign = PrefAlign;
 623   } else {
 624     // Insert before I to keep the vector sorted.
 625     Alignments->insert(I, LayoutAlignElem::get(ABIAlign, PrefAlign, BitWidth));
 626   }
 627   return Error::success();
 628 }
 629
 630 const PointerAlignElem &
 631 DataLayout::getPointerAlignElem(uint32_t AddressSpace) const {
 632   if (AddressSpace != 0) {
 633     auto I = lower_bound(Pointers, AddressSpace,
 634                          [](const PointerAlignElem &A, uint32_t AddressSpace) {
 635       return A.AddressSpace < AddressSpace;
 636     });
 637     if (I != Pointers.end() && I->AddressSpace == AddressSpace)
 638       return *I;
 639   }
 640
 641   assert(Pointers[0].AddressSpace == 0);
 642   return Pointers[0];
 643 }
 644
 645 Error DataLayout::setPointerAlignmentInBits(uint32_t AddrSpace, Align ABIAlign,
 646                                             Align PrefAlign,
 647                                             uint32_t TypeBitWidth,
 648                                             uint32_t IndexBitWidth) {
 649   if (PrefAlign < ABIAlign)
 650     return reportError(
 651         "Preferred alignment cannot be less than the ABI alignment");
 652   if (IndexBitWidth > TypeBitWidth)
 653     return reportError("Index width cannot be larger than pointer width");
 654
 655   auto I = lower_bound(Pointers, AddrSpace,
 656                        [](const PointerAlignElem &A, uint32_t AddressSpace) {
 657     return A.AddressSpace < AddressSpace;
 658   });
 659   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 660     Pointers.insert(I,
 661                     PointerAlignElem::getInBits(AddrSpace, ABIAlign, PrefAlign,
 662                                                 TypeBitWidth, IndexBitWidth));
 663   } else {
 664     I->ABIAlign = ABIAlign;
 665     I->PrefAlign = PrefAlign;
 666     I->TypeBitWidth = TypeBitWidth;
 667     I->IndexBitWidth = IndexBitWidth;
 668   }
 669   return Error::success();
 670 }
 671
 672 Align DataLayout::getIntegerAlignment(uint32_t BitWidth,
 673                                       bool abi_or_pref) const {
 674   auto I = findAlignmentLowerBound(IntAlignments, BitWidth);
 675   // If we don't have an exact match, use alignment of next larger integer
 676   // type. If there is none, use alignment of largest integer type by going
 677   // back one element.
 678   if (I == IntAlignments.end())
 679     --I;
 680   return abi_or_pref ? I->ABIAlign : I->PrefAlign;
 681 }
 682
 683 namespace {
 684
 685 class StructLayoutMap {
 686   using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
 687   LayoutInfoTy LayoutInfo;
 688
 689 public:
 690   ~StructLayoutMap() {
 691     // Remove any layouts.
 692     for (const auto &I : LayoutInfo) {
 693       StructLayout *Value = I.second;
 694       Value->~StructLayout();
 695       free(Value);
 696     }
 697   }
 698
 699   StructLayout *&operator[](StructType *STy) {
 700     return LayoutInfo[STy];
 701   }
 702 };
 703
 704 } // end anonymous namespace
 705
 706 void DataLayout::clear() {
 707   LegalIntWidths.clear();
 708   IntAlignments.clear();
 709   FloatAlignments.clear();
 710   VectorAlignments.clear();
 711   Pointers.clear();
 712   delete static_cast<StructLayoutMap *>(LayoutMap);
 713   LayoutMap = nullptr;
 714 }
 715
 716 DataLayout::~DataLayout() {
 717   clear();
 718 }
 719
 720 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 721   if (!LayoutMap)
 722     LayoutMap = new StructLayoutMap();
 723
 724   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 725   StructLayout *&SL = (*STM)[Ty];
 726   if (SL) return SL;
 727
 728   // Otherwise, create the struct layout.  Because it is variable length, we
 729   // malloc it, then use placement new.
 730   StructLayout *L = (StructLayout *)safe_malloc(
 731       StructLayout::totalSizeToAlloc<TypeSize>(Ty->getNumElements()));
 732
 733   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 734   // entries to be added to TheMap, invalidating our reference.
 735   SL = L;
 736
 737   new (L) StructLayout(Ty, *this);
 738
 739   return L;
 740 }
 741
 742 Align DataLayout::getPointerABIAlignment(unsigned AS) const {
 743   return getPointerAlignElem(AS).ABIAlign;
 744 }
 745
 746 Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
 747   return getPointerAlignElem(AS).PrefAlign;
 748 }
 749
 750 unsigned DataLayout::getPointerSize(unsigned AS) const {
 751   return divideCeil(getPointerAlignElem(AS).TypeBitWidth, 8);
 752 }
 753
 754 unsigned DataLayout::getMaxIndexSize() const {
 755   unsigned MaxIndexSize = 0;
 756   for (auto &P : Pointers)
 757     MaxIndexSize =
 758         std::max(MaxIndexSize, (unsigned)divideCeil(P.TypeBitWidth, 8));
 759
 760   return MaxIndexSize;
 761 }
 762
 763 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 764   assert(Ty->isPtrOrPtrVectorTy() &&
 765          "This should only be called with a pointer or pointer vector type");
 766   Ty = Ty->getScalarType();
 767   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 768 }
 769
 770 unsigned DataLayout::getIndexSize(unsigned AS) const {
 771   return divideCeil(getPointerAlignElem(AS).IndexBitWidth, 8);
 772 }
 773
 774 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
 775   assert(Ty->isPtrOrPtrVectorTy() &&
 776          "This should only be called with a pointer or pointer vector type");
 777   Ty = Ty->getScalarType();
 778   return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 779 }
 780
 781 /*!
 782   \param abi_or_pref Flag that determines which alignment is returned. true
 783   returns the ABI alignment, false returns the preferred alignment.
 784   \param Ty The underlying type for which alignment is determined.
 785
 786   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 787   == false) for the requested type \a Ty.
 788  */
 789 Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 790   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 791   switch (Ty->getTypeID()) {
 792   // Early escape for the non-numeric types.
 793   case Type::LabelTyID:
 794     return abi_or_pref ? getPointerABIAlignment(0) : getPointerPrefAlignment(0);
 795   case Type::PointerTyID: {
 796     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 797     return abi_or_pref ? getPointerABIAlignment(AS)
 798                        : getPointerPrefAlignment(AS);
 799     }
 800   case Type::ArrayTyID:
 801     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 802
 803   case Type::StructTyID: {
 804     // Packed structure types always have an ABI alignment of one.
 805     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 806       return Align(1);
 807
 808     // Get the layout annotation... which is lazily created on demand.
 809     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 810     const Align Align =
 811         abi_or_pref ? StructAlignment.ABIAlign : StructAlignment.PrefAlign;
 812     return std::max(Align, Layout->getAlignment());
 813   }
 814   case Type::IntegerTyID:
 815     return getIntegerAlignment(Ty->getIntegerBitWidth(), abi_or_pref);
 816   case Type::HalfTyID:
 817   case Type::BFloatTyID:
 818   case Type::FloatTyID:
 819   case Type::DoubleTyID:
 820   // PPC_FP128TyID and FP128TyID have different data contents, but the
 821   // same size and alignment, so they look the same here.
 822   case Type::PPC_FP128TyID:
 823   case Type::FP128TyID:
 824   case Type::X86_FP80TyID: {
 825     unsigned BitWidth = getTypeSizeInBits(Ty).getFixedValue();
 826     auto I = findAlignmentLowerBound(FloatAlignments, BitWidth);
 827     if (I != FloatAlignments.end() && I->TypeBitWidth == BitWidth)
 828       return abi_or_pref ? I->ABIAlign : I->PrefAlign;
 829
 830     // If we still couldn't find a reasonable default alignment, fall back
 831     // to a simple heuristic that the alignment is the first power of two
 832     // greater-or-equal to the store size of the type.  This is a reasonable
 833     // approximation of reality, and if the user wanted something less
 834     // less conservative, they should have specified it explicitly in the data
 835     // layout.
 836     return Align(PowerOf2Ceil(BitWidth / 8));
 837   }
 838   case Type::X86_MMXTyID:
 839   case Type::FixedVectorTyID:
 840   case Type::ScalableVectorTyID: {
 841     unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinValue();
 842     auto I = findAlignmentLowerBound(VectorAlignments, BitWidth);
 843     if (I != VectorAlignments.end() && I->TypeBitWidth == BitWidth)
 844       return abi_or_pref ? I->ABIAlign : I->PrefAlign;
 845
 846     // By default, use natural alignment for vector types. This is consistent
 847     // with what clang and llvm-gcc do.
 848     //
 849     // We're only calculating a natural alignment, so it doesn't have to be
 850     // based on the full size for scalable vectors. Using the minimum element
 851     // count should be enough here.
 852     return Align(PowerOf2Ceil(getTypeStoreSize(Ty).getKnownMinValue()));
 853   }
 854   case Type::X86_AMXTyID:
 855     return Align(64);
 856   case Type::TargetExtTyID: {
 857     Type *LayoutTy = cast<TargetExtType>(Ty)->getLayoutType();
 858     return getAlignment(LayoutTy, abi_or_pref);
 859   }
 860   default:
 861     llvm_unreachable("Bad type for getAlignment!!!");
 862   }
 863 }
 864
 865 Align DataLayout::getABITypeAlign(Type *Ty) const {
 866   return getAlignment(Ty, true);
 867 }
 868
 869 /// TODO: Remove this function once the transition to Align is over.
 870 uint64_t DataLayout::getPrefTypeAlignment(Type *Ty) const {
 871   return getPrefTypeAlign(Ty).value();
 872 }
 873
 874 Align DataLayout::getPrefTypeAlign(Type *Ty) const {
 875   return getAlignment(Ty, false);
 876 }
 877
 878 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 879                                        unsigned AddressSpace) const {
 880   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 881 }
 882
 883 Type *DataLayout::getIntPtrType(Type *Ty) const {
 884   assert(Ty->isPtrOrPtrVectorTy() &&
 885          "Expected a pointer or pointer vector type.");
 886   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 887   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 888   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 889     return VectorType::get(IntTy, VecTy);
 890   return IntTy;
 891 }
 892
 893 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 894   for (unsigned LegalIntWidth : LegalIntWidths)
 895     if (Width <= LegalIntWidth)
 896       return Type::getIntNTy(C, LegalIntWidth);
 897   return nullptr;
 898 }
 899
 900 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
 901   auto Max = llvm::max_element(LegalIntWidths);
 902   return Max != LegalIntWidths.end() ? *Max : 0;
 903 }
 904
 905 IntegerType *DataLayout::getIndexType(LLVMContext &C,
 906                                       unsigned AddressSpace) const {
 907   return IntegerType::get(C, getIndexSizeInBits(AddressSpace));
 908 }
 909
 910 Type *DataLayout::getIndexType(Type *Ty) const {
 911   assert(Ty->isPtrOrPtrVectorTy() &&
 912          "Expected a pointer or pointer vector type.");
 913   unsigned NumBits = getIndexTypeSizeInBits(Ty);
 914   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 915   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 916     return VectorType::get(IntTy, VecTy);
 917   return IntTy;
 918 }
 919
 920 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
 921                                            ArrayRef<Value *> Indices) const {
 922   int64_t Result = 0;
 923
 924   generic_gep_type_iterator<Value* const*>
 925     GTI = gep_type_begin(ElemTy, Indices),
 926     GTE = gep_type_end(ElemTy, Indices);
 927   for (; GTI != GTE; ++GTI) {
 928     Value *Idx = GTI.getOperand();
 929     if (StructType *STy = GTI.getStructTypeOrNull()) {
 930       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
 931       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
 932
 933       // Get structure layout information...
 934       const StructLayout *Layout = getStructLayout(STy);
 935
 936       // Add in the offset, as calculated by the structure layout info...
 937       Result += Layout->getElementOffset(FieldNo);
 938     } else {
 939       if (int64_t ArrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
 940         Result += ArrayIdx * GTI.getSequentialElementStride(*this);
 941     }
 942   }
 943
 944   return Result;
 945 }
 946
 947 static APInt getElementIndex(TypeSize ElemSize, APInt &Offset) {
 948   // Skip over scalable or zero size elements. Also skip element sizes larger
 949   // than the positive index space, because the arithmetic below may not be
 950   // correct in that case.
 951   unsigned BitWidth = Offset.getBitWidth();
 952   if (ElemSize.isScalable() || ElemSize == 0 ||
 953       !isUIntN(BitWidth - 1, ElemSize)) {
 954     return APInt::getZero(BitWidth);
 955   }
 956
 957   APInt Index = Offset.sdiv(ElemSize);
 958   Offset -= Index * ElemSize;
 959   if (Offset.isNegative()) {
 960     // Prefer a positive remaining offset to allow struct indexing.
 961     --Index;
 962     Offset += ElemSize;
 963     assert(Offset.isNonNegative() && "Remaining offset shouldn't be negative");
 964   }
 965   return Index;
 966 }
 967
 968 std::optional<APInt> DataLayout::getGEPIndexForOffset(Type *&ElemTy,
 969                                                       APInt &Offset) const {
 970   if (auto *ArrTy = dyn_cast<ArrayType>(ElemTy)) {
 971     ElemTy = ArrTy->getElementType();
 972     return getElementIndex(getTypeAllocSize(ElemTy), Offset);
 973   }
 974
 975   if (isa<VectorType>(ElemTy)) {
 976     // Vector GEPs are partially broken (e.g. for overaligned element types),
 977     // and may be forbidden in the future, so avoid generating GEPs into
 978     // vectors. See https://discourse.llvm.org/t/67497
 979     return std::nullopt;
 980   }
 981
 982   if (auto *STy = dyn_cast<StructType>(ElemTy)) {
 983     const StructLayout *SL = getStructLayout(STy);
 984     uint64_t IntOffset = Offset.getZExtValue();
 985     if (IntOffset >= SL->getSizeInBytes())
 986       return std::nullopt;
 987
 988     unsigned Index = SL->getElementContainingOffset(IntOffset);
 989     Offset -= SL->getElementOffset(Index);
 990     ElemTy = STy->getElementType(Index);
 991     return APInt(32, Index);
 992   }
 993
 994   // Non-aggregate type.
 995   return std::nullopt;
 996 }
 997
 998 SmallVector<APInt> DataLayout::getGEPIndicesForOffset(Type *&ElemTy,
 999                                                       APInt &Offset) const {
1000   assert(ElemTy->isSized() && "Element type must be sized");
1001   SmallVector<APInt> Indices;
1002   Indices.push_back(getElementIndex(getTypeAllocSize(ElemTy), Offset));
1003   while (Offset != 0) {
1004     std::optional<APInt> Index = getGEPIndexForOffset(ElemTy, Offset);
1005     if (!Index)
1006       break;
1007     Indices.push_back(*Index);
1008   }
1009
1010   return Indices;
1011 }
1012
1013 /// getPreferredAlign - Return the preferred alignment of the specified global.
1014 /// This includes an explicitly requested alignment (if the global has one).
1015 Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {
1016   MaybeAlign GVAlignment = GV->getAlign();
1017   // If a section is specified, always precisely honor explicit alignment,
1018   // so we don't insert padding into a section we don't control.
1019   if (GVAlignment && GV->hasSection())
1020     return *GVAlignment;
1021
1022   // If no explicit alignment is specified, compute the alignment based on
1023   // the IR type. If an alignment is specified, increase it to match the ABI
1024   // alignment of the IR type.
1025   //
1026   // FIXME: Not sure it makes sense to use the alignment of the type if
1027   // there's already an explicit alignment specification.
1028   Type *ElemType = GV->getValueType();
1029   Align Alignment = getPrefTypeAlign(ElemType);
1030   if (GVAlignment) {
1031     if (*GVAlignment >= Alignment)
1032       Alignment = *GVAlignment;
1033     else
1034       Alignment = std::max(*GVAlignment, getABITypeAlign(ElemType));
1035   }
1036
1037   // If no explicit alignment is specified, and the global is large, increase
1038   // the alignment to 16.
1039   // FIXME: Why 16, specifically?
1040   if (GV->hasInitializer() && !GVAlignment) {
1041     if (Alignment < Align(16)) {
1042       // If the global is not external, see if it is large.  If so, give it a
1043       // larger alignment.
1044       if (getTypeSizeInBits(ElemType) > 128)
1045         Alignment = Align(16); // 16-byte alignment.
1046     }
1047   }
1048   return Alignment;
1049 }