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