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 llvm::Align 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;
 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;
 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 llvm::Align(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 llvm::Align(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 llvm::Align 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;
 648 }
 649
 650 llvm::Align 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;
 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 llvm::Align 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 ? getPointerABIAlignment(0) : getPointerPrefAlignment(0);
 715   case Type::PointerTyID: {
 716     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 717     return abi_or_pref ? getPointerABIAlignment(AS)
 718                        : getPointerPrefAlignment(AS);
 719     }
 720   case Type::ArrayTyID:
 721     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 722
 723   case Type::StructTyID: {
 724     // Packed structure types always have an ABI alignment of one.
 725     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 726       return llvm::Align::None();
 727
 728     // Get the layout annotation... which is lazily created on demand.
 729     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 730     const llvm::Align Align =
 731         getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 732     return std::max(Align, Layout->getAlignment());
 733   }
 734   case Type::IntegerTyID:
 735     AlignType = INTEGER_ALIGN;
 736     break;
 737   case Type::HalfTyID:
 738   case Type::FloatTyID:
 739   case Type::DoubleTyID:
 740   // PPC_FP128TyID and FP128TyID have different data contents, but the
 741   // same size and alignment, so they look the same here.
 742   case Type::PPC_FP128TyID:
 743   case Type::FP128TyID:
 744   case Type::X86_FP80TyID:
 745     AlignType = FLOAT_ALIGN;
 746     break;
 747   case Type::X86_MMXTyID:
 748   case Type::VectorTyID:
 749     AlignType = VECTOR_ALIGN;
 750     break;
 751   default:
 752     llvm_unreachable("Bad type for getAlignment!!!");
 753   }
 754
 755   return getAlignmentInfo(AlignType, getTypeSizeInBits(Ty), abi_or_pref, Ty);
 756 }
 757
 758 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 759   return getAlignment(Ty, true).value();
 760 }
 761
 762 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 763 /// an integer type of the specified bitwidth.
 764 llvm::Align DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 765   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 766 }
 767
 768 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 769   return getAlignment(Ty, false).value();
 770 }
 771
 772 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 773                                        unsigned AddressSpace) const {
 774   return IntegerType::get(C, getIndexSizeInBits(AddressSpace));
 775 }
 776
 777 Type *DataLayout::getIntPtrType(Type *Ty) const {
 778   assert(Ty->isPtrOrPtrVectorTy() &&
 779          "Expected a pointer or pointer vector type.");
 780   unsigned NumBits = getIndexTypeSizeInBits(Ty);
 781   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 782   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 783     return VectorType::get(IntTy, VecTy->getNumElements());
 784   return IntTy;
 785 }
 786
 787 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 788   for (unsigned LegalIntWidth : LegalIntWidths)
 789     if (Width <= LegalIntWidth)
 790       return Type::getIntNTy(C, LegalIntWidth);
 791   return nullptr;
 792 }
 793
 794 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
 795   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 796   return Max != LegalIntWidths.end() ? *Max : 0;
 797 }
 798
 799 Type *DataLayout::getIndexType(Type *Ty) const {
 800   assert(Ty->isPtrOrPtrVectorTy() &&
 801          "Expected a pointer or pointer vector type.");
 802   unsigned NumBits = getIndexTypeSizeInBits(Ty);
 803   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 804   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 805     return VectorType::get(IntTy, VecTy->getNumElements());
 806   return IntTy;
 807 }
 808
 809 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
 810                                            ArrayRef<Value *> Indices) const {
 811   int64_t Result = 0;
 812
 813   generic_gep_type_iterator<Value* const*>
 814     GTI = gep_type_begin(ElemTy, Indices),
 815     GTE = gep_type_end(ElemTy, Indices);
 816   for (; GTI != GTE; ++GTI) {
 817     Value *Idx = GTI.getOperand();
 818     if (StructType *STy = GTI.getStructTypeOrNull()) {
 819       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
 820       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
 821
 822       // Get structure layout information...
 823       const StructLayout *Layout = getStructLayout(STy);
 824
 825       // Add in the offset, as calculated by the structure layout info...
 826       Result += Layout->getElementOffset(FieldNo);
 827     } else {
 828       // Get the array index and the size of each array element.
 829       if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
 830         Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
 831     }
 832   }
 833
 834   return Result;
 835 }
 836
 837 /// getPreferredAlignment - Return the preferred alignment of the specified
 838 /// global.  This includes an explicitly requested alignment (if the global
 839 /// has one).
 840 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 841   unsigned GVAlignment = GV->getAlignment();
 842   // If a section is specified, always precisely honor explicit alignment,
 843   // so we don't insert padding into a section we don't control.
 844   if (GVAlignment && GV->hasSection())
 845     return GVAlignment;
 846
 847   // If no explicit alignment is specified, compute the alignment based on
 848   // the IR type. If an alignment is specified, increase it to match the ABI
 849   // alignment of the IR type.
 850   //
 851   // FIXME: Not sure it makes sense to use the alignment of the type if
 852   // there's already an explicit alignment specification.
 853   Type *ElemType = GV->getValueType();
 854   unsigned Alignment = getPrefTypeAlignment(ElemType);
 855   if (GVAlignment >= Alignment) {
 856     Alignment = GVAlignment;
 857   } else if (GVAlignment != 0) {
 858     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 859   }
 860
 861   // If no explicit alignment is specified, and the global is large, increase
 862   // the alignment to 16.
 863   // FIXME: Why 16, specifically?
 864   if (GV->hasInitializer() && GVAlignment == 0) {
 865     if (Alignment < 16) {
 866       // If the global is not external, see if it is large.  If so, give it a
 867       // larger alignment.
 868       if (getTypeSizeInBits(ElemType) > 128)
 869         Alignment = 16;    // 16-byte alignment.
 870     }
 871   }
 872   return Alignment;
 873 }
 874
 875 /// getPreferredAlignmentLog - Return the preferred alignment of the
 876 /// specified global, returned in log form.  This includes an explicitly
 877 /// requested alignment (if the global has one).
 878 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 879   return Log2_32(getPreferredAlignment(GV));
 880 }