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