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