lib/IR/DataLayout.cpp

   1 //===-- DataLayout.cpp - Data size & alignment routines --------------------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines layout properties related to datatype size/offset/alignment
  11 // information.
  12 //
  13 // This structure should be created once, filled in if the defaults are not
  14 // correct and then passed around by const&.  None of the members functions
  15 // require modification to the object.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/IR/DataLayout.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/STLExtras.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DerivedTypes.h"
  24 #include "llvm/IR/Module.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/GetElementPtrTypeIterator.h"
  27 #include "llvm/Support/ManagedStatic.h"
  28 #include "llvm/Support/MathExtras.h"
  29 #include "llvm/Support/Mutex.h"
  30 #include "llvm/Support/raw_ostream.h"
  31 #include <algorithm>
  32 #include <cstdlib>
  33 using namespace llvm;
  34
  35 // Handle the Pass registration stuff necessary to use DataLayout's.
  36
  37 // Register the default SparcV9 implementation...
  38 INITIALIZE_PASS(DataLayout, "datalayout", "Data Layout", false, true)
  39 char DataLayout::ID = 0;
  40
  41 //===----------------------------------------------------------------------===//
  42 // Support for StructLayout
  43 //===----------------------------------------------------------------------===//
  44
  45 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
  46   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
  47   StructAlignment = 0;
  48   StructSize = 0;
  49   NumElements = ST->getNumElements();
  50
  51   // Loop over each of the elements, placing them in memory.
  52   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  53     Type *Ty = ST->getElementType(i);
  54     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
  55
  56     // Add padding if necessary to align the data element properly.
  57     if ((StructSize & (TyAlign-1)) != 0)
  58       StructSize = DataLayout::RoundUpAlignment(StructSize, TyAlign);
  59
  60     // Keep track of maximum alignment constraint.
  61     StructAlignment = std::max(TyAlign, StructAlignment);
  62
  63     MemberOffsets[i] = StructSize;
  64     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  65   }
  66
  67   // Empty structures have alignment of 1 byte.
  68   if (StructAlignment == 0) StructAlignment = 1;
  69
  70   // Add padding to the end of the struct so that it could be put in an array
  71   // and all array elements would be aligned correctly.
  72   if ((StructSize & (StructAlignment-1)) != 0)
  73     StructSize = DataLayout::RoundUpAlignment(StructSize, StructAlignment);
  74 }
  75
  76
  77 /// getElementContainingOffset - Given a valid offset into the structure,
  78 /// return the structure index that contains it.
  79 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  80   const uint64_t *SI =
  81     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  82   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  83   --SI;
  84   assert(*SI <= Offset && "upper_bound didn't work");
  85   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  86          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  87          "Upper bound didn't work!");
  88
  89   // Multiple fields can have the same offset if any of them are zero sized.
  90   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  91   // at the i32 element, because it is the last element at that offset.  This is
  92   // the right one to return, because anything after it will have a higher
  93   // offset, implying that this element is non-empty.
  94   return SI-&MemberOffsets[0];
  95 }
  96
  97 //===----------------------------------------------------------------------===//
  98 // LayoutAlignElem, LayoutAlign support
  99 //===----------------------------------------------------------------------===//
 100
 101 LayoutAlignElem
 102 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
 103                      unsigned pref_align, uint32_t bit_width) {
 104   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 105   LayoutAlignElem retval;
 106   retval.AlignType = align_type;
 107   retval.ABIAlign = abi_align;
 108   retval.PrefAlign = pref_align;
 109   retval.TypeBitWidth = bit_width;
 110   return retval;
 111 }
 112
 113 bool
 114 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 115   return (AlignType == rhs.AlignType
 116           && ABIAlign == rhs.ABIAlign
 117           && PrefAlign == rhs.PrefAlign
 118           && TypeBitWidth == rhs.TypeBitWidth);
 119 }
 120
 121 const LayoutAlignElem
 122 DataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 };
 123
 124 //===----------------------------------------------------------------------===//
 125 // PointerAlignElem, PointerAlign support
 126 //===----------------------------------------------------------------------===//
 127
 128 PointerAlignElem
 129 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
 130                       unsigned PrefAlign, uint32_t TypeByteWidth) {
 131   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 132   PointerAlignElem retval;
 133   retval.AddressSpace = AddressSpace;
 134   retval.ABIAlign = ABIAlign;
 135   retval.PrefAlign = PrefAlign;
 136   retval.TypeByteWidth = TypeByteWidth;
 137   return retval;
 138 }
 139
 140 bool
 141 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
 142   return (ABIAlign == rhs.ABIAlign
 143           && AddressSpace == rhs.AddressSpace
 144           && PrefAlign == rhs.PrefAlign
 145           && TypeByteWidth == rhs.TypeByteWidth);
 146 }
 147
 148 const PointerAlignElem
 149 DataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U };
 150
 151 //===----------------------------------------------------------------------===//
 152 //                       DataLayout Class Implementation
 153 //===----------------------------------------------------------------------===//
 154
 155 static const LayoutAlignElem DefaultAlignments[] = {
 156   { INTEGER_ALIGN, 1, 1, 1 },    // i1
 157   { INTEGER_ALIGN, 8, 1, 1 },    // i8
 158   { INTEGER_ALIGN, 16, 2, 2 },   // i16
 159   { INTEGER_ALIGN, 32, 4, 4 },   // i32
 160   { INTEGER_ALIGN, 64, 4, 8 },   // i64
 161   { FLOAT_ALIGN, 16, 2, 2 },     // half
 162   { FLOAT_ALIGN, 32, 4, 4 },     // float
 163   { FLOAT_ALIGN, 64, 8, 8 },     // double
 164   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
 165   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
 166   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
 167   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
 168 };
 169
 170 void DataLayout::init(StringRef Desc) {
 171   initializeDataLayoutPass(*PassRegistry::getPassRegistry());
 172
 173   LayoutMap = 0;
 174   LittleEndian = false;
 175   StackNaturalAlign = 0;
 176
 177   // Default alignments
 178   for (int I = 0, N = array_lengthof(DefaultAlignments); I < N; ++I) {
 179     const LayoutAlignElem &E = DefaultAlignments[I];
 180     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
 181                  E.TypeBitWidth);
 182   }
 183   setPointerAlignment(0, 8, 8, 8);
 184
 185   parseSpecifier(Desc);
 186 }
 187
 188 /// Checked version of split, to ensure mandatory subparts.
 189 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
 190   assert(!Str.empty() && "parse error, string can't be empty here");
 191   std::pair<StringRef, StringRef> Split = Str.split(Separator);
 192   assert((!Split.second.empty() || Split.first == Str) &&
 193          "a trailing separator is not allowed");
 194   return Split;
 195 }
 196
 197 /// Get an unsinged integer, including error checks.
 198 static unsigned getInt(StringRef R) {
 199   unsigned Result;
 200   bool error = R.getAsInteger(10, Result); (void)error;
 201   assert(!error && "not a number, or does not fit in an unsigned int");
 202   return Result;
 203 }
 204
 205 /// Convert bits into bytes. Assert if not a byte width multiple.
 206 static unsigned inBytes(unsigned Bits) {
 207   assert(Bits % 8 == 0 && "number of bits must be a byte width multiple");
 208   return Bits / 8;
 209 }
 210
 211 void DataLayout::parseSpecifier(StringRef Desc) {
 212   while (!Desc.empty()) {
 213     // Split at '-'.
 214     std::pair<StringRef, StringRef> Split = split(Desc, '-');
 215     Desc = Split.second;
 216
 217     // Split at ':'.
 218     Split = split(Split.first, ':');
 219
 220     // Aliases used below.
 221     StringRef &Tok  = Split.first;  // Current token.
 222     StringRef &Rest = Split.second; // The rest of the string.
 223
 224     char Specifier = Tok.front();
 225     Tok = Tok.substr(1);
 226
 227     switch (Specifier) {
 228     case 's':
 229       // Ignored for backward compatibility.
 230       // FIXME: remove this on LLVM 4.0.
 231       break;
 232     case 'E':
 233       LittleEndian = false;
 234       break;
 235     case 'e':
 236       LittleEndian = true;
 237       break;
 238     case 'p': {
 239       // Address space.
 240       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
 241       assert(AddrSpace < 1 << 24 &&
 242              "Invalid address space, must be a 24bit integer");
 243
 244       // Size.
 245       Split = split(Rest, ':');
 246       unsigned PointerMemSize = inBytes(getInt(Tok));
 247
 248       // ABI alignment.
 249       Split = split(Rest, ':');
 250       unsigned PointerABIAlign = inBytes(getInt(Tok));
 251
 252       // Preferred alignment.
 253       unsigned PointerPrefAlign = PointerABIAlign;
 254       if (!Rest.empty()) {
 255         Split = split(Rest, ':');
 256         PointerPrefAlign = inBytes(getInt(Tok));
 257       }
 258
 259       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
 260                           PointerMemSize);
 261       break;
 262     }
 263     case 'i':
 264     case 'v':
 265     case 'f':
 266     case 'a': {
 267       AlignTypeEnum AlignType;
 268       switch (Specifier) {
 269       default:
 270       case 'i': AlignType = INTEGER_ALIGN; break;
 271       case 'v': AlignType = VECTOR_ALIGN; break;
 272       case 'f': AlignType = FLOAT_ALIGN; break;
 273       case 'a': AlignType = AGGREGATE_ALIGN; break;
 274       }
 275
 276       // Bit size.
 277       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
 278
 279       // ABI alignment.
 280       Split = split(Rest, ':');
 281       unsigned ABIAlign = inBytes(getInt(Tok));
 282
 283       // Preferred alignment.
 284       unsigned PrefAlign = ABIAlign;
 285       if (!Rest.empty()) {
 286         Split = split(Rest, ':');
 287         PrefAlign = inBytes(getInt(Tok));
 288       }
 289
 290       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 291
 292       break;
 293     }
 294     case 'n':  // Native integer types.
 295       for (;;) {
 296         unsigned Width = getInt(Tok);
 297         assert(Width != 0 && "width must be non-zero");
 298         LegalIntWidths.push_back(Width);
 299         if (Rest.empty())
 300           break;
 301         Split = split(Rest, ':');
 302       }
 303       break;
 304     case 'S': { // Stack natural alignment.
 305       StackNaturalAlign = inBytes(getInt(Tok));
 306       break;
 307     }
 308     default:
 309       llvm_unreachable("Unknown specifier in datalayout string");
 310       break;
 311     }
 312   }
 313 }
 314
 315 /// Default ctor.
 316 ///
 317 /// @note This has to exist, because this is a pass, but it should never be
 318 /// used.
 319 DataLayout::DataLayout() : ImmutablePass(ID) {
 320   report_fatal_error("Bad DataLayout ctor used.  "
 321                      "Tool did not specify a DataLayout to use?");
 322 }
 323
 324 DataLayout::DataLayout(const Module *M)
 325   : ImmutablePass(ID) {
 326   init(M->getDataLayout());
 327 }
 328
 329 void
 330 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 331                          unsigned pref_align, uint32_t bit_width) {
 332   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 333   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
 334   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
 335   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 336     if (Alignments[i].AlignType == (unsigned)align_type &&
 337         Alignments[i].TypeBitWidth == bit_width) {
 338       // Update the abi, preferred alignments.
 339       Alignments[i].ABIAlign = abi_align;
 340       Alignments[i].PrefAlign = pref_align;
 341       return;
 342     }
 343   }
 344
 345   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 346                                             pref_align, bit_width));
 347 }
 348
 349 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 350                                      unsigned PrefAlign,
 351                                      uint32_t TypeByteWidth) {
 352   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 353   DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(AddrSpace);
 354   if (val == Pointers.end()) {
 355     Pointers[AddrSpace] =
 356         PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, TypeByteWidth);
 357   } else {
 358     val->second.ABIAlign = ABIAlign;
 359     val->second.PrefAlign = PrefAlign;
 360     val->second.TypeByteWidth = TypeByteWidth;
 361   }
 362 }
 363
 364 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 365 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 366 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 367                                       uint32_t BitWidth, bool ABIInfo,
 368                                       Type *Ty) const {
 369   // Check to see if we have an exact match and remember the best match we see.
 370   int BestMatchIdx = -1;
 371   int LargestInt = -1;
 372   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 373     if (Alignments[i].AlignType == (unsigned)AlignType &&
 374         Alignments[i].TypeBitWidth == BitWidth)
 375       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 376
 377     // The best match so far depends on what we're looking for.
 378      if (AlignType == INTEGER_ALIGN &&
 379          Alignments[i].AlignType == INTEGER_ALIGN) {
 380       // The "best match" for integers is the smallest size that is larger than
 381       // the BitWidth requested.
 382       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 383           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 384         BestMatchIdx = i;
 385       // However, if there isn't one that's larger, then we must use the
 386       // largest one we have (see below)
 387       if (LargestInt == -1 ||
 388           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 389         LargestInt = i;
 390     }
 391   }
 392
 393   // Okay, we didn't find an exact solution.  Fall back here depending on what
 394   // is being looked for.
 395   if (BestMatchIdx == -1) {
 396     // If we didn't find an integer alignment, fall back on most conservative.
 397     if (AlignType == INTEGER_ALIGN) {
 398       BestMatchIdx = LargestInt;
 399     } else {
 400       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 401
 402       // By default, use natural alignment for vector types. This is consistent
 403       // with what clang and llvm-gcc do.
 404       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 405       Align *= cast<VectorType>(Ty)->getNumElements();
 406       // If the alignment is not a power of 2, round up to the next power of 2.
 407       // This happens for non-power-of-2 length vectors.
 408       if (Align & (Align-1))
 409         Align = NextPowerOf2(Align);
 410       return Align;
 411     }
 412   }
 413
 414   // Since we got a "best match" index, just return it.
 415   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 416                  : Alignments[BestMatchIdx].PrefAlign;
 417 }
 418
 419 namespace {
 420
 421 class StructLayoutMap {
 422   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 423   LayoutInfoTy LayoutInfo;
 424
 425 public:
 426   virtual ~StructLayoutMap() {
 427     // Remove any layouts.
 428     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
 429          I != E; ++I) {
 430       StructLayout *Value = I->second;
 431       Value->~StructLayout();
 432       free(Value);
 433     }
 434   }
 435
 436   StructLayout *&operator[](StructType *STy) {
 437     return LayoutInfo[STy];
 438   }
 439
 440   // for debugging...
 441   virtual void dump() const {}
 442 };
 443
 444 } // end anonymous namespace
 445
 446 DataLayout::~DataLayout() {
 447   delete static_cast<StructLayoutMap*>(LayoutMap);
 448 }
 449
 450 bool DataLayout::doFinalization(Module &M) {
 451   delete static_cast<StructLayoutMap*>(LayoutMap);
 452   LayoutMap = 0;
 453   return false;
 454 }
 455
 456 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 457   if (!LayoutMap)
 458     LayoutMap = new StructLayoutMap();
 459
 460   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 461   StructLayout *&SL = (*STM)[Ty];
 462   if (SL) return SL;
 463
 464   // Otherwise, create the struct layout.  Because it is variable length, we
 465   // malloc it, then use placement new.
 466   int NumElts = Ty->getNumElements();
 467   StructLayout *L =
 468     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 469
 470   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 471   // entries to be added to TheMap, invalidating our reference.
 472   SL = L;
 473
 474   new (L) StructLayout(Ty, *this);
 475
 476   return L;
 477 }
 478
 479 std::string DataLayout::getStringRepresentation() const {
 480   std::string Result;
 481   raw_string_ostream OS(Result);
 482
 483   OS << (LittleEndian ? "e" : "E");
 484   SmallVector<unsigned, 8> addrSpaces;
 485   // Lets get all of the known address spaces and sort them
 486   // into increasing order so that we can emit the string
 487   // in a cleaner format.
 488   for (DenseMap<unsigned, PointerAlignElem>::const_iterator
 489       pib = Pointers.begin(), pie = Pointers.end();
 490       pib != pie; ++pib) {
 491     addrSpaces.push_back(pib->first);
 492   }
 493   std::sort(addrSpaces.begin(), addrSpaces.end());
 494   for (SmallVectorImpl<unsigned>::iterator asb = addrSpaces.begin(),
 495       ase = addrSpaces.end(); asb != ase; ++asb) {
 496     const PointerAlignElem &PI = Pointers.find(*asb)->second;
 497
 498     // Skip default.
 499     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
 500         PI.TypeByteWidth == 8)
 501       continue;
 502
 503     OS << "-p";
 504     if (PI.AddressSpace) {
 505       OS << PI.AddressSpace;
 506     }
 507     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
 508     if (PI.PrefAlign != PI.ABIAlign)
 509       OS << ':' << PI.PrefAlign*8;
 510   }
 511
 512   const LayoutAlignElem *DefaultStart = DefaultAlignments;
 513   const LayoutAlignElem *DefaultEnd =
 514       DefaultStart + array_lengthof(DefaultAlignments);
 515   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 516     const LayoutAlignElem &AI = Alignments[i];
 517     if (std::find(DefaultStart, DefaultEnd, AI) != DefaultEnd)
 518       continue;
 519     OS << '-' << (char)AI.AlignType;
 520     if (AI.TypeBitWidth)
 521       OS << AI.TypeBitWidth;
 522     OS << ':' << AI.ABIAlign*8;
 523     if (AI.ABIAlign != AI.PrefAlign)
 524       OS << ':' << AI.PrefAlign*8;
 525   }
 526
 527   if (!LegalIntWidths.empty()) {
 528     OS << "-n" << (unsigned)LegalIntWidths[0];
 529
 530     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 531       OS << ':' << (unsigned)LegalIntWidths[i];
 532   }
 533
 534   if (StackNaturalAlign)
 535     OS << "-S" << StackNaturalAlign*8;
 536
 537   return OS.str();
 538 }
 539
 540 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 541   assert(Ty->isPtrOrPtrVectorTy() &&
 542          "This should only be called with a pointer or pointer vector type");
 543
 544   if (Ty->isPointerTy())
 545     return getTypeSizeInBits(Ty);
 546
 547   return getTypeSizeInBits(Ty->getScalarType());
 548 }
 549
 550 /*!
 551   \param abi_or_pref Flag that determines which alignment is returned. true
 552   returns the ABI alignment, false returns the preferred alignment.
 553   \param Ty The underlying type for which alignment is determined.
 554
 555   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 556   == false) for the requested type \a Ty.
 557  */
 558 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 559   int AlignType = -1;
 560
 561   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 562   switch (Ty->getTypeID()) {
 563   // Early escape for the non-numeric types.
 564   case Type::LabelTyID:
 565     return (abi_or_pref
 566             ? getPointerABIAlignment(0)
 567             : getPointerPrefAlignment(0));
 568   case Type::PointerTyID: {
 569     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 570     return (abi_or_pref
 571             ? getPointerABIAlignment(AS)
 572             : getPointerPrefAlignment(AS));
 573     }
 574   case Type::ArrayTyID:
 575     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 576
 577   case Type::StructTyID: {
 578     // Packed structure types always have an ABI alignment of one.
 579     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 580       return 1;
 581
 582     // Get the layout annotation... which is lazily created on demand.
 583     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 584     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 585     return std::max(Align, Layout->getAlignment());
 586   }
 587   case Type::IntegerTyID:
 588     AlignType = INTEGER_ALIGN;
 589     break;
 590   case Type::HalfTyID:
 591   case Type::FloatTyID:
 592   case Type::DoubleTyID:
 593   // PPC_FP128TyID and FP128TyID have different data contents, but the
 594   // same size and alignment, so they look the same here.
 595   case Type::PPC_FP128TyID:
 596   case Type::FP128TyID:
 597   case Type::X86_FP80TyID:
 598     AlignType = FLOAT_ALIGN;
 599     break;
 600   case Type::X86_MMXTyID:
 601   case Type::VectorTyID:
 602     AlignType = VECTOR_ALIGN;
 603     break;
 604   default:
 605     llvm_unreachable("Bad type for getAlignment!!!");
 606   }
 607
 608   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 609                           abi_or_pref, Ty);
 610 }
 611
 612 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 613   return getAlignment(Ty, true);
 614 }
 615
 616 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 617 /// an integer type of the specified bitwidth.
 618 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 619   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 620 }
 621
 622 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 623   return getAlignment(Ty, false);
 624 }
 625
 626 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 627   unsigned Align = getPrefTypeAlignment(Ty);
 628   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 629   return Log2_32(Align);
 630 }
 631
 632 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 633                                        unsigned AddressSpace) const {
 634   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 635 }
 636
 637 Type *DataLayout::getIntPtrType(Type *Ty) const {
 638   assert(Ty->isPtrOrPtrVectorTy() &&
 639          "Expected a pointer or pointer vector type.");
 640   unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
 641   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 642   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 643     return VectorType::get(IntTy, VecTy->getNumElements());
 644   return IntTy;
 645 }
 646
 647 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 648   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 649     if (Width <= LegalIntWidths[i])
 650       return Type::getIntNTy(C, LegalIntWidths[i]);
 651   return 0;
 652 }
 653
 654 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 655   unsigned MaxWidth = 0;
 656   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 657     MaxWidth = std::max<unsigned>(MaxWidth, LegalIntWidths[i]);
 658   return MaxWidth;
 659 }
 660
 661 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 662                                       ArrayRef<Value *> Indices) const {
 663   Type *Ty = ptrTy;
 664   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 665   uint64_t Result = 0;
 666
 667   generic_gep_type_iterator<Value* const*>
 668     TI = gep_type_begin(ptrTy, Indices);
 669   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 670        ++CurIDX, ++TI) {
 671     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 672       assert(Indices[CurIDX]->getType() ==
 673              Type::getInt32Ty(ptrTy->getContext()) &&
 674              "Illegal struct idx");
 675       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 676
 677       // Get structure layout information...
 678       const StructLayout *Layout = getStructLayout(STy);
 679
 680       // Add in the offset, as calculated by the structure layout info...
 681       Result += Layout->getElementOffset(FieldNo);
 682
 683       // Update Ty to refer to current element
 684       Ty = STy->getElementType(FieldNo);
 685     } else {
 686       // Update Ty to refer to current element
 687       Ty = cast<SequentialType>(Ty)->getElementType();
 688
 689       // Get the array index and the size of each array element.
 690       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 691         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 692     }
 693   }
 694
 695   return Result;
 696 }
 697
 698 /// getPreferredAlignment - Return the preferred alignment of the specified
 699 /// global.  This includes an explicitly requested alignment (if the global
 700 /// has one).
 701 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 702   Type *ElemType = GV->getType()->getElementType();
 703   unsigned Alignment = getPrefTypeAlignment(ElemType);
 704   unsigned GVAlignment = GV->getAlignment();
 705   if (GVAlignment >= Alignment) {
 706     Alignment = GVAlignment;
 707   } else if (GVAlignment != 0) {
 708     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 709   }
 710
 711   if (GV->hasInitializer() && GVAlignment == 0) {
 712     if (Alignment < 16) {
 713       // If the global is not external, see if it is large.  If so, give it a
 714       // larger alignment.
 715       if (getTypeSizeInBits(ElemType) > 128)
 716         Alignment = 16;    // 16-byte alignment.
 717     }
 718   }
 719   return Alignment;
 720 }
 721
 722 /// getPreferredAlignmentLog - Return the preferred alignment of the
 723 /// specified global, returned in log form.  This includes an explicitly
 724 /// requested alignment (if the global has one).
 725 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 726   return Log2_32(getPreferredAlignment(GV));
 727 }