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   string_ostream OS;
 523
 524   OS << (LittleEndian ? "e" : "E");
 525
 526   switch (ManglingMode) {
 527   case MM_None:
 528     break;
 529   case MM_ELF:
 530     OS << "-m:e";
 531     break;
 532   case MM_MachO:
 533     OS << "-m:o";
 534     break;
 535   case MM_WINCOFF:
 536     OS << "-m:w";
 537     break;
 538   case MM_Mips:
 539     OS << "-m:m";
 540     break;
 541   }
 542
 543   for (const PointerAlignElem &PI : Pointers) {
 544     // Skip default.
 545     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
 546         PI.TypeByteWidth == 8)
 547       continue;
 548
 549     OS << "-p";
 550     if (PI.AddressSpace) {
 551       OS << PI.AddressSpace;
 552     }
 553     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
 554     if (PI.PrefAlign != PI.ABIAlign)
 555       OS << ':' << PI.PrefAlign*8;
 556   }
 557
 558   for (const LayoutAlignElem &AI : Alignments) {
 559     if (std::find(std::begin(DefaultAlignments), std::end(DefaultAlignments),
 560                   AI) != std::end(DefaultAlignments))
 561       continue;
 562     OS << '-' << (char)AI.AlignType;
 563     if (AI.TypeBitWidth)
 564       OS << AI.TypeBitWidth;
 565     OS << ':' << AI.ABIAlign*8;
 566     if (AI.ABIAlign != AI.PrefAlign)
 567       OS << ':' << AI.PrefAlign*8;
 568   }
 569
 570   if (!LegalIntWidths.empty()) {
 571     OS << "-n" << (unsigned)LegalIntWidths[0];
 572
 573     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 574       OS << ':' << (unsigned)LegalIntWidths[i];
 575   }
 576
 577   if (StackNaturalAlign)
 578     OS << "-S" << StackNaturalAlign*8;
 579
 580   return OS.str();
 581 }
 582
 583 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 584   PointersTy::const_iterator I = findPointerLowerBound(AS);
 585   if (I == Pointers.end() || I->AddressSpace != AS) {
 586     I = findPointerLowerBound(0);
 587     assert(I->AddressSpace == 0);
 588   }
 589   return I->ABIAlign;
 590 }
 591
 592 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 593   PointersTy::const_iterator I = findPointerLowerBound(AS);
 594   if (I == Pointers.end() || I->AddressSpace != AS) {
 595     I = findPointerLowerBound(0);
 596     assert(I->AddressSpace == 0);
 597   }
 598   return I->PrefAlign;
 599 }
 600
 601 unsigned DataLayout::getPointerSize(unsigned AS) const {
 602   PointersTy::const_iterator I = findPointerLowerBound(AS);
 603   if (I == Pointers.end() || I->AddressSpace != AS) {
 604     I = findPointerLowerBound(0);
 605     assert(I->AddressSpace == 0);
 606   }
 607   return I->TypeByteWidth;
 608 }
 609
 610 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 611   assert(Ty->isPtrOrPtrVectorTy() &&
 612          "This should only be called with a pointer or pointer vector type");
 613
 614   if (Ty->isPointerTy())
 615     return getTypeSizeInBits(Ty);
 616
 617   return getTypeSizeInBits(Ty->getScalarType());
 618 }
 619
 620 /*!
 621   \param abi_or_pref Flag that determines which alignment is returned. true
 622   returns the ABI alignment, false returns the preferred alignment.
 623   \param Ty The underlying type for which alignment is determined.
 624
 625   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 626   == false) for the requested type \a Ty.
 627  */
 628 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 629   int AlignType = -1;
 630
 631   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 632   switch (Ty->getTypeID()) {
 633   // Early escape for the non-numeric types.
 634   case Type::LabelTyID:
 635     return (abi_or_pref
 636             ? getPointerABIAlignment(0)
 637             : getPointerPrefAlignment(0));
 638   case Type::PointerTyID: {
 639     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 640     return (abi_or_pref
 641             ? getPointerABIAlignment(AS)
 642             : getPointerPrefAlignment(AS));
 643     }
 644   case Type::ArrayTyID:
 645     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 646
 647   case Type::StructTyID: {
 648     // Packed structure types always have an ABI alignment of one.
 649     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 650       return 1;
 651
 652     // Get the layout annotation... which is lazily created on demand.
 653     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 654     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 655     return std::max(Align, Layout->getAlignment());
 656   }
 657   case Type::IntegerTyID:
 658     AlignType = INTEGER_ALIGN;
 659     break;
 660   case Type::HalfTyID:
 661   case Type::FloatTyID:
 662   case Type::DoubleTyID:
 663   // PPC_FP128TyID and FP128TyID have different data contents, but the
 664   // same size and alignment, so they look the same here.
 665   case Type::PPC_FP128TyID:
 666   case Type::FP128TyID:
 667   case Type::X86_FP80TyID:
 668     AlignType = FLOAT_ALIGN;
 669     break;
 670   case Type::X86_MMXTyID:
 671   case Type::VectorTyID:
 672     AlignType = VECTOR_ALIGN;
 673     break;
 674   default:
 675     llvm_unreachable("Bad type for getAlignment!!!");
 676   }
 677
 678   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 679                           abi_or_pref, Ty);
 680 }
 681
 682 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 683   return getAlignment(Ty, true);
 684 }
 685
 686 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 687 /// an integer type of the specified bitwidth.
 688 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 689   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 690 }
 691
 692 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 693   return getAlignment(Ty, false);
 694 }
 695
 696 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 697   unsigned Align = getPrefTypeAlignment(Ty);
 698   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 699   return Log2_32(Align);
 700 }
 701
 702 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 703                                        unsigned AddressSpace) const {
 704   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 705 }
 706
 707 Type *DataLayout::getIntPtrType(Type *Ty) const {
 708   assert(Ty->isPtrOrPtrVectorTy() &&
 709          "Expected a pointer or pointer vector type.");
 710   unsigned NumBits = getPointerTypeSizeInBits(Ty);
 711   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 712   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 713     return VectorType::get(IntTy, VecTy->getNumElements());
 714   return IntTy;
 715 }
 716
 717 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 718   for (unsigned LegalIntWidth : LegalIntWidths)
 719     if (Width <= LegalIntWidth)
 720       return Type::getIntNTy(C, LegalIntWidth);
 721   return nullptr;
 722 }
 723
 724 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 725   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 726   return Max != LegalIntWidths.end() ? *Max : 0;
 727 }
 728
 729 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 730                                       ArrayRef<Value *> Indices) const {
 731   Type *Ty = ptrTy;
 732   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 733   uint64_t Result = 0;
 734
 735   generic_gep_type_iterator<Value* const*>
 736     TI = gep_type_begin(ptrTy, Indices);
 737   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 738        ++CurIDX, ++TI) {
 739     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 740       assert(Indices[CurIDX]->getType() ==
 741              Type::getInt32Ty(ptrTy->getContext()) &&
 742              "Illegal struct idx");
 743       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 744
 745       // Get structure layout information...
 746       const StructLayout *Layout = getStructLayout(STy);
 747
 748       // Add in the offset, as calculated by the structure layout info...
 749       Result += Layout->getElementOffset(FieldNo);
 750
 751       // Update Ty to refer to current element
 752       Ty = STy->getElementType(FieldNo);
 753     } else {
 754       // Update Ty to refer to current element
 755       Ty = cast<SequentialType>(Ty)->getElementType();
 756
 757       // Get the array index and the size of each array element.
 758       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 759         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 760     }
 761   }
 762
 763   return Result;
 764 }
 765
 766 /// getPreferredAlignment - Return the preferred alignment of the specified
 767 /// global.  This includes an explicitly requested alignment (if the global
 768 /// has one).
 769 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 770   Type *ElemType = GV->getType()->getElementType();
 771   unsigned Alignment = getPrefTypeAlignment(ElemType);
 772   unsigned GVAlignment = GV->getAlignment();
 773   if (GVAlignment >= Alignment) {
 774     Alignment = GVAlignment;
 775   } else if (GVAlignment != 0) {
 776     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 777   }
 778
 779   if (GV->hasInitializer() && GVAlignment == 0) {
 780     if (Alignment < 16) {
 781       // If the global is not external, see if it is large.  If so, give it a
 782       // larger alignment.
 783       if (getTypeSizeInBits(ElemType) > 128)
 784         Alignment = 16;    // 16-byte alignment.
 785     }
 786   }
 787   return Alignment;
 788 }
 789
 790 /// getPreferredAlignmentLog - Return the preferred alignment of the
 791 /// specified global, returned in log form.  This includes an explicitly
 792 /// requested alignment (if the global has one).
 793 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 794   return Log2_32(getPreferredAlignment(GV));
 795 }
 796
 797 DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
 798   report_fatal_error("Bad DataLayoutPass ctor used. Tool did not specify a "
 799                      "DataLayout to use?");
 800 }
 801
 802 DataLayoutPass::~DataLayoutPass() {}
 803
 804 DataLayoutPass::DataLayoutPass(const DataLayout &DL)
 805     : ImmutablePass(ID), DL(DL) {
 806   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 807 }
 808
 809 DataLayoutPass::DataLayoutPass(const Module *M) : ImmutablePass(ID), DL(M) {
 810   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 811 }