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