contrib/llvm/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     VectorType *VTy = cast<VectorType>(Ty);
 564     return VTy->getNumElements()*getTypeSizeInBits(VTy->getElementType());
 565   }
 566   default:
 567     llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type");
 568   }
 569 }
 570
 571 /*!
 572   \param abi_or_pref Flag that determines which alignment is returned. true
 573   returns the ABI alignment, false returns the preferred alignment.
 574   \param Ty The underlying type for which alignment is determined.
 575
 576   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 577   == false) for the requested type \a Ty.
 578  */
 579 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 580   int AlignType = -1;
 581
 582   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 583   switch (Ty->getTypeID()) {
 584   // Early escape for the non-numeric types.
 585   case Type::LabelTyID:
 586     return (abi_or_pref
 587             ? getPointerABIAlignment(0)
 588             : getPointerPrefAlignment(0));
 589   case Type::PointerTyID: {
 590     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 591     return (abi_or_pref
 592             ? getPointerABIAlignment(AS)
 593             : getPointerPrefAlignment(AS));
 594     }
 595   case Type::ArrayTyID:
 596     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 597
 598   case Type::StructTyID: {
 599     // Packed structure types always have an ABI alignment of one.
 600     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 601       return 1;
 602
 603     // Get the layout annotation... which is lazily created on demand.
 604     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 605     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 606     return std::max(Align, Layout->getAlignment());
 607   }
 608   case Type::IntegerTyID:
 609   case Type::VoidTyID:
 610     AlignType = INTEGER_ALIGN;
 611     break;
 612   case Type::HalfTyID:
 613   case Type::FloatTyID:
 614   case Type::DoubleTyID:
 615   // PPC_FP128TyID and FP128TyID have different data contents, but the
 616   // same size and alignment, so they look the same here.
 617   case Type::PPC_FP128TyID:
 618   case Type::FP128TyID:
 619   case Type::X86_FP80TyID:
 620     AlignType = FLOAT_ALIGN;
 621     break;
 622   case Type::X86_MMXTyID:
 623   case Type::VectorTyID:
 624     AlignType = VECTOR_ALIGN;
 625     break;
 626   default:
 627     llvm_unreachable("Bad type for getAlignment!!!");
 628   }
 629
 630   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 631                           abi_or_pref, Ty);
 632 }
 633
 634 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 635   return getAlignment(Ty, true);
 636 }
 637
 638 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 639 /// an integer type of the specified bitwidth.
 640 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 641   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 642 }
 643
 644
 645 unsigned DataLayout::getCallFrameTypeAlignment(Type *Ty) const {
 646   for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
 647     if (Alignments[i].AlignType == STACK_ALIGN)
 648       return Alignments[i].ABIAlign;
 649
 650   return getABITypeAlignment(Ty);
 651 }
 652
 653 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 654   return getAlignment(Ty, false);
 655 }
 656
 657 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 658   unsigned Align = getPrefTypeAlignment(Ty);
 659   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 660   return Log2_32(Align);
 661 }
 662
 663 /// getIntPtrType - Return an integer type with size at least as big as that
 664 /// of a pointer in the given address space.
 665 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 666                                        unsigned AddressSpace) const {
 667   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 668 }
 669
 670 /// getIntPtrType - Return an integer (vector of integer) type with size at
 671 /// least as big as that of a pointer of the given pointer (vector of pointer)
 672 /// type.
 673 Type *DataLayout::getIntPtrType(Type *Ty) const {
 674   assert(Ty->isPtrOrPtrVectorTy() &&
 675          "Expected a pointer or pointer vector type.");
 676   unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
 677   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 678   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 679     return VectorType::get(IntTy, VecTy->getNumElements());
 680   return IntTy;
 681 }
 682
 683 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 684                                       ArrayRef<Value *> Indices) const {
 685   Type *Ty = ptrTy;
 686   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 687   uint64_t Result = 0;
 688
 689   generic_gep_type_iterator<Value* const*>
 690     TI = gep_type_begin(ptrTy, Indices);
 691   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 692        ++CurIDX, ++TI) {
 693     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 694       assert(Indices[CurIDX]->getType() ==
 695              Type::getInt32Ty(ptrTy->getContext()) &&
 696              "Illegal struct idx");
 697       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 698
 699       // Get structure layout information...
 700       const StructLayout *Layout = getStructLayout(STy);
 701
 702       // Add in the offset, as calculated by the structure layout info...
 703       Result += Layout->getElementOffset(FieldNo);
 704
 705       // Update Ty to refer to current element
 706       Ty = STy->getElementType(FieldNo);
 707     } else {
 708       // Update Ty to refer to current element
 709       Ty = cast<SequentialType>(Ty)->getElementType();
 710
 711       // Get the array index and the size of each array element.
 712       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 713         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 714     }
 715   }
 716
 717   return Result;
 718 }
 719
 720 /// getPreferredAlignment - Return the preferred alignment of the specified
 721 /// global.  This includes an explicitly requested alignment (if the global
 722 /// has one).
 723 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 724   Type *ElemType = GV->getType()->getElementType();
 725   unsigned Alignment = getPrefTypeAlignment(ElemType);
 726   unsigned GVAlignment = GV->getAlignment();
 727   if (GVAlignment >= Alignment) {
 728     Alignment = GVAlignment;
 729   } else if (GVAlignment != 0) {
 730     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 731   }
 732
 733   if (GV->hasInitializer() && GVAlignment == 0) {
 734     if (Alignment < 16) {
 735       // If the global is not external, see if it is large.  If so, give it a
 736       // larger alignment.
 737       if (getTypeSizeInBits(ElemType) > 128)
 738         Alignment = 16;    // 16-byte alignment.
 739     }
 740   }
 741   return Alignment;
 742 }
 743
 744 /// getPreferredAlignmentLog - Return the preferred alignment of the
 745 /// specified global, returned in log form.  This includes an explicitly
 746 /// requested alignment (if the global has one).
 747 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 748   return Log2_32(getPreferredAlignment(GV));
 749 }