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