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