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.reset();
 186   ProgramAddrSpace = 0;
 187   FunctionPtrAlign.reset();
 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       uint64_t Alignment = inBytes(getInt(Tok));
 382       if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
 383         report_fatal_error("Alignment is neither 0 nor a power of 2");
 384       StackNaturalAlign = MaybeAlign(Alignment);
 385       break;
 386     }
 387     case 'F': {
 388       switch (Tok.front()) {
 389       case 'i':
 390         TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
 391         break;
 392       case 'n':
 393         TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;
 394         break;
 395       default:
 396         report_fatal_error("Unknown function pointer alignment type in "
 397                            "datalayout string");
 398       }
 399       Tok = Tok.substr(1);
 400       uint64_t Alignment = inBytes(getInt(Tok));
 401       if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
 402         report_fatal_error("Alignment is neither 0 nor a power of 2");
 403       FunctionPtrAlign = MaybeAlign(Alignment);
 404       break;
 405     }
 406     case 'P': { // Function address space.
 407       ProgramAddrSpace = getAddrSpace(Tok);
 408       break;
 409     }
 410     case 'A': { // Default stack/alloca address space.
 411       AllocaAddrSpace = getAddrSpace(Tok);
 412       break;
 413     }
 414     case 'm':
 415       if (!Tok.empty())
 416         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
 417       if (Rest.empty())
 418         report_fatal_error("Expected mangling specifier in datalayout string");
 419       if (Rest.size() > 1)
 420         report_fatal_error("Unknown mangling specifier in datalayout string");
 421       switch(Rest[0]) {
 422       default:
 423         report_fatal_error("Unknown mangling in datalayout string");
 424       case 'e':
 425         ManglingMode = MM_ELF;
 426         break;
 427       case 'o':
 428         ManglingMode = MM_MachO;
 429         break;
 430       case 'm':
 431         ManglingMode = MM_Mips;
 432         break;
 433       case 'w':
 434         ManglingMode = MM_WinCOFF;
 435         break;
 436       case 'x':
 437         ManglingMode = MM_WinCOFFX86;
 438         break;
 439       }
 440       break;
 441     default:
 442       report_fatal_error("Unknown specifier in datalayout string");
 443       break;
 444     }
 445   }
 446 }
 447
 448 DataLayout::DataLayout(const Module *M) {
 449   init(M);
 450 }
 451
 452 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 453
 454 bool DataLayout::operator==(const DataLayout &Other) const {
 455   bool Ret = BigEndian == Other.BigEndian &&
 456              AllocaAddrSpace == Other.AllocaAddrSpace &&
 457              StackNaturalAlign == Other.StackNaturalAlign &&
 458              ProgramAddrSpace == Other.ProgramAddrSpace &&
 459              FunctionPtrAlign == Other.FunctionPtrAlign &&
 460              TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&
 461              ManglingMode == Other.ManglingMode &&
 462              LegalIntWidths == Other.LegalIntWidths &&
 463              Alignments == Other.Alignments && Pointers == Other.Pointers;
 464   // Note: getStringRepresentation() might differs, it is not canonicalized
 465   return Ret;
 466 }
 467
 468 DataLayout::AlignmentsTy::iterator
 469 DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType,
 470                                     uint32_t BitWidth) {
 471   auto Pair = std::make_pair((unsigned)AlignType, BitWidth);
 472   return partition_point(Alignments, [=](const LayoutAlignElem &E) {
 473     return std::make_pair(E.AlignType, E.TypeBitWidth) < Pair;
 474   });
 475 }
 476
 477 void
 478 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 479                          unsigned pref_align, uint32_t bit_width) {
 480   if (!isUInt<24>(bit_width))
 481     report_fatal_error("Invalid bit width, must be a 24bit integer");
 482   if (!isUInt<16>(abi_align))
 483     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
 484   if (!isUInt<16>(pref_align))
 485     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
 486   if (abi_align != 0 && !isPowerOf2_64(abi_align))
 487     report_fatal_error("Invalid ABI alignment, must be a power of 2");
 488   if (pref_align != 0 && !isPowerOf2_64(pref_align))
 489     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 490
 491   if (pref_align < abi_align)
 492     report_fatal_error(
 493         "Preferred alignment cannot be less than the ABI alignment");
 494
 495   AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width);
 496   if (I != Alignments.end() &&
 497       I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) {
 498     // Update the abi, preferred alignments.
 499     I->ABIAlign = abi_align;
 500     I->PrefAlign = pref_align;
 501   } else {
 502     // Insert before I to keep the vector sorted.
 503     Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
 504                                               pref_align, bit_width));
 505   }
 506 }
 507
 508 DataLayout::PointersTy::iterator
 509 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
 510   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 511                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
 512     return A.AddressSpace < AddressSpace;
 513   });
 514 }
 515
 516 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 517                                      unsigned PrefAlign, uint32_t TypeByteWidth,
 518                                      uint32_t IndexWidth) {
 519   if (PrefAlign < ABIAlign)
 520     report_fatal_error(
 521         "Preferred alignment cannot be less than the ABI alignment");
 522
 523   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 524   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 525     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 526                                              TypeByteWidth, IndexWidth));
 527   } else {
 528     I->ABIAlign = ABIAlign;
 529     I->PrefAlign = PrefAlign;
 530     I->TypeByteWidth = TypeByteWidth;
 531     I->IndexWidth = IndexWidth;
 532   }
 533 }
 534
 535 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 536 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 537 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 538                                       uint32_t BitWidth, bool ABIInfo,
 539                                       Type *Ty) const {
 540   AlignmentsTy::const_iterator I = findAlignmentLowerBound(AlignType, BitWidth);
 541   // See if we found an exact match. Of if we are looking for an integer type,
 542   // but don't have an exact match take the next largest integer. This is where
 543   // the lower_bound will point to when it fails an exact match.
 544   if (I != Alignments.end() && I->AlignType == (unsigned)AlignType &&
 545       (I->TypeBitWidth == BitWidth || AlignType == INTEGER_ALIGN))
 546     return ABIInfo ? I->ABIAlign : I->PrefAlign;
 547
 548   if (AlignType == INTEGER_ALIGN) {
 549     // If we didn't have a larger value try the largest value we have.
 550     if (I != Alignments.begin()) {
 551       --I; // Go to the previous entry and see if its an integer.
 552       if (I->AlignType == INTEGER_ALIGN)
 553         return ABIInfo ? I->ABIAlign : I->PrefAlign;
 554     }
 555   } else if (AlignType == VECTOR_ALIGN) {
 556     // By default, use natural alignment for vector types. This is consistent
 557     // with what clang and llvm-gcc do.
 558     unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 559     Align *= cast<VectorType>(Ty)->getNumElements();
 560     Align = PowerOf2Ceil(Align);
 561     return Align;
 562    }
 563
 564   // If we still couldn't find a reasonable default alignment, fall back
 565   // to a simple heuristic that the alignment is the first power of two
 566   // greater-or-equal to the store size of the type.  This is a reasonable
 567   // approximation of reality, and if the user wanted something less
 568   // less conservative, they should have specified it explicitly in the data
 569   // layout.
 570   unsigned Align = getTypeStoreSize(Ty);
 571   Align = PowerOf2Ceil(Align);
 572   return Align;
 573 }
 574
 575 namespace {
 576
 577 class StructLayoutMap {
 578   using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
 579   LayoutInfoTy LayoutInfo;
 580
 581 public:
 582   ~StructLayoutMap() {
 583     // Remove any layouts.
 584     for (const auto &I : LayoutInfo) {
 585       StructLayout *Value = I.second;
 586       Value->~StructLayout();
 587       free(Value);
 588     }
 589   }
 590
 591   StructLayout *&operator[](StructType *STy) {
 592     return LayoutInfo[STy];
 593   }
 594 };
 595
 596 } // end anonymous namespace
 597
 598 void DataLayout::clear() {
 599   LegalIntWidths.clear();
 600   Alignments.clear();
 601   Pointers.clear();
 602   delete static_cast<StructLayoutMap *>(LayoutMap);
 603   LayoutMap = nullptr;
 604 }
 605
 606 DataLayout::~DataLayout() {
 607   clear();
 608 }
 609
 610 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 611   if (!LayoutMap)
 612     LayoutMap = new StructLayoutMap();
 613
 614   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 615   StructLayout *&SL = (*STM)[Ty];
 616   if (SL) return SL;
 617
 618   // Otherwise, create the struct layout.  Because it is variable length, we
 619   // malloc it, then use placement new.
 620   int NumElts = Ty->getNumElements();
 621   StructLayout *L = (StructLayout *)
 622       safe_malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 623
 624   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 625   // entries to be added to TheMap, invalidating our reference.
 626   SL = L;
 627
 628   new (L) StructLayout(Ty, *this);
 629
 630   return L;
 631 }
 632
 633 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 634   PointersTy::const_iterator I = findPointerLowerBound(AS);
 635   if (I == Pointers.end() || I->AddressSpace != AS) {
 636     I = findPointerLowerBound(0);
 637     assert(I->AddressSpace == 0);
 638   }
 639   return I->ABIAlign;
 640 }
 641
 642 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 643   PointersTy::const_iterator I = findPointerLowerBound(AS);
 644   if (I == Pointers.end() || I->AddressSpace != AS) {
 645     I = findPointerLowerBound(0);
 646     assert(I->AddressSpace == 0);
 647   }
 648   return I->PrefAlign;
 649 }
 650
 651 unsigned DataLayout::getPointerSize(unsigned AS) const {
 652   PointersTy::const_iterator I = findPointerLowerBound(AS);
 653   if (I == Pointers.end() || I->AddressSpace != AS) {
 654     I = findPointerLowerBound(0);
 655     assert(I->AddressSpace == 0);
 656   }
 657   return I->TypeByteWidth;
 658 }
 659
 660 unsigned DataLayout::getMaxPointerSize() const {
 661   unsigned MaxPointerSize = 0;
 662   for (auto &P : Pointers)
 663     MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth);
 664
 665   return MaxPointerSize;
 666 }
 667
 668 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 669   assert(Ty->isPtrOrPtrVectorTy() &&
 670          "This should only be called with a pointer or pointer vector type");
 671   Ty = Ty->getScalarType();
 672   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 673 }
 674
 675 unsigned DataLayout::getIndexSize(unsigned AS) const {
 676   PointersTy::const_iterator I = findPointerLowerBound(AS);
 677   if (I == Pointers.end() || I->AddressSpace != AS) {
 678     I = findPointerLowerBound(0);
 679     assert(I->AddressSpace == 0);
 680   }
 681   return I->IndexWidth;
 682 }
 683
 684 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
 685   assert(Ty->isPtrOrPtrVectorTy() &&
 686          "This should only be called with a pointer or pointer vector type");
 687   Ty = Ty->getScalarType();
 688   return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 689 }
 690
 691 /*!
 692   \param abi_or_pref Flag that determines which alignment is returned. true
 693   returns the ABI alignment, false returns the preferred alignment.
 694   \param Ty The underlying type for which alignment is determined.
 695
 696   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 697   == false) for the requested type \a Ty.
 698  */
 699 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 700   AlignTypeEnum AlignType;
 701
 702   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 703   switch (Ty->getTypeID()) {
 704   // Early escape for the non-numeric types.
 705   case Type::LabelTyID:
 706     return (abi_or_pref
 707             ? getPointerABIAlignment(0)
 708             : getPointerPrefAlignment(0));
 709   case Type::PointerTyID: {
 710     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 711     return (abi_or_pref
 712             ? getPointerABIAlignment(AS)
 713             : getPointerPrefAlignment(AS));
 714     }
 715   case Type::ArrayTyID:
 716     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 717
 718   case Type::StructTyID: {
 719     // Packed structure types always have an ABI alignment of one.
 720     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 721       return 1;
 722
 723     // Get the layout annotation... which is lazily created on demand.
 724     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 725     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 726     return std::max(Align, Layout->getAlignment());
 727   }
 728   case Type::IntegerTyID:
 729     AlignType = INTEGER_ALIGN;
 730     break;
 731   case Type::HalfTyID:
 732   case Type::FloatTyID:
 733   case Type::DoubleTyID:
 734   // PPC_FP128TyID and FP128TyID have different data contents, but the
 735   // same size and alignment, so they look the same here.
 736   case Type::PPC_FP128TyID:
 737   case Type::FP128TyID:
 738   case Type::X86_FP80TyID:
 739     AlignType = FLOAT_ALIGN;
 740     break;
 741   case Type::X86_MMXTyID:
 742   case Type::VectorTyID:
 743     AlignType = VECTOR_ALIGN;
 744     break;
 745   default:
 746     llvm_unreachable("Bad type for getAlignment!!!");
 747   }
 748
 749   return getAlignmentInfo(AlignType, getTypeSizeInBits(Ty), abi_or_pref, Ty);
 750 }
 751
 752 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 753   return getAlignment(Ty, true);
 754 }
 755
 756 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 757 /// an integer type of the specified bitwidth.
 758 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 759   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 760 }
 761
 762 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 763   return getAlignment(Ty, false);
 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 }