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