contrib/llvm-project/llvm/lib/IR/DataLayout.cpp

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