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