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   if (PrefAlign < ABIAlign)
 428     report_fatal_error(
 429         "Preferred alignment cannot be less than the ABI alignment");
 430
 431   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 432   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 433     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 434                                              TypeByteWidth));
 435   } else {
 436     I->ABIAlign = ABIAlign;
 437     I->PrefAlign = PrefAlign;
 438     I->TypeByteWidth = TypeByteWidth;
 439   }
 440 }
 441
 442 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 443 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 444 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 445                                       uint32_t BitWidth, bool ABIInfo,
 446                                       Type *Ty) const {
 447   // Check to see if we have an exact match and remember the best match we see.
 448   int BestMatchIdx = -1;
 449   int LargestInt = -1;
 450   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 451     if (Alignments[i].AlignType == (unsigned)AlignType &&
 452         Alignments[i].TypeBitWidth == BitWidth)
 453       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 454
 455     // The best match so far depends on what we're looking for.
 456      if (AlignType == INTEGER_ALIGN &&
 457          Alignments[i].AlignType == INTEGER_ALIGN) {
 458       // The "best match" for integers is the smallest size that is larger than
 459       // the BitWidth requested.
 460       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 461           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 462         BestMatchIdx = i;
 463       // However, if there isn't one that's larger, then we must use the
 464       // largest one we have (see below)
 465       if (LargestInt == -1 ||
 466           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 467         LargestInt = i;
 468     }
 469   }
 470
 471   // Okay, we didn't find an exact solution.  Fall back here depending on what
 472   // is being looked for.
 473   if (BestMatchIdx == -1) {
 474     // If we didn't find an integer alignment, fall back on most conservative.
 475     if (AlignType == INTEGER_ALIGN) {
 476       BestMatchIdx = LargestInt;
 477     } else {
 478       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 479
 480       // By default, use natural alignment for vector types. This is consistent
 481       // with what clang and llvm-gcc do.
 482       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 483       Align *= cast<VectorType>(Ty)->getNumElements();
 484       // If the alignment is not a power of 2, round up to the next power of 2.
 485       // This happens for non-power-of-2 length vectors.
 486       if (Align & (Align-1))
 487         Align = NextPowerOf2(Align);
 488       return Align;
 489     }
 490   }
 491
 492   // Since we got a "best match" index, just return it.
 493   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 494                  : Alignments[BestMatchIdx].PrefAlign;
 495 }
 496
 497 namespace {
 498
 499 class StructLayoutMap {
 500   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 501   LayoutInfoTy LayoutInfo;
 502
 503 public:
 504   ~StructLayoutMap() {
 505     // Remove any layouts.
 506     for (const auto &I : LayoutInfo) {
 507       StructLayout *Value = I.second;
 508       Value->~StructLayout();
 509       free(Value);
 510     }
 511   }
 512
 513   StructLayout *&operator[](StructType *STy) {
 514     return LayoutInfo[STy];
 515   }
 516 };
 517
 518 } // end anonymous namespace
 519
 520 void DataLayout::clear() {
 521   LegalIntWidths.clear();
 522   Alignments.clear();
 523   Pointers.clear();
 524   delete static_cast<StructLayoutMap *>(LayoutMap);
 525   LayoutMap = nullptr;
 526 }
 527
 528 DataLayout::~DataLayout() {
 529   clear();
 530 }
 531
 532 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 533   if (!LayoutMap)
 534     LayoutMap = new StructLayoutMap();
 535
 536   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 537   StructLayout *&SL = (*STM)[Ty];
 538   if (SL) return SL;
 539
 540   // Otherwise, create the struct layout.  Because it is variable length, we
 541   // malloc it, then use placement new.
 542   int NumElts = Ty->getNumElements();
 543   StructLayout *L =
 544     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 545
 546   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 547   // entries to be added to TheMap, invalidating our reference.
 548   SL = L;
 549
 550   new (L) StructLayout(Ty, *this);
 551
 552   return L;
 553 }
 554
 555 std::string DataLayout::getStringRepresentation() const {
 556   std::string Result;
 557   raw_string_ostream OS(Result);
 558
 559   OS << (BigEndian ? "E" : "e");
 560
 561   switch (ManglingMode) {
 562   case MM_None:
 563     break;
 564   case MM_ELF:
 565     OS << "-m:e";
 566     break;
 567   case MM_MachO:
 568     OS << "-m:o";
 569     break;
 570   case MM_WINCOFF:
 571     OS << "-m:w";
 572     break;
 573   case MM_Mips:
 574     OS << "-m:m";
 575     break;
 576   }
 577
 578   for (const PointerAlignElem &PI : Pointers) {
 579     // Skip default.
 580     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
 581         PI.TypeByteWidth == 8)
 582       continue;
 583
 584     OS << "-p";
 585     if (PI.AddressSpace) {
 586       OS << PI.AddressSpace;
 587     }
 588     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
 589     if (PI.PrefAlign != PI.ABIAlign)
 590       OS << ':' << PI.PrefAlign*8;
 591   }
 592
 593   for (const LayoutAlignElem &AI : Alignments) {
 594     if (std::find(std::begin(DefaultAlignments), std::end(DefaultAlignments),
 595                   AI) != std::end(DefaultAlignments))
 596       continue;
 597     OS << '-' << (char)AI.AlignType;
 598     if (AI.TypeBitWidth)
 599       OS << AI.TypeBitWidth;
 600     OS << ':' << AI.ABIAlign*8;
 601     if (AI.ABIAlign != AI.PrefAlign)
 602       OS << ':' << AI.PrefAlign*8;
 603   }
 604
 605   if (!LegalIntWidths.empty()) {
 606     OS << "-n" << (unsigned)LegalIntWidths[0];
 607
 608     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 609       OS << ':' << (unsigned)LegalIntWidths[i];
 610   }
 611
 612   if (StackNaturalAlign)
 613     OS << "-S" << StackNaturalAlign*8;
 614
 615   return OS.str();
 616 }
 617
 618 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 619   PointersTy::const_iterator I = findPointerLowerBound(AS);
 620   if (I == Pointers.end() || I->AddressSpace != AS) {
 621     I = findPointerLowerBound(0);
 622     assert(I->AddressSpace == 0);
 623   }
 624   return I->ABIAlign;
 625 }
 626
 627 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 628   PointersTy::const_iterator I = findPointerLowerBound(AS);
 629   if (I == Pointers.end() || I->AddressSpace != AS) {
 630     I = findPointerLowerBound(0);
 631     assert(I->AddressSpace == 0);
 632   }
 633   return I->PrefAlign;
 634 }
 635
 636 unsigned DataLayout::getPointerSize(unsigned AS) const {
 637   PointersTy::const_iterator I = findPointerLowerBound(AS);
 638   if (I == Pointers.end() || I->AddressSpace != AS) {
 639     I = findPointerLowerBound(0);
 640     assert(I->AddressSpace == 0);
 641   }
 642   return I->TypeByteWidth;
 643 }
 644
 645 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 646   assert(Ty->isPtrOrPtrVectorTy() &&
 647          "This should only be called with a pointer or pointer vector type");
 648
 649   if (Ty->isPointerTy())
 650     return getTypeSizeInBits(Ty);
 651
 652   return getTypeSizeInBits(Ty->getScalarType());
 653 }
 654
 655 /*!
 656   \param abi_or_pref Flag that determines which alignment is returned. true
 657   returns the ABI alignment, false returns the preferred alignment.
 658   \param Ty The underlying type for which alignment is determined.
 659
 660   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 661   == false) for the requested type \a Ty.
 662  */
 663 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 664   int AlignType = -1;
 665
 666   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 667   switch (Ty->getTypeID()) {
 668   // Early escape for the non-numeric types.
 669   case Type::LabelTyID:
 670     return (abi_or_pref
 671             ? getPointerABIAlignment(0)
 672             : getPointerPrefAlignment(0));
 673   case Type::PointerTyID: {
 674     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 675     return (abi_or_pref
 676             ? getPointerABIAlignment(AS)
 677             : getPointerPrefAlignment(AS));
 678     }
 679   case Type::ArrayTyID:
 680     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 681
 682   case Type::StructTyID: {
 683     // Packed structure types always have an ABI alignment of one.
 684     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 685       return 1;
 686
 687     // Get the layout annotation... which is lazily created on demand.
 688     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 689     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 690     return std::max(Align, Layout->getAlignment());
 691   }
 692   case Type::IntegerTyID:
 693     AlignType = INTEGER_ALIGN;
 694     break;
 695   case Type::HalfTyID:
 696   case Type::FloatTyID:
 697   case Type::DoubleTyID:
 698   // PPC_FP128TyID and FP128TyID have different data contents, but the
 699   // same size and alignment, so they look the same here.
 700   case Type::PPC_FP128TyID:
 701   case Type::FP128TyID:
 702   case Type::X86_FP80TyID:
 703     AlignType = FLOAT_ALIGN;
 704     break;
 705   case Type::X86_MMXTyID:
 706   case Type::VectorTyID:
 707     AlignType = VECTOR_ALIGN;
 708     break;
 709   default:
 710     llvm_unreachable("Bad type for getAlignment!!!");
 711   }
 712
 713   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 714                           abi_or_pref, Ty);
 715 }
 716
 717 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 718   return getAlignment(Ty, true);
 719 }
 720
 721 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 722 /// an integer type of the specified bitwidth.
 723 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 724   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 725 }
 726
 727 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 728   return getAlignment(Ty, false);
 729 }
 730
 731 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 732   unsigned Align = getPrefTypeAlignment(Ty);
 733   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 734   return Log2_32(Align);
 735 }
 736
 737 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 738                                        unsigned AddressSpace) const {
 739   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 740 }
 741
 742 Type *DataLayout::getIntPtrType(Type *Ty) const {
 743   assert(Ty->isPtrOrPtrVectorTy() &&
 744          "Expected a pointer or pointer vector type.");
 745   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 746   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 747   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 748     return VectorType::get(IntTy, VecTy->getNumElements());
 749   return IntTy;
 750 }
 751
 752 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 753   for (unsigned LegalIntWidth : LegalIntWidths)
 754     if (Width <= LegalIntWidth)
 755       return Type::getIntNTy(C, LegalIntWidth);
 756   return nullptr;
 757 }
 758
 759 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 760   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 761   return Max != LegalIntWidths.end() ? *Max : 0;
 762 }
 763
 764 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 765                                       ArrayRef<Value *> Indices) const {
 766   Type *Ty = ptrTy;
 767   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 768   uint64_t Result = 0;
 769
 770   generic_gep_type_iterator<Value* const*>
 771     TI = gep_type_begin(ptrTy, Indices);
 772   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 773        ++CurIDX, ++TI) {
 774     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 775       assert(Indices[CurIDX]->getType() ==
 776              Type::getInt32Ty(ptrTy->getContext()) &&
 777              "Illegal struct idx");
 778       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 779
 780       // Get structure layout information...
 781       const StructLayout *Layout = getStructLayout(STy);
 782
 783       // Add in the offset, as calculated by the structure layout info...
 784       Result += Layout->getElementOffset(FieldNo);
 785
 786       // Update Ty to refer to current element
 787       Ty = STy->getElementType(FieldNo);
 788     } else {
 789       // Update Ty to refer to current element
 790       Ty = cast<SequentialType>(Ty)->getElementType();
 791
 792       // Get the array index and the size of each array element.
 793       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 794         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 795     }
 796   }
 797
 798   return Result;
 799 }
 800
 801 /// getPreferredAlignment - Return the preferred alignment of the specified
 802 /// global.  This includes an explicitly requested alignment (if the global
 803 /// has one).
 804 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 805   Type *ElemType = GV->getType()->getElementType();
 806   unsigned Alignment = getPrefTypeAlignment(ElemType);
 807   unsigned GVAlignment = GV->getAlignment();
 808   if (GVAlignment >= Alignment) {
 809     Alignment = GVAlignment;
 810   } else if (GVAlignment != 0) {
 811     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 812   }
 813
 814   if (GV->hasInitializer() && GVAlignment == 0) {
 815     if (Alignment < 16) {
 816       // If the global is not external, see if it is large.  If so, give it a
 817       // larger alignment.
 818       if (getTypeSizeInBits(ElemType) > 128)
 819         Alignment = 16;    // 16-byte alignment.
 820     }
 821   }
 822   return Alignment;
 823 }
 824
 825 /// getPreferredAlignmentLog - Return the preferred alignment of the
 826 /// specified global, returned in log form.  This includes an explicitly
 827 /// requested alignment (if the global has one).
 828 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 829   return Log2_32(getPreferredAlignment(GV));
 830 }
 831
 832 DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
 833   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 834 }
 835
 836 DataLayoutPass::~DataLayoutPass() {}
 837
 838 bool DataLayoutPass::doInitialization(Module &M) {
 839   DL.init(&M);
 840   return false;
 841 }
 842
 843 bool DataLayoutPass::doFinalization(Module &M) {
 844   DL.reset("");
 845   return false;
 846 }