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