LLVM  mainline
DataLayout.cpp
Go to the documentation of this file.
00001 //===-- DataLayout.cpp - Data size & alignment routines --------------------==//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines layout properties related to datatype size/offset/alignment
00011 // information.
00012 //
00013 // This structure should be created once, filled in if the defaults are not
00014 // correct and then passed around by const&.  None of the members functions
00015 // require modification to the object.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "llvm/IR/DataLayout.h"
00020 #include "llvm/ADT/DenseMap.h"
00021 #include "llvm/ADT/STLExtras.h"
00022 #include "llvm/ADT/Triple.h"
00023 #include "llvm/IR/Constants.h"
00024 #include "llvm/IR/DerivedTypes.h"
00025 #include "llvm/IR/GetElementPtrTypeIterator.h"
00026 #include "llvm/IR/Module.h"
00027 #include "llvm/Support/ErrorHandling.h"
00028 #include "llvm/Support/ManagedStatic.h"
00029 #include "llvm/Support/MathExtras.h"
00030 #include "llvm/Support/Mutex.h"
00031 #include "llvm/Support/raw_ostream.h"
00032 #include <algorithm>
00033 #include <cstdlib>
00034 using namespace llvm;
00035 
00036 //===----------------------------------------------------------------------===//
00037 // Support for StructLayout
00038 //===----------------------------------------------------------------------===//
00039 
00040 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
00041   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
00042   StructAlignment = 0;
00043   StructSize = 0;
00044   IsPadded = false;
00045   NumElements = ST->getNumElements();
00046 
00047   // Loop over each of the elements, placing them in memory.
00048   for (unsigned i = 0, e = NumElements; i != e; ++i) {
00049     Type *Ty = ST->getElementType(i);
00050     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
00051 
00052     // Add padding if necessary to align the data element properly.
00053     if ((StructSize & (TyAlign-1)) != 0) {
00054       IsPadded = true;
00055       StructSize = alignTo(StructSize, TyAlign);
00056     }
00057 
00058     // Keep track of maximum alignment constraint.
00059     StructAlignment = std::max(TyAlign, StructAlignment);
00060 
00061     MemberOffsets[i] = StructSize;
00062     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
00063   }
00064 
00065   // Empty structures have alignment of 1 byte.
00066   if (StructAlignment == 0) StructAlignment = 1;
00067 
00068   // Add padding to the end of the struct so that it could be put in an array
00069   // and all array elements would be aligned correctly.
00070   if ((StructSize & (StructAlignment-1)) != 0) {
00071     IsPadded = true;
00072     StructSize = alignTo(StructSize, StructAlignment);
00073   }
00074 }
00075 
00076 
00077 /// getElementContainingOffset - Given a valid offset into the structure,
00078 /// return the structure index that contains it.
00079 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
00080   const uint64_t *SI =
00081     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
00082   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
00083   --SI;
00084   assert(*SI <= Offset && "upper_bound didn't work");
00085   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
00086          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
00087          "Upper bound didn't work!");
00088 
00089   // Multiple fields can have the same offset if any of them are zero sized.
00090   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
00091   // at the i32 element, because it is the last element at that offset.  This is
00092   // the right one to return, because anything after it will have a higher
00093   // offset, implying that this element is non-empty.
00094   return SI-&MemberOffsets[0];
00095 }
00096 
00097 //===----------------------------------------------------------------------===//
00098 // LayoutAlignElem, LayoutAlign support
00099 //===----------------------------------------------------------------------===//
00100 
00101 LayoutAlignElem
00102 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
00103                      unsigned pref_align, uint32_t bit_width) {
00104   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
00105   LayoutAlignElem retval;
00106   retval.AlignType = align_type;
00107   retval.ABIAlign = abi_align;
00108   retval.PrefAlign = pref_align;
00109   retval.TypeBitWidth = bit_width;
00110   return retval;
00111 }
00112 
00113 bool
00114 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
00115   return (AlignType == rhs.AlignType
00116           && ABIAlign == rhs.ABIAlign
00117           && PrefAlign == rhs.PrefAlign
00118           && TypeBitWidth == rhs.TypeBitWidth);
00119 }
00120 
00121 const LayoutAlignElem
00122 DataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 };
00123 
00124 //===----------------------------------------------------------------------===//
00125 // PointerAlignElem, PointerAlign support
00126 //===----------------------------------------------------------------------===//
00127 
00128 PointerAlignElem
00129 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
00130                       unsigned PrefAlign, uint32_t TypeByteWidth) {
00131   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
00132   PointerAlignElem retval;
00133   retval.AddressSpace = AddressSpace;
00134   retval.ABIAlign = ABIAlign;
00135   retval.PrefAlign = PrefAlign;
00136   retval.TypeByteWidth = TypeByteWidth;
00137   return retval;
00138 }
00139 
00140 bool
00141 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
00142   return (ABIAlign == rhs.ABIAlign
00143           && AddressSpace == rhs.AddressSpace
00144           && PrefAlign == rhs.PrefAlign
00145           && TypeByteWidth == rhs.TypeByteWidth);
00146 }
00147 
00148 const PointerAlignElem
00149 DataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U };
00150 
00151 //===----------------------------------------------------------------------===//
00152 //                       DataLayout Class Implementation
00153 //===----------------------------------------------------------------------===//
00154 
00155 const char *DataLayout::getManglingComponent(const Triple &T) {
00156   if (T.isOSBinFormatMachO())
00157     return "-m:o";
00158   if (T.isOSWindows() && T.isOSBinFormatCOFF())
00159     return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
00160   return "-m:e";
00161 }
00162 
00163 static const LayoutAlignElem DefaultAlignments[] = {
00164   { INTEGER_ALIGN, 1, 1, 1 },    // i1
00165   { INTEGER_ALIGN, 8, 1, 1 },    // i8
00166   { INTEGER_ALIGN, 16, 2, 2 },   // i16
00167   { INTEGER_ALIGN, 32, 4, 4 },   // i32
00168   { INTEGER_ALIGN, 64, 4, 8 },   // i64
00169   { FLOAT_ALIGN, 16, 2, 2 },     // half
00170   { FLOAT_ALIGN, 32, 4, 4 },     // float
00171   { FLOAT_ALIGN, 64, 8, 8 },     // double
00172   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
00173   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
00174   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
00175   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
00176 };
00177 
00178 void DataLayout::reset(StringRef Desc) {
00179   clear();
00180 
00181   LayoutMap = nullptr;
00182   BigEndian = false;
00183   StackNaturalAlign = 0;
00184   ManglingMode = MM_None;
00185 
00186   // Default alignments
00187   for (const LayoutAlignElem &E : DefaultAlignments) {
00188     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
00189                  E.TypeBitWidth);
00190   }
00191   setPointerAlignment(0, 8, 8, 8);
00192 
00193   parseSpecifier(Desc);
00194 }
00195 
00196 /// Checked version of split, to ensure mandatory subparts.
00197 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
00198   assert(!Str.empty() && "parse error, string can't be empty here");
00199   std::pair<StringRef, StringRef> Split = Str.split(Separator);
00200   if (Split.second.empty() && Split.first != Str)
00201     report_fatal_error("Trailing separator in datalayout string");
00202   if (!Split.second.empty() && Split.first.empty())
00203     report_fatal_error("Expected token before separator in datalayout string");
00204   return Split;
00205 }
00206 
00207 /// Get an unsigned integer, including error checks.
00208 static unsigned getInt(StringRef R) {
00209   unsigned Result;
00210   bool error = R.getAsInteger(10, Result); (void)error;
00211   if (error)
00212     report_fatal_error("not a number, or does not fit in an unsigned int");
00213   return Result;
00214 }
00215 
00216 /// Convert bits into bytes. Assert if not a byte width multiple.
00217 static unsigned inBytes(unsigned Bits) {
00218   if (Bits % 8)
00219     report_fatal_error("number of bits must be a byte width multiple");
00220   return Bits / 8;
00221 }
00222 
00223 void DataLayout::parseSpecifier(StringRef Desc) {
00224   StringRepresentation = Desc;
00225   while (!Desc.empty()) {
00226     // Split at '-'.
00227     std::pair<StringRef, StringRef> Split = split(Desc, '-');
00228     Desc = Split.second;
00229 
00230     // Split at ':'.
00231     Split = split(Split.first, ':');
00232 
00233     // Aliases used below.
00234     StringRef &Tok  = Split.first;  // Current token.
00235     StringRef &Rest = Split.second; // The rest of the string.
00236 
00237     char Specifier = Tok.front();
00238     Tok = Tok.substr(1);
00239 
00240     switch (Specifier) {
00241     case 's':
00242       // Ignored for backward compatibility.
00243       // FIXME: remove this on LLVM 4.0.
00244       break;
00245     case 'E':
00246       BigEndian = true;
00247       break;
00248     case 'e':
00249       BigEndian = false;
00250       break;
00251     case 'p': {
00252       // Address space.
00253       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
00254       if (!isUInt<24>(AddrSpace))
00255         report_fatal_error("Invalid address space, must be a 24bit integer");
00256 
00257       // Size.
00258       if (Rest.empty())
00259         report_fatal_error(
00260             "Missing size specification for pointer in datalayout string");
00261       Split = split(Rest, ':');
00262       unsigned PointerMemSize = inBytes(getInt(Tok));
00263       if (!PointerMemSize)
00264         report_fatal_error("Invalid pointer size of 0 bytes");
00265 
00266       // ABI alignment.
00267       if (Rest.empty())
00268         report_fatal_error(
00269             "Missing alignment specification for pointer in datalayout string");
00270       Split = split(Rest, ':');
00271       unsigned PointerABIAlign = inBytes(getInt(Tok));
00272       if (!isPowerOf2_64(PointerABIAlign))
00273         report_fatal_error(
00274             "Pointer ABI alignment must be a power of 2");
00275 
00276       // Preferred alignment.
00277       unsigned PointerPrefAlign = PointerABIAlign;
00278       if (!Rest.empty()) {
00279         Split = split(Rest, ':');
00280         PointerPrefAlign = inBytes(getInt(Tok));
00281         if (!isPowerOf2_64(PointerPrefAlign))
00282           report_fatal_error(
00283             "Pointer preferred alignment must be a power of 2");
00284       }
00285 
00286       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
00287                           PointerMemSize);
00288       break;
00289     }
00290     case 'i':
00291     case 'v':
00292     case 'f':
00293     case 'a': {
00294       AlignTypeEnum AlignType;
00295       switch (Specifier) {
00296       default:
00297       case 'i': AlignType = INTEGER_ALIGN; break;
00298       case 'v': AlignType = VECTOR_ALIGN; break;
00299       case 'f': AlignType = FLOAT_ALIGN; break;
00300       case 'a': AlignType = AGGREGATE_ALIGN; break;
00301       }
00302 
00303       // Bit size.
00304       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
00305 
00306       if (AlignType == AGGREGATE_ALIGN && Size != 0)
00307         report_fatal_error(
00308             "Sized aggregate specification in datalayout string");
00309 
00310       // ABI alignment.
00311       if (Rest.empty())
00312         report_fatal_error(
00313             "Missing alignment specification in datalayout string");
00314       Split = split(Rest, ':');
00315       unsigned ABIAlign = inBytes(getInt(Tok));
00316       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
00317         report_fatal_error(
00318             "ABI alignment specification must be >0 for non-aggregate types");
00319 
00320       // Preferred alignment.
00321       unsigned PrefAlign = ABIAlign;
00322       if (!Rest.empty()) {
00323         Split = split(Rest, ':');
00324         PrefAlign = inBytes(getInt(Tok));
00325       }
00326 
00327       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
00328 
00329       break;
00330     }
00331     case 'n':  // Native integer types.
00332       for (;;) {
00333         unsigned Width = getInt(Tok);
00334         if (Width == 0)
00335           report_fatal_error(
00336               "Zero width native integer type in datalayout string");
00337         LegalIntWidths.push_back(Width);
00338         if (Rest.empty())
00339           break;
00340         Split = split(Rest, ':');
00341       }
00342       break;
00343     case 'S': { // Stack natural alignment.
00344       StackNaturalAlign = inBytes(getInt(Tok));
00345       break;
00346     }
00347     case 'm':
00348       if (!Tok.empty())
00349         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
00350       if (Rest.empty())
00351         report_fatal_error("Expected mangling specifier in datalayout string");
00352       if (Rest.size() > 1)
00353         report_fatal_error("Unknown mangling specifier in datalayout string");
00354       switch(Rest[0]) {
00355       default:
00356         report_fatal_error("Unknown mangling in datalayout string");
00357       case 'e':
00358         ManglingMode = MM_ELF;
00359         break;
00360       case 'o':
00361         ManglingMode = MM_MachO;
00362         break;
00363       case 'm':
00364         ManglingMode = MM_Mips;
00365         break;
00366       case 'w':
00367         ManglingMode = MM_WinCOFF;
00368         break;
00369       case 'x':
00370         ManglingMode = MM_WinCOFFX86;
00371         break;
00372       }
00373       break;
00374     default:
00375       report_fatal_error("Unknown specifier in datalayout string");
00376       break;
00377     }
00378   }
00379 }
00380 
00381 DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
00382   init(M);
00383 }
00384 
00385 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
00386 
00387 bool DataLayout::operator==(const DataLayout &Other) const {
00388   bool Ret = BigEndian == Other.BigEndian &&
00389              StackNaturalAlign == Other.StackNaturalAlign &&
00390              ManglingMode == Other.ManglingMode &&
00391              LegalIntWidths == Other.LegalIntWidths &&
00392              Alignments == Other.Alignments && Pointers == Other.Pointers;
00393   // Note: getStringRepresentation() might differs, it is not canonicalized
00394   return Ret;
00395 }
00396 
00397 void
00398 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
00399                          unsigned pref_align, uint32_t bit_width) {
00400   if (!isUInt<24>(bit_width))
00401     report_fatal_error("Invalid bit width, must be a 24bit integer");
00402   if (!isUInt<16>(abi_align))
00403     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
00404   if (!isUInt<16>(pref_align))
00405     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
00406   if (abi_align != 0 && !isPowerOf2_64(abi_align))
00407     report_fatal_error("Invalid ABI alignment, must be a power of 2");
00408   if (pref_align != 0 && !isPowerOf2_64(pref_align))
00409     report_fatal_error("Invalid preferred alignment, must be a power of 2");
00410 
00411   if (pref_align < abi_align)
00412     report_fatal_error(
00413         "Preferred alignment cannot be less than the ABI alignment");
00414 
00415   for (LayoutAlignElem &Elem : Alignments) {
00416     if (Elem.AlignType == (unsigned)align_type &&
00417         Elem.TypeBitWidth == bit_width) {
00418       // Update the abi, preferred alignments.
00419       Elem.ABIAlign = abi_align;
00420       Elem.PrefAlign = pref_align;
00421       return;
00422     }
00423   }
00424 
00425   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
00426                                             pref_align, bit_width));
00427 }
00428 
00429 DataLayout::PointersTy::iterator
00430 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
00431   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
00432                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
00433     return A.AddressSpace < AddressSpace;
00434   });
00435 }
00436 
00437 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
00438                                      unsigned PrefAlign,
00439                                      uint32_t TypeByteWidth) {
00440   if (PrefAlign < ABIAlign)
00441     report_fatal_error(
00442         "Preferred alignment cannot be less than the ABI alignment");
00443 
00444   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
00445   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
00446     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
00447                                              TypeByteWidth));
00448   } else {
00449     I->ABIAlign = ABIAlign;
00450     I->PrefAlign = PrefAlign;
00451     I->TypeByteWidth = TypeByteWidth;
00452   }
00453 }
00454 
00455 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
00456 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
00457 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
00458                                       uint32_t BitWidth, bool ABIInfo,
00459                                       Type *Ty) const {
00460   // Check to see if we have an exact match and remember the best match we see.
00461   int BestMatchIdx = -1;
00462   int LargestInt = -1;
00463   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
00464     if (Alignments[i].AlignType == (unsigned)AlignType &&
00465         Alignments[i].TypeBitWidth == BitWidth)
00466       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
00467 
00468     // The best match so far depends on what we're looking for.
00469     if (AlignType == INTEGER_ALIGN &&
00470         Alignments[i].AlignType == INTEGER_ALIGN) {
00471       // The "best match" for integers is the smallest size that is larger than
00472       // the BitWidth requested.
00473       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
00474           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
00475         BestMatchIdx = i;
00476       // However, if there isn't one that's larger, then we must use the
00477       // largest one we have (see below)
00478       if (LargestInt == -1 ||
00479           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
00480         LargestInt = i;
00481     }
00482   }
00483 
00484   // Okay, we didn't find an exact solution.  Fall back here depending on what
00485   // is being looked for.
00486   if (BestMatchIdx == -1) {
00487     // If we didn't find an integer alignment, fall back on most conservative.
00488     if (AlignType == INTEGER_ALIGN) {
00489       BestMatchIdx = LargestInt;
00490     } else if (AlignType == VECTOR_ALIGN) {
00491       // By default, use natural alignment for vector types. This is consistent
00492       // with what clang and llvm-gcc do.
00493       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
00494       Align *= cast<VectorType>(Ty)->getNumElements();
00495       // If the alignment is not a power of 2, round up to the next power of 2.
00496       // This happens for non-power-of-2 length vectors.
00497       if (Align & (Align-1))
00498         Align = NextPowerOf2(Align);
00499       return Align;
00500     }
00501   }
00502 
00503   // If we still couldn't find a reasonable default alignment, fall back
00504   // to a simple heuristic that the alignment is the first power of two
00505   // greater-or-equal to the store size of the type.  This is a reasonable
00506   // approximation of reality, and if the user wanted something less
00507   // less conservative, they should have specified it explicitly in the data
00508   // layout.
00509   if (BestMatchIdx == -1) {
00510     unsigned Align = getTypeStoreSize(Ty);
00511     if (Align & (Align-1))
00512       Align = NextPowerOf2(Align);
00513     return Align;
00514   }
00515 
00516   // Since we got a "best match" index, just return it.
00517   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
00518                  : Alignments[BestMatchIdx].PrefAlign;
00519 }
00520 
00521 namespace {
00522 
00523 class StructLayoutMap {
00524   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
00525   LayoutInfoTy LayoutInfo;
00526 
00527 public:
00528   ~StructLayoutMap() {
00529     // Remove any layouts.
00530     for (const auto &I : LayoutInfo) {
00531       StructLayout *Value = I.second;
00532       Value->~StructLayout();
00533       free(Value);
00534     }
00535   }
00536 
00537   StructLayout *&operator[](StructType *STy) {
00538     return LayoutInfo[STy];
00539   }
00540 };
00541 
00542 } // end anonymous namespace
00543 
00544 void DataLayout::clear() {
00545   LegalIntWidths.clear();
00546   Alignments.clear();
00547   Pointers.clear();
00548   delete static_cast<StructLayoutMap *>(LayoutMap);
00549   LayoutMap = nullptr;
00550 }
00551 
00552 DataLayout::~DataLayout() {
00553   clear();
00554 }
00555 
00556 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
00557   if (!LayoutMap)
00558     LayoutMap = new StructLayoutMap();
00559 
00560   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
00561   StructLayout *&SL = (*STM)[Ty];
00562   if (SL) return SL;
00563 
00564   // Otherwise, create the struct layout.  Because it is variable length, we
00565   // malloc it, then use placement new.
00566   int NumElts = Ty->getNumElements();
00567   StructLayout *L =
00568     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
00569 
00570   // Set SL before calling StructLayout's ctor.  The ctor could cause other
00571   // entries to be added to TheMap, invalidating our reference.
00572   SL = L;
00573 
00574   new (L) StructLayout(Ty, *this);
00575 
00576   return L;
00577 }
00578 
00579 
00580 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
00581   PointersTy::const_iterator I = findPointerLowerBound(AS);
00582   if (I == Pointers.end() || I->AddressSpace != AS) {
00583     I = findPointerLowerBound(0);
00584     assert(I->AddressSpace == 0);
00585   }
00586   return I->ABIAlign;
00587 }
00588 
00589 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
00590   PointersTy::const_iterator I = findPointerLowerBound(AS);
00591   if (I == Pointers.end() || I->AddressSpace != AS) {
00592     I = findPointerLowerBound(0);
00593     assert(I->AddressSpace == 0);
00594   }
00595   return I->PrefAlign;
00596 }
00597 
00598 unsigned DataLayout::getPointerSize(unsigned AS) const {
00599   PointersTy::const_iterator I = findPointerLowerBound(AS);
00600   if (I == Pointers.end() || I->AddressSpace != AS) {
00601     I = findPointerLowerBound(0);
00602     assert(I->AddressSpace == 0);
00603   }
00604   return I->TypeByteWidth;
00605 }
00606 
00607 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
00608   assert(Ty->isPtrOrPtrVectorTy() &&
00609          "This should only be called with a pointer or pointer vector type");
00610 
00611   if (Ty->isPointerTy())
00612     return getTypeSizeInBits(Ty);
00613 
00614   return getTypeSizeInBits(Ty->getScalarType());
00615 }
00616 
00617 /*!
00618   \param abi_or_pref Flag that determines which alignment is returned. true
00619   returns the ABI alignment, false returns the preferred alignment.
00620   \param Ty The underlying type for which alignment is determined.
00621 
00622   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
00623   == false) for the requested type \a Ty.
00624  */
00625 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
00626   int AlignType = -1;
00627 
00628   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
00629   switch (Ty->getTypeID()) {
00630   // Early escape for the non-numeric types.
00631   case Type::LabelTyID:
00632     return (abi_or_pref
00633             ? getPointerABIAlignment(0)
00634             : getPointerPrefAlignment(0));
00635   case Type::PointerTyID: {
00636     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
00637     return (abi_or_pref
00638             ? getPointerABIAlignment(AS)
00639             : getPointerPrefAlignment(AS));
00640     }
00641   case Type::ArrayTyID:
00642     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
00643 
00644   case Type::StructTyID: {
00645     // Packed structure types always have an ABI alignment of one.
00646     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
00647       return 1;
00648 
00649     // Get the layout annotation... which is lazily created on demand.
00650     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
00651     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
00652     return std::max(Align, Layout->getAlignment());
00653   }
00654   case Type::IntegerTyID:
00655     AlignType = INTEGER_ALIGN;
00656     break;
00657   case Type::HalfTyID:
00658   case Type::FloatTyID:
00659   case Type::DoubleTyID:
00660   // PPC_FP128TyID and FP128TyID have different data contents, but the
00661   // same size and alignment, so they look the same here.
00662   case Type::PPC_FP128TyID:
00663   case Type::FP128TyID:
00664   case Type::X86_FP80TyID:
00665     AlignType = FLOAT_ALIGN;
00666     break;
00667   case Type::X86_MMXTyID:
00668   case Type::VectorTyID:
00669     AlignType = VECTOR_ALIGN;
00670     break;
00671   default:
00672     llvm_unreachable("Bad type for getAlignment!!!");
00673   }
00674 
00675   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
00676                           abi_or_pref, Ty);
00677 }
00678 
00679 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
00680   return getAlignment(Ty, true);
00681 }
00682 
00683 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
00684 /// an integer type of the specified bitwidth.
00685 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
00686   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
00687 }
00688 
00689 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
00690   return getAlignment(Ty, false);
00691 }
00692 
00693 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
00694   unsigned Align = getPrefTypeAlignment(Ty);
00695   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
00696   return Log2_32(Align);
00697 }
00698 
00699 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
00700                                        unsigned AddressSpace) const {
00701   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
00702 }
00703 
00704 Type *DataLayout::getIntPtrType(Type *Ty) const {
00705   assert(Ty->isPtrOrPtrVectorTy() &&
00706          "Expected a pointer or pointer vector type.");
00707   unsigned NumBits = getPointerTypeSizeInBits(Ty);
00708   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
00709   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
00710     return VectorType::get(IntTy, VecTy->getNumElements());
00711   return IntTy;
00712 }
00713 
00714 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
00715   for (unsigned LegalIntWidth : LegalIntWidths)
00716     if (Width <= LegalIntWidth)
00717       return Type::getIntNTy(C, LegalIntWidth);
00718   return nullptr;
00719 }
00720 
00721 unsigned DataLayout::getLargestLegalIntTypeSize() const {
00722   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
00723   return Max != LegalIntWidths.end() ? *Max : 0;
00724 }
00725 
00726 uint64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
00727                                             ArrayRef<Value *> Indices) const {
00728   uint64_t Result = 0;
00729 
00730   // We can use 0 as the address space as we don't need
00731   // to get pointer types back from gep_type_iterator.
00732   unsigned AS = 0;
00733   generic_gep_type_iterator<Value* const*>
00734     GTI = gep_type_begin(ElemTy, AS, Indices),
00735     GTE = gep_type_end(ElemTy, AS, Indices);
00736   for (; GTI != GTE; ++GTI) {
00737     Value *Idx = GTI.getOperand();
00738     if (StructType *STy = dyn_cast<StructType>(*GTI)) {
00739       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
00740       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
00741 
00742       // Get structure layout information...
00743       const StructLayout *Layout = getStructLayout(STy);
00744 
00745       // Add in the offset, as calculated by the structure layout info...
00746       Result += Layout->getElementOffset(FieldNo);
00747     } else {
00748       // Get the array index and the size of each array element.
00749       if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
00750         Result += (uint64_t)arrayIdx * getTypeAllocSize(GTI.getIndexedType());
00751     }
00752   }
00753 
00754   return Result;
00755 }
00756 
00757 /// getPreferredAlignment - Return the preferred alignment of the specified
00758 /// global.  This includes an explicitly requested alignment (if the global
00759 /// has one).
00760 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
00761   Type *ElemType = GV->getValueType();
00762   unsigned Alignment = getPrefTypeAlignment(ElemType);
00763   unsigned GVAlignment = GV->getAlignment();
00764   if (GVAlignment >= Alignment) {
00765     Alignment = GVAlignment;
00766   } else if (GVAlignment != 0) {
00767     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
00768   }
00769 
00770   if (GV->hasInitializer() && GVAlignment == 0) {
00771     if (Alignment < 16) {
00772       // If the global is not external, see if it is large.  If so, give it a
00773       // larger alignment.
00774       if (getTypeSizeInBits(ElemType) > 128)
00775         Alignment = 16;    // 16-byte alignment.
00776     }
00777   }
00778   return Alignment;
00779 }
00780 
00781 /// getPreferredAlignmentLog - Return the preferred alignment of the
00782 /// specified global, returned in log form.  This includes an explicitly
00783 /// requested alignment (if the global has one).
00784 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
00785   return Log2_32(getPreferredAlignment(GV));
00786 }
00787