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