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