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