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