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 /// getInt - Get an integer ignoring errors.
 156 static int getInt(StringRef R) {
 157   int Result = 0;
 158   R.getAsInteger(10, Result);
 159   return Result;
 160 }
 161
 162 void DataLayout::init() {
 163   initializeDataLayoutPass(*PassRegistry::getPassRegistry());
 164
 165   LayoutMap = 0;
 166   LittleEndian = false;
 167   StackNaturalAlign = 0;
 168
 169   // Default alignments
 170   setAlignment(INTEGER_ALIGN,   1,  1, 1);   // i1
 171   setAlignment(INTEGER_ALIGN,   1,  1, 8);   // i8
 172   setAlignment(INTEGER_ALIGN,   2,  2, 16);  // i16
 173   setAlignment(INTEGER_ALIGN,   4,  4, 32);  // i32
 174   setAlignment(INTEGER_ALIGN,   4,  8, 64);  // i64
 175   setAlignment(FLOAT_ALIGN,     2,  2, 16);  // half
 176   setAlignment(FLOAT_ALIGN,     4,  4, 32);  // float
 177   setAlignment(FLOAT_ALIGN,     8,  8, 64);  // double
 178   setAlignment(FLOAT_ALIGN,    16, 16, 128); // ppcf128, quad, ...
 179   setAlignment(VECTOR_ALIGN,    8,  8, 64);  // v2i32, v1i64, ...
 180   setAlignment(VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
 181   setAlignment(AGGREGATE_ALIGN, 0,  8,  0);  // struct
 182   setPointerAlignment(0, 8, 8, 8);
 183 }
 184
 185 std::string DataLayout::parseSpecifier(StringRef Desc, DataLayout *td) {
 186
 187   if (td)
 188     td->init();
 189
 190   while (!Desc.empty()) {
 191     std::pair<StringRef, StringRef> Split = Desc.split('-');
 192     StringRef Token = Split.first;
 193     Desc = Split.second;
 194
 195     if (Token.empty())
 196       continue;
 197
 198     Split = Token.split(':');
 199     StringRef Specifier = Split.first;
 200     Token = Split.second;
 201
 202     assert(!Specifier.empty() && "Can't be empty here");
 203
 204     switch (Specifier[0]) {
 205     case 'E':
 206       if (td)
 207         td->LittleEndian = false;
 208       break;
 209     case 'e':
 210       if (td)
 211         td->LittleEndian = true;
 212       break;
 213     case 'p': {
 214       int AddrSpace = 0;
 215       if (Specifier.size() > 1) {
 216         AddrSpace = getInt(Specifier.substr(1));
 217         if (AddrSpace < 0 || AddrSpace > (1 << 24))
 218           return "Invalid address space, must be a positive 24bit integer";
 219       }
 220       Split = Token.split(':');
 221       int PointerMemSizeBits = getInt(Split.first);
 222       if (PointerMemSizeBits < 0 || PointerMemSizeBits % 8 != 0)
 223         return "invalid pointer size, must be a positive 8-bit multiple";
 224
 225       // Pointer ABI alignment.
 226       Split = Split.second.split(':');
 227       int PointerABIAlignBits = getInt(Split.first);
 228       if (PointerABIAlignBits < 0 || PointerABIAlignBits % 8 != 0) {
 229         return "invalid pointer ABI alignment, "
 230                "must be a positive 8-bit multiple";
 231       }
 232
 233       // Pointer preferred alignment.
 234       Split = Split.second.split(':');
 235       int PointerPrefAlignBits = getInt(Split.first);
 236       if (PointerPrefAlignBits < 0 || PointerPrefAlignBits % 8 != 0) {
 237         return "invalid pointer preferred alignment, "
 238                "must be a positive 8-bit multiple";
 239       }
 240
 241       if (PointerPrefAlignBits == 0)
 242         PointerPrefAlignBits = PointerABIAlignBits;
 243       if (td)
 244         td->setPointerAlignment(AddrSpace, PointerABIAlignBits/8,
 245             PointerPrefAlignBits/8, PointerMemSizeBits/8);
 246       break;
 247     }
 248     case 'i':
 249     case 'v':
 250     case 'f':
 251     case 'a':
 252     case 's': {
 253       AlignTypeEnum AlignType;
 254       char field = Specifier[0];
 255       switch (field) {
 256       default:
 257       case 'i': AlignType = INTEGER_ALIGN; break;
 258       case 'v': AlignType = VECTOR_ALIGN; break;
 259       case 'f': AlignType = FLOAT_ALIGN; break;
 260       case 'a': AlignType = AGGREGATE_ALIGN; break;
 261       case 's': AlignType = STACK_ALIGN; break;
 262       }
 263       int Size = getInt(Specifier.substr(1));
 264       if (Size < 0) {
 265         return std::string("invalid ") + field + "-size field, "
 266                "must be positive";
 267       }
 268
 269       Split = Token.split(':');
 270       int ABIAlignBits = getInt(Split.first);
 271       if (ABIAlignBits < 0 || ABIAlignBits % 8 != 0) {
 272         return std::string("invalid ") + field +"-abi-alignment field, "
 273                "must be a positive 8-bit multiple";
 274       }
 275       unsigned ABIAlign = ABIAlignBits / 8;
 276
 277       Split = Split.second.split(':');
 278
 279       int PrefAlignBits = getInt(Split.first);
 280       if (PrefAlignBits < 0 || PrefAlignBits % 8 != 0) {
 281         return std::string("invalid ") + field +"-preferred-alignment field, "
 282                "must be a positive 8-bit multiple";
 283       }
 284       unsigned PrefAlign = PrefAlignBits / 8;
 285       if (PrefAlign == 0)
 286         PrefAlign = ABIAlign;
 287
 288       if (td)
 289         td->setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 290       break;
 291     }
 292     case 'n':  // Native integer types.
 293       Specifier = Specifier.substr(1);
 294       do {
 295         int Width = getInt(Specifier);
 296         if (Width <= 0) {
 297           return std::string("invalid native integer size \'") +
 298             Specifier.str() + "\', must be a positive integer.";
 299         }
 300         if (td && Width != 0)
 301           td->LegalIntWidths.push_back(Width);
 302         Split = Token.split(':');
 303         Specifier = Split.first;
 304         Token = Split.second;
 305       } while (!Specifier.empty() || !Token.empty());
 306       break;
 307     case 'S': { // Stack natural alignment.
 308       int StackNaturalAlignBits = getInt(Specifier.substr(1));
 309       if (StackNaturalAlignBits < 0 || StackNaturalAlignBits % 8 != 0) {
 310         return "invalid natural stack alignment (S-field), "
 311                "must be a positive 8-bit multiple";
 312       }
 313       if (td)
 314         td->StackNaturalAlign = StackNaturalAlignBits / 8;
 315       break;
 316     }
 317     default:
 318       break;
 319     }
 320   }
 321
 322   return "";
 323 }
 324
 325 /// Default ctor.
 326 ///
 327 /// @note This has to exist, because this is a pass, but it should never be
 328 /// used.
 329 DataLayout::DataLayout() : ImmutablePass(ID) {
 330   report_fatal_error("Bad DataLayout ctor used.  "
 331                     "Tool did not specify a DataLayout to use?");
 332 }
 333
 334 DataLayout::DataLayout(const Module *M)
 335   : ImmutablePass(ID) {
 336   std::string errMsg = parseSpecifier(M->getDataLayout(), this);
 337   assert(errMsg == "" && "Module M has malformed data layout string.");
 338   (void)errMsg;
 339 }
 340
 341 void
 342 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 343                          unsigned pref_align, uint32_t bit_width) {
 344   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 345   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
 346   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
 347   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 348     if (Alignments[i].AlignType == (unsigned)align_type &&
 349         Alignments[i].TypeBitWidth == bit_width) {
 350       // Update the abi, preferred alignments.
 351       Alignments[i].ABIAlign = abi_align;
 352       Alignments[i].PrefAlign = pref_align;
 353       return;
 354     }
 355   }
 356
 357   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 358                                             pref_align, bit_width));
 359 }
 360
 361 void
 362 DataLayout::setPointerAlignment(uint32_t addr_space, unsigned abi_align,
 363                          unsigned pref_align, uint32_t bit_width) {
 364   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 365   DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(addr_space);
 366   if (val == Pointers.end()) {
 367     Pointers[addr_space] = PointerAlignElem::get(addr_space,
 368           abi_align, pref_align, bit_width);
 369   } else {
 370     val->second.ABIAlign = abi_align;
 371     val->second.PrefAlign = pref_align;
 372     val->second.TypeBitWidth = bit_width;
 373   }
 374 }
 375
 376 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 377 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 378 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 379                                       uint32_t BitWidth, bool ABIInfo,
 380                                       Type *Ty) const {
 381   // Check to see if we have an exact match and remember the best match we see.
 382   int BestMatchIdx = -1;
 383   int LargestInt = -1;
 384   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 385     if (Alignments[i].AlignType == (unsigned)AlignType &&
 386         Alignments[i].TypeBitWidth == BitWidth)
 387       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 388
 389     // The best match so far depends on what we're looking for.
 390      if (AlignType == INTEGER_ALIGN &&
 391          Alignments[i].AlignType == INTEGER_ALIGN) {
 392       // The "best match" for integers is the smallest size that is larger than
 393       // the BitWidth requested.
 394       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 395            Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 396         BestMatchIdx = i;
 397       // However, if there isn't one that's larger, then we must use the
 398       // largest one we have (see below)
 399       if (LargestInt == -1 ||
 400           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 401         LargestInt = i;
 402     }
 403   }
 404
 405   // Okay, we didn't find an exact solution.  Fall back here depending on what
 406   // is being looked for.
 407   if (BestMatchIdx == -1) {
 408     // If we didn't find an integer alignment, fall back on most conservative.
 409     if (AlignType == INTEGER_ALIGN) {
 410       BestMatchIdx = LargestInt;
 411     } else {
 412       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 413
 414       // By default, use natural alignment for vector types. This is consistent
 415       // with what clang and llvm-gcc do.
 416       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 417       Align *= cast<VectorType>(Ty)->getNumElements();
 418       // If the alignment is not a power of 2, round up to the next power of 2.
 419       // This happens for non-power-of-2 length vectors.
 420       if (Align & (Align-1))
 421         Align = NextPowerOf2(Align);
 422       return Align;
 423     }
 424   }
 425
 426   // Since we got a "best match" index, just return it.
 427   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 428                  : Alignments[BestMatchIdx].PrefAlign;
 429 }
 430
 431 namespace {
 432
 433 class StructLayoutMap {
 434   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 435   LayoutInfoTy LayoutInfo;
 436
 437 public:
 438   virtual ~StructLayoutMap() {
 439     // Remove any layouts.
 440     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
 441          I != E; ++I) {
 442       StructLayout *Value = I->second;
 443       Value->~StructLayout();
 444       free(Value);
 445     }
 446   }
 447
 448   StructLayout *&operator[](StructType *STy) {
 449     return LayoutInfo[STy];
 450   }
 451
 452   // for debugging...
 453   virtual void dump() const {}
 454 };
 455
 456 } // end anonymous namespace
 457
 458 DataLayout::~DataLayout() {
 459   delete static_cast<StructLayoutMap*>(LayoutMap);
 460 }
 461
 462 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 463   if (!LayoutMap)
 464     LayoutMap = new StructLayoutMap();
 465
 466   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 467   StructLayout *&SL = (*STM)[Ty];
 468   if (SL) return SL;
 469
 470   // Otherwise, create the struct layout.  Because it is variable length, we
 471   // malloc it, then use placement new.
 472   int NumElts = Ty->getNumElements();
 473   StructLayout *L =
 474     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 475
 476   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 477   // entries to be added to TheMap, invalidating our reference.
 478   SL = L;
 479
 480   new (L) StructLayout(Ty, *this);
 481
 482   return L;
 483 }
 484
 485 std::string DataLayout::getStringRepresentation() const {
 486   std::string Result;
 487   raw_string_ostream OS(Result);
 488
 489   OS << (LittleEndian ? "e" : "E");
 490   SmallVector<unsigned, 8> addrSpaces;
 491   // Lets get all of the known address spaces and sort them
 492   // into increasing order so that we can emit the string
 493   // in a cleaner format.
 494   for (DenseMap<unsigned, PointerAlignElem>::const_iterator
 495       pib = Pointers.begin(), pie = Pointers.end();
 496       pib != pie; ++pib) {
 497     addrSpaces.push_back(pib->first);
 498   }
 499   std::sort(addrSpaces.begin(), addrSpaces.end());
 500   for (SmallVector<unsigned, 8>::iterator asb = addrSpaces.begin(),
 501       ase = addrSpaces.end(); asb != ase; ++asb) {
 502     const PointerAlignElem &PI = Pointers.find(*asb)->second;
 503     OS << "-p";
 504     if (PI.AddressSpace) {
 505       OS << PI.AddressSpace;
 506     }
 507      OS << ":" << PI.TypeBitWidth*8 << ':' << PI.ABIAlign*8
 508         << ':' << PI.PrefAlign*8;
 509   }
 510   OS << "-S" << StackNaturalAlign*8;
 511
 512   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 513     const LayoutAlignElem &AI = Alignments[i];
 514     OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
 515        << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
 516   }
 517
 518   if (!LegalIntWidths.empty()) {
 519     OS << "-n" << (unsigned)LegalIntWidths[0];
 520
 521     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 522       OS << ':' << (unsigned)LegalIntWidths[i];
 523   }
 524   return OS.str();
 525 }
 526
 527
 528 uint64_t DataLayout::getTypeSizeInBits(Type *Ty) const {
 529   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 530   switch (Ty->getTypeID()) {
 531   case Type::LabelTyID:
 532     return getPointerSizeInBits(0);
 533   case Type::PointerTyID: {
 534     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 535     return getPointerSizeInBits(AS);
 536     }
 537   case Type::ArrayTyID: {
 538     ArrayType *ATy = cast<ArrayType>(Ty);
 539     return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
 540   }
 541   case Type::StructTyID:
 542     // Get the layout annotation... which is lazily created on demand.
 543     return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
 544   case Type::IntegerTyID:
 545     return cast<IntegerType>(Ty)->getBitWidth();
 546   case Type::VoidTyID:
 547     return 8;
 548   case Type::HalfTyID:
 549     return 16;
 550   case Type::FloatTyID:
 551     return 32;
 552   case Type::DoubleTyID:
 553   case Type::X86_MMXTyID:
 554     return 64;
 555   case Type::PPC_FP128TyID:
 556   case Type::FP128TyID:
 557     return 128;
 558   // In memory objects this is always aligned to a higher boundary, but
 559   // only 80 bits contain information.
 560   case Type::X86_FP80TyID:
 561     return 80;
 562   case Type::VectorTyID:
 563     return cast<VectorType>(Ty)->getBitWidth();
 564   default:
 565     llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type");
 566   }
 567 }
 568
 569 /*!
 570   \param abi_or_pref Flag that determines which alignment is returned. true
 571   returns the ABI alignment, false returns the preferred alignment.
 572   \param Ty The underlying type for which alignment is determined.
 573
 574   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 575   == false) for the requested type \a Ty.
 576  */
 577 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 578   int AlignType = -1;
 579
 580   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 581   switch (Ty->getTypeID()) {
 582   // Early escape for the non-numeric types.
 583   case Type::LabelTyID:
 584     return (abi_or_pref
 585             ? getPointerABIAlignment(0)
 586             : getPointerPrefAlignment(0));
 587   case Type::PointerTyID: {
 588     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 589     return (abi_or_pref
 590             ? getPointerABIAlignment(AS)
 591             : getPointerPrefAlignment(AS));
 592     }
 593   case Type::ArrayTyID:
 594     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 595
 596   case Type::StructTyID: {
 597     // Packed structure types always have an ABI alignment of one.
 598     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 599       return 1;
 600
 601     // Get the layout annotation... which is lazily created on demand.
 602     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 603     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 604     return std::max(Align, Layout->getAlignment());
 605   }
 606   case Type::IntegerTyID:
 607   case Type::VoidTyID:
 608     AlignType = INTEGER_ALIGN;
 609     break;
 610   case Type::HalfTyID:
 611   case Type::FloatTyID:
 612   case Type::DoubleTyID:
 613   // PPC_FP128TyID and FP128TyID have different data contents, but the
 614   // same size and alignment, so they look the same here.
 615   case Type::PPC_FP128TyID:
 616   case Type::FP128TyID:
 617   case Type::X86_FP80TyID:
 618     AlignType = FLOAT_ALIGN;
 619     break;
 620   case Type::X86_MMXTyID:
 621   case Type::VectorTyID:
 622     AlignType = VECTOR_ALIGN;
 623     break;
 624   default:
 625     llvm_unreachable("Bad type for getAlignment!!!");
 626   }
 627
 628   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 629                           abi_or_pref, Ty);
 630 }
 631
 632 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 633   return getAlignment(Ty, true);
 634 }
 635
 636 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 637 /// an integer type of the specified bitwidth.
 638 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 639   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 640 }
 641
 642
 643 unsigned DataLayout::getCallFrameTypeAlignment(Type *Ty) const {
 644   for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
 645     if (Alignments[i].AlignType == STACK_ALIGN)
 646       return Alignments[i].ABIAlign;
 647
 648   return getABITypeAlignment(Ty);
 649 }
 650
 651 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 652   return getAlignment(Ty, false);
 653 }
 654
 655 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 656   unsigned Align = getPrefTypeAlignment(Ty);
 657   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 658   return Log2_32(Align);
 659 }
 660
 661 /// getIntPtrType - Return an unsigned integer type that is the same size or
 662 /// greater to the host pointer size.
 663 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 664                                        unsigned AddressSpace) const {
 665   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 666 }
 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 }