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.isOSBinFormatCOFF())
 154     return T.getArch() == Triple::x86 ? "-m:x" : "-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       case 'x':
 365         ManglingMode = MM_WinCOFFX86;
 366         break;
 367       }
 368       break;
 369     default:
 370       report_fatal_error("Unknown specifier in datalayout string");
 371       break;
 372     }
 373   }
 374 }
 375
 376 DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
 377   init(M);
 378 }
 379
 380 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 381
 382 bool DataLayout::operator==(const DataLayout &Other) const {
 383   bool Ret = BigEndian == Other.BigEndian &&
 384              StackNaturalAlign == Other.StackNaturalAlign &&
 385              ManglingMode == Other.ManglingMode &&
 386              LegalIntWidths == Other.LegalIntWidths &&
 387              Alignments == Other.Alignments && Pointers == Other.Pointers;
 388   // Note: getStringRepresentation() might differs, it is not canonicalized
 389   return Ret;
 390 }
 391
 392 void
 393 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 394                          unsigned pref_align, uint32_t bit_width) {
 395   if (!isUInt<24>(bit_width))
 396     report_fatal_error("Invalid bit width, must be a 24bit integer");
 397   if (!isUInt<16>(abi_align))
 398     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
 399   if (!isUInt<16>(pref_align))
 400     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
 401   if (abi_align != 0 && !isPowerOf2_64(abi_align))
 402     report_fatal_error("Invalid ABI alignment, must be a power of 2");
 403   if (pref_align != 0 && !isPowerOf2_64(pref_align))
 404     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 405
 406   if (pref_align < abi_align)
 407     report_fatal_error(
 408         "Preferred alignment cannot be less than the ABI alignment");
 409
 410   for (LayoutAlignElem &Elem : Alignments) {
 411     if (Elem.AlignType == (unsigned)align_type &&
 412         Elem.TypeBitWidth == bit_width) {
 413       // Update the abi, preferred alignments.
 414       Elem.ABIAlign = abi_align;
 415       Elem.PrefAlign = pref_align;
 416       return;
 417     }
 418   }
 419
 420   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 421                                             pref_align, bit_width));
 422 }
 423
 424 DataLayout::PointersTy::iterator
 425 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
 426   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 427                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
 428     return A.AddressSpace < AddressSpace;
 429   });
 430 }
 431
 432 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 433                                      unsigned PrefAlign,
 434                                      uint32_t TypeByteWidth) {
 435   if (PrefAlign < ABIAlign)
 436     report_fatal_error(
 437         "Preferred alignment cannot be less than the ABI alignment");
 438
 439   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 440   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 441     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 442                                              TypeByteWidth));
 443   } else {
 444     I->ABIAlign = ABIAlign;
 445     I->PrefAlign = PrefAlign;
 446     I->TypeByteWidth = TypeByteWidth;
 447   }
 448 }
 449
 450 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 451 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 452 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 453                                       uint32_t BitWidth, bool ABIInfo,
 454                                       Type *Ty) const {
 455   // Check to see if we have an exact match and remember the best match we see.
 456   int BestMatchIdx = -1;
 457   int LargestInt = -1;
 458   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 459     if (Alignments[i].AlignType == (unsigned)AlignType &&
 460         Alignments[i].TypeBitWidth == BitWidth)
 461       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 462
 463     // The best match so far depends on what we're looking for.
 464     if (AlignType == INTEGER_ALIGN &&
 465         Alignments[i].AlignType == INTEGER_ALIGN) {
 466       // The "best match" for integers is the smallest size that is larger than
 467       // the BitWidth requested.
 468       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 469           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 470         BestMatchIdx = i;
 471       // However, if there isn't one that's larger, then we must use the
 472       // largest one we have (see below)
 473       if (LargestInt == -1 ||
 474           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 475         LargestInt = i;
 476     }
 477   }
 478
 479   // Okay, we didn't find an exact solution.  Fall back here depending on what
 480   // is being looked for.
 481   if (BestMatchIdx == -1) {
 482     // If we didn't find an integer alignment, fall back on most conservative.
 483     if (AlignType == INTEGER_ALIGN) {
 484       BestMatchIdx = LargestInt;
 485     } else if (AlignType == VECTOR_ALIGN) {
 486       // By default, use natural alignment for vector types. This is consistent
 487       // with what clang and llvm-gcc do.
 488       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 489       Align *= cast<VectorType>(Ty)->getNumElements();
 490       // If the alignment is not a power of 2, round up to the next power of 2.
 491       // This happens for non-power-of-2 length vectors.
 492       if (Align & (Align-1))
 493         Align = NextPowerOf2(Align);
 494       return Align;
 495     }
 496   }
 497
 498   // If we still couldn't find a reasonable default alignment, fall back
 499   // to a simple heuristic that the alignment is the first power of two
 500   // greater-or-equal to the store size of the type.  This is a reasonable
 501   // approximation of reality, and if the user wanted something less
 502   // less conservative, they should have specified it explicitly in the data
 503   // layout.
 504   if (BestMatchIdx == -1) {
 505     unsigned Align = getTypeStoreSize(Ty);
 506     if (Align & (Align-1))
 507       Align = NextPowerOf2(Align);
 508     return Align;
 509   }
 510
 511   // Since we got a "best match" index, just return it.
 512   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 513                  : Alignments[BestMatchIdx].PrefAlign;
 514 }
 515
 516 namespace {
 517
 518 class StructLayoutMap {
 519   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 520   LayoutInfoTy LayoutInfo;
 521
 522 public:
 523   ~StructLayoutMap() {
 524     // Remove any layouts.
 525     for (const auto &I : LayoutInfo) {
 526       StructLayout *Value = I.second;
 527       Value->~StructLayout();
 528       free(Value);
 529     }
 530   }
 531
 532   StructLayout *&operator[](StructType *STy) {
 533     return LayoutInfo[STy];
 534   }
 535 };
 536
 537 } // end anonymous namespace
 538
 539 void DataLayout::clear() {
 540   LegalIntWidths.clear();
 541   Alignments.clear();
 542   Pointers.clear();
 543   delete static_cast<StructLayoutMap *>(LayoutMap);
 544   LayoutMap = nullptr;
 545 }
 546
 547 DataLayout::~DataLayout() {
 548   clear();
 549 }
 550
 551 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 552   if (!LayoutMap)
 553     LayoutMap = new StructLayoutMap();
 554
 555   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 556   StructLayout *&SL = (*STM)[Ty];
 557   if (SL) return SL;
 558
 559   // Otherwise, create the struct layout.  Because it is variable length, we
 560   // malloc it, then use placement new.
 561   int NumElts = Ty->getNumElements();
 562   StructLayout *L =
 563     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 564
 565   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 566   // entries to be added to TheMap, invalidating our reference.
 567   SL = L;
 568
 569   new (L) StructLayout(Ty, *this);
 570
 571   return L;
 572 }
 573
 574
 575 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 576   PointersTy::const_iterator I = findPointerLowerBound(AS);
 577   if (I == Pointers.end() || I->AddressSpace != AS) {
 578     I = findPointerLowerBound(0);
 579     assert(I->AddressSpace == 0);
 580   }
 581   return I->ABIAlign;
 582 }
 583
 584 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 585   PointersTy::const_iterator I = findPointerLowerBound(AS);
 586   if (I == Pointers.end() || I->AddressSpace != AS) {
 587     I = findPointerLowerBound(0);
 588     assert(I->AddressSpace == 0);
 589   }
 590   return I->PrefAlign;
 591 }
 592
 593 unsigned DataLayout::getPointerSize(unsigned AS) const {
 594   PointersTy::const_iterator I = findPointerLowerBound(AS);
 595   if (I == Pointers.end() || I->AddressSpace != AS) {
 596     I = findPointerLowerBound(0);
 597     assert(I->AddressSpace == 0);
 598   }
 599   return I->TypeByteWidth;
 600 }
 601
 602 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 603   assert(Ty->isPtrOrPtrVectorTy() &&
 604          "This should only be called with a pointer or pointer vector type");
 605
 606   if (Ty->isPointerTy())
 607     return getTypeSizeInBits(Ty);
 608
 609   return getTypeSizeInBits(Ty->getScalarType());
 610 }
 611
 612 /*!
 613   \param abi_or_pref Flag that determines which alignment is returned. true
 614   returns the ABI alignment, false returns the preferred alignment.
 615   \param Ty The underlying type for which alignment is determined.
 616
 617   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 618   == false) for the requested type \a Ty.
 619  */
 620 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 621   int AlignType = -1;
 622
 623   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 624   switch (Ty->getTypeID()) {
 625   // Early escape for the non-numeric types.
 626   case Type::LabelTyID:
 627     return (abi_or_pref
 628             ? getPointerABIAlignment(0)
 629             : getPointerPrefAlignment(0));
 630   case Type::PointerTyID: {
 631     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 632     return (abi_or_pref
 633             ? getPointerABIAlignment(AS)
 634             : getPointerPrefAlignment(AS));
 635     }
 636   case Type::ArrayTyID:
 637     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 638
 639   case Type::StructTyID: {
 640     // Packed structure types always have an ABI alignment of one.
 641     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 642       return 1;
 643
 644     // Get the layout annotation... which is lazily created on demand.
 645     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 646     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 647     return std::max(Align, Layout->getAlignment());
 648   }
 649   case Type::IntegerTyID:
 650     AlignType = INTEGER_ALIGN;
 651     break;
 652   case Type::HalfTyID:
 653   case Type::FloatTyID:
 654   case Type::DoubleTyID:
 655   // PPC_FP128TyID and FP128TyID have different data contents, but the
 656   // same size and alignment, so they look the same here.
 657   case Type::PPC_FP128TyID:
 658   case Type::FP128TyID:
 659   case Type::X86_FP80TyID:
 660     AlignType = FLOAT_ALIGN;
 661     break;
 662   case Type::X86_MMXTyID:
 663   case Type::VectorTyID:
 664     AlignType = VECTOR_ALIGN;
 665     break;
 666   default:
 667     llvm_unreachable("Bad type for getAlignment!!!");
 668   }
 669
 670   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 671                           abi_or_pref, Ty);
 672 }
 673
 674 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 675   return getAlignment(Ty, true);
 676 }
 677
 678 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 679 /// an integer type of the specified bitwidth.
 680 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 681   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 682 }
 683
 684 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 685   return getAlignment(Ty, false);
 686 }
 687
 688 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 689   unsigned Align = getPrefTypeAlignment(Ty);
 690   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 691   return Log2_32(Align);
 692 }
 693
 694 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 695                                        unsigned AddressSpace) const {
 696   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 697 }
 698
 699 Type *DataLayout::getIntPtrType(Type *Ty) const {
 700   assert(Ty->isPtrOrPtrVectorTy() &&
 701          "Expected a pointer or pointer vector type.");
 702   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 703   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 704   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 705     return VectorType::get(IntTy, VecTy->getNumElements());
 706   return IntTy;
 707 }
 708
 709 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 710   for (unsigned LegalIntWidth : LegalIntWidths)
 711     if (Width <= LegalIntWidth)
 712       return Type::getIntNTy(C, LegalIntWidth);
 713   return nullptr;
 714 }
 715
 716 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 717   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 718   return Max != LegalIntWidths.end() ? *Max : 0;
 719 }
 720
 721 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 722                                       ArrayRef<Value *> Indices) const {
 723   Type *Ty = ptrTy;
 724   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 725   uint64_t Result = 0;
 726
 727   generic_gep_type_iterator<Value* const*>
 728     TI = gep_type_begin(ptrTy, Indices);
 729   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 730        ++CurIDX, ++TI) {
 731     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 732       assert(Indices[CurIDX]->getType() ==
 733              Type::getInt32Ty(ptrTy->getContext()) &&
 734              "Illegal struct idx");
 735       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 736
 737       // Get structure layout information...
 738       const StructLayout *Layout = getStructLayout(STy);
 739
 740       // Add in the offset, as calculated by the structure layout info...
 741       Result += Layout->getElementOffset(FieldNo);
 742
 743       // Update Ty to refer to current element
 744       Ty = STy->getElementType(FieldNo);
 745     } else {
 746       // Update Ty to refer to current element
 747       Ty = cast<SequentialType>(Ty)->getElementType();
 748
 749       // Get the array index and the size of each array element.
 750       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 751         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 752     }
 753   }
 754
 755   return Result;
 756 }
 757
 758 /// getPreferredAlignment - Return the preferred alignment of the specified
 759 /// global.  This includes an explicitly requested alignment (if the global
 760 /// has one).
 761 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 762   Type *ElemType = GV->getType()->getElementType();
 763   unsigned Alignment = getPrefTypeAlignment(ElemType);
 764   unsigned GVAlignment = GV->getAlignment();
 765   if (GVAlignment >= Alignment) {
 766     Alignment = GVAlignment;
 767   } else if (GVAlignment != 0) {
 768     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 769   }
 770
 771   if (GV->hasInitializer() && GVAlignment == 0) {
 772     if (Alignment < 16) {
 773       // If the global is not external, see if it is large.  If so, give it a
 774       // larger alignment.
 775       if (getTypeSizeInBits(ElemType) > 128)
 776         Alignment = 16;    // 16-byte alignment.
 777     }
 778   }
 779   return Alignment;
 780 }
 781
 782 /// getPreferredAlignmentLog - Return the preferred alignment of the
 783 /// specified global, returned in log form.  This includes an explicitly
 784 /// requested alignment (if the global has one).
 785 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 786   return Log2_32(getPreferredAlignment(GV));
 787 }
 788