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