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