LLVM API Documentation

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 // Handle the Pass registration stuff necessary to use DataLayout's.
00037 
00038 INITIALIZE_PASS(DataLayoutPass, "datalayout", "Data Layout", false, true)
00039 char DataLayoutPass::ID = 0;
00040 
00041 //===----------------------------------------------------------------------===//
00042 // Support for StructLayout
00043 //===----------------------------------------------------------------------===//
00044 
00045 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
00046   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
00047   StructAlignment = 0;
00048   StructSize = 0;
00049   NumElements = ST->getNumElements();
00050 
00051   // Loop over each of the elements, placing them in memory.
00052   for (unsigned i = 0, e = NumElements; i != e; ++i) {
00053     Type *Ty = ST->getElementType(i);
00054     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
00055 
00056     // Add padding if necessary to align the data element properly.
00057     if ((StructSize & (TyAlign-1)) != 0)
00058       StructSize = DataLayout::RoundUpAlignment(StructSize, TyAlign);
00059 
00060     // Keep track of maximum alignment constraint.
00061     StructAlignment = std::max(TyAlign, StructAlignment);
00062 
00063     MemberOffsets[i] = StructSize;
00064     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
00065   }
00066 
00067   // Empty structures have alignment of 1 byte.
00068   if (StructAlignment == 0) StructAlignment = 1;
00069 
00070   // Add padding to the end of the struct so that it could be put in an array
00071   // and all array elements would be aligned correctly.
00072   if ((StructSize & (StructAlignment-1)) != 0)
00073     StructSize = DataLayout::RoundUpAlignment(StructSize, StructAlignment);
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.getArch() == Triple::x86 && T.isOSBinFormatCOFF())
00159     return "-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   LittleEndian = 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   assert((!Split.second.empty() || Split.first == Str) &&
00201          "a trailing separator is not allowed");
00202   return Split;
00203 }
00204 
00205 /// Get an unsigned integer, including error checks.
00206 static unsigned getInt(StringRef R) {
00207   unsigned Result;
00208   bool error = R.getAsInteger(10, Result); (void)error;
00209   if (error)
00210     report_fatal_error("not a number, or does not fit in an unsigned int");
00211   return Result;
00212 }
00213 
00214 /// Convert bits into bytes. Assert if not a byte width multiple.
00215 static unsigned inBytes(unsigned Bits) {
00216   assert(Bits % 8 == 0 && "number of bits must be a byte width multiple");
00217   return Bits / 8;
00218 }
00219 
00220 void DataLayout::parseSpecifier(StringRef Desc) {
00221   while (!Desc.empty()) {
00222     // Split at '-'.
00223     std::pair<StringRef, StringRef> Split = split(Desc, '-');
00224     Desc = Split.second;
00225 
00226     // Split at ':'.
00227     Split = split(Split.first, ':');
00228 
00229     // Aliases used below.
00230     StringRef &Tok  = Split.first;  // Current token.
00231     StringRef &Rest = Split.second; // The rest of the string.
00232 
00233     char Specifier = Tok.front();
00234     Tok = Tok.substr(1);
00235 
00236     switch (Specifier) {
00237     case 's':
00238       // Ignored for backward compatibility.
00239       // FIXME: remove this on LLVM 4.0.
00240       break;
00241     case 'E':
00242       LittleEndian = false;
00243       break;
00244     case 'e':
00245       LittleEndian = true;
00246       break;
00247     case 'p': {
00248       // Address space.
00249       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
00250       assert(AddrSpace < 1 << 24 &&
00251              "Invalid address space, must be a 24bit integer");
00252 
00253       // Size.
00254       Split = split(Rest, ':');
00255       unsigned PointerMemSize = inBytes(getInt(Tok));
00256 
00257       // ABI alignment.
00258       Split = split(Rest, ':');
00259       unsigned PointerABIAlign = inBytes(getInt(Tok));
00260 
00261       // Preferred alignment.
00262       unsigned PointerPrefAlign = PointerABIAlign;
00263       if (!Rest.empty()) {
00264         Split = split(Rest, ':');
00265         PointerPrefAlign = inBytes(getInt(Tok));
00266       }
00267 
00268       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
00269                           PointerMemSize);
00270       break;
00271     }
00272     case 'i':
00273     case 'v':
00274     case 'f':
00275     case 'a': {
00276       AlignTypeEnum AlignType;
00277       switch (Specifier) {
00278       default:
00279       case 'i': AlignType = INTEGER_ALIGN; break;
00280       case 'v': AlignType = VECTOR_ALIGN; break;
00281       case 'f': AlignType = FLOAT_ALIGN; break;
00282       case 'a': AlignType = AGGREGATE_ALIGN; break;
00283       }
00284 
00285       // Bit size.
00286       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
00287 
00288       assert((AlignType != AGGREGATE_ALIGN || Size == 0) &&
00289              "These specifications don't have a size");
00290 
00291       // ABI alignment.
00292       Split = split(Rest, ':');
00293       unsigned ABIAlign = inBytes(getInt(Tok));
00294 
00295       // Preferred alignment.
00296       unsigned PrefAlign = ABIAlign;
00297       if (!Rest.empty()) {
00298         Split = split(Rest, ':');
00299         PrefAlign = inBytes(getInt(Tok));
00300       }
00301 
00302       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
00303 
00304       break;
00305     }
00306     case 'n':  // Native integer types.
00307       for (;;) {
00308         unsigned Width = getInt(Tok);
00309         assert(Width != 0 && "width must be non-zero");
00310         LegalIntWidths.push_back(Width);
00311         if (Rest.empty())
00312           break;
00313         Split = split(Rest, ':');
00314       }
00315       break;
00316     case 'S': { // Stack natural alignment.
00317       StackNaturalAlign = inBytes(getInt(Tok));
00318       break;
00319     }
00320     case 'm':
00321       assert(Tok.empty());
00322       assert(Rest.size() == 1);
00323       switch(Rest[0]) {
00324       default:
00325         llvm_unreachable("Unknown mangling in datalayout string");
00326       case 'e':
00327         ManglingMode = MM_ELF;
00328         break;
00329       case 'o':
00330         ManglingMode = MM_MachO;
00331         break;
00332       case 'm':
00333         ManglingMode = MM_Mips;
00334         break;
00335       case 'w':
00336         ManglingMode = MM_WINCOFF;
00337         break;
00338       }
00339       break;
00340     default:
00341       llvm_unreachable("Unknown specifier in datalayout string");
00342       break;
00343     }
00344   }
00345 }
00346 
00347 DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
00348   init(M);
00349 }
00350 
00351 void DataLayout::init(const Module *M) {
00352   const DataLayout *Other = M->getDataLayout();
00353   if (Other)
00354     *this = *Other;
00355   else
00356     reset("");
00357 }
00358 
00359 bool DataLayout::operator==(const DataLayout &Other) const {
00360   bool Ret = LittleEndian == Other.LittleEndian &&
00361              StackNaturalAlign == Other.StackNaturalAlign &&
00362              ManglingMode == Other.ManglingMode &&
00363              LegalIntWidths == Other.LegalIntWidths &&
00364              Alignments == Other.Alignments && Pointers == Other.Pointers;
00365   assert(Ret == (getStringRepresentation() == Other.getStringRepresentation()));
00366   return Ret;
00367 }
00368 
00369 void
00370 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
00371                          unsigned pref_align, uint32_t bit_width) {
00372   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
00373   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
00374   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
00375   for (LayoutAlignElem &Elem : Alignments) {
00376     if (Elem.AlignType == (unsigned)align_type &&
00377         Elem.TypeBitWidth == bit_width) {
00378       // Update the abi, preferred alignments.
00379       Elem.ABIAlign = abi_align;
00380       Elem.PrefAlign = pref_align;
00381       return;
00382     }
00383   }
00384 
00385   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
00386                                             pref_align, bit_width));
00387 }
00388 
00389 DataLayout::PointersTy::iterator
00390 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
00391   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
00392                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
00393     return A.AddressSpace < AddressSpace;
00394   });
00395 }
00396 
00397 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
00398                                      unsigned PrefAlign,
00399                                      uint32_t TypeByteWidth) {
00400   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
00401   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
00402   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
00403     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
00404                                              TypeByteWidth));
00405   } else {
00406     I->ABIAlign = ABIAlign;
00407     I->PrefAlign = PrefAlign;
00408     I->TypeByteWidth = TypeByteWidth;
00409   }
00410 }
00411 
00412 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
00413 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
00414 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
00415                                       uint32_t BitWidth, bool ABIInfo,
00416                                       Type *Ty) const {
00417   // Check to see if we have an exact match and remember the best match we see.
00418   int BestMatchIdx = -1;
00419   int LargestInt = -1;
00420   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
00421     if (Alignments[i].AlignType == (unsigned)AlignType &&
00422         Alignments[i].TypeBitWidth == BitWidth)
00423       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
00424 
00425     // The best match so far depends on what we're looking for.
00426      if (AlignType == INTEGER_ALIGN &&
00427          Alignments[i].AlignType == INTEGER_ALIGN) {
00428       // The "best match" for integers is the smallest size that is larger than
00429       // the BitWidth requested.
00430       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
00431           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
00432         BestMatchIdx = i;
00433       // However, if there isn't one that's larger, then we must use the
00434       // largest one we have (see below)
00435       if (LargestInt == -1 ||
00436           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
00437         LargestInt = i;
00438     }
00439   }
00440 
00441   // Okay, we didn't find an exact solution.  Fall back here depending on what
00442   // is being looked for.
00443   if (BestMatchIdx == -1) {
00444     // If we didn't find an integer alignment, fall back on most conservative.
00445     if (AlignType == INTEGER_ALIGN) {
00446       BestMatchIdx = LargestInt;
00447     } else {
00448       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
00449 
00450       // By default, use natural alignment for vector types. This is consistent
00451       // with what clang and llvm-gcc do.
00452       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
00453       Align *= cast<VectorType>(Ty)->getNumElements();
00454       // If the alignment is not a power of 2, round up to the next power of 2.
00455       // This happens for non-power-of-2 length vectors.
00456       if (Align & (Align-1))
00457         Align = NextPowerOf2(Align);
00458       return Align;
00459     }
00460   }
00461 
00462   // Since we got a "best match" index, just return it.
00463   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
00464                  : Alignments[BestMatchIdx].PrefAlign;
00465 }
00466 
00467 namespace {
00468 
00469 class StructLayoutMap {
00470   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
00471   LayoutInfoTy LayoutInfo;
00472 
00473 public:
00474   ~StructLayoutMap() {
00475     // Remove any layouts.
00476     for (const auto &I : LayoutInfo) {
00477       StructLayout *Value = I.second;
00478       Value->~StructLayout();
00479       free(Value);
00480     }
00481   }
00482 
00483   StructLayout *&operator[](StructType *STy) {
00484     return LayoutInfo[STy];
00485   }
00486 };
00487 
00488 } // end anonymous namespace
00489 
00490 void DataLayout::clear() {
00491   LegalIntWidths.clear();
00492   Alignments.clear();
00493   Pointers.clear();
00494   delete static_cast<StructLayoutMap *>(LayoutMap);
00495   LayoutMap = nullptr;
00496 }
00497 
00498 DataLayout::~DataLayout() {
00499   clear();
00500 }
00501 
00502 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
00503   if (!LayoutMap)
00504     LayoutMap = new StructLayoutMap();
00505 
00506   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
00507   StructLayout *&SL = (*STM)[Ty];
00508   if (SL) return SL;
00509 
00510   // Otherwise, create the struct layout.  Because it is variable length, we
00511   // malloc it, then use placement new.
00512   int NumElts = Ty->getNumElements();
00513   StructLayout *L =
00514     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
00515 
00516   // Set SL before calling StructLayout's ctor.  The ctor could cause other
00517   // entries to be added to TheMap, invalidating our reference.
00518   SL = L;
00519 
00520   new (L) StructLayout(Ty, *this);
00521 
00522   return L;
00523 }
00524 
00525 std::string DataLayout::getStringRepresentation() const {
00526   std::string Result;
00527   raw_string_ostream OS(Result);
00528 
00529   OS << (LittleEndian ? "e" : "E");
00530 
00531   switch (ManglingMode) {
00532   case MM_None:
00533     break;
00534   case MM_ELF:
00535     OS << "-m:e";
00536     break;
00537   case MM_MachO:
00538     OS << "-m:o";
00539     break;
00540   case MM_WINCOFF:
00541     OS << "-m:w";
00542     break;
00543   case MM_Mips:
00544     OS << "-m:m";
00545     break;
00546   }
00547 
00548   for (const PointerAlignElem &PI : Pointers) {
00549     // Skip default.
00550     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
00551         PI.TypeByteWidth == 8)
00552       continue;
00553 
00554     OS << "-p";
00555     if (PI.AddressSpace) {
00556       OS << PI.AddressSpace;
00557     }
00558     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
00559     if (PI.PrefAlign != PI.ABIAlign)
00560       OS << ':' << PI.PrefAlign*8;
00561   }
00562 
00563   for (const LayoutAlignElem &AI : Alignments) {
00564     if (std::find(std::begin(DefaultAlignments), std::end(DefaultAlignments),
00565                   AI) != std::end(DefaultAlignments))
00566       continue;
00567     OS << '-' << (char)AI.AlignType;
00568     if (AI.TypeBitWidth)
00569       OS << AI.TypeBitWidth;
00570     OS << ':' << AI.ABIAlign*8;
00571     if (AI.ABIAlign != AI.PrefAlign)
00572       OS << ':' << AI.PrefAlign*8;
00573   }
00574 
00575   if (!LegalIntWidths.empty()) {
00576     OS << "-n" << (unsigned)LegalIntWidths[0];
00577 
00578     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
00579       OS << ':' << (unsigned)LegalIntWidths[i];
00580   }
00581 
00582   if (StackNaturalAlign)
00583     OS << "-S" << StackNaturalAlign*8;
00584 
00585   return OS.str();
00586 }
00587 
00588 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
00589   PointersTy::const_iterator I = findPointerLowerBound(AS);
00590   if (I == Pointers.end() || I->AddressSpace != AS) {
00591     I = findPointerLowerBound(0);
00592     assert(I->AddressSpace == 0);
00593   }
00594   return I->ABIAlign;
00595 }
00596 
00597 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
00598   PointersTy::const_iterator I = findPointerLowerBound(AS);
00599   if (I == Pointers.end() || I->AddressSpace != AS) {
00600     I = findPointerLowerBound(0);
00601     assert(I->AddressSpace == 0);
00602   }
00603   return I->PrefAlign;
00604 }
00605 
00606 unsigned DataLayout::getPointerSize(unsigned AS) const {
00607   PointersTy::const_iterator I = findPointerLowerBound(AS);
00608   if (I == Pointers.end() || I->AddressSpace != AS) {
00609     I = findPointerLowerBound(0);
00610     assert(I->AddressSpace == 0);
00611   }
00612   return I->TypeByteWidth;
00613 }
00614 
00615 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
00616   assert(Ty->isPtrOrPtrVectorTy() &&
00617          "This should only be called with a pointer or pointer vector type");
00618 
00619   if (Ty->isPointerTy())
00620     return getTypeSizeInBits(Ty);
00621 
00622   return getTypeSizeInBits(Ty->getScalarType());
00623 }
00624 
00625 /*!
00626   \param abi_or_pref Flag that determines which alignment is returned. true
00627   returns the ABI alignment, false returns the preferred alignment.
00628   \param Ty The underlying type for which alignment is determined.
00629 
00630   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
00631   == false) for the requested type \a Ty.
00632  */
00633 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
00634   int AlignType = -1;
00635 
00636   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
00637   switch (Ty->getTypeID()) {
00638   // Early escape for the non-numeric types.
00639   case Type::LabelTyID:
00640     return (abi_or_pref
00641             ? getPointerABIAlignment(0)
00642             : getPointerPrefAlignment(0));
00643   case Type::PointerTyID: {
00644     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
00645     return (abi_or_pref
00646             ? getPointerABIAlignment(AS)
00647             : getPointerPrefAlignment(AS));
00648     }
00649   case Type::ArrayTyID:
00650     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
00651 
00652   case Type::StructTyID: {
00653     // Packed structure types always have an ABI alignment of one.
00654     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
00655       return 1;
00656 
00657     // Get the layout annotation... which is lazily created on demand.
00658     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
00659     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
00660     return std::max(Align, Layout->getAlignment());
00661   }
00662   case Type::IntegerTyID:
00663     AlignType = INTEGER_ALIGN;
00664     break;
00665   case Type::HalfTyID:
00666   case Type::FloatTyID:
00667   case Type::DoubleTyID:
00668   // PPC_FP128TyID and FP128TyID have different data contents, but the
00669   // same size and alignment, so they look the same here.
00670   case Type::PPC_FP128TyID:
00671   case Type::FP128TyID:
00672   case Type::X86_FP80TyID:
00673     AlignType = FLOAT_ALIGN;
00674     break;
00675   case Type::X86_MMXTyID:
00676   case Type::VectorTyID:
00677     AlignType = VECTOR_ALIGN;
00678     break;
00679   default:
00680     llvm_unreachable("Bad type for getAlignment!!!");
00681   }
00682 
00683   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
00684                           abi_or_pref, Ty);
00685 }
00686 
00687 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
00688   return getAlignment(Ty, true);
00689 }
00690 
00691 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
00692 /// an integer type of the specified bitwidth.
00693 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
00694   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
00695 }
00696 
00697 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
00698   return getAlignment(Ty, false);
00699 }
00700 
00701 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
00702   unsigned Align = getPrefTypeAlignment(Ty);
00703   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
00704   return Log2_32(Align);
00705 }
00706 
00707 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
00708                                        unsigned AddressSpace) const {
00709   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
00710 }
00711 
00712 Type *DataLayout::getIntPtrType(Type *Ty) const {
00713   assert(Ty->isPtrOrPtrVectorTy() &&
00714          "Expected a pointer or pointer vector type.");
00715   unsigned NumBits = getPointerTypeSizeInBits(Ty);
00716   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
00717   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
00718     return VectorType::get(IntTy, VecTy->getNumElements());
00719   return IntTy;
00720 }
00721 
00722 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
00723   for (unsigned LegalIntWidth : LegalIntWidths)
00724     if (Width <= LegalIntWidth)
00725       return Type::getIntNTy(C, LegalIntWidth);
00726   return nullptr;
00727 }
00728 
00729 unsigned DataLayout::getLargestLegalIntTypeSize() const {
00730   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
00731   return Max != LegalIntWidths.end() ? *Max : 0;
00732 }
00733 
00734 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
00735                                       ArrayRef<Value *> Indices) const {
00736   Type *Ty = ptrTy;
00737   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
00738   uint64_t Result = 0;
00739 
00740   generic_gep_type_iterator<Value* const*>
00741     TI = gep_type_begin(ptrTy, Indices);
00742   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
00743        ++CurIDX, ++TI) {
00744     if (StructType *STy = dyn_cast<StructType>(*TI)) {
00745       assert(Indices[CurIDX]->getType() ==
00746              Type::getInt32Ty(ptrTy->getContext()) &&
00747              "Illegal struct idx");
00748       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
00749 
00750       // Get structure layout information...
00751       const StructLayout *Layout = getStructLayout(STy);
00752 
00753       // Add in the offset, as calculated by the structure layout info...
00754       Result += Layout->getElementOffset(FieldNo);
00755 
00756       // Update Ty to refer to current element
00757       Ty = STy->getElementType(FieldNo);
00758     } else {
00759       // Update Ty to refer to current element
00760       Ty = cast<SequentialType>(Ty)->getElementType();
00761 
00762       // Get the array index and the size of each array element.
00763       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
00764         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
00765     }
00766   }
00767 
00768   return Result;
00769 }
00770 
00771 /// getPreferredAlignment - Return the preferred alignment of the specified
00772 /// global.  This includes an explicitly requested alignment (if the global
00773 /// has one).
00774 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
00775   Type *ElemType = GV->getType()->getElementType();
00776   unsigned Alignment = getPrefTypeAlignment(ElemType);
00777   unsigned GVAlignment = GV->getAlignment();
00778   if (GVAlignment >= Alignment) {
00779     Alignment = GVAlignment;
00780   } else if (GVAlignment != 0) {
00781     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
00782   }
00783 
00784   if (GV->hasInitializer() && GVAlignment == 0) {
00785     if (Alignment < 16) {
00786       // If the global is not external, see if it is large.  If so, give it a
00787       // larger alignment.
00788       if (getTypeSizeInBits(ElemType) > 128)
00789         Alignment = 16;    // 16-byte alignment.
00790     }
00791   }
00792   return Alignment;
00793 }
00794 
00795 /// getPreferredAlignmentLog - Return the preferred alignment of the
00796 /// specified global, returned in log form.  This includes an explicitly
00797 /// requested alignment (if the global has one).
00798 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
00799   return Log2_32(getPreferredAlignment(GV));
00800 }
00801 
00802 DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
00803   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
00804 }
00805 
00806 DataLayoutPass::~DataLayoutPass() {}
00807 
00808 bool DataLayoutPass::doInitialization(Module &M) {
00809   DL.init(&M);
00810   return false;
00811 }
00812 
00813 bool DataLayoutPass::doFinalization(Module &M) {
00814   DL.reset("");
00815   return false;
00816 }