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