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