lib/IR/DataLayout.cpp

   1 //===-- DataLayout.cpp - Data size & alignment routines --------------------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines layout properties related to datatype size/offset/alignment
  11 // information.
  12 //
  13 // This structure should be created once, filled in if the defaults are not
  14 // correct and then passed around by const&.  None of the members functions
  15 // require modification to the object.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/IR/DataLayout.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/STLExtras.h"
  22 #include "llvm/ADT/Triple.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/DerivedTypes.h"
  25 #include "llvm/IR/GetElementPtrTypeIterator.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include "llvm/Support/ManagedStatic.h"
  29 #include "llvm/Support/MathExtras.h"
  30 #include "llvm/Support/Mutex.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include <algorithm>
  33 #include <cstdlib>
  34 using namespace llvm;
  35
  36 //===----------------------------------------------------------------------===//
  37 // Support for StructLayout
  38 //===----------------------------------------------------------------------===//
  39
  40 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
  41   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
  42   StructAlignment = 0;
  43   StructSize = 0;
  44   NumElements = ST->getNumElements();
  45
  46   // Loop over each of the elements, placing them in memory.
  47   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  48     Type *Ty = ST->getElementType(i);
  49     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
  50
  51     // Add padding if necessary to align the data element properly.
  52     if ((StructSize & (TyAlign-1)) != 0)
  53       StructSize = RoundUpToAlignment(StructSize, TyAlign);
  54
  55     // Keep track of maximum alignment constraint.
  56     StructAlignment = std::max(TyAlign, StructAlignment);
  57
  58     MemberOffsets[i] = StructSize;
  59     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  60   }
  61
  62   // Empty structures have alignment of 1 byte.
  63   if (StructAlignment == 0) StructAlignment = 1;
  64
  65   // Add padding to the end of the struct so that it could be put in an array
  66   // and all array elements would be aligned correctly.
  67   if ((StructSize & (StructAlignment-1)) != 0)
  68     StructSize = RoundUpToAlignment(StructSize, StructAlignment);
  69 }
  70
  71
  72 /// getElementContainingOffset - Given a valid offset into the structure,
  73 /// return the structure index that contains it.
  74 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  75   const uint64_t *SI =
  76     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  77   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  78   --SI;
  79   assert(*SI <= Offset && "upper_bound didn't work");
  80   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  81          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  82          "Upper bound didn't work!");
  83
  84   // Multiple fields can have the same offset if any of them are zero sized.
  85   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  86   // at the i32 element, because it is the last element at that offset.  This is
  87   // the right one to return, because anything after it will have a higher
  88   // offset, implying that this element is non-empty.
  89   return SI-&MemberOffsets[0];
  90 }
  91
  92 //===----------------------------------------------------------------------===//
  93 // LayoutAlignElem, LayoutAlign support
  94 //===----------------------------------------------------------------------===//
  95
  96 LayoutAlignElem
  97 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
  98                      unsigned pref_align, uint32_t bit_width) {
  99   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 100   LayoutAlignElem retval;
 101   retval.AlignType = align_type;
 102   retval.ABIAlign = abi_align;
 103   retval.PrefAlign = pref_align;
 104   retval.TypeBitWidth = bit_width;
 105   return retval;
 106 }
 107
 108 bool
 109 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 110   return (AlignType == rhs.AlignType
 111           && ABIAlign == rhs.ABIAlign
 112           && PrefAlign == rhs.PrefAlign
 113           && TypeBitWidth == rhs.TypeBitWidth);
 114 }
 115
 116 const LayoutAlignElem
 117 DataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 };
 118
 119 //===----------------------------------------------------------------------===//
 120 // PointerAlignElem, PointerAlign support
 121 //===----------------------------------------------------------------------===//
 122
 123 PointerAlignElem
 124 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
 125                       unsigned PrefAlign, uint32_t TypeByteWidth) {
 126   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 127   PointerAlignElem retval;
 128   retval.AddressSpace = AddressSpace;
 129   retval.ABIAlign = ABIAlign;
 130   retval.PrefAlign = PrefAlign;
 131   retval.TypeByteWidth = TypeByteWidth;
 132   return retval;
 133 }
 134
 135 bool
 136 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
 137   return (ABIAlign == rhs.ABIAlign
 138           && AddressSpace == rhs.AddressSpace
 139           && PrefAlign == rhs.PrefAlign
 140           && TypeByteWidth == rhs.TypeByteWidth);
 141 }
 142
 143 const PointerAlignElem
 144 DataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U };
 145
 146 //===----------------------------------------------------------------------===//
 147 //                       DataLayout Class Implementation
 148 //===----------------------------------------------------------------------===//
 149
 150 const char *DataLayout::getManglingComponent(const Triple &T) {
 151   if (T.isOSBinFormatMachO())
 152     return "-m:o";
 153   if (T.isOSWindows() && T.getArch() == Triple::x86 && T.isOSBinFormatCOFF())
 154     return "-m:w";
 155   return "-m:e";
 156 }
 157
 158 static const LayoutAlignElem DefaultAlignments[] = {
 159   { INTEGER_ALIGN, 1, 1, 1 },    // i1
 160   { INTEGER_ALIGN, 8, 1, 1 },    // i8
 161   { INTEGER_ALIGN, 16, 2, 2 },   // i16
 162   { INTEGER_ALIGN, 32, 4, 4 },   // i32
 163   { INTEGER_ALIGN, 64, 4, 8 },   // i64
 164   { FLOAT_ALIGN, 16, 2, 2 },     // half
 165   { FLOAT_ALIGN, 32, 4, 4 },     // float
 166   { FLOAT_ALIGN, 64, 8, 8 },     // double
 167   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
 168   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
 169   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
 170   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
 171 };
 172
 173 void DataLayout::reset(StringRef Desc) {
 174   clear();
 175
 176   LayoutMap = nullptr;
 177   BigEndian = false;
 178   StackNaturalAlign = 0;
 179   ManglingMode = MM_None;
 180
 181   // Default alignments
 182   for (const LayoutAlignElem &E : DefaultAlignments) {
 183     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
 184                  E.TypeBitWidth);
 185   }
 186   setPointerAlignment(0, 8, 8, 8);
 187
 188   parseSpecifier(Desc);
 189 }
 190
 191 /// Checked version of split, to ensure mandatory subparts.
 192 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
 193   assert(!Str.empty() && "parse error, string can't be empty here");
 194   std::pair<StringRef, StringRef> Split = Str.split(Separator);
 195   if (Split.second.empty() && Split.first != Str)
 196     report_fatal_error("Trailing separator in datalayout string");
 197   if (!Split.second.empty() && Split.first.empty())
 198     report_fatal_error("Expected token before separator in datalayout string");
 199   return Split;
 200 }
 201
 202 /// Get an unsigned integer, including error checks.
 203 static unsigned getInt(StringRef R) {
 204   unsigned Result;
 205   bool error = R.getAsInteger(10, Result); (void)error;
 206   if (error)
 207     report_fatal_error("not a number, or does not fit in an unsigned int");
 208   return Result;
 209 }
 210
 211 /// Convert bits into bytes. Assert if not a byte width multiple.
 212 static unsigned inBytes(unsigned Bits) {
 213   if (Bits % 8)
 214     report_fatal_error("number of bits must be a byte width multiple");
 215   return Bits / 8;
 216 }
 217
 218 void DataLayout::parseSpecifier(StringRef Desc) {
 219   StringRepresentation = Desc;
 220   while (!Desc.empty()) {
 221     // Split at '-'.
 222     std::pair<StringRef, StringRef> Split = split(Desc, '-');
 223     Desc = Split.second;
 224
 225     // Split at ':'.
 226     Split = split(Split.first, ':');
 227
 228     // Aliases used below.
 229     StringRef &Tok  = Split.first;  // Current token.
 230     StringRef &Rest = Split.second; // The rest of the string.
 231
 232     char Specifier = Tok.front();
 233     Tok = Tok.substr(1);
 234
 235     switch (Specifier) {
 236     case 's':
 237       // Ignored for backward compatibility.
 238       // FIXME: remove this on LLVM 4.0.
 239       break;
 240     case 'E':
 241       BigEndian = true;
 242       break;
 243     case 'e':
 244       BigEndian = false;
 245       break;
 246     case 'p': {
 247       // Address space.
 248       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
 249       if (!isUInt<24>(AddrSpace))
 250         report_fatal_error("Invalid address space, must be a 24bit integer");
 251
 252       // Size.
 253       if (Rest.empty())
 254         report_fatal_error(
 255             "Missing size specification for pointer in datalayout string");
 256       Split = split(Rest, ':');
 257       unsigned PointerMemSize = inBytes(getInt(Tok));
 258       if (!PointerMemSize)
 259         report_fatal_error("Invalid pointer size of 0 bytes");
 260
 261       // ABI alignment.
 262       if (Rest.empty())
 263         report_fatal_error(
 264             "Missing alignment specification for pointer in datalayout string");
 265       Split = split(Rest, ':');
 266       unsigned PointerABIAlign = inBytes(getInt(Tok));
 267       if (!isPowerOf2_64(PointerABIAlign))
 268         report_fatal_error(
 269             "Pointer ABI alignment must be a power of 2");
 270
 271       // Preferred alignment.
 272       unsigned PointerPrefAlign = PointerABIAlign;
 273       if (!Rest.empty()) {
 274         Split = split(Rest, ':');
 275         PointerPrefAlign = inBytes(getInt(Tok));
 276         if (!isPowerOf2_64(PointerPrefAlign))
 277           report_fatal_error(
 278             "Pointer preferred alignment must be a power of 2");
 279       }
 280
 281       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
 282                           PointerMemSize);
 283       break;
 284     }
 285     case 'i':
 286     case 'v':
 287     case 'f':
 288     case 'a': {
 289       AlignTypeEnum AlignType;
 290       switch (Specifier) {
 291       default:
 292       case 'i': AlignType = INTEGER_ALIGN; break;
 293       case 'v': AlignType = VECTOR_ALIGN; break;
 294       case 'f': AlignType = FLOAT_ALIGN; break;
 295       case 'a': AlignType = AGGREGATE_ALIGN; break;
 296       }
 297
 298       // Bit size.
 299       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
 300
 301       if (AlignType == AGGREGATE_ALIGN && Size != 0)
 302         report_fatal_error(
 303             "Sized aggregate specification in datalayout string");
 304
 305       // ABI alignment.
 306       if (Rest.empty())
 307         report_fatal_error(
 308             "Missing alignment specification in datalayout string");
 309       Split = split(Rest, ':');
 310       unsigned ABIAlign = inBytes(getInt(Tok));
 311       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
 312         report_fatal_error(
 313             "ABI alignment specification must be >0 for non-aggregate types");
 314
 315       // Preferred alignment.
 316       unsigned PrefAlign = ABIAlign;
 317       if (!Rest.empty()) {
 318         Split = split(Rest, ':');
 319         PrefAlign = inBytes(getInt(Tok));
 320       }
 321
 322       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 323
 324       break;
 325     }
 326     case 'n':  // Native integer types.
 327       for (;;) {
 328         unsigned Width = getInt(Tok);
 329         if (Width == 0)
 330           report_fatal_error(
 331               "Zero width native integer type in datalayout string");
 332         LegalIntWidths.push_back(Width);
 333         if (Rest.empty())
 334           break;
 335         Split = split(Rest, ':');
 336       }
 337       break;
 338     case 'S': { // Stack natural alignment.
 339       StackNaturalAlign = inBytes(getInt(Tok));
 340       break;
 341     }
 342     case 'm':
 343       if (!Tok.empty())
 344         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
 345       if (Rest.empty())
 346         report_fatal_error("Expected mangling specifier in datalayout string");
 347       if (Rest.size() > 1)
 348         report_fatal_error("Unknown mangling specifier in datalayout string");
 349       switch(Rest[0]) {
 350       default:
 351         report_fatal_error("Unknown mangling in datalayout string");
 352       case 'e':
 353         ManglingMode = MM_ELF;
 354         break;
 355       case 'o':
 356         ManglingMode = MM_MachO;
 357         break;
 358       case 'm':
 359         ManglingMode = MM_Mips;
 360         break;
 361       case 'w':
 362         ManglingMode = MM_WINCOFF;
 363         break;
 364       }
 365       break;
 366     default:
 367       report_fatal_error("Unknown specifier in datalayout string");
 368       break;
 369     }
 370   }
 371 }
 372
 373 DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
 374   init(M);
 375 }
 376
 377 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 378
 379 bool DataLayout::operator==(const DataLayout &Other) const {
 380   bool Ret = BigEndian == Other.BigEndian &&
 381              StackNaturalAlign == Other.StackNaturalAlign &&
 382              ManglingMode == Other.ManglingMode &&
 383              LegalIntWidths == Other.LegalIntWidths &&
 384              Alignments == Other.Alignments && Pointers == Other.Pointers;
 385   // Note: getStringRepresentation() might differs, it is not canonicalized
 386   return Ret;
 387 }
 388
 389 void
 390 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 391                          unsigned pref_align, uint32_t bit_width) {
 392   if (!isUInt<24>(bit_width))
 393     report_fatal_error("Invalid bit width, must be a 24bit integer");
 394   if (!isUInt<16>(abi_align))
 395     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
 396   if (!isUInt<16>(pref_align))
 397     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
 398   if (abi_align != 0 && !isPowerOf2_64(abi_align))
 399     report_fatal_error("Invalid ABI alignment, must be a power of 2");
 400   if (pref_align != 0 && !isPowerOf2_64(pref_align))
 401     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 402
 403   if (pref_align < abi_align)
 404     report_fatal_error(
 405         "Preferred alignment cannot be less than the ABI alignment");
 406
 407   for (LayoutAlignElem &Elem : Alignments) {
 408     if (Elem.AlignType == (unsigned)align_type &&
 409         Elem.TypeBitWidth == bit_width) {
 410       // Update the abi, preferred alignments.
 411       Elem.ABIAlign = abi_align;
 412       Elem.PrefAlign = pref_align;
 413       return;
 414     }
 415   }
 416
 417   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 418                                             pref_align, bit_width));
 419 }
 420
 421 DataLayout::PointersTy::iterator
 422 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
 423   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 424                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
 425     return A.AddressSpace < AddressSpace;
 426   });
 427 }
 428
 429 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 430                                      unsigned PrefAlign,
 431                                      uint32_t TypeByteWidth) {
 432   if (PrefAlign < ABIAlign)
 433     report_fatal_error(
 434         "Preferred alignment cannot be less than the ABI alignment");
 435
 436   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 437   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 438     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 439                                              TypeByteWidth));
 440   } else {
 441     I->ABIAlign = ABIAlign;
 442     I->PrefAlign = PrefAlign;
 443     I->TypeByteWidth = TypeByteWidth;
 444   }
 445 }
 446
 447 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 448 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 449 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 450                                       uint32_t BitWidth, bool ABIInfo,
 451                                       Type *Ty) const {
 452   // Check to see if we have an exact match and remember the best match we see.
 453   int BestMatchIdx = -1;
 454   int LargestInt = -1;
 455   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 456     if (Alignments[i].AlignType == (unsigned)AlignType &&
 457         Alignments[i].TypeBitWidth == BitWidth)
 458       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 459
 460     // The best match so far depends on what we're looking for.
 461      if (AlignType == INTEGER_ALIGN &&
 462          Alignments[i].AlignType == INTEGER_ALIGN) {
 463       // The "best match" for integers is the smallest size that is larger than
 464       // the BitWidth requested.
 465       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 466           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 467         BestMatchIdx = i;
 468       // However, if there isn't one that's larger, then we must use the
 469       // largest one we have (see below)
 470       if (LargestInt == -1 ||
 471           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 472         LargestInt = i;
 473     }
 474   }
 475
 476   // Okay, we didn't find an exact solution.  Fall back here depending on what
 477   // is being looked for.
 478   if (BestMatchIdx == -1) {
 479     // If we didn't find an integer alignment, fall back on most conservative.
 480     if (AlignType == INTEGER_ALIGN) {
 481       BestMatchIdx = LargestInt;
 482     } else {
 483       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 484
 485       // By default, use natural alignment for vector types. This is consistent
 486       // with what clang and llvm-gcc do.
 487       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 488       Align *= cast<VectorType>(Ty)->getNumElements();
 489       // If the alignment is not a power of 2, round up to the next power of 2.
 490       // This happens for non-power-of-2 length vectors.
 491       if (Align & (Align-1))
 492         Align = NextPowerOf2(Align);
 493       return Align;
 494     }
 495   }
 496
 497   // Since we got a "best match" index, just return it.
 498   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 499                  : Alignments[BestMatchIdx].PrefAlign;
 500 }
 501
 502 namespace {
 503
 504 class StructLayoutMap {
 505   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 506   LayoutInfoTy LayoutInfo;
 507
 508 public:
 509   ~StructLayoutMap() {
 510     // Remove any layouts.
 511     for (const auto &I : LayoutInfo) {
 512       StructLayout *Value = I.second;
 513       Value->~StructLayout();
 514       free(Value);
 515     }
 516   }
 517
 518   StructLayout *&operator[](StructType *STy) {
 519     return LayoutInfo[STy];
 520   }
 521 };
 522
 523 } // end anonymous namespace
 524
 525 void DataLayout::clear() {
 526   LegalIntWidths.clear();
 527   Alignments.clear();
 528   Pointers.clear();
 529   delete static_cast<StructLayoutMap *>(LayoutMap);
 530   LayoutMap = nullptr;
 531 }
 532
 533 DataLayout::~DataLayout() {
 534   clear();
 535 }
 536
 537 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 538   if (!LayoutMap)
 539     LayoutMap = new StructLayoutMap();
 540
 541   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 542   StructLayout *&SL = (*STM)[Ty];
 543   if (SL) return SL;
 544
 545   // Otherwise, create the struct layout.  Because it is variable length, we
 546   // malloc it, then use placement new.
 547   int NumElts = Ty->getNumElements();
 548   StructLayout *L =
 549     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 550
 551   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 552   // entries to be added to TheMap, invalidating our reference.
 553   SL = L;
 554
 555   new (L) StructLayout(Ty, *this);
 556
 557   return L;
 558 }
 559
 560
 561 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 562   PointersTy::const_iterator I = findPointerLowerBound(AS);
 563   if (I == Pointers.end() || I->AddressSpace != AS) {
 564     I = findPointerLowerBound(0);
 565     assert(I->AddressSpace == 0);
 566   }
 567   return I->ABIAlign;
 568 }
 569
 570 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 571   PointersTy::const_iterator I = findPointerLowerBound(AS);
 572   if (I == Pointers.end() || I->AddressSpace != AS) {
 573     I = findPointerLowerBound(0);
 574     assert(I->AddressSpace == 0);
 575   }
 576   return I->PrefAlign;
 577 }
 578
 579 unsigned DataLayout::getPointerSize(unsigned AS) const {
 580   PointersTy::const_iterator I = findPointerLowerBound(AS);
 581   if (I == Pointers.end() || I->AddressSpace != AS) {
 582     I = findPointerLowerBound(0);
 583     assert(I->AddressSpace == 0);
 584   }
 585   return I->TypeByteWidth;
 586 }
 587
 588 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 589   assert(Ty->isPtrOrPtrVectorTy() &&
 590          "This should only be called with a pointer or pointer vector type");
 591
 592   if (Ty->isPointerTy())
 593     return getTypeSizeInBits(Ty);
 594
 595   return getTypeSizeInBits(Ty->getScalarType());
 596 }
 597
 598 /*!
 599   \param abi_or_pref Flag that determines which alignment is returned. true
 600   returns the ABI alignment, false returns the preferred alignment.
 601   \param Ty The underlying type for which alignment is determined.
 602
 603   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 604   == false) for the requested type \a Ty.
 605  */
 606 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 607   int AlignType = -1;
 608
 609   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 610   switch (Ty->getTypeID()) {
 611   // Early escape for the non-numeric types.
 612   case Type::LabelTyID:
 613     return (abi_or_pref
 614             ? getPointerABIAlignment(0)
 615             : getPointerPrefAlignment(0));
 616   case Type::PointerTyID: {
 617     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 618     return (abi_or_pref
 619             ? getPointerABIAlignment(AS)
 620             : getPointerPrefAlignment(AS));
 621     }
 622   case Type::ArrayTyID:
 623     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 624
 625   case Type::StructTyID: {
 626     // Packed structure types always have an ABI alignment of one.
 627     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 628       return 1;
 629
 630     // Get the layout annotation... which is lazily created on demand.
 631     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 632     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 633     return std::max(Align, Layout->getAlignment());
 634   }
 635   case Type::IntegerTyID:
 636     AlignType = INTEGER_ALIGN;
 637     break;
 638   case Type::HalfTyID:
 639   case Type::FloatTyID:
 640   case Type::DoubleTyID:
 641   // PPC_FP128TyID and FP128TyID have different data contents, but the
 642   // same size and alignment, so they look the same here.
 643   case Type::PPC_FP128TyID:
 644   case Type::FP128TyID:
 645   case Type::X86_FP80TyID:
 646     AlignType = FLOAT_ALIGN;
 647     break;
 648   case Type::X86_MMXTyID:
 649   case Type::VectorTyID:
 650     AlignType = VECTOR_ALIGN;
 651     break;
 652   default:
 653     llvm_unreachable("Bad type for getAlignment!!!");
 654   }
 655
 656   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 657                           abi_or_pref, Ty);
 658 }
 659
 660 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 661   return getAlignment(Ty, true);
 662 }
 663
 664 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 665 /// an integer type of the specified bitwidth.
 666 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 667   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 668 }
 669
 670 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 671   return getAlignment(Ty, false);
 672 }
 673
 674 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 675   unsigned Align = getPrefTypeAlignment(Ty);
 676   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 677   return Log2_32(Align);
 678 }
 679
 680 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 681                                        unsigned AddressSpace) const {
 682   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 683 }
 684
 685 Type *DataLayout::getIntPtrType(Type *Ty) const {
 686   assert(Ty->isPtrOrPtrVectorTy() &&
 687          "Expected a pointer or pointer vector type.");
 688   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 689   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 690   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 691     return VectorType::get(IntTy, VecTy->getNumElements());
 692   return IntTy;
 693 }
 694
 695 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 696   for (unsigned LegalIntWidth : LegalIntWidths)
 697     if (Width <= LegalIntWidth)
 698       return Type::getIntNTy(C, LegalIntWidth);
 699   return nullptr;
 700 }
 701
 702 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 703   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 704   return Max != LegalIntWidths.end() ? *Max : 0;
 705 }
 706
 707 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 708                                       ArrayRef<Value *> Indices) const {
 709   Type *Ty = ptrTy;
 710   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 711   uint64_t Result = 0;
 712
 713   generic_gep_type_iterator<Value* const*>
 714     TI = gep_type_begin(ptrTy, Indices);
 715   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 716        ++CurIDX, ++TI) {
 717     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 718       assert(Indices[CurIDX]->getType() ==
 719              Type::getInt32Ty(ptrTy->getContext()) &&
 720              "Illegal struct idx");
 721       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 722
 723       // Get structure layout information...
 724       const StructLayout *Layout = getStructLayout(STy);
 725
 726       // Add in the offset, as calculated by the structure layout info...
 727       Result += Layout->getElementOffset(FieldNo);
 728
 729       // Update Ty to refer to current element
 730       Ty = STy->getElementType(FieldNo);
 731     } else {
 732       // Update Ty to refer to current element
 733       Ty = cast<SequentialType>(Ty)->getElementType();
 734
 735       // Get the array index and the size of each array element.
 736       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 737         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 738     }
 739   }
 740
 741   return Result;
 742 }
 743
 744 /// getPreferredAlignment - Return the preferred alignment of the specified
 745 /// global.  This includes an explicitly requested alignment (if the global
 746 /// has one).
 747 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 748   Type *ElemType = GV->getType()->getElementType();
 749   unsigned Alignment = getPrefTypeAlignment(ElemType);
 750   unsigned GVAlignment = GV->getAlignment();
 751   if (GVAlignment >= Alignment) {
 752     Alignment = GVAlignment;
 753   } else if (GVAlignment != 0) {
 754     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 755   }
 756
 757   if (GV->hasInitializer() && GVAlignment == 0) {
 758     if (Alignment < 16) {
 759       // If the global is not external, see if it is large.  If so, give it a
 760       // larger alignment.
 761       if (getTypeSizeInBits(ElemType) > 128)
 762         Alignment = 16;    // 16-byte alignment.
 763     }
 764   }
 765   return Alignment;
 766 }
 767
 768 /// getPreferredAlignmentLog - Return the preferred alignment of the
 769 /// specified global, returned in log form.  This includes an explicitly
 770 /// requested alignment (if the global has one).
 771 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 772   return Log2_32(getPreferredAlignment(GV));
 773 }
 774