contrib/llvm/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 //===----------------------------------------------------------------------===//
  37 // Support for StructLayout
  38 //===----------------------------------------------------------------------===//
  39
  40 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
  41   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
  42   StructAlignment = 0;
  43   StructSize = 0;
  44   IsPadded = false;
  45   NumElements = ST->getNumElements();
  46
  47   // Loop over each of the elements, placing them in memory.
  48   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  49     Type *Ty = ST->getElementType(i);
  50     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
  51
  52     // Add padding if necessary to align the data element properly.
  53     if ((StructSize & (TyAlign-1)) != 0) {
  54       IsPadded = true;
  55       StructSize = alignTo(StructSize, TyAlign);
  56     }
  57
  58     // Keep track of maximum alignment constraint.
  59     StructAlignment = std::max(TyAlign, StructAlignment);
  60
  61     MemberOffsets[i] = StructSize;
  62     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  63   }
  64
  65   // Empty structures have alignment of 1 byte.
  66   if (StructAlignment == 0) StructAlignment = 1;
  67
  68   // Add padding to the end of the struct so that it could be put in an array
  69   // and all array elements would be aligned correctly.
  70   if ((StructSize & (StructAlignment-1)) != 0) {
  71     IsPadded = true;
  72     StructSize = alignTo(StructSize, StructAlignment);
  73   }
  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.isOSBinFormatCOFF())
 159     return T.getArch() == Triple::x86 ? "-m:x" : "-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   NonIntegralAddressSpaces.clear();
 186
 187   // Default alignments
 188   for (const LayoutAlignElem &E : DefaultAlignments) {
 189     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
 190                  E.TypeBitWidth);
 191   }
 192   setPointerAlignment(0, 8, 8, 8);
 193
 194   parseSpecifier(Desc);
 195 }
 196
 197 /// Checked version of split, to ensure mandatory subparts.
 198 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
 199   assert(!Str.empty() && "parse error, string can't be empty here");
 200   std::pair<StringRef, StringRef> Split = Str.split(Separator);
 201   if (Split.second.empty() && Split.first != Str)
 202     report_fatal_error("Trailing separator in datalayout string");
 203   if (!Split.second.empty() && Split.first.empty())
 204     report_fatal_error("Expected token before separator in datalayout string");
 205   return Split;
 206 }
 207
 208 /// Get an unsigned integer, including error checks.
 209 static unsigned getInt(StringRef R) {
 210   unsigned Result;
 211   bool error = R.getAsInteger(10, Result); (void)error;
 212   if (error)
 213     report_fatal_error("not a number, or does not fit in an unsigned int");
 214   return Result;
 215 }
 216
 217 /// Convert bits into bytes. Assert if not a byte width multiple.
 218 static unsigned inBytes(unsigned Bits) {
 219   if (Bits % 8)
 220     report_fatal_error("number of bits must be a byte width multiple");
 221   return Bits / 8;
 222 }
 223
 224 void DataLayout::parseSpecifier(StringRef Desc) {
 225   StringRepresentation = Desc;
 226   while (!Desc.empty()) {
 227     // Split at '-'.
 228     std::pair<StringRef, StringRef> Split = split(Desc, '-');
 229     Desc = Split.second;
 230
 231     // Split at ':'.
 232     Split = split(Split.first, ':');
 233
 234     // Aliases used below.
 235     StringRef &Tok  = Split.first;  // Current token.
 236     StringRef &Rest = Split.second; // The rest of the string.
 237
 238     if (Tok == "ni") {
 239       do {
 240         Split = split(Rest, ':');
 241         Rest = Split.second;
 242         unsigned AS = getInt(Split.first);
 243         if (AS == 0)
 244           report_fatal_error("Address space 0 can never be non-integral");
 245         NonIntegralAddressSpaces.push_back(AS);
 246       } while (!Rest.empty());
 247
 248       continue;
 249     }
 250
 251     char Specifier = Tok.front();
 252     Tok = Tok.substr(1);
 253
 254     switch (Specifier) {
 255     case 's':
 256       // Ignored for backward compatibility.
 257       // FIXME: remove this on LLVM 4.0.
 258       break;
 259     case 'E':
 260       BigEndian = true;
 261       break;
 262     case 'e':
 263       BigEndian = false;
 264       break;
 265     case 'p': {
 266       // Address space.
 267       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
 268       if (!isUInt<24>(AddrSpace))
 269         report_fatal_error("Invalid address space, must be a 24bit integer");
 270
 271       // Size.
 272       if (Rest.empty())
 273         report_fatal_error(
 274             "Missing size specification for pointer in datalayout string");
 275       Split = split(Rest, ':');
 276       unsigned PointerMemSize = inBytes(getInt(Tok));
 277       if (!PointerMemSize)
 278         report_fatal_error("Invalid pointer size of 0 bytes");
 279
 280       // ABI alignment.
 281       if (Rest.empty())
 282         report_fatal_error(
 283             "Missing alignment specification for pointer in datalayout string");
 284       Split = split(Rest, ':');
 285       unsigned PointerABIAlign = inBytes(getInt(Tok));
 286       if (!isPowerOf2_64(PointerABIAlign))
 287         report_fatal_error(
 288             "Pointer ABI alignment must be a power of 2");
 289
 290       // Preferred alignment.
 291       unsigned PointerPrefAlign = PointerABIAlign;
 292       if (!Rest.empty()) {
 293         Split = split(Rest, ':');
 294         PointerPrefAlign = inBytes(getInt(Tok));
 295         if (!isPowerOf2_64(PointerPrefAlign))
 296           report_fatal_error(
 297             "Pointer preferred alignment must be a power of 2");
 298       }
 299
 300       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
 301                           PointerMemSize);
 302       break;
 303     }
 304     case 'i':
 305     case 'v':
 306     case 'f':
 307     case 'a': {
 308       AlignTypeEnum AlignType;
 309       switch (Specifier) {
 310       default:
 311       case 'i': AlignType = INTEGER_ALIGN; break;
 312       case 'v': AlignType = VECTOR_ALIGN; break;
 313       case 'f': AlignType = FLOAT_ALIGN; break;
 314       case 'a': AlignType = AGGREGATE_ALIGN; break;
 315       }
 316
 317       // Bit size.
 318       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
 319
 320       if (AlignType == AGGREGATE_ALIGN && Size != 0)
 321         report_fatal_error(
 322             "Sized aggregate specification in datalayout string");
 323
 324       // ABI alignment.
 325       if (Rest.empty())
 326         report_fatal_error(
 327             "Missing alignment specification in datalayout string");
 328       Split = split(Rest, ':');
 329       unsigned ABIAlign = inBytes(getInt(Tok));
 330       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
 331         report_fatal_error(
 332             "ABI alignment specification must be >0 for non-aggregate types");
 333
 334       // Preferred alignment.
 335       unsigned PrefAlign = ABIAlign;
 336       if (!Rest.empty()) {
 337         Split = split(Rest, ':');
 338         PrefAlign = inBytes(getInt(Tok));
 339       }
 340
 341       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 342
 343       break;
 344     }
 345     case 'n':  // Native integer types.
 346       for (;;) {
 347         unsigned Width = getInt(Tok);
 348         if (Width == 0)
 349           report_fatal_error(
 350               "Zero width native integer type in datalayout string");
 351         LegalIntWidths.push_back(Width);
 352         if (Rest.empty())
 353           break;
 354         Split = split(Rest, ':');
 355       }
 356       break;
 357     case 'S': { // Stack natural alignment.
 358       StackNaturalAlign = inBytes(getInt(Tok));
 359       break;
 360     }
 361     case 'm':
 362       if (!Tok.empty())
 363         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
 364       if (Rest.empty())
 365         report_fatal_error("Expected mangling specifier in datalayout string");
 366       if (Rest.size() > 1)
 367         report_fatal_error("Unknown mangling specifier in datalayout string");
 368       switch(Rest[0]) {
 369       default:
 370         report_fatal_error("Unknown mangling in datalayout string");
 371       case 'e':
 372         ManglingMode = MM_ELF;
 373         break;
 374       case 'o':
 375         ManglingMode = MM_MachO;
 376         break;
 377       case 'm':
 378         ManglingMode = MM_Mips;
 379         break;
 380       case 'w':
 381         ManglingMode = MM_WinCOFF;
 382         break;
 383       case 'x':
 384         ManglingMode = MM_WinCOFFX86;
 385         break;
 386       }
 387       break;
 388     default:
 389       report_fatal_error("Unknown specifier in datalayout string");
 390       break;
 391     }
 392   }
 393 }
 394
 395 DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
 396   init(M);
 397 }
 398
 399 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 400
 401 bool DataLayout::operator==(const DataLayout &Other) const {
 402   bool Ret = BigEndian == Other.BigEndian &&
 403              StackNaturalAlign == Other.StackNaturalAlign &&
 404              ManglingMode == Other.ManglingMode &&
 405              LegalIntWidths == Other.LegalIntWidths &&
 406              Alignments == Other.Alignments && Pointers == Other.Pointers;
 407   // Note: getStringRepresentation() might differs, it is not canonicalized
 408   return Ret;
 409 }
 410
 411 void
 412 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 413                          unsigned pref_align, uint32_t bit_width) {
 414   if (!isUInt<24>(bit_width))
 415     report_fatal_error("Invalid bit width, must be a 24bit integer");
 416   if (!isUInt<16>(abi_align))
 417     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
 418   if (!isUInt<16>(pref_align))
 419     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
 420   if (abi_align != 0 && !isPowerOf2_64(abi_align))
 421     report_fatal_error("Invalid ABI alignment, must be a power of 2");
 422   if (pref_align != 0 && !isPowerOf2_64(pref_align))
 423     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 424
 425   if (pref_align < abi_align)
 426     report_fatal_error(
 427         "Preferred alignment cannot be less than the ABI alignment");
 428
 429   for (LayoutAlignElem &Elem : Alignments) {
 430     if (Elem.AlignType == (unsigned)align_type &&
 431         Elem.TypeBitWidth == bit_width) {
 432       // Update the abi, preferred alignments.
 433       Elem.ABIAlign = abi_align;
 434       Elem.PrefAlign = pref_align;
 435       return;
 436     }
 437   }
 438
 439   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 440                                             pref_align, bit_width));
 441 }
 442
 443 DataLayout::PointersTy::iterator
 444 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
 445   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 446                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
 447     return A.AddressSpace < AddressSpace;
 448   });
 449 }
 450
 451 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 452                                      unsigned PrefAlign,
 453                                      uint32_t TypeByteWidth) {
 454   if (PrefAlign < ABIAlign)
 455     report_fatal_error(
 456         "Preferred alignment cannot be less than the ABI alignment");
 457
 458   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 459   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 460     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 461                                              TypeByteWidth));
 462   } else {
 463     I->ABIAlign = ABIAlign;
 464     I->PrefAlign = PrefAlign;
 465     I->TypeByteWidth = TypeByteWidth;
 466   }
 467 }
 468
 469 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 470 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 471 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 472                                       uint32_t BitWidth, bool ABIInfo,
 473                                       Type *Ty) const {
 474   // Check to see if we have an exact match and remember the best match we see.
 475   int BestMatchIdx = -1;
 476   int LargestInt = -1;
 477   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 478     if (Alignments[i].AlignType == (unsigned)AlignType &&
 479         Alignments[i].TypeBitWidth == BitWidth)
 480       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 481
 482     // The best match so far depends on what we're looking for.
 483     if (AlignType == INTEGER_ALIGN &&
 484         Alignments[i].AlignType == INTEGER_ALIGN) {
 485       // The "best match" for integers is the smallest size that is larger than
 486       // the BitWidth requested.
 487       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 488           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 489         BestMatchIdx = i;
 490       // However, if there isn't one that's larger, then we must use the
 491       // largest one we have (see below)
 492       if (LargestInt == -1 ||
 493           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 494         LargestInt = i;
 495     }
 496   }
 497
 498   // Okay, we didn't find an exact solution.  Fall back here depending on what
 499   // is being looked for.
 500   if (BestMatchIdx == -1) {
 501     // If we didn't find an integer alignment, fall back on most conservative.
 502     if (AlignType == INTEGER_ALIGN) {
 503       BestMatchIdx = LargestInt;
 504     } else if (AlignType == VECTOR_ALIGN) {
 505       // By default, use natural alignment for vector types. This is consistent
 506       // with what clang and llvm-gcc do.
 507       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 508       Align *= cast<VectorType>(Ty)->getNumElements();
 509       Align = PowerOf2Ceil(Align);
 510       return Align;
 511     }
 512   }
 513
 514   // If we still couldn't find a reasonable default alignment, fall back
 515   // to a simple heuristic that the alignment is the first power of two
 516   // greater-or-equal to the store size of the type.  This is a reasonable
 517   // approximation of reality, and if the user wanted something less
 518   // less conservative, they should have specified it explicitly in the data
 519   // layout.
 520   if (BestMatchIdx == -1) {
 521     unsigned Align = getTypeStoreSize(Ty);
 522     Align = PowerOf2Ceil(Align);
 523     return Align;
 524   }
 525
 526   // Since we got a "best match" index, just return it.
 527   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 528                  : Alignments[BestMatchIdx].PrefAlign;
 529 }
 530
 531 namespace {
 532
 533 class StructLayoutMap {
 534   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 535   LayoutInfoTy LayoutInfo;
 536
 537 public:
 538   ~StructLayoutMap() {
 539     // Remove any layouts.
 540     for (const auto &I : LayoutInfo) {
 541       StructLayout *Value = I.second;
 542       Value->~StructLayout();
 543       free(Value);
 544     }
 545   }
 546
 547   StructLayout *&operator[](StructType *STy) {
 548     return LayoutInfo[STy];
 549   }
 550 };
 551
 552 } // end anonymous namespace
 553
 554 void DataLayout::clear() {
 555   LegalIntWidths.clear();
 556   Alignments.clear();
 557   Pointers.clear();
 558   delete static_cast<StructLayoutMap *>(LayoutMap);
 559   LayoutMap = nullptr;
 560 }
 561
 562 DataLayout::~DataLayout() {
 563   clear();
 564 }
 565
 566 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 567   if (!LayoutMap)
 568     LayoutMap = new StructLayoutMap();
 569
 570   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 571   StructLayout *&SL = (*STM)[Ty];
 572   if (SL) return SL;
 573
 574   // Otherwise, create the struct layout.  Because it is variable length, we
 575   // malloc it, then use placement new.
 576   int NumElts = Ty->getNumElements();
 577   StructLayout *L =
 578     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 579
 580   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 581   // entries to be added to TheMap, invalidating our reference.
 582   SL = L;
 583
 584   new (L) StructLayout(Ty, *this);
 585
 586   return L;
 587 }
 588
 589
 590 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 591   PointersTy::const_iterator I = findPointerLowerBound(AS);
 592   if (I == Pointers.end() || I->AddressSpace != AS) {
 593     I = findPointerLowerBound(0);
 594     assert(I->AddressSpace == 0);
 595   }
 596   return I->ABIAlign;
 597 }
 598
 599 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 600   PointersTy::const_iterator I = findPointerLowerBound(AS);
 601   if (I == Pointers.end() || I->AddressSpace != AS) {
 602     I = findPointerLowerBound(0);
 603     assert(I->AddressSpace == 0);
 604   }
 605   return I->PrefAlign;
 606 }
 607
 608 unsigned DataLayout::getPointerSize(unsigned AS) const {
 609   PointersTy::const_iterator I = findPointerLowerBound(AS);
 610   if (I == Pointers.end() || I->AddressSpace != AS) {
 611     I = findPointerLowerBound(0);
 612     assert(I->AddressSpace == 0);
 613   }
 614   return I->TypeByteWidth;
 615 }
 616
 617 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 618   assert(Ty->isPtrOrPtrVectorTy() &&
 619          "This should only be called with a pointer or pointer vector type");
 620
 621   if (Ty->isPointerTy())
 622     return getTypeSizeInBits(Ty);
 623
 624   return getTypeSizeInBits(Ty->getScalarType());
 625 }
 626
 627 /*!
 628   \param abi_or_pref Flag that determines which alignment is returned. true
 629   returns the ABI alignment, false returns the preferred alignment.
 630   \param Ty The underlying type for which alignment is determined.
 631
 632   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 633   == false) for the requested type \a Ty.
 634  */
 635 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 636   int AlignType = -1;
 637
 638   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 639   switch (Ty->getTypeID()) {
 640   // Early escape for the non-numeric types.
 641   case Type::LabelTyID:
 642     return (abi_or_pref
 643             ? getPointerABIAlignment(0)
 644             : getPointerPrefAlignment(0));
 645   case Type::PointerTyID: {
 646     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 647     return (abi_or_pref
 648             ? getPointerABIAlignment(AS)
 649             : getPointerPrefAlignment(AS));
 650     }
 651   case Type::ArrayTyID:
 652     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 653
 654   case Type::StructTyID: {
 655     // Packed structure types always have an ABI alignment of one.
 656     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 657       return 1;
 658
 659     // Get the layout annotation... which is lazily created on demand.
 660     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 661     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 662     return std::max(Align, Layout->getAlignment());
 663   }
 664   case Type::IntegerTyID:
 665     AlignType = INTEGER_ALIGN;
 666     break;
 667   case Type::HalfTyID:
 668   case Type::FloatTyID:
 669   case Type::DoubleTyID:
 670   // PPC_FP128TyID and FP128TyID have different data contents, but the
 671   // same size and alignment, so they look the same here.
 672   case Type::PPC_FP128TyID:
 673   case Type::FP128TyID:
 674   case Type::X86_FP80TyID:
 675     AlignType = FLOAT_ALIGN;
 676     break;
 677   case Type::X86_MMXTyID:
 678   case Type::VectorTyID:
 679     AlignType = VECTOR_ALIGN;
 680     break;
 681   default:
 682     llvm_unreachable("Bad type for getAlignment!!!");
 683   }
 684
 685   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 686                           abi_or_pref, Ty);
 687 }
 688
 689 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 690   return getAlignment(Ty, true);
 691 }
 692
 693 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 694 /// an integer type of the specified bitwidth.
 695 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 696   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 697 }
 698
 699 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 700   return getAlignment(Ty, false);
 701 }
 702
 703 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 704   unsigned Align = getPrefTypeAlignment(Ty);
 705   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 706   return Log2_32(Align);
 707 }
 708
 709 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 710                                        unsigned AddressSpace) const {
 711   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 712 }
 713
 714 Type *DataLayout::getIntPtrType(Type *Ty) const {
 715   assert(Ty->isPtrOrPtrVectorTy() &&
 716          "Expected a pointer or pointer vector type.");
 717   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 718   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 719   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 720     return VectorType::get(IntTy, VecTy->getNumElements());
 721   return IntTy;
 722 }
 723
 724 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 725   for (unsigned LegalIntWidth : LegalIntWidths)
 726     if (Width <= LegalIntWidth)
 727       return Type::getIntNTy(C, LegalIntWidth);
 728   return nullptr;
 729 }
 730
 731 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
 732   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 733   return Max != LegalIntWidths.end() ? *Max : 0;
 734 }
 735
 736 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
 737                                            ArrayRef<Value *> Indices) const {
 738   int64_t Result = 0;
 739
 740   generic_gep_type_iterator<Value* const*>
 741     GTI = gep_type_begin(ElemTy, Indices),
 742     GTE = gep_type_end(ElemTy, Indices);
 743   for (; GTI != GTE; ++GTI) {
 744     Value *Idx = GTI.getOperand();
 745     if (StructType *STy = GTI.getStructTypeOrNull()) {
 746       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
 747       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
 748
 749       // Get structure layout information...
 750       const StructLayout *Layout = getStructLayout(STy);
 751
 752       // Add in the offset, as calculated by the structure layout info...
 753       Result += Layout->getElementOffset(FieldNo);
 754     } else {
 755       // Get the array index and the size of each array element.
 756       if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
 757         Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
 758     }
 759   }
 760
 761   return Result;
 762 }
 763
 764 /// getPreferredAlignment - Return the preferred alignment of the specified
 765 /// global.  This includes an explicitly requested alignment (if the global
 766 /// has one).
 767 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 768   Type *ElemType = GV->getValueType();
 769   unsigned Alignment = getPrefTypeAlignment(ElemType);
 770   unsigned GVAlignment = GV->getAlignment();
 771   if (GVAlignment >= Alignment) {
 772     Alignment = GVAlignment;
 773   } else if (GVAlignment != 0) {
 774     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 775   }
 776
 777   if (GV->hasInitializer() && GVAlignment == 0) {
 778     if (Alignment < 16) {
 779       // If the global is not external, see if it is large.  If so, give it a
 780       // larger alignment.
 781       if (getTypeSizeInBits(ElemType) > 128)
 782         Alignment = 16;    // 16-byte alignment.
 783     }
 784   }
 785   return Alignment;
 786 }
 787
 788 /// getPreferredAlignmentLog - Return the preferred alignment of the
 789 /// specified global, returned in log form.  This includes an explicitly
 790 /// requested alignment (if the global has one).
 791 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 792   return Log2_32(getPreferredAlignment(GV));
 793 }
 794