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 if (AlignType == VECTOR_ALIGN) {
 483       // By default, use natural alignment for vector types. This is consistent
 484       // with what clang and llvm-gcc do.
 485       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 486       Align *= cast<VectorType>(Ty)->getNumElements();
 487       // If the alignment is not a power of 2, round up to the next power of 2.
 488       // This happens for non-power-of-2 length vectors.
 489       if (Align & (Align-1))
 490         Align = NextPowerOf2(Align);
 491       return Align;
 492     }
 493   }
 494
 495   // If we still couldn't find a reasonable default alignment, fall back
 496   // to a simple heuristic that the alignment is the first power of two
 497   // greater-or-equal to the store size of the type.  This is a reasonable
 498   // approximation of reality, and if the user wanted something less
 499   // less conservative, they should have specified it explicitly in the data
 500   // layout.
 501   if (BestMatchIdx == -1) {
 502     unsigned Align = getTypeStoreSize(Ty);
 503     if (Align & (Align-1))
 504       Align = NextPowerOf2(Align);
 505     return Align;
 506   }
 507
 508   // Since we got a "best match" index, just return it.
 509   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 510                  : Alignments[BestMatchIdx].PrefAlign;
 511 }
 512
 513 namespace {
 514
 515 class StructLayoutMap {
 516   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 517   LayoutInfoTy LayoutInfo;
 518
 519 public:
 520   ~StructLayoutMap() {
 521     // Remove any layouts.
 522     for (const auto &I : LayoutInfo) {
 523       StructLayout *Value = I.second;
 524       Value->~StructLayout();
 525       free(Value);
 526     }
 527   }
 528
 529   StructLayout *&operator[](StructType *STy) {
 530     return LayoutInfo[STy];
 531   }
 532 };
 533
 534 } // end anonymous namespace
 535
 536 void DataLayout::clear() {
 537   LegalIntWidths.clear();
 538   Alignments.clear();
 539   Pointers.clear();
 540   delete static_cast<StructLayoutMap *>(LayoutMap);
 541   LayoutMap = nullptr;
 542 }
 543
 544 DataLayout::~DataLayout() {
 545   clear();
 546 }
 547
 548 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 549   if (!LayoutMap)
 550     LayoutMap = new StructLayoutMap();
 551
 552   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 553   StructLayout *&SL = (*STM)[Ty];
 554   if (SL) return SL;
 555
 556   // Otherwise, create the struct layout.  Because it is variable length, we
 557   // malloc it, then use placement new.
 558   int NumElts = Ty->getNumElements();
 559   StructLayout *L =
 560     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 561
 562   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 563   // entries to be added to TheMap, invalidating our reference.
 564   SL = L;
 565
 566   new (L) StructLayout(Ty, *this);
 567
 568   return L;
 569 }
 570
 571
 572 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 573   PointersTy::const_iterator I = findPointerLowerBound(AS);
 574   if (I == Pointers.end() || I->AddressSpace != AS) {
 575     I = findPointerLowerBound(0);
 576     assert(I->AddressSpace == 0);
 577   }
 578   return I->ABIAlign;
 579 }
 580
 581 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 582   PointersTy::const_iterator I = findPointerLowerBound(AS);
 583   if (I == Pointers.end() || I->AddressSpace != AS) {
 584     I = findPointerLowerBound(0);
 585     assert(I->AddressSpace == 0);
 586   }
 587   return I->PrefAlign;
 588 }
 589
 590 unsigned DataLayout::getPointerSize(unsigned AS) const {
 591   PointersTy::const_iterator I = findPointerLowerBound(AS);
 592   if (I == Pointers.end() || I->AddressSpace != AS) {
 593     I = findPointerLowerBound(0);
 594     assert(I->AddressSpace == 0);
 595   }
 596   return I->TypeByteWidth;
 597 }
 598
 599 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 600   assert(Ty->isPtrOrPtrVectorTy() &&
 601          "This should only be called with a pointer or pointer vector type");
 602
 603   if (Ty->isPointerTy())
 604     return getTypeSizeInBits(Ty);
 605
 606   return getTypeSizeInBits(Ty->getScalarType());
 607 }
 608
 609 /*!
 610   \param abi_or_pref Flag that determines which alignment is returned. true
 611   returns the ABI alignment, false returns the preferred alignment.
 612   \param Ty The underlying type for which alignment is determined.
 613
 614   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 615   == false) for the requested type \a Ty.
 616  */
 617 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 618   int AlignType = -1;
 619
 620   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 621   switch (Ty->getTypeID()) {
 622   // Early escape for the non-numeric types.
 623   case Type::LabelTyID:
 624     return (abi_or_pref
 625             ? getPointerABIAlignment(0)
 626             : getPointerPrefAlignment(0));
 627   case Type::PointerTyID: {
 628     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 629     return (abi_or_pref
 630             ? getPointerABIAlignment(AS)
 631             : getPointerPrefAlignment(AS));
 632     }
 633   case Type::ArrayTyID:
 634     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 635
 636   case Type::StructTyID: {
 637     // Packed structure types always have an ABI alignment of one.
 638     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 639       return 1;
 640
 641     // Get the layout annotation... which is lazily created on demand.
 642     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 643     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 644     return std::max(Align, Layout->getAlignment());
 645   }
 646   case Type::IntegerTyID:
 647     AlignType = INTEGER_ALIGN;
 648     break;
 649   case Type::HalfTyID:
 650   case Type::FloatTyID:
 651   case Type::DoubleTyID:
 652   // PPC_FP128TyID and FP128TyID have different data contents, but the
 653   // same size and alignment, so they look the same here.
 654   case Type::PPC_FP128TyID:
 655   case Type::FP128TyID:
 656   case Type::X86_FP80TyID:
 657     AlignType = FLOAT_ALIGN;
 658     break;
 659   case Type::X86_MMXTyID:
 660   case Type::VectorTyID:
 661     AlignType = VECTOR_ALIGN;
 662     break;
 663   default:
 664     llvm_unreachable("Bad type for getAlignment!!!");
 665   }
 666
 667   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 668                           abi_or_pref, Ty);
 669 }
 670
 671 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 672   return getAlignment(Ty, true);
 673 }
 674
 675 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 676 /// an integer type of the specified bitwidth.
 677 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 678   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 679 }
 680
 681 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 682   return getAlignment(Ty, false);
 683 }
 684
 685 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 686   unsigned Align = getPrefTypeAlignment(Ty);
 687   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 688   return Log2_32(Align);
 689 }
 690
 691 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 692                                        unsigned AddressSpace) const {
 693   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 694 }
 695
 696 Type *DataLayout::getIntPtrType(Type *Ty) const {
 697   assert(Ty->isPtrOrPtrVectorTy() &&
 698          "Expected a pointer or pointer vector type.");
 699   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 700   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 701   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 702     return VectorType::get(IntTy, VecTy->getNumElements());
 703   return IntTy;
 704 }
 705
 706 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 707   for (unsigned LegalIntWidth : LegalIntWidths)
 708     if (Width <= LegalIntWidth)
 709       return Type::getIntNTy(C, LegalIntWidth);
 710   return nullptr;
 711 }
 712
 713 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 714   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 715   return Max != LegalIntWidths.end() ? *Max : 0;
 716 }
 717
 718 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 719                                       ArrayRef<Value *> Indices) const {
 720   Type *Ty = ptrTy;
 721   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 722   uint64_t Result = 0;
 723
 724   generic_gep_type_iterator<Value* const*>
 725     TI = gep_type_begin(ptrTy, Indices);
 726   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 727        ++CurIDX, ++TI) {
 728     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 729       assert(Indices[CurIDX]->getType() ==
 730              Type::getInt32Ty(ptrTy->getContext()) &&
 731              "Illegal struct idx");
 732       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 733
 734       // Get structure layout information...
 735       const StructLayout *Layout = getStructLayout(STy);
 736
 737       // Add in the offset, as calculated by the structure layout info...
 738       Result += Layout->getElementOffset(FieldNo);
 739
 740       // Update Ty to refer to current element
 741       Ty = STy->getElementType(FieldNo);
 742     } else {
 743       // Update Ty to refer to current element
 744       Ty = cast<SequentialType>(Ty)->getElementType();
 745
 746       // Get the array index and the size of each array element.
 747       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 748         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 749     }
 750   }
 751
 752   return Result;
 753 }
 754
 755 /// getPreferredAlignment - Return the preferred alignment of the specified
 756 /// global.  This includes an explicitly requested alignment (if the global
 757 /// has one).
 758 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 759   Type *ElemType = GV->getType()->getElementType();
 760   unsigned Alignment = getPrefTypeAlignment(ElemType);
 761   unsigned GVAlignment = GV->getAlignment();
 762   if (GVAlignment >= Alignment) {
 763     Alignment = GVAlignment;
 764   } else if (GVAlignment != 0) {
 765     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 766   }
 767
 768   if (GV->hasInitializer() && GVAlignment == 0) {
 769     if (Alignment < 16) {
 770       // If the global is not external, see if it is large.  If so, give it a
 771       // larger alignment.
 772       if (getTypeSizeInBits(ElemType) > 128)
 773         Alignment = 16;    // 16-byte alignment.
 774     }
 775   }
 776   return Alignment;
 777 }
 778
 779 /// getPreferredAlignmentLog - Return the preferred alignment of the
 780 /// specified global, returned in log form.  This includes an explicitly
 781 /// requested alignment (if the global has one).
 782 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 783   return Log2_32(getPreferredAlignment(GV));
 784 }
 785