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