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