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