lib/IR/DataLayout.cpp

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