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