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 // Handle the Pass registration stuff necessary to use DataLayout's.
     37 
     38 INITIALIZE_PASS(DataLayoutPass, "datalayout", "Data Layout", false, true)
     39 char DataLayoutPass::ID = 0;
     40 
     41 //===----------------------------------------------------------------------===//
     42 // Support for StructLayout
     43 //===----------------------------------------------------------------------===//
     44 
     45 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
     46   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
     47   StructAlignment = 0;
     48   StructSize = 0;
     49   NumElements = ST->getNumElements();
     50 
     51   // Loop over each of the elements, placing them in memory.
     52   for (unsigned i = 0, e = NumElements; i != e; ++i) {
     53     Type *Ty = ST->getElementType(i);
     54     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
     55 
     56     // Add padding if necessary to align the data element properly.
     57     if ((StructSize & (TyAlign-1)) != 0)
     58       StructSize = DataLayout::RoundUpAlignment(StructSize, TyAlign);
     59 
     60     // Keep track of maximum alignment constraint.
     61     StructAlignment = std::max(TyAlign, StructAlignment);
     62 
     63     MemberOffsets[i] = StructSize;
     64     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
     65   }
     66 
     67   // Empty structures have alignment of 1 byte.
     68   if (StructAlignment == 0) StructAlignment = 1;
     69 
     70   // Add padding to the end of the struct so that it could be put in an array
     71   // and all array elements would be aligned correctly.
     72   if ((StructSize & (StructAlignment-1)) != 0)
     73     StructSize = DataLayout::RoundUpAlignment(StructSize, StructAlignment);
     74 }
     75 
     76 
     77 /// getElementContainingOffset - Given a valid offset into the structure,
     78 /// return the structure index that contains it.
     79 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
     80   const uint64_t *SI =
     81     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
     82   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
     83   --SI;
     84   assert(*SI <= Offset && "upper_bound didn't work");
     85   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
     86          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
     87          "Upper bound didn't work!");
     88 
     89   // Multiple fields can have the same offset if any of them are zero sized.
     90   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
     91   // at the i32 element, because it is the last element at that offset.  This is
     92   // the right one to return, because anything after it will have a higher
     93   // offset, implying that this element is non-empty.
     94   return SI-&MemberOffsets[0];
     95 }
     96 
     97 //===----------------------------------------------------------------------===//
     98 // LayoutAlignElem, LayoutAlign support
     99 //===----------------------------------------------------------------------===//
    100 
    101 LayoutAlignElem
    102 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
    103                      unsigned pref_align, uint32_t bit_width) {
    104   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
    105   LayoutAlignElem retval;
    106   retval.AlignType = align_type;
    107   retval.ABIAlign = abi_align;
    108   retval.PrefAlign = pref_align;
    109   retval.TypeBitWidth = bit_width;
    110   return retval;
    111 }
    112 
    113 bool
    114 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
    115   return (AlignType == rhs.AlignType
    116           && ABIAlign == rhs.ABIAlign
    117           && PrefAlign == rhs.PrefAlign
    118           && TypeBitWidth == rhs.TypeBitWidth);
    119 }
    120 
    121 const LayoutAlignElem
    122 DataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 };
    123 
    124 //===----------------------------------------------------------------------===//
    125 // PointerAlignElem, PointerAlign support
    126 //===----------------------------------------------------------------------===//
    127 
    128 PointerAlignElem
    129 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
    130                       unsigned PrefAlign, uint32_t TypeByteWidth) {
    131   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
    132   PointerAlignElem retval;
    133   retval.AddressSpace = AddressSpace;
    134   retval.ABIAlign = ABIAlign;
    135   retval.PrefAlign = PrefAlign;
    136   retval.TypeByteWidth = TypeByteWidth;
    137   return retval;
    138 }
    139 
    140 bool
    141 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
    142   return (ABIAlign == rhs.ABIAlign
    143           && AddressSpace == rhs.AddressSpace
    144           && PrefAlign == rhs.PrefAlign
    145           && TypeByteWidth == rhs.TypeByteWidth);
    146 }
    147 
    148 const PointerAlignElem
    149 DataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U };
    150 
    151 //===----------------------------------------------------------------------===//
    152 //                       DataLayout Class Implementation
    153 //===----------------------------------------------------------------------===//
    154 
    155 const char *DataLayout::getManglingComponent(const Triple &T) {
    156   if (T.isOSBinFormatMachO())
    157     return "-m:o";
    158   if (T.isOSWindows() && T.getArch() == Triple::x86 && T.isOSBinFormatCOFF())
    159     return "-m:w";
    160   return "-m:e";
    161 }
    162 
    163 static const LayoutAlignElem DefaultAlignments[] = {
    164   { INTEGER_ALIGN, 1, 1, 1 },    // i1
    165   { INTEGER_ALIGN, 8, 1, 1 },    // i8
    166   { INTEGER_ALIGN, 16, 2, 2 },   // i16
    167   { INTEGER_ALIGN, 32, 4, 4 },   // i32
    168   { INTEGER_ALIGN, 64, 4, 8 },   // i64
    169   { FLOAT_ALIGN, 16, 2, 2 },     // half
    170   { FLOAT_ALIGN, 32, 4, 4 },     // float
    171   { FLOAT_ALIGN, 64, 8, 8 },     // double
    172   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
    173   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
    174   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
    175   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
    176 };
    177 
    178 void DataLayout::reset(StringRef Desc) {
    179   clear();
    180 
    181   LayoutMap = nullptr;
    182   LittleEndian = 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   assert((!Split.second.empty() || Split.first == Str) &&
    201          "a trailing separator is not allowed");
    202   return Split;
    203 }
    204 
    205 /// Get an unsigned integer, including error checks.
    206 static unsigned getInt(StringRef R) {
    207   unsigned Result;
    208   bool error = R.getAsInteger(10, Result); (void)error;
    209   if (error)
    210     report_fatal_error("not a number, or does not fit in an unsigned int");
    211   return Result;
    212 }
    213 
    214 /// Convert bits into bytes. Assert if not a byte width multiple.
    215 static unsigned inBytes(unsigned Bits) {
    216   assert(Bits % 8 == 0 && "number of bits must be a byte width multiple");
    217   return Bits / 8;
    218 }
    219 
    220 void DataLayout::parseSpecifier(StringRef Desc) {
    221   while (!Desc.empty()) {
    222     // Split at '-'.
    223     std::pair<StringRef, StringRef> Split = split(Desc, '-');
    224     Desc = Split.second;
    225 
    226     // Split at ':'.
    227     Split = split(Split.first, ':');
    228 
    229     // Aliases used below.
    230     StringRef &Tok  = Split.first;  // Current token.
    231     StringRef &Rest = Split.second; // The rest of the string.
    232 
    233     char Specifier = Tok.front();
    234     Tok = Tok.substr(1);
    235 
    236     switch (Specifier) {
    237     case 's':
    238       // Ignored for backward compatibility.
    239       // FIXME: remove this on LLVM 4.0.
    240       break;
    241     case 'E':
    242       LittleEndian = false;
    243       break;
    244     case 'e':
    245       LittleEndian = true;
    246       break;
    247     case 'p': {
    248       // Address space.
    249       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
    250       assert(AddrSpace < 1 << 24 &&
    251              "Invalid address space, must be a 24bit integer");
    252 
    253       // Size.
    254       Split = split(Rest, ':');
    255       unsigned PointerMemSize = inBytes(getInt(Tok));
    256 
    257       // ABI alignment.
    258       Split = split(Rest, ':');
    259       unsigned PointerABIAlign = inBytes(getInt(Tok));
    260 
    261       // Preferred alignment.
    262       unsigned PointerPrefAlign = PointerABIAlign;
    263       if (!Rest.empty()) {
    264         Split = split(Rest, ':');
    265         PointerPrefAlign = inBytes(getInt(Tok));
    266       }
    267 
    268       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
    269                           PointerMemSize);
    270       break;
    271     }
    272     case 'i':
    273     case 'v':
    274     case 'f':
    275     case 'a': {
    276       AlignTypeEnum AlignType;
    277       switch (Specifier) {
    278       default:
    279       case 'i': AlignType = INTEGER_ALIGN; break;
    280       case 'v': AlignType = VECTOR_ALIGN; break;
    281       case 'f': AlignType = FLOAT_ALIGN; break;
    282       case 'a': AlignType = AGGREGATE_ALIGN; break;
    283       }
    284 
    285       // Bit size.
    286       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
    287 
    288       assert((AlignType != AGGREGATE_ALIGN || Size == 0) &&
    289              "These specifications don't have a size");
    290 
    291       // ABI alignment.
    292       Split = split(Rest, ':');
    293       unsigned ABIAlign = inBytes(getInt(Tok));
    294 
    295       // Preferred alignment.
    296       unsigned PrefAlign = ABIAlign;
    297       if (!Rest.empty()) {
    298         Split = split(Rest, ':');
    299         PrefAlign = inBytes(getInt(Tok));
    300       }
    301 
    302       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
    303 
    304       break;
    305     }
    306     case 'n':  // Native integer types.
    307       for (;;) {
    308         unsigned Width = getInt(Tok);
    309         assert(Width != 0 && "width must be non-zero");
    310         LegalIntWidths.push_back(Width);
    311         if (Rest.empty())
    312           break;
    313         Split = split(Rest, ':');
    314       }
    315       break;
    316     case 'S': { // Stack natural alignment.
    317       StackNaturalAlign = inBytes(getInt(Tok));
    318       break;
    319     }
    320     case 'm':
    321       assert(Tok.empty());
    322       assert(Rest.size() == 1);
    323       switch(Rest[0]) {
    324       default:
    325         llvm_unreachable("Unknown mangling in datalayout string");
    326       case 'e':
    327         ManglingMode = MM_ELF;
    328         break;
    329       case 'o':
    330         ManglingMode = MM_MachO;
    331         break;
    332       case 'm':
    333         ManglingMode = MM_Mips;
    334         break;
    335       case 'w':
    336         ManglingMode = MM_WINCOFF;
    337         break;
    338       }
    339       break;
    340     default:
    341       llvm_unreachable("Unknown specifier in datalayout string");
    342       break;
    343     }
    344   }
    345 }
    346 
    347 DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
    348   const DataLayout *Other = M->getDataLayout();
    349   if (Other)
    350     *this = *Other;
    351   else
    352     reset("");
    353 }
    354 
    355 bool DataLayout::operator==(const DataLayout &Other) const {
    356   bool Ret = LittleEndian == Other.LittleEndian &&
    357              StackNaturalAlign == Other.StackNaturalAlign &&
    358              ManglingMode == Other.ManglingMode &&
    359              LegalIntWidths == Other.LegalIntWidths &&
    360              Alignments == Other.Alignments && Pointers == Other.Pointers;
    361   assert(Ret == (getStringRepresentation() == Other.getStringRepresentation()));
    362   return Ret;
    363 }
    364 
    365 void
    366 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
    367                          unsigned pref_align, uint32_t bit_width) {
    368   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
    369   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
    370   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
    371   for (LayoutAlignElem &Elem : Alignments) {
    372     if (Elem.AlignType == (unsigned)align_type &&
    373         Elem.TypeBitWidth == bit_width) {
    374       // Update the abi, preferred alignments.
    375       Elem.ABIAlign = abi_align;
    376       Elem.PrefAlign = pref_align;
    377       return;
    378     }
    379   }
    380 
    381   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
    382                                             pref_align, bit_width));
    383 }
    384 
    385 DataLayout::PointersTy::iterator
    386 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
    387   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
    388                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
    389     return A.AddressSpace < AddressSpace;
    390   });
    391 }
    392 
    393 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
    394                                      unsigned PrefAlign,
    395                                      uint32_t TypeByteWidth) {
    396   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
    397   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
    398   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
    399     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
    400                                              TypeByteWidth));
    401   } else {
    402     I->ABIAlign = ABIAlign;
    403     I->PrefAlign = PrefAlign;
    404     I->TypeByteWidth = TypeByteWidth;
    405   }
    406 }
    407 
    408 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
    409 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
    410 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
    411                                       uint32_t BitWidth, bool ABIInfo,
    412                                       Type *Ty) const {
    413   // Check to see if we have an exact match and remember the best match we see.
    414   int BestMatchIdx = -1;
    415   int LargestInt = -1;
    416   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
    417     if (Alignments[i].AlignType == (unsigned)AlignType &&
    418         Alignments[i].TypeBitWidth == BitWidth)
    419       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
    420 
    421     // The best match so far depends on what we're looking for.
    422      if (AlignType == INTEGER_ALIGN &&
    423          Alignments[i].AlignType == INTEGER_ALIGN) {
    424       // The "best match" for integers is the smallest size that is larger than
    425       // the BitWidth requested.
    426       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
    427           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
    428         BestMatchIdx = i;
    429       // However, if there isn't one that's larger, then we must use the
    430       // largest one we have (see below)
    431       if (LargestInt == -1 ||
    432           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
    433         LargestInt = i;
    434     }
    435   }
    436 
    437   // Okay, we didn't find an exact solution.  Fall back here depending on what
    438   // is being looked for.
    439   if (BestMatchIdx == -1) {
    440     // If we didn't find an integer alignment, fall back on most conservative.
    441     if (AlignType == INTEGER_ALIGN) {
    442       BestMatchIdx = LargestInt;
    443     } else {
    444       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
    445 
    446       // By default, use natural alignment for vector types. This is consistent
    447       // with what clang and llvm-gcc do.
    448       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
    449       Align *= cast<VectorType>(Ty)->getNumElements();
    450       // If the alignment is not a power of 2, round up to the next power of 2.
    451       // This happens for non-power-of-2 length vectors.
    452       if (Align & (Align-1))
    453         Align = NextPowerOf2(Align);
    454       return Align;
    455     }
    456   }
    457 
    458   // Since we got a "best match" index, just return it.
    459   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
    460                  : Alignments[BestMatchIdx].PrefAlign;
    461 }
    462 
    463 namespace {
    464 
    465 class StructLayoutMap {
    466   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
    467   LayoutInfoTy LayoutInfo;
    468 
    469 public:
    470   ~StructLayoutMap() {
    471     // Remove any layouts.
    472     for (const auto &I : LayoutInfo) {
    473       StructLayout *Value = I.second;
    474       Value->~StructLayout();
    475       free(Value);
    476     }
    477   }
    478 
    479   StructLayout *&operator[](StructType *STy) {
    480     return LayoutInfo[STy];
    481   }
    482 };
    483 
    484 } // end anonymous namespace
    485 
    486 void DataLayout::clear() {
    487   LegalIntWidths.clear();
    488   Alignments.clear();
    489   Pointers.clear();
    490   delete static_cast<StructLayoutMap *>(LayoutMap);
    491   LayoutMap = nullptr;
    492 }
    493 
    494 DataLayout::~DataLayout() {
    495   clear();
    496 }
    497 
    498 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
    499   if (!LayoutMap)
    500     LayoutMap = new StructLayoutMap();
    501 
    502   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
    503   StructLayout *&SL = (*STM)[Ty];
    504   if (SL) return SL;
    505 
    506   // Otherwise, create the struct layout.  Because it is variable length, we
    507   // malloc it, then use placement new.
    508   int NumElts = Ty->getNumElements();
    509   StructLayout *L =
    510     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
    511 
    512   // Set SL before calling StructLayout's ctor.  The ctor could cause other
    513   // entries to be added to TheMap, invalidating our reference.
    514   SL = L;
    515 
    516   new (L) StructLayout(Ty, *this);
    517 
    518   return L;
    519 }
    520 
    521 std::string DataLayout::getStringRepresentation() const {
    522   std::string Result;
    523   raw_string_ostream OS(Result);
    524 
    525   OS << (LittleEndian ? "e" : "E");
    526 
    527   switch (ManglingMode) {
    528   case MM_None:
    529     break;
    530   case MM_ELF:
    531     OS << "-m:e";
    532     break;
    533   case MM_MachO:
    534     OS << "-m:o";
    535     break;
    536   case MM_WINCOFF:
    537     OS << "-m:w";
    538     break;
    539   case MM_Mips:
    540     OS << "-m:m";
    541     break;
    542   }
    543 
    544   for (const PointerAlignElem &PI : Pointers) {
    545     // Skip default.
    546     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
    547         PI.TypeByteWidth == 8)
    548       continue;
    549 
    550     OS << "-p";
    551     if (PI.AddressSpace) {
    552       OS << PI.AddressSpace;
    553     }
    554     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
    555     if (PI.PrefAlign != PI.ABIAlign)
    556       OS << ':' << PI.PrefAlign*8;
    557   }
    558 
    559   for (const LayoutAlignElem &AI : Alignments) {
    560     if (std::find(std::begin(DefaultAlignments), std::end(DefaultAlignments),
    561                   AI) != std::end(DefaultAlignments))
    562       continue;
    563     OS << '-' << (char)AI.AlignType;
    564     if (AI.TypeBitWidth)
    565       OS << AI.TypeBitWidth;
    566     OS << ':' << AI.ABIAlign*8;
    567     if (AI.ABIAlign != AI.PrefAlign)
    568       OS << ':' << AI.PrefAlign*8;
    569   }
    570 
    571   if (!LegalIntWidths.empty()) {
    572     OS << "-n" << (unsigned)LegalIntWidths[0];
    573 
    574     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
    575       OS << ':' << (unsigned)LegalIntWidths[i];
    576   }
    577 
    578   if (StackNaturalAlign)
    579     OS << "-S" << StackNaturalAlign*8;
    580 
    581   return OS.str();
    582 }
    583 
    584 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
    585   PointersTy::const_iterator I = findPointerLowerBound(AS);
    586   if (I == Pointers.end() || I->AddressSpace != AS) {
    587     I = findPointerLowerBound(0);
    588     assert(I->AddressSpace == 0);
    589   }
    590   return I->ABIAlign;
    591 }
    592 
    593 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
    594   PointersTy::const_iterator I = findPointerLowerBound(AS);
    595   if (I == Pointers.end() || I->AddressSpace != AS) {
    596     I = findPointerLowerBound(0);
    597     assert(I->AddressSpace == 0);
    598   }
    599   return I->PrefAlign;
    600 }
    601 
    602 unsigned DataLayout::getPointerSize(unsigned AS) const {
    603   PointersTy::const_iterator I = findPointerLowerBound(AS);
    604   if (I == Pointers.end() || I->AddressSpace != AS) {
    605     I = findPointerLowerBound(0);
    606     assert(I->AddressSpace == 0);
    607   }
    608   return I->TypeByteWidth;
    609 }
    610 
    611 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
    612   assert(Ty->isPtrOrPtrVectorTy() &&
    613          "This should only be called with a pointer or pointer vector type");
    614 
    615   if (Ty->isPointerTy())
    616     return getTypeSizeInBits(Ty);
    617 
    618   return getTypeSizeInBits(Ty->getScalarType());
    619 }
    620 
    621 /*!
    622   \param abi_or_pref Flag that determines which alignment is returned. true
    623   returns the ABI alignment, false returns the preferred alignment.
    624   \param Ty The underlying type for which alignment is determined.
    625 
    626   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
    627   == false) for the requested type \a Ty.
    628  */
    629 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
    630   int AlignType = -1;
    631 
    632   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
    633   switch (Ty->getTypeID()) {
    634   // Early escape for the non-numeric types.
    635   case Type::LabelTyID:
    636     return (abi_or_pref
    637             ? getPointerABIAlignment(0)
    638             : getPointerPrefAlignment(0));
    639   case Type::PointerTyID: {
    640     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
    641     return (abi_or_pref
    642             ? getPointerABIAlignment(AS)
    643             : getPointerPrefAlignment(AS));
    644     }
    645   case Type::ArrayTyID:
    646     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
    647 
    648   case Type::StructTyID: {
    649     // Packed structure types always have an ABI alignment of one.
    650     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
    651       return 1;
    652 
    653     // Get the layout annotation... which is lazily created on demand.
    654     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
    655     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
    656     return std::max(Align, Layout->getAlignment());
    657   }
    658   case Type::IntegerTyID:
    659     AlignType = INTEGER_ALIGN;
    660     break;
    661   case Type::HalfTyID:
    662   case Type::FloatTyID:
    663   case Type::DoubleTyID:
    664   // PPC_FP128TyID and FP128TyID have different data contents, but the
    665   // same size and alignment, so they look the same here.
    666   case Type::PPC_FP128TyID:
    667   case Type::FP128TyID:
    668   case Type::X86_FP80TyID:
    669     AlignType = FLOAT_ALIGN;
    670     break;
    671   case Type::X86_MMXTyID:
    672   case Type::VectorTyID:
    673     AlignType = VECTOR_ALIGN;
    674     break;
    675   default:
    676     llvm_unreachable("Bad type for getAlignment!!!");
    677   }
    678 
    679   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
    680                           abi_or_pref, Ty);
    681 }
    682 
    683 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
    684   return getAlignment(Ty, true);
    685 }
    686 
    687 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
    688 /// an integer type of the specified bitwidth.
    689 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
    690   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
    691 }
    692 
    693 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
    694   return getAlignment(Ty, false);
    695 }
    696 
    697 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
    698   unsigned Align = getPrefTypeAlignment(Ty);
    699   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
    700   return Log2_32(Align);
    701 }
    702 
    703 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
    704                                        unsigned AddressSpace) const {
    705   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
    706 }
    707 
    708 Type *DataLayout::getIntPtrType(Type *Ty) const {
    709   assert(Ty->isPtrOrPtrVectorTy() &&
    710          "Expected a pointer or pointer vector type.");
    711   unsigned NumBits = getPointerTypeSizeInBits(Ty);
    712   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
    713   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
    714     return VectorType::get(IntTy, VecTy->getNumElements());
    715   return IntTy;
    716 }
    717 
    718 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
    719   for (unsigned LegalIntWidth : LegalIntWidths)
    720     if (Width <= LegalIntWidth)
    721       return Type::getIntNTy(C, LegalIntWidth);
    722   return nullptr;
    723 }
    724 
    725 unsigned DataLayout::getLargestLegalIntTypeSize() const {
    726   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
    727   return Max != LegalIntWidths.end() ? *Max : 0;
    728 }
    729 
    730 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
    731                                       ArrayRef<Value *> Indices) const {
    732   Type *Ty = ptrTy;
    733   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
    734   uint64_t Result = 0;
    735 
    736   generic_gep_type_iterator<Value* const*>
    737     TI = gep_type_begin(ptrTy, Indices);
    738   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
    739        ++CurIDX, ++TI) {
    740     if (StructType *STy = dyn_cast<StructType>(*TI)) {
    741       assert(Indices[CurIDX]->getType() ==
    742              Type::getInt32Ty(ptrTy->getContext()) &&
    743              "Illegal struct idx");
    744       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
    745 
    746       // Get structure layout information...
    747       const StructLayout *Layout = getStructLayout(STy);
    748 
    749       // Add in the offset, as calculated by the structure layout info...
    750       Result += Layout->getElementOffset(FieldNo);
    751 
    752       // Update Ty to refer to current element
    753       Ty = STy->getElementType(FieldNo);
    754     } else {
    755       // Update Ty to refer to current element
    756       Ty = cast<SequentialType>(Ty)->getElementType();
    757 
    758       // Get the array index and the size of each array element.
    759       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
    760         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
    761     }
    762   }
    763 
    764   return Result;
    765 }
    766 
    767 /// getPreferredAlignment - Return the preferred alignment of the specified
    768 /// global.  This includes an explicitly requested alignment (if the global
    769 /// has one).
    770 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
    771   Type *ElemType = GV->getType()->getElementType();
    772   unsigned Alignment = getPrefTypeAlignment(ElemType);
    773   unsigned GVAlignment = GV->getAlignment();
    774   if (GVAlignment >= Alignment) {
    775     Alignment = GVAlignment;
    776   } else if (GVAlignment != 0) {
    777     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
    778   }
    779 
    780   if (GV->hasInitializer() && GVAlignment == 0) {
    781     if (Alignment < 16) {
    782       // If the global is not external, see if it is large.  If so, give it a
    783       // larger alignment.
    784       if (getTypeSizeInBits(ElemType) > 128)
    785         Alignment = 16;    // 16-byte alignment.
    786     }
    787   }
    788   return Alignment;
    789 }
    790 
    791 /// getPreferredAlignmentLog - Return the preferred alignment of the
    792 /// specified global, returned in log form.  This includes an explicitly
    793 /// requested alignment (if the global has one).
    794 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
    795   return Log2_32(getPreferredAlignment(GV));
    796 }
    797 
    798 DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
    799   report_fatal_error("Bad DataLayoutPass ctor used. Tool did not specify a "
    800                      "DataLayout to use?");
    801 }
    802 
    803 DataLayoutPass::~DataLayoutPass() {}
    804 
    805 DataLayoutPass::DataLayoutPass(const DataLayout &DL)
    806     : ImmutablePass(ID), DL(DL) {
    807   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
    808 }
    809 
    810 DataLayoutPass::DataLayoutPass(const Module *M) : ImmutablePass(ID), DL(M) {
    811   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
    812 }
    813