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(StringRef Desc) {
 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   std::string errMsg = parseSpecifier(Desc);
 185   assert(errMsg == "" && "Invalid target data layout string.");
 186   (void)errMsg;
 187 }
 188
 189 std::string DataLayout::parseSpecifier(StringRef Desc) {
 190
 191   while (!Desc.empty()) {
 192     std::pair<StringRef, StringRef> Split = Desc.split('-');
 193     StringRef Token = Split.first;
 194     Desc = Split.second;
 195
 196     if (Token.empty())
 197       continue;
 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       int AddrSpace = 0;
 214       if (Specifier.size() > 1) {
 215         AddrSpace = getInt(Specifier.substr(1));
 216         if (AddrSpace < 0 || AddrSpace > (1 << 24))
 217           return "Invalid address space, must be a positive 24bit integer";
 218       }
 219       Split = Token.split(':');
 220       int PointerMemSizeBits = getInt(Split.first);
 221       if (PointerMemSizeBits < 0 || PointerMemSizeBits % 8 != 0)
 222         return "invalid pointer size, must be a positive 8-bit multiple";
 223
 224       // Pointer ABI alignment.
 225       Split = Split.second.split(':');
 226       int PointerABIAlignBits = getInt(Split.first);
 227       if (PointerABIAlignBits < 0 || PointerABIAlignBits % 8 != 0) {
 228         return "invalid pointer ABI alignment, "
 229                "must be a positive 8-bit multiple";
 230       }
 231
 232       // Pointer preferred alignment.
 233       Split = Split.second.split(':');
 234       int PointerPrefAlignBits = getInt(Split.first);
 235       if (PointerPrefAlignBits < 0 || PointerPrefAlignBits % 8 != 0) {
 236         return "invalid pointer preferred alignment, "
 237                "must be a positive 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       int Size = getInt(Specifier.substr(1));
 262       if (Size < 0) {
 263         return std::string("invalid ") + field + "-size field, "
 264                "must be positive";
 265       }
 266
 267       Split = Token.split(':');
 268       int ABIAlignBits = getInt(Split.first);
 269       if (ABIAlignBits < 0 || ABIAlignBits % 8 != 0) {
 270         return std::string("invalid ") + field +"-abi-alignment field, "
 271                "must be a positive 8-bit multiple";
 272       }
 273       unsigned ABIAlign = ABIAlignBits / 8;
 274
 275       Split = Split.second.split(':');
 276
 277       int PrefAlignBits = getInt(Split.first);
 278       if (PrefAlignBits < 0 || PrefAlignBits % 8 != 0) {
 279         return std::string("invalid ") + field +"-preferred-alignment field, "
 280                "must be a positive 8-bit multiple";
 281       }
 282       unsigned PrefAlign = PrefAlignBits / 8;
 283       if (PrefAlign == 0)
 284         PrefAlign = ABIAlign;
 285       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 286
 287       break;
 288     }
 289     case 'n':  // Native integer types.
 290       Specifier = Specifier.substr(1);
 291       do {
 292         int Width = getInt(Specifier);
 293         if (Width <= 0) {
 294           return std::string("invalid native integer size \'") +
 295             Specifier.str() + "\', must be a positive integer.";
 296         }
 297         if (Width != 0)
 298           LegalIntWidths.push_back(Width);
 299         Split = Token.split(':');
 300         Specifier = Split.first;
 301         Token = Split.second;
 302       } while (!Specifier.empty() || !Token.empty());
 303       break;
 304     case 'S': { // Stack natural alignment.
 305       int StackNaturalAlignBits = getInt(Specifier.substr(1));
 306       if (StackNaturalAlignBits < 0 || StackNaturalAlignBits % 8 != 0) {
 307         return "invalid natural stack alignment (S-field), "
 308                "must be a positive 8-bit multiple";
 309       }
 310       StackNaturalAlign = StackNaturalAlignBits / 8;
 311       break;
 312     }
 313     default:
 314       break;
 315     }
 316   }
 317
 318   return "";
 319 }
 320
 321 /// Default ctor.
 322 ///
 323 /// @note This has to exist, because this is a pass, but it should never be
 324 /// used.
 325 DataLayout::DataLayout() : ImmutablePass(ID) {
 326   report_fatal_error("Bad DataLayout ctor used.  "
 327                     "Tool did not specify a DataLayout to use?");
 328 }
 329
 330 DataLayout::DataLayout(const Module *M)
 331   : ImmutablePass(ID) {
 332   init(M->getDataLayout());
 333 }
 334
 335 void
 336 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 337                          unsigned pref_align, uint32_t bit_width) {
 338   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 339   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
 340   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
 341   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 342     if (Alignments[i].AlignType == (unsigned)align_type &&
 343         Alignments[i].TypeBitWidth == bit_width) {
 344       // Update the abi, preferred alignments.
 345       Alignments[i].ABIAlign = abi_align;
 346       Alignments[i].PrefAlign = pref_align;
 347       return;
 348     }
 349   }
 350
 351   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 352                                             pref_align, bit_width));
 353 }
 354
 355 void
 356 DataLayout::setPointerAlignment(uint32_t addr_space, unsigned abi_align,
 357                          unsigned pref_align, uint32_t bit_width) {
 358   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 359   DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(addr_space);
 360   if (val == Pointers.end()) {
 361     Pointers[addr_space] = PointerAlignElem::get(addr_space,
 362           abi_align, pref_align, bit_width);
 363   } else {
 364     val->second.ABIAlign = abi_align;
 365     val->second.PrefAlign = pref_align;
 366     val->second.TypeBitWidth = bit_width;
 367   }
 368 }
 369
 370 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 371 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 372 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 373                                       uint32_t BitWidth, bool ABIInfo,
 374                                       Type *Ty) const {
 375   // Check to see if we have an exact match and remember the best match we see.
 376   int BestMatchIdx = -1;
 377   int LargestInt = -1;
 378   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 379     if (Alignments[i].AlignType == (unsigned)AlignType &&
 380         Alignments[i].TypeBitWidth == BitWidth)
 381       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 382
 383     // The best match so far depends on what we're looking for.
 384      if (AlignType == INTEGER_ALIGN &&
 385          Alignments[i].AlignType == INTEGER_ALIGN) {
 386       // The "best match" for integers is the smallest size that is larger than
 387       // the BitWidth requested.
 388       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 389            Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 390         BestMatchIdx = i;
 391       // However, if there isn't one that's larger, then we must use the
 392       // largest one we have (see below)
 393       if (LargestInt == -1 ||
 394           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 395         LargestInt = i;
 396     }
 397   }
 398
 399   // Okay, we didn't find an exact solution.  Fall back here depending on what
 400   // is being looked for.
 401   if (BestMatchIdx == -1) {
 402     // If we didn't find an integer alignment, fall back on most conservative.
 403     if (AlignType == INTEGER_ALIGN) {
 404       BestMatchIdx = LargestInt;
 405     } else {
 406       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 407
 408       // By default, use natural alignment for vector types. This is consistent
 409       // with what clang and llvm-gcc do.
 410       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 411       Align *= cast<VectorType>(Ty)->getNumElements();
 412       // If the alignment is not a power of 2, round up to the next power of 2.
 413       // This happens for non-power-of-2 length vectors.
 414       if (Align & (Align-1))
 415         Align = NextPowerOf2(Align);
 416       return Align;
 417     }
 418   }
 419
 420   // Since we got a "best match" index, just return it.
 421   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 422                  : Alignments[BestMatchIdx].PrefAlign;
 423 }
 424
 425 namespace {
 426
 427 class StructLayoutMap {
 428   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 429   LayoutInfoTy LayoutInfo;
 430
 431 public:
 432   virtual ~StructLayoutMap() {
 433     // Remove any layouts.
 434     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
 435          I != E; ++I) {
 436       StructLayout *Value = I->second;
 437       Value->~StructLayout();
 438       free(Value);
 439     }
 440   }
 441
 442   StructLayout *&operator[](StructType *STy) {
 443     return LayoutInfo[STy];
 444   }
 445
 446   // for debugging...
 447   virtual void dump() const {}
 448 };
 449
 450 } // end anonymous namespace
 451
 452 DataLayout::~DataLayout() {
 453   delete static_cast<StructLayoutMap*>(LayoutMap);
 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 (SmallVector<unsigned, 8>::iterator asb = addrSpaces.begin(),
 495       ase = addrSpaces.end(); asb != ase; ++asb) {
 496     const PointerAlignElem &PI = Pointers.find(*asb)->second;
 497     OS << "-p";
 498     if (PI.AddressSpace) {
 499       OS << PI.AddressSpace;
 500     }
 501      OS << ":" << PI.TypeBitWidth*8 << ':' << PI.ABIAlign*8
 502         << ':' << PI.PrefAlign*8;
 503   }
 504   OS << "-S" << StackNaturalAlign*8;
 505
 506   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 507     const LayoutAlignElem &AI = Alignments[i];
 508     OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
 509        << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
 510   }
 511
 512   if (!LegalIntWidths.empty()) {
 513     OS << "-n" << (unsigned)LegalIntWidths[0];
 514
 515     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 516       OS << ':' << (unsigned)LegalIntWidths[i];
 517   }
 518   return OS.str();
 519 }
 520
 521
 522 uint64_t DataLayout::getTypeSizeInBits(Type *Ty) const {
 523   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 524   switch (Ty->getTypeID()) {
 525   case Type::LabelTyID:
 526     return getPointerSizeInBits(0);
 527   case Type::PointerTyID: {
 528     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 529     return getPointerSizeInBits(AS);
 530     }
 531   case Type::ArrayTyID: {
 532     ArrayType *ATy = cast<ArrayType>(Ty);
 533     return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
 534   }
 535   case Type::StructTyID:
 536     // Get the layout annotation... which is lazily created on demand.
 537     return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
 538   case Type::IntegerTyID:
 539     return cast<IntegerType>(Ty)->getBitWidth();
 540   case Type::VoidTyID:
 541     return 8;
 542   case Type::HalfTyID:
 543     return 16;
 544   case Type::FloatTyID:
 545     return 32;
 546   case Type::DoubleTyID:
 547   case Type::X86_MMXTyID:
 548     return 64;
 549   case Type::PPC_FP128TyID:
 550   case Type::FP128TyID:
 551     return 128;
 552   // In memory objects this is always aligned to a higher boundary, but
 553   // only 80 bits contain information.
 554   case Type::X86_FP80TyID:
 555     return 80;
 556   case Type::VectorTyID: {
 557     VectorType *VTy = cast<VectorType>(Ty);
 558     return VTy->getNumElements()*getTypeSizeInBits(VTy->getElementType());
 559   }
 560   default:
 561     llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type");
 562   }
 563 }
 564
 565 /*!
 566   \param abi_or_pref Flag that determines which alignment is returned. true
 567   returns the ABI alignment, false returns the preferred alignment.
 568   \param Ty The underlying type for which alignment is determined.
 569
 570   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 571   == false) for the requested type \a Ty.
 572  */
 573 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 574   int AlignType = -1;
 575
 576   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 577   switch (Ty->getTypeID()) {
 578   // Early escape for the non-numeric types.
 579   case Type::LabelTyID:
 580     return (abi_or_pref
 581             ? getPointerABIAlignment(0)
 582             : getPointerPrefAlignment(0));
 583   case Type::PointerTyID: {
 584     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 585     return (abi_or_pref
 586             ? getPointerABIAlignment(AS)
 587             : getPointerPrefAlignment(AS));
 588     }
 589   case Type::ArrayTyID:
 590     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 591
 592   case Type::StructTyID: {
 593     // Packed structure types always have an ABI alignment of one.
 594     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 595       return 1;
 596
 597     // Get the layout annotation... which is lazily created on demand.
 598     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 599     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 600     return std::max(Align, Layout->getAlignment());
 601   }
 602   case Type::IntegerTyID:
 603   case Type::VoidTyID:
 604     AlignType = INTEGER_ALIGN;
 605     break;
 606   case Type::HalfTyID:
 607   case Type::FloatTyID:
 608   case Type::DoubleTyID:
 609   // PPC_FP128TyID and FP128TyID have different data contents, but the
 610   // same size and alignment, so they look the same here.
 611   case Type::PPC_FP128TyID:
 612   case Type::FP128TyID:
 613   case Type::X86_FP80TyID:
 614     AlignType = FLOAT_ALIGN;
 615     break;
 616   case Type::X86_MMXTyID:
 617   case Type::VectorTyID:
 618     AlignType = VECTOR_ALIGN;
 619     break;
 620   default:
 621     llvm_unreachable("Bad type for getAlignment!!!");
 622   }
 623
 624   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 625                           abi_or_pref, Ty);
 626 }
 627
 628 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 629   return getAlignment(Ty, true);
 630 }
 631
 632 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 633 /// an integer type of the specified bitwidth.
 634 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 635   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 636 }
 637
 638
 639 unsigned DataLayout::getCallFrameTypeAlignment(Type *Ty) const {
 640   for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
 641     if (Alignments[i].AlignType == STACK_ALIGN)
 642       return Alignments[i].ABIAlign;
 643
 644   return getABITypeAlignment(Ty);
 645 }
 646
 647 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 648   return getAlignment(Ty, false);
 649 }
 650
 651 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 652   unsigned Align = getPrefTypeAlignment(Ty);
 653   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 654   return Log2_32(Align);
 655 }
 656
 657 /// getIntPtrType - Return an integer type with size at least as big as that
 658 /// of a pointer in the given address space.
 659 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 660                                        unsigned AddressSpace) const {
 661   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 662 }
 663
 664 /// getIntPtrType - Return an integer (vector of integer) type with size at
 665 /// least as big as that of a pointer of the given pointer (vector of pointer)
 666 /// type.
 667 Type *DataLayout::getIntPtrType(Type *Ty) const {
 668   assert(Ty->isPtrOrPtrVectorTy() &&
 669          "Expected a pointer or pointer vector type.");
 670   unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
 671   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 672   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 673     return VectorType::get(IntTy, VecTy->getNumElements());
 674   return IntTy;
 675 }
 676
 677 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 678                                       ArrayRef<Value *> Indices) const {
 679   Type *Ty = ptrTy;
 680   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 681   uint64_t Result = 0;
 682
 683   generic_gep_type_iterator<Value* const*>
 684     TI = gep_type_begin(ptrTy, Indices);
 685   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 686        ++CurIDX, ++TI) {
 687     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 688       assert(Indices[CurIDX]->getType() ==
 689              Type::getInt32Ty(ptrTy->getContext()) &&
 690              "Illegal struct idx");
 691       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 692
 693       // Get structure layout information...
 694       const StructLayout *Layout = getStructLayout(STy);
 695
 696       // Add in the offset, as calculated by the structure layout info...
 697       Result += Layout->getElementOffset(FieldNo);
 698
 699       // Update Ty to refer to current element
 700       Ty = STy->getElementType(FieldNo);
 701     } else {
 702       // Update Ty to refer to current element
 703       Ty = cast<SequentialType>(Ty)->getElementType();
 704
 705       // Get the array index and the size of each array element.
 706       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 707         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 708     }
 709   }
 710
 711   return Result;
 712 }
 713
 714 /// getPreferredAlignment - Return the preferred alignment of the specified
 715 /// global.  This includes an explicitly requested alignment (if the global
 716 /// has one).
 717 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 718   Type *ElemType = GV->getType()->getElementType();
 719   unsigned Alignment = getPrefTypeAlignment(ElemType);
 720   unsigned GVAlignment = GV->getAlignment();
 721   if (GVAlignment >= Alignment) {
 722     Alignment = GVAlignment;
 723   } else if (GVAlignment != 0) {
 724     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 725   }
 726
 727   if (GV->hasInitializer() && GVAlignment == 0) {
 728     if (Alignment < 16) {
 729       // If the global is not external, see if it is large.  If so, give it a
 730       // larger alignment.
 731       if (getTypeSizeInBits(ElemType) > 128)
 732         Alignment = 16;    // 16-byte alignment.
 733     }
 734   }
 735   return Alignment;
 736 }
 737
 738 /// getPreferredAlignmentLog - Return the preferred alignment of the
 739 /// specified global, returned in log form.  This includes an explicitly
 740 /// requested alignment (if the global has one).
 741 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 742   return Log2_32(getPreferredAlignment(GV));
 743 }