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