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/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
  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 namespace {
 122
 123 class StructLayoutMap {
 124   using LayoutInfoTy = DenseMap<StructType *, StructLayout *>;
 125   LayoutInfoTy LayoutInfo;
 126
 127 public:
 128   ~StructLayoutMap() {
 129     // Remove any layouts.
 130     for (const auto &I : LayoutInfo) {
 131       StructLayout *Value = I.second;
 132       Value->~StructLayout();
 133       free(Value);
 134     }
 135   }
 136
 137   StructLayout *&operator[](StructType *STy) { return LayoutInfo[STy]; }
 138 };
 139
 140 } // end anonymous namespace
 141
 142 //===----------------------------------------------------------------------===//
 143 //                       DataLayout Class Implementation
 144 //===----------------------------------------------------------------------===//
 145
 146 bool DataLayout::PrimitiveSpec::operator==(const PrimitiveSpec &Other) const {
 147   return BitWidth == Other.BitWidth && ABIAlign == Other.ABIAlign &&
 148          PrefAlign == Other.PrefAlign;
 149 }
 150
 151 bool DataLayout::PointerSpec::operator==(const PointerSpec &Other) const {
 152   return AddrSpace == Other.AddrSpace && BitWidth == Other.BitWidth &&
 153          ABIAlign == Other.ABIAlign && PrefAlign == Other.PrefAlign &&
 154          IndexBitWidth == Other.IndexBitWidth &&
 155          IsNonIntegral == Other.IsNonIntegral;
 156 }
 157
 158 namespace {
 159 /// Predicate to sort primitive specs by bit width.
 160 struct 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.
 168 struct LessPointerAddrSpace {
 169   bool operator()(const DataLayout::PointerSpec &LHS,
 170                   unsigned RHSAddrSpace) const {
 171     return LHS.AddrSpace < RHSAddrSpace;
 172   }
 173 };
 174 } // namespace
 175
 176 const char *DataLayout::getManglingComponent(const Triple &T) {
 177   if (T.isOSBinFormatGOFF())
 178     return "-m:l";
 179   if (T.isOSBinFormatMachO())
 180     return "-m:o";
 181   if (T.isOSWindowsOrUEFI() && T.isOSBinFormatCOFF())
 182     return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
 183   if (T.isOSBinFormatXCOFF())
 184     return "-m:a";
 185   return "-m:e";
 186 }
 187
 188 // Default primitive type specifications.
 189 // NOTE: These arrays must be sorted by type bit width.
 190 constexpr DataLayout::PrimitiveSpec DefaultIntSpecs[] = {
 191     {1, Align::Constant<1>(), Align::Constant<1>()},  // i1:8:8
 192     {8, Align::Constant<1>(), Align::Constant<1>()},  // i8:8:8
 193     {16, Align::Constant<2>(), Align::Constant<2>()}, // i16:16:16
 194     {32, Align::Constant<4>(), Align::Constant<4>()}, // i32:32:32
 195     {64, Align::Constant<4>(), Align::Constant<8>()}, // i64:32:64
 196 };
 197 constexpr DataLayout::PrimitiveSpec DefaultFloatSpecs[] = {
 198     {16, Align::Constant<2>(), Align::Constant<2>()},    // f16:16:16
 199     {32, Align::Constant<4>(), Align::Constant<4>()},    // f32:32:32
 200     {64, Align::Constant<8>(), Align::Constant<8>()},    // f64:64:64
 201     {128, Align::Constant<16>(), Align::Constant<16>()}, // f128:128:128
 202 };
 203 constexpr DataLayout::PrimitiveSpec DefaultVectorSpecs[] = {
 204     {64, Align::Constant<8>(), Align::Constant<8>()},    // v64:64:64
 205     {128, Align::Constant<16>(), Align::Constant<16>()}, // v128:128:128
 206 };
 207
 208 // Default pointer type specifications.
 209 constexpr DataLayout::PointerSpec DefaultPointerSpecs[] = {
 210     // p0:64:64:64:64
 211     {0, 64, Align::Constant<8>(), Align::Constant<8>(), 64, false},
 212 };
 213
 214 DataLayout::DataLayout()
 215     : IntSpecs(ArrayRef(DefaultIntSpecs)),
 216       FloatSpecs(ArrayRef(DefaultFloatSpecs)),
 217       VectorSpecs(ArrayRef(DefaultVectorSpecs)),
 218       PointerSpecs(ArrayRef(DefaultPointerSpecs)) {}
 219
 220 DataLayout::DataLayout(StringRef LayoutString) : DataLayout() {
 221   if (Error Err = parseLayoutString(LayoutString))
 222     report_fatal_error(std::move(Err));
 223 }
 224
 225 DataLayout &DataLayout::operator=(const DataLayout &Other) {
 226   delete static_cast<StructLayoutMap *>(LayoutMap);
 227   LayoutMap = nullptr;
 228   StringRepresentation = Other.StringRepresentation;
 229   BigEndian = Other.BigEndian;
 230   AllocaAddrSpace = Other.AllocaAddrSpace;
 231   ProgramAddrSpace = Other.ProgramAddrSpace;
 232   DefaultGlobalsAddrSpace = Other.DefaultGlobalsAddrSpace;
 233   StackNaturalAlign = Other.StackNaturalAlign;
 234   FunctionPtrAlign = Other.FunctionPtrAlign;
 235   TheFunctionPtrAlignType = Other.TheFunctionPtrAlignType;
 236   ManglingMode = Other.ManglingMode;
 237   LegalIntWidths = Other.LegalIntWidths;
 238   IntSpecs = Other.IntSpecs;
 239   FloatSpecs = Other.FloatSpecs;
 240   VectorSpecs = Other.VectorSpecs;
 241   PointerSpecs = Other.PointerSpecs;
 242   StructABIAlignment = Other.StructABIAlignment;
 243   StructPrefAlignment = Other.StructPrefAlignment;
 244   return *this;
 245 }
 246
 247 bool DataLayout::operator==(const DataLayout &Other) const {
 248   // NOTE: StringRepresentation might differ, it is not canonicalized.
 249   return BigEndian == Other.BigEndian &&
 250          AllocaAddrSpace == Other.AllocaAddrSpace &&
 251          ProgramAddrSpace == Other.ProgramAddrSpace &&
 252          DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace &&
 253          StackNaturalAlign == Other.StackNaturalAlign &&
 254          FunctionPtrAlign == Other.FunctionPtrAlign &&
 255          TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&
 256          ManglingMode == Other.ManglingMode &&
 257          LegalIntWidths == Other.LegalIntWidths && IntSpecs == Other.IntSpecs &&
 258          FloatSpecs == Other.FloatSpecs && VectorSpecs == Other.VectorSpecs &&
 259          PointerSpecs == Other.PointerSpecs &&
 260          StructABIAlignment == Other.StructABIAlignment &&
 261          StructPrefAlignment == Other.StructPrefAlignment;
 262 }
 263
 264 Expected<DataLayout> DataLayout::parse(StringRef LayoutString) {
 265   DataLayout Layout;
 266   if (Error Err = Layout.parseLayoutString(LayoutString))
 267     return std::move(Err);
 268   return Layout;
 269 }
 270
 271 static Error createSpecFormatError(Twine Format) {
 272   return createStringError("malformed specification, must be of the form \"" +
 273                            Format + "\"");
 274 }
 275
 276 /// Attempts to parse an address space component of a specification.
 277 static Error parseAddrSpace(StringRef Str, unsigned &AddrSpace) {
 278   if (Str.empty())
 279     return createStringError("address space component cannot be empty");
 280
 281   if (!to_integer(Str, AddrSpace, 10) || !isUInt<24>(AddrSpace))
 282     return createStringError("address space must be a 24-bit integer");
 283
 284   return Error::success();
 285 }
 286
 287 /// Attempts to parse a size component of a specification.
 288 static Error parseSize(StringRef Str, unsigned &BitWidth,
 289                        StringRef Name = "size") {
 290   if (Str.empty())
 291     return createStringError(Name + " component cannot be empty");
 292
 293   if (!to_integer(Str, BitWidth, 10) || BitWidth == 0 || !isUInt<24>(BitWidth))
 294     return createStringError(Name + " must be a non-zero 24-bit integer");
 295
 296   return Error::success();
 297 }
 298
 299 /// Attempts to parse an alignment component of a specification.
 300 ///
 301 /// On success, returns the value converted to byte amount in \p Alignment.
 302 /// If the value is zero and \p AllowZero is true, \p Alignment is set to one.
 303 ///
 304 /// Return an error in a number of cases:
 305 /// - \p Str is empty or contains characters other than decimal digits;
 306 /// - the value is zero and \p AllowZero is false;
 307 /// - the value is too large;
 308 /// - the value is not a multiple of the byte width;
 309 /// - the value converted to byte amount is not not a power of two.
 310 static Error parseAlignment(StringRef Str, Align &Alignment, StringRef Name,
 311                             bool AllowZero = false) {
 312   if (Str.empty())
 313     return createStringError(Name + " alignment component cannot be empty");
 314
 315   unsigned Value;
 316   if (!to_integer(Str, Value, 10) || !isUInt<16>(Value))
 317     return createStringError(Name + " alignment must be a 16-bit integer");
 318
 319   if (Value == 0) {
 320     if (!AllowZero)
 321       return createStringError(Name + " alignment must be non-zero");
 322     Alignment = Align(1);
 323     return Error::success();
 324   }
 325
 326   constexpr unsigned ByteWidth = 8;
 327   if (Value % ByteWidth || !isPowerOf2_32(Value / ByteWidth))
 328     return createStringError(
 329         Name + " alignment must be a power of two times the byte width");
 330
 331   Alignment = Align(Value / ByteWidth);
 332   return Error::success();
 333 }
 334
 335 Error DataLayout::parsePrimitiveSpec(StringRef Spec) {
 336   // [ifv]<size>:<abi>[:<pref>]
 337   SmallVector<StringRef, 3> Components;
 338   char Specifier = Spec.front();
 339   assert(Specifier == 'i' || Specifier == 'f' || Specifier == 'v');
 340   Spec.drop_front().split(Components, ':');
 341
 342   if (Components.size() < 2 || Components.size() > 3)
 343     return createSpecFormatError(Twine(Specifier) + "<size>:<abi>[:<pref>]");
 344
 345   // Size. Required, cannot be zero.
 346   unsigned BitWidth;
 347   if (Error Err = parseSize(Components[0], BitWidth))
 348     return Err;
 349
 350   // ABI alignment.
 351   Align ABIAlign;
 352   if (Error Err = parseAlignment(Components[1], ABIAlign, "ABI"))
 353     return Err;
 354
 355   if (Specifier == 'i' && BitWidth == 8 && ABIAlign != 1)
 356     return createStringError("i8 must be 8-bit aligned");
 357
 358   // Preferred alignment. Optional, defaults to the ABI alignment.
 359   Align PrefAlign = ABIAlign;
 360   if (Components.size() > 2)
 361     if (Error Err = parseAlignment(Components[2], PrefAlign, "preferred"))
 362       return Err;
 363
 364   if (PrefAlign < ABIAlign)
 365     return createStringError(
 366         "preferred alignment cannot be less than the ABI alignment");
 367
 368   setPrimitiveSpec(Specifier, BitWidth, ABIAlign, PrefAlign);
 369   return Error::success();
 370 }
 371
 372 Error DataLayout::parseAggregateSpec(StringRef Spec) {
 373   // a<size>:<abi>[:<pref>]
 374   SmallVector<StringRef, 3> Components;
 375   assert(Spec.front() == 'a');
 376   Spec.drop_front().split(Components, ':');
 377
 378   if (Components.size() < 2 || Components.size() > 3)
 379     return createSpecFormatError("a:<abi>[:<pref>]");
 380
 381   // According to LangRef, <size> component must be absent altogether.
 382   // For backward compatibility, allow it to be specified, but require
 383   // it to be zero.
 384   if (!Components[0].empty()) {
 385     unsigned BitWidth;
 386     if (!to_integer(Components[0], BitWidth, 10) || BitWidth != 0)
 387       return createStringError("size must be zero");
 388   }
 389
 390   // ABI alignment. Required. Can be zero, meaning use one byte alignment.
 391   Align ABIAlign;
 392   if (Error Err =
 393           parseAlignment(Components[1], ABIAlign, "ABI", /*AllowZero=*/true))
 394     return Err;
 395
 396   // Preferred alignment. Optional, defaults to the ABI alignment.
 397   Align PrefAlign = ABIAlign;
 398   if (Components.size() > 2)
 399     if (Error Err = parseAlignment(Components[2], PrefAlign, "preferred"))
 400       return Err;
 401
 402   if (PrefAlign < ABIAlign)
 403     return createStringError(
 404         "preferred alignment cannot be less than the ABI alignment");
 405
 406   StructABIAlignment = ABIAlign;
 407   StructPrefAlignment = PrefAlign;
 408   return Error::success();
 409 }
 410
 411 Error DataLayout::parsePointerSpec(StringRef Spec) {
 412   // p[<n>]:<size>:<abi>[:<pref>[:<idx>]]
 413   SmallVector<StringRef, 5> Components;
 414   assert(Spec.front() == 'p');
 415   Spec.drop_front().split(Components, ':');
 416
 417   if (Components.size() < 3 || Components.size() > 5)
 418     return createSpecFormatError("p[<n>]:<size>:<abi>[:<pref>[:<idx>]]");
 419
 420   // Address space. Optional, defaults to 0.
 421   unsigned AddrSpace = 0;
 422   if (!Components[0].empty())
 423     if (Error Err = parseAddrSpace(Components[0], AddrSpace))
 424       return Err;
 425
 426   // Size. Required, cannot be zero.
 427   unsigned BitWidth;
 428   if (Error Err = parseSize(Components[1], BitWidth, "pointer size"))
 429     return Err;
 430
 431   // ABI alignment. Required, cannot be zero.
 432   Align ABIAlign;
 433   if (Error Err = parseAlignment(Components[2], ABIAlign, "ABI"))
 434     return Err;
 435
 436   // Preferred alignment. Optional, defaults to the ABI alignment.
 437   // Cannot be zero.
 438   Align PrefAlign = ABIAlign;
 439   if (Components.size() > 3)
 440     if (Error Err = parseAlignment(Components[3], PrefAlign, "preferred"))
 441       return Err;
 442
 443   if (PrefAlign < ABIAlign)
 444     return createStringError(
 445         "preferred alignment cannot be less than the ABI alignment");
 446
 447   // Index size. Optional, defaults to pointer size. Cannot be zero.
 448   unsigned IndexBitWidth = BitWidth;
 449   if (Components.size() > 4)
 450     if (Error Err = parseSize(Components[4], IndexBitWidth, "index size"))
 451       return Err;
 452
 453   if (IndexBitWidth > BitWidth)
 454     return createStringError(
 455         "index size cannot be larger than the pointer size");
 456
 457   setPointerSpec(AddrSpace, BitWidth, ABIAlign, PrefAlign, IndexBitWidth,
 458                  false);
 459   return Error::success();
 460 }
 461
 462 Error DataLayout::parseSpecification(
 463     StringRef Spec, SmallVectorImpl<unsigned> &NonIntegralAddressSpaces) {
 464   // The "ni" specifier is the only two-character specifier. Handle it first.
 465   if (Spec.starts_with("ni")) {
 466     // ni:<address space>[:<address space>]...
 467     StringRef Rest = Spec.drop_front(2);
 468
 469     // Drop the first ':', then split the rest of the string the usual way.
 470     if (!Rest.consume_front(":"))
 471       return createSpecFormatError("ni:<address space>[:<address space>]...");
 472
 473     for (StringRef Str : split(Rest, ':')) {
 474       unsigned AddrSpace;
 475       if (Error Err = parseAddrSpace(Str, AddrSpace))
 476         return Err;
 477       if (AddrSpace == 0)
 478         return createStringError("address space 0 cannot be non-integral");
 479       NonIntegralAddressSpaces.push_back(AddrSpace);
 480     }
 481     return Error::success();
 482   }
 483
 484   // The rest of the specifiers are single-character.
 485   assert(!Spec.empty() && "Empty specification is handled by the caller");
 486   char Specifier = Spec.front();
 487
 488   if (Specifier == 'i' || Specifier == 'f' || Specifier == 'v')
 489     return parsePrimitiveSpec(Spec);
 490
 491   if (Specifier == 'a')
 492     return parseAggregateSpec(Spec);
 493
 494   if (Specifier == 'p')
 495     return parsePointerSpec(Spec);
 496
 497   StringRef Rest = Spec.drop_front();
 498   switch (Specifier) {
 499   case 's':
 500     // Deprecated, but ignoring here to preserve loading older textual llvm
 501     // ASM file
 502     break;
 503   case 'e':
 504   case 'E':
 505     if (!Rest.empty())
 506       return createStringError(
 507           "malformed specification, must be just 'e' or 'E'");
 508     BigEndian = Specifier == 'E';
 509     break;
 510   case 'n': // Native integer types.
 511     // n<size>[:<size>]...
 512     for (StringRef Str : split(Rest, ':')) {
 513       unsigned BitWidth;
 514       if (Error Err = parseSize(Str, BitWidth))
 515         return Err;
 516       LegalIntWidths.push_back(BitWidth);
 517     }
 518     break;
 519   case 'S': { // Stack natural alignment.
 520     // S<size>
 521     if (Rest.empty())
 522       return createSpecFormatError("S<size>");
 523     Align Alignment;
 524     if (Error Err = parseAlignment(Rest, Alignment, "stack natural"))
 525       return Err;
 526     StackNaturalAlign = Alignment;
 527     break;
 528   }
 529   case 'F': {
 530     // F<type><abi>
 531     if (Rest.empty())
 532       return createSpecFormatError("F<type><abi>");
 533     char Type = Rest.front();
 534     Rest = Rest.drop_front();
 535     switch (Type) {
 536     case 'i':
 537       TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
 538       break;
 539     case 'n':
 540       TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;
 541       break;
 542     default:
 543       return createStringError("unknown function pointer alignment type '" +
 544                                Twine(Type) + "'");
 545     }
 546     Align Alignment;
 547     if (Error Err = parseAlignment(Rest, Alignment, "ABI"))
 548       return Err;
 549     FunctionPtrAlign = Alignment;
 550     break;
 551   }
 552   case 'P': { // Function address space.
 553     if (Rest.empty())
 554       return createSpecFormatError("P<address space>");
 555     if (Error Err = parseAddrSpace(Rest, ProgramAddrSpace))
 556       return Err;
 557     break;
 558   }
 559   case 'A': { // Default stack/alloca address space.
 560     if (Rest.empty())
 561       return createSpecFormatError("A<address space>");
 562     if (Error Err = parseAddrSpace(Rest, AllocaAddrSpace))
 563       return Err;
 564     break;
 565   }
 566   case 'G': { // Default address space for global variables.
 567     if (Rest.empty())
 568       return createSpecFormatError("G<address space>");
 569     if (Error Err = parseAddrSpace(Rest, DefaultGlobalsAddrSpace))
 570       return Err;
 571     break;
 572   }
 573   case 'm':
 574     if (!Rest.consume_front(":") || Rest.empty())
 575       return createSpecFormatError("m:<mangling>");
 576     if (Rest.size() > 1)
 577       return createStringError("unknown mangling mode");
 578     switch (Rest[0]) {
 579     default:
 580       return createStringError("unknown mangling mode");
 581     case 'e':
 582       ManglingMode = MM_ELF;
 583       break;
 584     case 'l':
 585       ManglingMode = MM_GOFF;
 586       break;
 587     case 'o':
 588       ManglingMode = MM_MachO;
 589       break;
 590     case 'm':
 591       ManglingMode = MM_Mips;
 592       break;
 593     case 'w':
 594       ManglingMode = MM_WinCOFF;
 595       break;
 596     case 'x':
 597       ManglingMode = MM_WinCOFFX86;
 598       break;
 599     case 'a':
 600       ManglingMode = MM_XCOFF;
 601       break;
 602     }
 603     break;
 604   default:
 605     return createStringError("unknown specifier '" + Twine(Specifier) + "'");
 606   }
 607
 608   return Error::success();
 609 }
 610
 611 Error DataLayout::parseLayoutString(StringRef LayoutString) {
 612   StringRepresentation = std::string(LayoutString);
 613
 614   if (LayoutString.empty())
 615     return Error::success();
 616
 617   // Split the data layout string into specifications separated by '-' and
 618   // parse each specification individually, updating internal data structures.
 619   SmallVector<unsigned, 8> NonIntegralAddressSpaces;
 620   for (StringRef Spec : split(LayoutString, '-')) {
 621     if (Spec.empty())
 622       return createStringError("empty specification is not allowed");
 623     if (Error Err = parseSpecification(Spec, NonIntegralAddressSpaces))
 624       return Err;
 625   }
 626   // Mark all address spaces that were qualified as non-integral now. This has
 627   // to be done later since the non-integral property is not part of the data
 628   // layout pointer specification.
 629   for (unsigned AS : NonIntegralAddressSpaces) {
 630     // If there is no special spec for a given AS, getPointerSpec(AS) returns
 631     // the spec for AS0, and we then update that to mark it non-integral.
 632     const PointerSpec &PS = getPointerSpec(AS);
 633     setPointerSpec(AS, PS.BitWidth, PS.ABIAlign, PS.PrefAlign, PS.IndexBitWidth,
 634                    true);
 635   }
 636
 637   return Error::success();
 638 }
 639
 640 void DataLayout::setPrimitiveSpec(char Specifier, uint32_t BitWidth,
 641                                   Align ABIAlign, Align PrefAlign) {
 642   SmallVectorImpl<PrimitiveSpec> *Specs;
 643   switch (Specifier) {
 644   default:
 645     llvm_unreachable("Unexpected specifier");
 646   case 'i':
 647     Specs = &IntSpecs;
 648     break;
 649   case 'f':
 650     Specs = &FloatSpecs;
 651     break;
 652   case 'v':
 653     Specs = &VectorSpecs;
 654     break;
 655   }
 656
 657   auto I = lower_bound(*Specs, BitWidth, LessPrimitiveBitWidth());
 658   if (I != Specs->end() && I->BitWidth == BitWidth) {
 659     // Update the abi, preferred alignments.
 660     I->ABIAlign = ABIAlign;
 661     I->PrefAlign = PrefAlign;
 662   } else {
 663     // Insert before I to keep the vector sorted.
 664     Specs->insert(I, PrimitiveSpec{BitWidth, ABIAlign, PrefAlign});
 665   }
 666 }
 667
 668 const DataLayout::PointerSpec &
 669 DataLayout::getPointerSpec(uint32_t AddrSpace) const {
 670   if (AddrSpace != 0) {
 671     auto I = lower_bound(PointerSpecs, AddrSpace, LessPointerAddrSpace());
 672     if (I != PointerSpecs.end() && I->AddrSpace == AddrSpace)
 673       return *I;
 674   }
 675
 676   assert(PointerSpecs[0].AddrSpace == 0);
 677   return PointerSpecs[0];
 678 }
 679
 680 void DataLayout::setPointerSpec(uint32_t AddrSpace, uint32_t BitWidth,
 681                                 Align ABIAlign, Align PrefAlign,
 682                                 uint32_t IndexBitWidth, bool IsNonIntegral) {
 683   auto I = lower_bound(PointerSpecs, AddrSpace, LessPointerAddrSpace());
 684   if (I == PointerSpecs.end() || I->AddrSpace != AddrSpace) {
 685     PointerSpecs.insert(I, PointerSpec{AddrSpace, BitWidth, ABIAlign, PrefAlign,
 686                                        IndexBitWidth, IsNonIntegral});
 687   } else {
 688     I->BitWidth = BitWidth;
 689     I->ABIAlign = ABIAlign;
 690     I->PrefAlign = PrefAlign;
 691     I->IndexBitWidth = IndexBitWidth;
 692     I->IsNonIntegral = IsNonIntegral;
 693   }
 694 }
 695
 696 Align DataLayout::getIntegerAlignment(uint32_t BitWidth,
 697                                       bool abi_or_pref) const {
 698   auto I = lower_bound(IntSpecs, BitWidth, LessPrimitiveBitWidth());
 699   // If we don't have an exact match, use alignment of next larger integer
 700   // type. If there is none, use alignment of largest integer type by going
 701   // back one element.
 702   if (I == IntSpecs.end())
 703     --I;
 704   return abi_or_pref ? I->ABIAlign : I->PrefAlign;
 705 }
 706
 707 DataLayout::~DataLayout() { delete static_cast<StructLayoutMap *>(LayoutMap); }
 708
 709 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 710   if (!LayoutMap)
 711     LayoutMap = new StructLayoutMap();
 712
 713   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 714   StructLayout *&SL = (*STM)[Ty];
 715   if (SL) return SL;
 716
 717   // Otherwise, create the struct layout.  Because it is variable length, we
 718   // malloc it, then use placement new.
 719   StructLayout *L = (StructLayout *)safe_malloc(
 720       StructLayout::totalSizeToAlloc<TypeSize>(Ty->getNumElements()));
 721
 722   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 723   // entries to be added to TheMap, invalidating our reference.
 724   SL = L;
 725
 726   new (L) StructLayout(Ty, *this);
 727
 728   return L;
 729 }
 730
 731 Align DataLayout::getPointerABIAlignment(unsigned AS) const {
 732   return getPointerSpec(AS).ABIAlign;
 733 }
 734
 735 Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
 736   return getPointerSpec(AS).PrefAlign;
 737 }
 738
 739 unsigned DataLayout::getPointerSize(unsigned AS) const {
 740   return divideCeil(getPointerSpec(AS).BitWidth, 8);
 741 }
 742
 743 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 744   assert(Ty->isPtrOrPtrVectorTy() &&
 745          "This should only be called with a pointer or pointer vector type");
 746   Ty = Ty->getScalarType();
 747   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 748 }
 749
 750 unsigned DataLayout::getIndexSize(unsigned AS) const {
 751   return divideCeil(getPointerSpec(AS).IndexBitWidth, 8);
 752 }
 753
 754 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
 755   assert(Ty->isPtrOrPtrVectorTy() &&
 756          "This should only be called with a pointer or pointer vector type");
 757   Ty = Ty->getScalarType();
 758   return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 759 }
 760
 761 /*!
 762   \param abi_or_pref Flag that determines which alignment is returned. true
 763   returns the ABI alignment, false returns the preferred alignment.
 764   \param Ty The underlying type for which alignment is determined.
 765
 766   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 767   == false) for the requested type \a Ty.
 768  */
 769 Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 770   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 771   switch (Ty->getTypeID()) {
 772   // Early escape for the non-numeric types.
 773   case Type::LabelTyID:
 774     return abi_or_pref ? getPointerABIAlignment(0) : getPointerPrefAlignment(0);
 775   case Type::PointerTyID: {
 776     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 777     return abi_or_pref ? getPointerABIAlignment(AS)
 778                        : getPointerPrefAlignment(AS);
 779     }
 780   case Type::ArrayTyID:
 781     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 782
 783   case Type::StructTyID: {
 784     // Packed structure types always have an ABI alignment of one.
 785     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 786       return Align(1);
 787
 788     // Get the layout annotation... which is lazily created on demand.
 789     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 790     const Align Align = abi_or_pref ? StructABIAlignment : StructPrefAlignment;
 791     return std::max(Align, Layout->getAlignment());
 792   }
 793   case Type::IntegerTyID:
 794     return getIntegerAlignment(Ty->getIntegerBitWidth(), abi_or_pref);
 795   case Type::HalfTyID:
 796   case Type::BFloatTyID:
 797   case Type::FloatTyID:
 798   case Type::DoubleTyID:
 799   // PPC_FP128TyID and FP128TyID have different data contents, but the
 800   // same size and alignment, so they look the same here.
 801   case Type::PPC_FP128TyID:
 802   case Type::FP128TyID:
 803   case Type::X86_FP80TyID: {
 804     unsigned BitWidth = getTypeSizeInBits(Ty).getFixedValue();
 805     auto I = lower_bound(FloatSpecs, BitWidth, LessPrimitiveBitWidth());
 806     if (I != FloatSpecs.end() && I->BitWidth == BitWidth)
 807       return abi_or_pref ? I->ABIAlign : I->PrefAlign;
 808
 809     // If we still couldn't find a reasonable default alignment, fall back
 810     // to a simple heuristic that the alignment is the first power of two
 811     // greater-or-equal to the store size of the type.  This is a reasonable
 812     // approximation of reality, and if the user wanted something less
 813     // less conservative, they should have specified it explicitly in the data
 814     // layout.
 815     return Align(PowerOf2Ceil(BitWidth / 8));
 816   }
 817   case Type::FixedVectorTyID:
 818   case Type::ScalableVectorTyID: {
 819     unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinValue();
 820     auto I = lower_bound(VectorSpecs, BitWidth, LessPrimitiveBitWidth());
 821     if (I != VectorSpecs.end() && I->BitWidth == BitWidth)
 822       return abi_or_pref ? I->ABIAlign : I->PrefAlign;
 823
 824     // By default, use natural alignment for vector types. This is consistent
 825     // with what clang and llvm-gcc do.
 826     //
 827     // We're only calculating a natural alignment, so it doesn't have to be
 828     // based on the full size for scalable vectors. Using the minimum element
 829     // count should be enough here.
 830     return Align(PowerOf2Ceil(getTypeStoreSize(Ty).getKnownMinValue()));
 831   }
 832   case Type::X86_AMXTyID:
 833     return Align(64);
 834   case Type::TargetExtTyID: {
 835     Type *LayoutTy = cast<TargetExtType>(Ty)->getLayoutType();
 836     return getAlignment(LayoutTy, abi_or_pref);
 837   }
 838   default:
 839     llvm_unreachable("Bad type for getAlignment!!!");
 840   }
 841 }
 842
 843 Align DataLayout::getABITypeAlign(Type *Ty) const {
 844   return getAlignment(Ty, true);
 845 }
 846
 847 Align DataLayout::getPrefTypeAlign(Type *Ty) const {
 848   return getAlignment(Ty, false);
 849 }
 850
 851 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 852                                        unsigned AddressSpace) const {
 853   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 854 }
 855
 856 Type *DataLayout::getIntPtrType(Type *Ty) const {
 857   assert(Ty->isPtrOrPtrVectorTy() &&
 858          "Expected a pointer or pointer vector type.");
 859   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 860   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 861   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 862     return VectorType::get(IntTy, VecTy);
 863   return IntTy;
 864 }
 865
 866 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 867   for (unsigned LegalIntWidth : LegalIntWidths)
 868     if (Width <= LegalIntWidth)
 869       return Type::getIntNTy(C, LegalIntWidth);
 870   return nullptr;
 871 }
 872
 873 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
 874   auto Max = llvm::max_element(LegalIntWidths);
 875   return Max != LegalIntWidths.end() ? *Max : 0;
 876 }
 877
 878 IntegerType *DataLayout::getIndexType(LLVMContext &C,
 879                                       unsigned AddressSpace) const {
 880   return IntegerType::get(C, getIndexSizeInBits(AddressSpace));
 881 }
 882
 883 Type *DataLayout::getIndexType(Type *Ty) const {
 884   assert(Ty->isPtrOrPtrVectorTy() &&
 885          "Expected a pointer or pointer vector type.");
 886   unsigned NumBits = getIndexTypeSizeInBits(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 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
 894                                            ArrayRef<Value *> Indices) const {
 895   int64_t Result = 0;
 896
 897   generic_gep_type_iterator<Value* const*>
 898     GTI = gep_type_begin(ElemTy, Indices),
 899     GTE = gep_type_end(ElemTy, Indices);
 900   for (; GTI != GTE; ++GTI) {
 901     Value *Idx = GTI.getOperand();
 902     if (StructType *STy = GTI.getStructTypeOrNull()) {
 903       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
 904       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
 905
 906       // Get structure layout information...
 907       const StructLayout *Layout = getStructLayout(STy);
 908
 909       // Add in the offset, as calculated by the structure layout info...
 910       Result += Layout->getElementOffset(FieldNo);
 911     } else {
 912       if (int64_t ArrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
 913         Result += ArrayIdx * GTI.getSequentialElementStride(*this);
 914     }
 915   }
 916
 917   return Result;
 918 }
 919
 920 static APInt getElementIndex(TypeSize ElemSize, APInt &Offset) {
 921   // Skip over scalable or zero size elements. Also skip element sizes larger
 922   // than the positive index space, because the arithmetic below may not be
 923   // correct in that case.
 924   unsigned BitWidth = Offset.getBitWidth();
 925   if (ElemSize.isScalable() || ElemSize == 0 ||
 926       !isUIntN(BitWidth - 1, ElemSize)) {
 927     return APInt::getZero(BitWidth);
 928   }
 929
 930   APInt Index = Offset.sdiv(ElemSize);
 931   Offset -= Index * ElemSize;
 932   if (Offset.isNegative()) {
 933     // Prefer a positive remaining offset to allow struct indexing.
 934     --Index;
 935     Offset += ElemSize;
 936     assert(Offset.isNonNegative() && "Remaining offset shouldn't be negative");
 937   }
 938   return Index;
 939 }
 940
 941 std::optional<APInt> DataLayout::getGEPIndexForOffset(Type *&ElemTy,
 942                                                       APInt &Offset) const {
 943   if (auto *ArrTy = dyn_cast<ArrayType>(ElemTy)) {
 944     ElemTy = ArrTy->getElementType();
 945     return getElementIndex(getTypeAllocSize(ElemTy), Offset);
 946   }
 947
 948   if (isa<VectorType>(ElemTy)) {
 949     // Vector GEPs are partially broken (e.g. for overaligned element types),
 950     // and may be forbidden in the future, so avoid generating GEPs into
 951     // vectors. See https://discourse.llvm.org/t/67497
 952     return std::nullopt;
 953   }
 954
 955   if (auto *STy = dyn_cast<StructType>(ElemTy)) {
 956     const StructLayout *SL = getStructLayout(STy);
 957     uint64_t IntOffset = Offset.getZExtValue();
 958     if (IntOffset >= SL->getSizeInBytes())
 959       return std::nullopt;
 960
 961     unsigned Index = SL->getElementContainingOffset(IntOffset);
 962     Offset -= SL->getElementOffset(Index);
 963     ElemTy = STy->getElementType(Index);
 964     return APInt(32, Index);
 965   }
 966
 967   // Non-aggregate type.
 968   return std::nullopt;
 969 }
 970
 971 SmallVector<APInt> DataLayout::getGEPIndicesForOffset(Type *&ElemTy,
 972                                                       APInt &Offset) const {
 973   assert(ElemTy->isSized() && "Element type must be sized");
 974   SmallVector<APInt> Indices;
 975   Indices.push_back(getElementIndex(getTypeAllocSize(ElemTy), Offset));
 976   while (Offset != 0) {
 977     std::optional<APInt> Index = getGEPIndexForOffset(ElemTy, Offset);
 978     if (!Index)
 979       break;
 980     Indices.push_back(*Index);
 981   }
 982
 983   return Indices;
 984 }
 985
 986 /// getPreferredAlign - Return the preferred alignment of the specified global.
 987 /// This includes an explicitly requested alignment (if the global has one).
 988 Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {
 989   MaybeAlign GVAlignment = GV->getAlign();
 990   // If a section is specified, always precisely honor explicit alignment,
 991   // so we don't insert padding into a section we don't control.
 992   if (GVAlignment && GV->hasSection())
 993     return *GVAlignment;
 994
 995   // If no explicit alignment is specified, compute the alignment based on
 996   // the IR type. If an alignment is specified, increase it to match the ABI
 997   // alignment of the IR type.
 998   //
 999   // FIXME: Not sure it makes sense to use the alignment of the type if
1000   // there's already an explicit alignment specification.
1001   Type *ElemType = GV->getValueType();
1002   Align Alignment = getPrefTypeAlign(ElemType);
1003   if (GVAlignment) {
1004     if (*GVAlignment >= Alignment)
1005       Alignment = *GVAlignment;
1006     else
1007       Alignment = std::max(*GVAlignment, getABITypeAlign(ElemType));
1008   }
1009
1010   // If no explicit alignment is specified, and the global is large, increase
1011   // the alignment to 16.
1012   // FIXME: Why 16, specifically?
1013   if (GV->hasInitializer() && !GVAlignment) {
1014     if (Alignment < Align(16)) {
1015       // If the global is not external, see if it is large.  If so, give it a
1016       // larger alignment.
1017       if (getTypeSizeInBits(ElemType) > 128)
1018         Alignment = Align(16); // 16-byte alignment.
1019     }
1020   }
1021   return Alignment;
1022 }