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