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) {
 348   const DataLayout *Other = M->getDataLayout();
 349   if (Other)
 350     *this = *Other;
 351   else
 352     init("");
 353 }
 354
 355 void
 356 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 357                          unsigned pref_align, uint32_t bit_width) {
 358   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 359   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
 360   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
 361   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 362     if (Alignments[i].AlignType == (unsigned)align_type &&
 363         Alignments[i].TypeBitWidth == bit_width) {
 364       // Update the abi, preferred alignments.
 365       Alignments[i].ABIAlign = abi_align;
 366       Alignments[i].PrefAlign = pref_align;
 367       return;
 368     }
 369   }
 370
 371   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 372                                             pref_align, bit_width));
 373 }
 374
 375 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 376                                      unsigned PrefAlign,
 377                                      uint32_t TypeByteWidth) {
 378   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 379   DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(AddrSpace);
 380   if (val == Pointers.end()) {
 381     Pointers[AddrSpace] =
 382         PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, TypeByteWidth);
 383   } else {
 384     val->second.ABIAlign = ABIAlign;
 385     val->second.PrefAlign = PrefAlign;
 386     val->second.TypeByteWidth = TypeByteWidth;
 387   }
 388 }
 389
 390 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 391 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 392 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 393                                       uint32_t BitWidth, bool ABIInfo,
 394                                       Type *Ty) const {
 395   // Check to see if we have an exact match and remember the best match we see.
 396   int BestMatchIdx = -1;
 397   int LargestInt = -1;
 398   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 399     if (Alignments[i].AlignType == (unsigned)AlignType &&
 400         Alignments[i].TypeBitWidth == BitWidth)
 401       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 402
 403     // The best match so far depends on what we're looking for.
 404      if (AlignType == INTEGER_ALIGN &&
 405          Alignments[i].AlignType == INTEGER_ALIGN) {
 406       // The "best match" for integers is the smallest size that is larger than
 407       // the BitWidth requested.
 408       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 409           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 410         BestMatchIdx = i;
 411       // However, if there isn't one that's larger, then we must use the
 412       // largest one we have (see below)
 413       if (LargestInt == -1 ||
 414           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 415         LargestInt = i;
 416     }
 417   }
 418
 419   // Okay, we didn't find an exact solution.  Fall back here depending on what
 420   // is being looked for.
 421   if (BestMatchIdx == -1) {
 422     // If we didn't find an integer alignment, fall back on most conservative.
 423     if (AlignType == INTEGER_ALIGN) {
 424       BestMatchIdx = LargestInt;
 425     } else {
 426       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 427
 428       // By default, use natural alignment for vector types. This is consistent
 429       // with what clang and llvm-gcc do.
 430       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 431       Align *= cast<VectorType>(Ty)->getNumElements();
 432       // If the alignment is not a power of 2, round up to the next power of 2.
 433       // This happens for non-power-of-2 length vectors.
 434       if (Align & (Align-1))
 435         Align = NextPowerOf2(Align);
 436       return Align;
 437     }
 438   }
 439
 440   // Since we got a "best match" index, just return it.
 441   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 442                  : Alignments[BestMatchIdx].PrefAlign;
 443 }
 444
 445 namespace {
 446
 447 class StructLayoutMap {
 448   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 449   LayoutInfoTy LayoutInfo;
 450
 451 public:
 452   virtual ~StructLayoutMap() {
 453     // Remove any layouts.
 454     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
 455          I != E; ++I) {
 456       StructLayout *Value = I->second;
 457       Value->~StructLayout();
 458       free(Value);
 459     }
 460   }
 461
 462   StructLayout *&operator[](StructType *STy) {
 463     return LayoutInfo[STy];
 464   }
 465
 466   // for debugging...
 467   virtual void dump() const {}
 468 };
 469
 470 } // end anonymous namespace
 471
 472 DataLayout::~DataLayout() {
 473   delete static_cast<StructLayoutMap*>(LayoutMap);
 474 }
 475
 476 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 477   if (!LayoutMap)
 478     LayoutMap = new StructLayoutMap();
 479
 480   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 481   StructLayout *&SL = (*STM)[Ty];
 482   if (SL) return SL;
 483
 484   // Otherwise, create the struct layout.  Because it is variable length, we
 485   // malloc it, then use placement new.
 486   int NumElts = Ty->getNumElements();
 487   StructLayout *L =
 488     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 489
 490   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 491   // entries to be added to TheMap, invalidating our reference.
 492   SL = L;
 493
 494   new (L) StructLayout(Ty, *this);
 495
 496   return L;
 497 }
 498
 499 std::string DataLayout::getStringRepresentation() const {
 500   std::string Result;
 501   raw_string_ostream OS(Result);
 502
 503   OS << (LittleEndian ? "e" : "E");
 504
 505   switch (ManglingMode) {
 506   case MM_None:
 507     break;
 508   case MM_ELF:
 509     OS << "-m:e";
 510     break;
 511   case MM_MachO:
 512     OS << "-m:o";
 513     break;
 514   case MM_WINCOFF:
 515     OS << "-m:w";
 516     break;
 517   case MM_Mips:
 518     OS << "-m:m";
 519     break;
 520   }
 521
 522   SmallVector<unsigned, 8> addrSpaces;
 523   // Lets get all of the known address spaces and sort them
 524   // into increasing order so that we can emit the string
 525   // in a cleaner format.
 526   for (DenseMap<unsigned, PointerAlignElem>::const_iterator
 527       pib = Pointers.begin(), pie = Pointers.end();
 528       pib != pie; ++pib) {
 529     addrSpaces.push_back(pib->first);
 530   }
 531   std::sort(addrSpaces.begin(), addrSpaces.end());
 532   for (SmallVectorImpl<unsigned>::iterator asb = addrSpaces.begin(),
 533       ase = addrSpaces.end(); asb != ase; ++asb) {
 534     const PointerAlignElem &PI = Pointers.find(*asb)->second;
 535
 536     // Skip default.
 537     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
 538         PI.TypeByteWidth == 8)
 539       continue;
 540
 541     OS << "-p";
 542     if (PI.AddressSpace) {
 543       OS << PI.AddressSpace;
 544     }
 545     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
 546     if (PI.PrefAlign != PI.ABIAlign)
 547       OS << ':' << PI.PrefAlign*8;
 548   }
 549
 550   const LayoutAlignElem *DefaultStart = DefaultAlignments;
 551   const LayoutAlignElem *DefaultEnd =
 552       DefaultStart + array_lengthof(DefaultAlignments);
 553   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 554     const LayoutAlignElem &AI = Alignments[i];
 555     if (std::find(DefaultStart, DefaultEnd, AI) != DefaultEnd)
 556       continue;
 557     OS << '-' << (char)AI.AlignType;
 558     if (AI.TypeBitWidth)
 559       OS << AI.TypeBitWidth;
 560     OS << ':' << AI.ABIAlign*8;
 561     if (AI.ABIAlign != AI.PrefAlign)
 562       OS << ':' << AI.PrefAlign*8;
 563   }
 564
 565   if (!LegalIntWidths.empty()) {
 566     OS << "-n" << (unsigned)LegalIntWidths[0];
 567
 568     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 569       OS << ':' << (unsigned)LegalIntWidths[i];
 570   }
 571
 572   if (StackNaturalAlign)
 573     OS << "-S" << StackNaturalAlign*8;
 574
 575   return OS.str();
 576 }
 577
 578 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 579   assert(Ty->isPtrOrPtrVectorTy() &&
 580          "This should only be called with a pointer or pointer vector type");
 581
 582   if (Ty->isPointerTy())
 583     return getTypeSizeInBits(Ty);
 584
 585   return getTypeSizeInBits(Ty->getScalarType());
 586 }
 587
 588 /*!
 589   \param abi_or_pref Flag that determines which alignment is returned. true
 590   returns the ABI alignment, false returns the preferred alignment.
 591   \param Ty The underlying type for which alignment is determined.
 592
 593   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 594   == false) for the requested type \a Ty.
 595  */
 596 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 597   int AlignType = -1;
 598
 599   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 600   switch (Ty->getTypeID()) {
 601   // Early escape for the non-numeric types.
 602   case Type::LabelTyID:
 603     return (abi_or_pref
 604             ? getPointerABIAlignment(0)
 605             : getPointerPrefAlignment(0));
 606   case Type::PointerTyID: {
 607     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 608     return (abi_or_pref
 609             ? getPointerABIAlignment(AS)
 610             : getPointerPrefAlignment(AS));
 611     }
 612   case Type::ArrayTyID:
 613     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 614
 615   case Type::StructTyID: {
 616     // Packed structure types always have an ABI alignment of one.
 617     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 618       return 1;
 619
 620     // Get the layout annotation... which is lazily created on demand.
 621     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 622     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 623     return std::max(Align, Layout->getAlignment());
 624   }
 625   case Type::IntegerTyID:
 626     AlignType = INTEGER_ALIGN;
 627     break;
 628   case Type::HalfTyID:
 629   case Type::FloatTyID:
 630   case Type::DoubleTyID:
 631   // PPC_FP128TyID and FP128TyID have different data contents, but the
 632   // same size and alignment, so they look the same here.
 633   case Type::PPC_FP128TyID:
 634   case Type::FP128TyID:
 635   case Type::X86_FP80TyID:
 636     AlignType = FLOAT_ALIGN;
 637     break;
 638   case Type::X86_MMXTyID:
 639   case Type::VectorTyID:
 640     AlignType = VECTOR_ALIGN;
 641     break;
 642   default:
 643     llvm_unreachable("Bad type for getAlignment!!!");
 644   }
 645
 646   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 647                           abi_or_pref, Ty);
 648 }
 649
 650 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 651   return getAlignment(Ty, true);
 652 }
 653
 654 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 655 /// an integer type of the specified bitwidth.
 656 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 657   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 658 }
 659
 660 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 661   return getAlignment(Ty, false);
 662 }
 663
 664 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 665   unsigned Align = getPrefTypeAlignment(Ty);
 666   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 667   return Log2_32(Align);
 668 }
 669
 670 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 671                                        unsigned AddressSpace) const {
 672   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 673 }
 674
 675 Type *DataLayout::getIntPtrType(Type *Ty) const {
 676   assert(Ty->isPtrOrPtrVectorTy() &&
 677          "Expected a pointer or pointer vector type.");
 678   unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
 679   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 680   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 681     return VectorType::get(IntTy, VecTy->getNumElements());
 682   return IntTy;
 683 }
 684
 685 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 686   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 687     if (Width <= LegalIntWidths[i])
 688       return Type::getIntNTy(C, LegalIntWidths[i]);
 689   return 0;
 690 }
 691
 692 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 693   unsigned MaxWidth = 0;
 694   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 695     MaxWidth = std::max<unsigned>(MaxWidth, LegalIntWidths[i]);
 696   return MaxWidth;
 697 }
 698
 699 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 700                                       ArrayRef<Value *> Indices) const {
 701   Type *Ty = ptrTy;
 702   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 703   uint64_t Result = 0;
 704
 705   generic_gep_type_iterator<Value* const*>
 706     TI = gep_type_begin(ptrTy, Indices);
 707   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 708        ++CurIDX, ++TI) {
 709     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 710       assert(Indices[CurIDX]->getType() ==
 711              Type::getInt32Ty(ptrTy->getContext()) &&
 712              "Illegal struct idx");
 713       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 714
 715       // Get structure layout information...
 716       const StructLayout *Layout = getStructLayout(STy);
 717
 718       // Add in the offset, as calculated by the structure layout info...
 719       Result += Layout->getElementOffset(FieldNo);
 720
 721       // Update Ty to refer to current element
 722       Ty = STy->getElementType(FieldNo);
 723     } else {
 724       // Update Ty to refer to current element
 725       Ty = cast<SequentialType>(Ty)->getElementType();
 726
 727       // Get the array index and the size of each array element.
 728       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 729         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 730     }
 731   }
 732
 733   return Result;
 734 }
 735
 736 /// getPreferredAlignment - Return the preferred alignment of the specified
 737 /// global.  This includes an explicitly requested alignment (if the global
 738 /// has one).
 739 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 740   Type *ElemType = GV->getType()->getElementType();
 741   unsigned Alignment = getPrefTypeAlignment(ElemType);
 742   unsigned GVAlignment = GV->getAlignment();
 743   if (GVAlignment >= Alignment) {
 744     Alignment = GVAlignment;
 745   } else if (GVAlignment != 0) {
 746     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 747   }
 748
 749   if (GV->hasInitializer() && GVAlignment == 0) {
 750     if (Alignment < 16) {
 751       // If the global is not external, see if it is large.  If so, give it a
 752       // larger alignment.
 753       if (getTypeSizeInBits(ElemType) > 128)
 754         Alignment = 16;    // 16-byte alignment.
 755     }
 756   }
 757   return Alignment;
 758 }
 759
 760 /// getPreferredAlignmentLog - Return the preferred alignment of the
 761 /// specified global, returned in log form.  This includes an explicitly
 762 /// requested alignment (if the global has one).
 763 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 764   return Log2_32(getPreferredAlignment(GV));
 765 }
 766
 767 DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
 768   report_fatal_error("Bad DataLayoutPass ctor used. Tool did not specify a "
 769                      "DataLayout to use?");
 770 }
 771
 772 DataLayoutPass::~DataLayoutPass() {}
 773
 774 DataLayoutPass::DataLayoutPass(const DataLayout &DL)
 775     : ImmutablePass(ID), DL(DL) {
 776   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 777 }
 778
 779 DataLayoutPass::DataLayoutPass(StringRef Str) : ImmutablePass(ID), DL(Str) {
 780   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 781 }
 782
 783 DataLayoutPass::DataLayoutPass(const Module *M) : ImmutablePass(ID), DL(M) {
 784   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 785 }