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/StringRef.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/GlobalVariable.h"
  27 #include "llvm/IR/Module.h"
  28 #include "llvm/IR/Type.h"
  29 #include "llvm/IR/Value.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include <algorithm>
  34 #include <cassert>
  35 #include <cstdint>
  36 #include <cstdlib>
  37 #include <tuple>
  38 #include <utility>
  39
  40 using namespace llvm;
  41
  42 //===----------------------------------------------------------------------===//
  43 // Support for StructLayout
  44 //===----------------------------------------------------------------------===//
  45
  46 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
  47   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
  48   StructAlignment = 0;
  49   StructSize = 0;
  50   IsPadded = false;
  51   NumElements = ST->getNumElements();
  52
  53   // Loop over each of the elements, placing them in memory.
  54   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  55     Type *Ty = ST->getElementType(i);
  56     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
  57
  58     // Add padding if necessary to align the data element properly.
  59     if ((StructSize & (TyAlign-1)) != 0) {
  60       IsPadded = true;
  61       StructSize = alignTo(StructSize, TyAlign);
  62     }
  63
  64     // Keep track of maximum alignment constraint.
  65     StructAlignment = std::max(TyAlign, StructAlignment);
  66
  67     MemberOffsets[i] = StructSize;
  68     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  69   }
  70
  71   // Empty structures have alignment of 1 byte.
  72   if (StructAlignment == 0) StructAlignment = 1;
  73
  74   // Add padding to the end of the struct so that it could be put in an array
  75   // and all array elements would be aligned correctly.
  76   if ((StructSize & (StructAlignment-1)) != 0) {
  77     IsPadded = true;
  78     StructSize = alignTo(StructSize, StructAlignment);
  79   }
  80 }
  81
  82 /// getElementContainingOffset - Given a valid offset into the structure,
  83 /// return the structure index that contains it.
  84 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  85   const uint64_t *SI =
  86     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  87   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  88   --SI;
  89   assert(*SI <= Offset && "upper_bound didn't work");
  90   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  91          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  92          "Upper bound didn't work!");
  93
  94   // Multiple fields can have the same offset if any of them are zero sized.
  95   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  96   // at the i32 element, because it is the last element at that offset.  This is
  97   // the right one to return, because anything after it will have a higher
  98   // offset, implying that this element is non-empty.
  99   return SI-&MemberOffsets[0];
 100 }
 101
 102 //===----------------------------------------------------------------------===//
 103 // LayoutAlignElem, LayoutAlign support
 104 //===----------------------------------------------------------------------===//
 105
 106 LayoutAlignElem
 107 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
 108                      unsigned pref_align, uint32_t bit_width) {
 109   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 110   LayoutAlignElem retval;
 111   retval.AlignType = align_type;
 112   retval.ABIAlign = abi_align;
 113   retval.PrefAlign = pref_align;
 114   retval.TypeBitWidth = bit_width;
 115   return retval;
 116 }
 117
 118 bool
 119 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 120   return (AlignType == rhs.AlignType
 121           && ABIAlign == rhs.ABIAlign
 122           && PrefAlign == rhs.PrefAlign
 123           && TypeBitWidth == rhs.TypeBitWidth);
 124 }
 125
 126 //===----------------------------------------------------------------------===//
 127 // PointerAlignElem, PointerAlign support
 128 //===----------------------------------------------------------------------===//
 129
 130 PointerAlignElem
 131 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
 132                       unsigned PrefAlign, uint32_t TypeByteWidth) {
 133   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 134   PointerAlignElem retval;
 135   retval.AddressSpace = AddressSpace;
 136   retval.ABIAlign = ABIAlign;
 137   retval.PrefAlign = PrefAlign;
 138   retval.TypeByteWidth = TypeByteWidth;
 139   return retval;
 140 }
 141
 142 bool
 143 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
 144   return (ABIAlign == rhs.ABIAlign
 145           && AddressSpace == rhs.AddressSpace
 146           && PrefAlign == rhs.PrefAlign
 147           && TypeByteWidth == rhs.TypeByteWidth);
 148 }
 149
 150 //===----------------------------------------------------------------------===//
 151 //                       DataLayout Class Implementation
 152 //===----------------------------------------------------------------------===//
 153
 154 const char *DataLayout::getManglingComponent(const Triple &T) {
 155   if (T.isOSBinFormatMachO())
 156     return "-m:o";
 157   if (T.isOSWindows() && T.isOSBinFormatCOFF())
 158     return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
 159   return "-m:e";
 160 }
 161
 162 static const LayoutAlignElem DefaultAlignments[] = {
 163   { INTEGER_ALIGN, 1, 1, 1 },    // i1
 164   { INTEGER_ALIGN, 8, 1, 1 },    // i8
 165   { INTEGER_ALIGN, 16, 2, 2 },   // i16
 166   { INTEGER_ALIGN, 32, 4, 4 },   // i32
 167   { INTEGER_ALIGN, 64, 4, 8 },   // i64
 168   { FLOAT_ALIGN, 16, 2, 2 },     // half
 169   { FLOAT_ALIGN, 32, 4, 4 },     // float
 170   { FLOAT_ALIGN, 64, 8, 8 },     // double
 171   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
 172   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
 173   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
 174   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
 175 };
 176
 177 void DataLayout::reset(StringRef Desc) {
 178   clear();
 179
 180   LayoutMap = nullptr;
 181   BigEndian = false;
 182   AllocaAddrSpace = 0;
 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: llvm_unreachable("Unexpected specifier!");
 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       while (true) {
 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 'A': { // Default stack/alloca address space.
 362       AllocaAddrSpace = getInt(Tok);
 363       if (!isUInt<24>(AllocaAddrSpace))
 364         report_fatal_error("Invalid address space, must be a 24bit integer");
 365       break;
 366     }
 367     case 'm':
 368       if (!Tok.empty())
 369         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
 370       if (Rest.empty())
 371         report_fatal_error("Expected mangling specifier in datalayout string");
 372       if (Rest.size() > 1)
 373         report_fatal_error("Unknown mangling specifier in datalayout string");
 374       switch(Rest[0]) {
 375       default:
 376         report_fatal_error("Unknown mangling in datalayout string");
 377       case 'e':
 378         ManglingMode = MM_ELF;
 379         break;
 380       case 'o':
 381         ManglingMode = MM_MachO;
 382         break;
 383       case 'm':
 384         ManglingMode = MM_Mips;
 385         break;
 386       case 'w':
 387         ManglingMode = MM_WinCOFF;
 388         break;
 389       case 'x':
 390         ManglingMode = MM_WinCOFFX86;
 391         break;
 392       }
 393       break;
 394     default:
 395       report_fatal_error("Unknown specifier in datalayout string");
 396       break;
 397     }
 398   }
 399 }
 400
 401 DataLayout::DataLayout(const Module *M) {
 402   init(M);
 403 }
 404
 405 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 406
 407 bool DataLayout::operator==(const DataLayout &Other) const {
 408   bool Ret = BigEndian == Other.BigEndian &&
 409              AllocaAddrSpace == Other.AllocaAddrSpace &&
 410              StackNaturalAlign == Other.StackNaturalAlign &&
 411              ManglingMode == Other.ManglingMode &&
 412              LegalIntWidths == Other.LegalIntWidths &&
 413              Alignments == Other.Alignments && Pointers == Other.Pointers;
 414   // Note: getStringRepresentation() might differs, it is not canonicalized
 415   return Ret;
 416 }
 417
 418 DataLayout::AlignmentsTy::iterator
 419 DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType,
 420                                     uint32_t BitWidth) {
 421   auto Pair = std::make_pair((unsigned)AlignType, BitWidth);
 422   return std::lower_bound(Alignments.begin(), Alignments.end(), Pair,
 423                           [](const LayoutAlignElem &LHS,
 424                              const std::pair<unsigned, uint32_t> &RHS) {
 425                             return std::tie(LHS.AlignType, LHS.TypeBitWidth) <
 426                                    std::tie(RHS.first, RHS.second);
 427                           });
 428 }
 429
 430 void
 431 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 432                          unsigned pref_align, uint32_t bit_width) {
 433   if (!isUInt<24>(bit_width))
 434     report_fatal_error("Invalid bit width, must be a 24bit integer");
 435   if (!isUInt<16>(abi_align))
 436     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
 437   if (!isUInt<16>(pref_align))
 438     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
 439   if (abi_align != 0 && !isPowerOf2_64(abi_align))
 440     report_fatal_error("Invalid ABI alignment, must be a power of 2");
 441   if (pref_align != 0 && !isPowerOf2_64(pref_align))
 442     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 443
 444   if (pref_align < abi_align)
 445     report_fatal_error(
 446         "Preferred alignment cannot be less than the ABI alignment");
 447
 448   AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width);
 449   if (I != Alignments.end() &&
 450       I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) {
 451     // Update the abi, preferred alignments.
 452     I->ABIAlign = abi_align;
 453     I->PrefAlign = pref_align;
 454   } else {
 455     // Insert before I to keep the vector sorted.
 456     Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
 457                                               pref_align, bit_width));
 458   }
 459 }
 460
 461 DataLayout::PointersTy::iterator
 462 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
 463   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 464                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
 465     return A.AddressSpace < AddressSpace;
 466   });
 467 }
 468
 469 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 470                                      unsigned PrefAlign,
 471                                      uint32_t TypeByteWidth) {
 472   if (PrefAlign < ABIAlign)
 473     report_fatal_error(
 474         "Preferred alignment cannot be less than the ABI alignment");
 475
 476   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 477   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 478     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 479                                              TypeByteWidth));
 480   } else {
 481     I->ABIAlign = ABIAlign;
 482     I->PrefAlign = PrefAlign;
 483     I->TypeByteWidth = TypeByteWidth;
 484   }
 485 }
 486
 487 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 488 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 489 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 490                                       uint32_t BitWidth, bool ABIInfo,
 491                                       Type *Ty) const {
 492   AlignmentsTy::const_iterator I = findAlignmentLowerBound(AlignType, BitWidth);
 493   // See if we found an exact match. Of if we are looking for an integer type,
 494   // but don't have an exact match take the next largest integer. This is where
 495   // the lower_bound will point to when it fails an exact match.
 496   if (I != Alignments.end() && I->AlignType == (unsigned)AlignType &&
 497       (I->TypeBitWidth == BitWidth || AlignType == INTEGER_ALIGN))
 498     return ABIInfo ? I->ABIAlign : I->PrefAlign;
 499
 500   if (AlignType == INTEGER_ALIGN) {
 501     // If we didn't have a larger value try the largest value we have.
 502     if (I != Alignments.begin()) {
 503       --I; // Go to the previous entry and see if its an integer.
 504       if (I->AlignType == INTEGER_ALIGN)
 505         return ABIInfo ? I->ABIAlign : I->PrefAlign;
 506     }
 507   } else if (AlignType == VECTOR_ALIGN) {
 508     // By default, use natural alignment for vector types. This is consistent
 509     // with what clang and llvm-gcc do.
 510     unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 511     Align *= cast<VectorType>(Ty)->getNumElements();
 512     Align = PowerOf2Ceil(Align);
 513     return Align;
 514    }
 515
 516   // If we still couldn't find a reasonable default alignment, fall back
 517   // to a simple heuristic that the alignment is the first power of two
 518   // greater-or-equal to the store size of the type.  This is a reasonable
 519   // approximation of reality, and if the user wanted something less
 520   // less conservative, they should have specified it explicitly in the data
 521   // layout.
 522   unsigned Align = getTypeStoreSize(Ty);
 523   Align = PowerOf2Ceil(Align);
 524   return Align;
 525 }
 526
 527 namespace {
 528
 529 class StructLayoutMap {
 530   using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
 531   LayoutInfoTy LayoutInfo;
 532
 533 public:
 534   ~StructLayoutMap() {
 535     // Remove any layouts.
 536     for (const auto &I : LayoutInfo) {
 537       StructLayout *Value = I.second;
 538       Value->~StructLayout();
 539       free(Value);
 540     }
 541   }
 542
 543   StructLayout *&operator[](StructType *STy) {
 544     return LayoutInfo[STy];
 545   }
 546 };
 547
 548 } // end anonymous namespace
 549
 550 void DataLayout::clear() {
 551   LegalIntWidths.clear();
 552   Alignments.clear();
 553   Pointers.clear();
 554   delete static_cast<StructLayoutMap *>(LayoutMap);
 555   LayoutMap = nullptr;
 556 }
 557
 558 DataLayout::~DataLayout() {
 559   clear();
 560 }
 561
 562 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 563   if (!LayoutMap)
 564     LayoutMap = new StructLayoutMap();
 565
 566   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 567   StructLayout *&SL = (*STM)[Ty];
 568   if (SL) return SL;
 569
 570   // Otherwise, create the struct layout.  Because it is variable length, we
 571   // malloc it, then use placement new.
 572   int NumElts = Ty->getNumElements();
 573   StructLayout *L =
 574     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 575
 576   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 577   // entries to be added to TheMap, invalidating our reference.
 578   SL = L;
 579
 580   new (L) StructLayout(Ty, *this);
 581
 582   return L;
 583 }
 584
 585 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 586   PointersTy::const_iterator I = findPointerLowerBound(AS);
 587   if (I == Pointers.end() || I->AddressSpace != AS) {
 588     I = findPointerLowerBound(0);
 589     assert(I->AddressSpace == 0);
 590   }
 591   return I->ABIAlign;
 592 }
 593
 594 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 595   PointersTy::const_iterator I = findPointerLowerBound(AS);
 596   if (I == Pointers.end() || I->AddressSpace != AS) {
 597     I = findPointerLowerBound(0);
 598     assert(I->AddressSpace == 0);
 599   }
 600   return I->PrefAlign;
 601 }
 602
 603 unsigned DataLayout::getPointerSize(unsigned AS) const {
 604   PointersTy::const_iterator I = findPointerLowerBound(AS);
 605   if (I == Pointers.end() || I->AddressSpace != AS) {
 606     I = findPointerLowerBound(0);
 607     assert(I->AddressSpace == 0);
 608   }
 609   return I->TypeByteWidth;
 610 }
 611
 612 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 613   assert(Ty->isPtrOrPtrVectorTy() &&
 614          "This should only be called with a pointer or pointer vector type");
 615   Ty = Ty->getScalarType();
 616   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 617 }
 618
 619 /*!
 620   \param abi_or_pref Flag that determines which alignment is returned. true
 621   returns the ABI alignment, false returns the preferred alignment.
 622   \param Ty The underlying type for which alignment is determined.
 623
 624   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 625   == false) for the requested type \a Ty.
 626  */
 627 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 628   AlignTypeEnum AlignType;
 629
 630   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 631   switch (Ty->getTypeID()) {
 632   // Early escape for the non-numeric types.
 633   case Type::LabelTyID:
 634     return (abi_or_pref
 635             ? getPointerABIAlignment(0)
 636             : getPointerPrefAlignment(0));
 637   case Type::PointerTyID: {
 638     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 639     return (abi_or_pref
 640             ? getPointerABIAlignment(AS)
 641             : getPointerPrefAlignment(AS));
 642     }
 643   case Type::ArrayTyID:
 644     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 645
 646   case Type::StructTyID: {
 647     // Packed structure types always have an ABI alignment of one.
 648     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 649       return 1;
 650
 651     // Get the layout annotation... which is lazily created on demand.
 652     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 653     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 654     return std::max(Align, Layout->getAlignment());
 655   }
 656   case Type::IntegerTyID:
 657     AlignType = INTEGER_ALIGN;
 658     break;
 659   case Type::HalfTyID:
 660   case Type::FloatTyID:
 661   case Type::DoubleTyID:
 662   // PPC_FP128TyID and FP128TyID have different data contents, but the
 663   // same size and alignment, so they look the same here.
 664   case Type::PPC_FP128TyID:
 665   case Type::FP128TyID:
 666   case Type::X86_FP80TyID:
 667     AlignType = FLOAT_ALIGN;
 668     break;
 669   case Type::X86_MMXTyID:
 670   case Type::VectorTyID:
 671     AlignType = VECTOR_ALIGN;
 672     break;
 673   default:
 674     llvm_unreachable("Bad type for getAlignment!!!");
 675   }
 676
 677   return getAlignmentInfo(AlignType, getTypeSizeInBits(Ty), abi_or_pref, Ty);
 678 }
 679
 680 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 681   return getAlignment(Ty, true);
 682 }
 683
 684 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 685 /// an integer type of the specified bitwidth.
 686 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 687   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 688 }
 689
 690 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 691   return getAlignment(Ty, false);
 692 }
 693
 694 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 695   unsigned Align = getPrefTypeAlignment(Ty);
 696   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 697   return Log2_32(Align);
 698 }
 699
 700 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 701                                        unsigned AddressSpace) const {
 702   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 703 }
 704
 705 Type *DataLayout::getIntPtrType(Type *Ty) const {
 706   assert(Ty->isPtrOrPtrVectorTy() &&
 707          "Expected a pointer or pointer vector type.");
 708   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 709   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 710   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 711     return VectorType::get(IntTy, VecTy->getNumElements());
 712   return IntTy;
 713 }
 714
 715 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 716   for (unsigned LegalIntWidth : LegalIntWidths)
 717     if (Width <= LegalIntWidth)
 718       return Type::getIntNTy(C, LegalIntWidth);
 719   return nullptr;
 720 }
 721
 722 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
 723   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 724   return Max != LegalIntWidths.end() ? *Max : 0;
 725 }
 726
 727 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
 728                                            ArrayRef<Value *> Indices) const {
 729   int64_t Result = 0;
 730
 731   generic_gep_type_iterator<Value* const*>
 732     GTI = gep_type_begin(ElemTy, Indices),
 733     GTE = gep_type_end(ElemTy, Indices);
 734   for (; GTI != GTE; ++GTI) {
 735     Value *Idx = GTI.getOperand();
 736     if (StructType *STy = GTI.getStructTypeOrNull()) {
 737       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
 738       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
 739
 740       // Get structure layout information...
 741       const StructLayout *Layout = getStructLayout(STy);
 742
 743       // Add in the offset, as calculated by the structure layout info...
 744       Result += Layout->getElementOffset(FieldNo);
 745     } else {
 746       // Get the array index and the size of each array element.
 747       if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
 748         Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
 749     }
 750   }
 751
 752   return Result;
 753 }
 754
 755 /// getPreferredAlignment - Return the preferred alignment of the specified
 756 /// global.  This includes an explicitly requested alignment (if the global
 757 /// has one).
 758 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 759   Type *ElemType = GV->getValueType();
 760   unsigned Alignment = getPrefTypeAlignment(ElemType);
 761   unsigned GVAlignment = GV->getAlignment();
 762   if (GVAlignment >= Alignment) {
 763     Alignment = GVAlignment;
 764   } else if (GVAlignment != 0) {
 765     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 766   }
 767
 768   if (GV->hasInitializer() && GVAlignment == 0) {
 769     if (Alignment < 16) {
 770       // If the global is not external, see if it is large.  If so, give it a
 771       // larger alignment.
 772       if (getTypeSizeInBits(ElemType) > 128)
 773         Alignment = 16;    // 16-byte alignment.
 774     }
 775   }
 776   return Alignment;
 777 }
 778
 779 /// getPreferredAlignmentLog - Return the preferred alignment of the
 780 /// specified global, returned in log form.  This includes an explicitly
 781 /// requested alignment (if the global has one).
 782 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 783   return Log2_32(getPreferredAlignment(GV));
 784 }