contrib/llvm/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/StringRef.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/GlobalVariable.h"
  27 #include "llvm/IR/Module.h"
  28 #include "llvm/IR/Type.h"
  29 #include "llvm/IR/Value.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include <algorithm>
  34 #include <cassert>
  35 #include <cstdint>
  36 #include <cstdlib>
  37 #include <tuple>
  38 #include <utility>
  39
  40 using namespace llvm;
  41
  42 //===----------------------------------------------------------------------===//
  43 // Support for StructLayout
  44 //===----------------------------------------------------------------------===//
  45
  46 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
  47   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
  48   StructAlignment = 0;
  49   StructSize = 0;
  50   IsPadded = false;
  51   NumElements = ST->getNumElements();
  52
  53   // Loop over each of the elements, placing them in memory.
  54   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  55     Type *Ty = ST->getElementType(i);
  56     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
  57
  58     // Add padding if necessary to align the data element properly.
  59     if ((StructSize & (TyAlign-1)) != 0) {
  60       IsPadded = true;
  61       StructSize = alignTo(StructSize, TyAlign);
  62     }
  63
  64     // Keep track of maximum alignment constraint.
  65     StructAlignment = std::max(TyAlign, StructAlignment);
  66
  67     MemberOffsets[i] = StructSize;
  68     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  69   }
  70
  71   // Empty structures have alignment of 1 byte.
  72   if (StructAlignment == 0) StructAlignment = 1;
  73
  74   // Add padding to the end of the struct so that it could be put in an array
  75   // and all array elements would be aligned correctly.
  76   if ((StructSize & (StructAlignment-1)) != 0) {
  77     IsPadded = true;
  78     StructSize = alignTo(StructSize, StructAlignment);
  79   }
  80 }
  81
  82 /// getElementContainingOffset - Given a valid offset into the structure,
  83 /// return the structure index that contains it.
  84 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  85   const uint64_t *SI =
  86     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  87   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  88   --SI;
  89   assert(*SI <= Offset && "upper_bound didn't work");
  90   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  91          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  92          "Upper bound didn't work!");
  93
  94   // Multiple fields can have the same offset if any of them are zero sized.
  95   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  96   // at the i32 element, because it is the last element at that offset.  This is
  97   // the right one to return, because anything after it will have a higher
  98   // offset, implying that this element is non-empty.
  99   return SI-&MemberOffsets[0];
 100 }
 101
 102 //===----------------------------------------------------------------------===//
 103 // LayoutAlignElem, LayoutAlign support
 104 //===----------------------------------------------------------------------===//
 105
 106 LayoutAlignElem
 107 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
 108                      unsigned pref_align, uint32_t bit_width) {
 109   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 110   LayoutAlignElem retval;
 111   retval.AlignType = align_type;
 112   retval.ABIAlign = abi_align;
 113   retval.PrefAlign = pref_align;
 114   retval.TypeBitWidth = bit_width;
 115   return retval;
 116 }
 117
 118 bool
 119 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 120   return (AlignType == rhs.AlignType
 121           && ABIAlign == rhs.ABIAlign
 122           && PrefAlign == rhs.PrefAlign
 123           && TypeBitWidth == rhs.TypeBitWidth);
 124 }
 125
 126 //===----------------------------------------------------------------------===//
 127 // PointerAlignElem, PointerAlign support
 128 //===----------------------------------------------------------------------===//
 129
 130 PointerAlignElem
 131 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
 132                       unsigned PrefAlign, uint32_t TypeByteWidth,
 133                       uint32_t IndexWidth) {
 134   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 135   PointerAlignElem retval;
 136   retval.AddressSpace = AddressSpace;
 137   retval.ABIAlign = ABIAlign;
 138   retval.PrefAlign = PrefAlign;
 139   retval.TypeByteWidth = TypeByteWidth;
 140   retval.IndexWidth = IndexWidth;
 141   return retval;
 142 }
 143
 144 bool
 145 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
 146   return (ABIAlign == rhs.ABIAlign
 147           && AddressSpace == rhs.AddressSpace
 148           && PrefAlign == rhs.PrefAlign
 149           && TypeByteWidth == rhs.TypeByteWidth
 150           && IndexWidth == rhs.IndexWidth);
 151 }
 152
 153 //===----------------------------------------------------------------------===//
 154 //                       DataLayout Class Implementation
 155 //===----------------------------------------------------------------------===//
 156
 157 const char *DataLayout::getManglingComponent(const Triple &T) {
 158   if (T.isOSBinFormatMachO())
 159     return "-m:o";
 160   if (T.isOSWindows() && T.isOSBinFormatCOFF())
 161     return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
 162   return "-m:e";
 163 }
 164
 165 static const LayoutAlignElem DefaultAlignments[] = {
 166   { INTEGER_ALIGN, 1, 1, 1 },    // i1
 167   { INTEGER_ALIGN, 8, 1, 1 },    // i8
 168   { INTEGER_ALIGN, 16, 2, 2 },   // i16
 169   { INTEGER_ALIGN, 32, 4, 4 },   // i32
 170   { INTEGER_ALIGN, 64, 4, 8 },   // i64
 171   { FLOAT_ALIGN, 16, 2, 2 },     // half
 172   { FLOAT_ALIGN, 32, 4, 4 },     // float
 173   { FLOAT_ALIGN, 64, 8, 8 },     // double
 174   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
 175   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
 176   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
 177   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
 178 };
 179
 180 void DataLayout::reset(StringRef Desc) {
 181   clear();
 182
 183   LayoutMap = nullptr;
 184   BigEndian = false;
 185   AllocaAddrSpace = 0;
 186   StackNaturalAlign = 0;
 187   ProgramAddrSpace = 0;
 188   ManglingMode = MM_None;
 189   NonIntegralAddressSpaces.clear();
 190
 191   // Default alignments
 192   for (const LayoutAlignElem &E : DefaultAlignments) {
 193     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
 194                  E.TypeBitWidth);
 195   }
 196   setPointerAlignment(0, 8, 8, 8, 8);
 197
 198   parseSpecifier(Desc);
 199 }
 200
 201 /// Checked version of split, to ensure mandatory subparts.
 202 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
 203   assert(!Str.empty() && "parse error, string can't be empty here");
 204   std::pair<StringRef, StringRef> Split = Str.split(Separator);
 205   if (Split.second.empty() && Split.first != Str)
 206     report_fatal_error("Trailing separator in datalayout string");
 207   if (!Split.second.empty() && Split.first.empty())
 208     report_fatal_error("Expected token before separator in datalayout string");
 209   return Split;
 210 }
 211
 212 /// Get an unsigned integer, including error checks.
 213 static unsigned getInt(StringRef R) {
 214   unsigned Result;
 215   bool error = R.getAsInteger(10, Result); (void)error;
 216   if (error)
 217     report_fatal_error("not a number, or does not fit in an unsigned int");
 218   return Result;
 219 }
 220
 221 /// Convert bits into bytes. Assert if not a byte width multiple.
 222 static unsigned inBytes(unsigned Bits) {
 223   if (Bits % 8)
 224     report_fatal_error("number of bits must be a byte width multiple");
 225   return Bits / 8;
 226 }
 227
 228 static unsigned getAddrSpace(StringRef R) {
 229   unsigned AddrSpace = getInt(R);
 230   if (!isUInt<24>(AddrSpace))
 231     report_fatal_error("Invalid address space, must be a 24-bit integer");
 232   return AddrSpace;
 233 }
 234
 235 void DataLayout::parseSpecifier(StringRef Desc) {
 236   StringRepresentation = Desc;
 237   while (!Desc.empty()) {
 238     // Split at '-'.
 239     std::pair<StringRef, StringRef> Split = split(Desc, '-');
 240     Desc = Split.second;
 241
 242     // Split at ':'.
 243     Split = split(Split.first, ':');
 244
 245     // Aliases used below.
 246     StringRef &Tok  = Split.first;  // Current token.
 247     StringRef &Rest = Split.second; // The rest of the string.
 248
 249     if (Tok == "ni") {
 250       do {
 251         Split = split(Rest, ':');
 252         Rest = Split.second;
 253         unsigned AS = getInt(Split.first);
 254         if (AS == 0)
 255           report_fatal_error("Address space 0 can never be non-integral");
 256         NonIntegralAddressSpaces.push_back(AS);
 257       } while (!Rest.empty());
 258
 259       continue;
 260     }
 261
 262     char Specifier = Tok.front();
 263     Tok = Tok.substr(1);
 264
 265     switch (Specifier) {
 266     case 's':
 267       // Ignored for backward compatibility.
 268       // FIXME: remove this on LLVM 4.0.
 269       break;
 270     case 'E':
 271       BigEndian = true;
 272       break;
 273     case 'e':
 274       BigEndian = false;
 275       break;
 276     case 'p': {
 277       // Address space.
 278       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
 279       if (!isUInt<24>(AddrSpace))
 280         report_fatal_error("Invalid address space, must be a 24bit integer");
 281
 282       // Size.
 283       if (Rest.empty())
 284         report_fatal_error(
 285             "Missing size specification for pointer in datalayout string");
 286       Split = split(Rest, ':');
 287       unsigned PointerMemSize = inBytes(getInt(Tok));
 288       if (!PointerMemSize)
 289         report_fatal_error("Invalid pointer size of 0 bytes");
 290
 291       // ABI alignment.
 292       if (Rest.empty())
 293         report_fatal_error(
 294             "Missing alignment specification for pointer in datalayout string");
 295       Split = split(Rest, ':');
 296       unsigned PointerABIAlign = inBytes(getInt(Tok));
 297       if (!isPowerOf2_64(PointerABIAlign))
 298         report_fatal_error(
 299             "Pointer ABI alignment must be a power of 2");
 300
 301       // Size of index used in GEP for address calculation.
 302       // The parameter is optional. By default it is equal to size of pointer.
 303       unsigned IndexSize = PointerMemSize;
 304
 305       // Preferred alignment.
 306       unsigned PointerPrefAlign = PointerABIAlign;
 307       if (!Rest.empty()) {
 308         Split = split(Rest, ':');
 309         PointerPrefAlign = inBytes(getInt(Tok));
 310         if (!isPowerOf2_64(PointerPrefAlign))
 311           report_fatal_error(
 312             "Pointer preferred alignment must be a power of 2");
 313
 314         // Now read the index. It is the second optional parameter here.
 315         if (!Rest.empty()) {
 316           Split = split(Rest, ':');
 317           IndexSize = inBytes(getInt(Tok));
 318           if (!IndexSize)
 319             report_fatal_error("Invalid index size of 0 bytes");
 320         }
 321       }
 322       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
 323                           PointerMemSize, IndexSize);
 324       break;
 325     }
 326     case 'i':
 327     case 'v':
 328     case 'f':
 329     case 'a': {
 330       AlignTypeEnum AlignType;
 331       switch (Specifier) {
 332       default: llvm_unreachable("Unexpected specifier!");
 333       case 'i': AlignType = INTEGER_ALIGN; break;
 334       case 'v': AlignType = VECTOR_ALIGN; break;
 335       case 'f': AlignType = FLOAT_ALIGN; break;
 336       case 'a': AlignType = AGGREGATE_ALIGN; break;
 337       }
 338
 339       // Bit size.
 340       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
 341
 342       if (AlignType == AGGREGATE_ALIGN && Size != 0)
 343         report_fatal_error(
 344             "Sized aggregate specification in datalayout string");
 345
 346       // ABI alignment.
 347       if (Rest.empty())
 348         report_fatal_error(
 349             "Missing alignment specification in datalayout string");
 350       Split = split(Rest, ':');
 351       unsigned ABIAlign = inBytes(getInt(Tok));
 352       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
 353         report_fatal_error(
 354             "ABI alignment specification must be >0 for non-aggregate types");
 355
 356       // Preferred alignment.
 357       unsigned PrefAlign = ABIAlign;
 358       if (!Rest.empty()) {
 359         Split = split(Rest, ':');
 360         PrefAlign = inBytes(getInt(Tok));
 361       }
 362
 363       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 364
 365       break;
 366     }
 367     case 'n':  // Native integer types.
 368       while (true) {
 369         unsigned Width = getInt(Tok);
 370         if (Width == 0)
 371           report_fatal_error(
 372               "Zero width native integer type in datalayout string");
 373         LegalIntWidths.push_back(Width);
 374         if (Rest.empty())
 375           break;
 376         Split = split(Rest, ':');
 377       }
 378       break;
 379     case 'S': { // Stack natural alignment.
 380       StackNaturalAlign = inBytes(getInt(Tok));
 381       break;
 382     }
 383     case 'P': { // Function address space.
 384       ProgramAddrSpace = getAddrSpace(Tok);
 385       break;
 386     }
 387     case 'A': { // Default stack/alloca address space.
 388       AllocaAddrSpace = getAddrSpace(Tok);
 389       break;
 390     }
 391     case 'm':
 392       if (!Tok.empty())
 393         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
 394       if (Rest.empty())
 395         report_fatal_error("Expected mangling specifier in datalayout string");
 396       if (Rest.size() > 1)
 397         report_fatal_error("Unknown mangling specifier in datalayout string");
 398       switch(Rest[0]) {
 399       default:
 400         report_fatal_error("Unknown mangling in datalayout string");
 401       case 'e':
 402         ManglingMode = MM_ELF;
 403         break;
 404       case 'o':
 405         ManglingMode = MM_MachO;
 406         break;
 407       case 'm':
 408         ManglingMode = MM_Mips;
 409         break;
 410       case 'w':
 411         ManglingMode = MM_WinCOFF;
 412         break;
 413       case 'x':
 414         ManglingMode = MM_WinCOFFX86;
 415         break;
 416       }
 417       break;
 418     default:
 419       report_fatal_error("Unknown specifier in datalayout string");
 420       break;
 421     }
 422   }
 423 }
 424
 425 DataLayout::DataLayout(const Module *M) {
 426   init(M);
 427 }
 428
 429 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 430
 431 bool DataLayout::operator==(const DataLayout &Other) const {
 432   bool Ret = BigEndian == Other.BigEndian &&
 433              AllocaAddrSpace == Other.AllocaAddrSpace &&
 434              StackNaturalAlign == Other.StackNaturalAlign &&
 435              ProgramAddrSpace == Other.ProgramAddrSpace &&
 436              ManglingMode == Other.ManglingMode &&
 437              LegalIntWidths == Other.LegalIntWidths &&
 438              Alignments == Other.Alignments && Pointers == Other.Pointers;
 439   // Note: getStringRepresentation() might differs, it is not canonicalized
 440   return Ret;
 441 }
 442
 443 DataLayout::AlignmentsTy::iterator
 444 DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType,
 445                                     uint32_t BitWidth) {
 446   auto Pair = std::make_pair((unsigned)AlignType, BitWidth);
 447   return std::lower_bound(Alignments.begin(), Alignments.end(), Pair,
 448                           [](const LayoutAlignElem &LHS,
 449                              const std::pair<unsigned, uint32_t> &RHS) {
 450                             return std::tie(LHS.AlignType, LHS.TypeBitWidth) <
 451                                    std::tie(RHS.first, RHS.second);
 452                           });
 453 }
 454
 455 void
 456 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 457                          unsigned pref_align, uint32_t bit_width) {
 458   if (!isUInt<24>(bit_width))
 459     report_fatal_error("Invalid bit width, must be a 24bit integer");
 460   if (!isUInt<16>(abi_align))
 461     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
 462   if (!isUInt<16>(pref_align))
 463     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
 464   if (abi_align != 0 && !isPowerOf2_64(abi_align))
 465     report_fatal_error("Invalid ABI alignment, must be a power of 2");
 466   if (pref_align != 0 && !isPowerOf2_64(pref_align))
 467     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 468
 469   if (pref_align < abi_align)
 470     report_fatal_error(
 471         "Preferred alignment cannot be less than the ABI alignment");
 472
 473   AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width);
 474   if (I != Alignments.end() &&
 475       I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) {
 476     // Update the abi, preferred alignments.
 477     I->ABIAlign = abi_align;
 478     I->PrefAlign = pref_align;
 479   } else {
 480     // Insert before I to keep the vector sorted.
 481     Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
 482                                               pref_align, bit_width));
 483   }
 484 }
 485
 486 DataLayout::PointersTy::iterator
 487 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
 488   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 489                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
 490     return A.AddressSpace < AddressSpace;
 491   });
 492 }
 493
 494 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 495                                      unsigned PrefAlign, uint32_t TypeByteWidth,
 496                                      uint32_t IndexWidth) {
 497   if (PrefAlign < ABIAlign)
 498     report_fatal_error(
 499         "Preferred alignment cannot be less than the ABI alignment");
 500
 501   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
 502   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 503     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 504                                              TypeByteWidth, IndexWidth));
 505   } else {
 506     I->ABIAlign = ABIAlign;
 507     I->PrefAlign = PrefAlign;
 508     I->TypeByteWidth = TypeByteWidth;
 509     I->IndexWidth = IndexWidth;
 510   }
 511 }
 512
 513 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 514 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 515 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 516                                       uint32_t BitWidth, bool ABIInfo,
 517                                       Type *Ty) const {
 518   AlignmentsTy::const_iterator I = findAlignmentLowerBound(AlignType, BitWidth);
 519   // See if we found an exact match. Of if we are looking for an integer type,
 520   // but don't have an exact match take the next largest integer. This is where
 521   // the lower_bound will point to when it fails an exact match.
 522   if (I != Alignments.end() && I->AlignType == (unsigned)AlignType &&
 523       (I->TypeBitWidth == BitWidth || AlignType == INTEGER_ALIGN))
 524     return ABIInfo ? I->ABIAlign : I->PrefAlign;
 525
 526   if (AlignType == INTEGER_ALIGN) {
 527     // If we didn't have a larger value try the largest value we have.
 528     if (I != Alignments.begin()) {
 529       --I; // Go to the previous entry and see if its an integer.
 530       if (I->AlignType == INTEGER_ALIGN)
 531         return ABIInfo ? I->ABIAlign : I->PrefAlign;
 532     }
 533   } else if (AlignType == VECTOR_ALIGN) {
 534     // By default, use natural alignment for vector types. This is consistent
 535     // with what clang and llvm-gcc do.
 536     unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 537     Align *= cast<VectorType>(Ty)->getNumElements();
 538     Align = PowerOf2Ceil(Align);
 539     return Align;
 540    }
 541
 542   // If we still couldn't find a reasonable default alignment, fall back
 543   // to a simple heuristic that the alignment is the first power of two
 544   // greater-or-equal to the store size of the type.  This is a reasonable
 545   // approximation of reality, and if the user wanted something less
 546   // less conservative, they should have specified it explicitly in the data
 547   // layout.
 548   unsigned Align = getTypeStoreSize(Ty);
 549   Align = PowerOf2Ceil(Align);
 550   return Align;
 551 }
 552
 553 namespace {
 554
 555 class StructLayoutMap {
 556   using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
 557   LayoutInfoTy LayoutInfo;
 558
 559 public:
 560   ~StructLayoutMap() {
 561     // Remove any layouts.
 562     for (const auto &I : LayoutInfo) {
 563       StructLayout *Value = I.second;
 564       Value->~StructLayout();
 565       free(Value);
 566     }
 567   }
 568
 569   StructLayout *&operator[](StructType *STy) {
 570     return LayoutInfo[STy];
 571   }
 572 };
 573
 574 } // end anonymous namespace
 575
 576 void DataLayout::clear() {
 577   LegalIntWidths.clear();
 578   Alignments.clear();
 579   Pointers.clear();
 580   delete static_cast<StructLayoutMap *>(LayoutMap);
 581   LayoutMap = nullptr;
 582 }
 583
 584 DataLayout::~DataLayout() {
 585   clear();
 586 }
 587
 588 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 589   if (!LayoutMap)
 590     LayoutMap = new StructLayoutMap();
 591
 592   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 593   StructLayout *&SL = (*STM)[Ty];
 594   if (SL) return SL;
 595
 596   // Otherwise, create the struct layout.  Because it is variable length, we
 597   // malloc it, then use placement new.
 598   int NumElts = Ty->getNumElements();
 599   StructLayout *L = (StructLayout *)
 600       safe_malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 601
 602   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 603   // entries to be added to TheMap, invalidating our reference.
 604   SL = L;
 605
 606   new (L) StructLayout(Ty, *this);
 607
 608   return L;
 609 }
 610
 611 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
 612   PointersTy::const_iterator I = findPointerLowerBound(AS);
 613   if (I == Pointers.end() || I->AddressSpace != AS) {
 614     I = findPointerLowerBound(0);
 615     assert(I->AddressSpace == 0);
 616   }
 617   return I->ABIAlign;
 618 }
 619
 620 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 621   PointersTy::const_iterator I = findPointerLowerBound(AS);
 622   if (I == Pointers.end() || I->AddressSpace != AS) {
 623     I = findPointerLowerBound(0);
 624     assert(I->AddressSpace == 0);
 625   }
 626   return I->PrefAlign;
 627 }
 628
 629 unsigned DataLayout::getPointerSize(unsigned AS) const {
 630   PointersTy::const_iterator I = findPointerLowerBound(AS);
 631   if (I == Pointers.end() || I->AddressSpace != AS) {
 632     I = findPointerLowerBound(0);
 633     assert(I->AddressSpace == 0);
 634   }
 635   return I->TypeByteWidth;
 636 }
 637
 638 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 639   assert(Ty->isPtrOrPtrVectorTy() &&
 640          "This should only be called with a pointer or pointer vector type");
 641   Ty = Ty->getScalarType();
 642   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 643 }
 644
 645 unsigned DataLayout::getIndexSize(unsigned AS) const {
 646   PointersTy::const_iterator I = findPointerLowerBound(AS);
 647   if (I == Pointers.end() || I->AddressSpace != AS) {
 648     I = findPointerLowerBound(0);
 649     assert(I->AddressSpace == 0);
 650   }
 651   return I->IndexWidth;
 652 }
 653
 654 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
 655   assert(Ty->isPtrOrPtrVectorTy() &&
 656          "This should only be called with a pointer or pointer vector type");
 657   Ty = Ty->getScalarType();
 658   return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 659 }
 660
 661 /*!
 662   \param abi_or_pref Flag that determines which alignment is returned. true
 663   returns the ABI alignment, false returns the preferred alignment.
 664   \param Ty The underlying type for which alignment is determined.
 665
 666   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 667   == false) for the requested type \a Ty.
 668  */
 669 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 670   AlignTypeEnum AlignType;
 671
 672   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 673   switch (Ty->getTypeID()) {
 674   // Early escape for the non-numeric types.
 675   case Type::LabelTyID:
 676     return (abi_or_pref
 677             ? getPointerABIAlignment(0)
 678             : getPointerPrefAlignment(0));
 679   case Type::PointerTyID: {
 680     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
 681     return (abi_or_pref
 682             ? getPointerABIAlignment(AS)
 683             : getPointerPrefAlignment(AS));
 684     }
 685   case Type::ArrayTyID:
 686     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 687
 688   case Type::StructTyID: {
 689     // Packed structure types always have an ABI alignment of one.
 690     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 691       return 1;
 692
 693     // Get the layout annotation... which is lazily created on demand.
 694     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 695     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 696     return std::max(Align, Layout->getAlignment());
 697   }
 698   case Type::IntegerTyID:
 699     AlignType = INTEGER_ALIGN;
 700     break;
 701   case Type::HalfTyID:
 702   case Type::FloatTyID:
 703   case Type::DoubleTyID:
 704   // PPC_FP128TyID and FP128TyID have different data contents, but the
 705   // same size and alignment, so they look the same here.
 706   case Type::PPC_FP128TyID:
 707   case Type::FP128TyID:
 708   case Type::X86_FP80TyID:
 709     AlignType = FLOAT_ALIGN;
 710     break;
 711   case Type::X86_MMXTyID:
 712   case Type::VectorTyID:
 713     AlignType = VECTOR_ALIGN;
 714     break;
 715   default:
 716     llvm_unreachable("Bad type for getAlignment!!!");
 717   }
 718
 719   return getAlignmentInfo(AlignType, getTypeSizeInBits(Ty), abi_or_pref, Ty);
 720 }
 721
 722 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 723   return getAlignment(Ty, true);
 724 }
 725
 726 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 727 /// an integer type of the specified bitwidth.
 728 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 729   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
 730 }
 731
 732 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 733   return getAlignment(Ty, false);
 734 }
 735
 736 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 737   unsigned Align = getPrefTypeAlignment(Ty);
 738   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 739   return Log2_32(Align);
 740 }
 741
 742 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 743                                        unsigned AddressSpace) const {
 744   return IntegerType::get(C, getIndexSizeInBits(AddressSpace));
 745 }
 746
 747 Type *DataLayout::getIntPtrType(Type *Ty) const {
 748   assert(Ty->isPtrOrPtrVectorTy() &&
 749          "Expected a pointer or pointer vector type.");
 750   unsigned NumBits = getIndexTypeSizeInBits(Ty);
 751   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 752   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 753     return VectorType::get(IntTy, VecTy->getNumElements());
 754   return IntTy;
 755 }
 756
 757 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 758   for (unsigned LegalIntWidth : LegalIntWidths)
 759     if (Width <= LegalIntWidth)
 760       return Type::getIntNTy(C, LegalIntWidth);
 761   return nullptr;
 762 }
 763
 764 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
 765   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
 766   return Max != LegalIntWidths.end() ? *Max : 0;
 767 }
 768
 769 Type *DataLayout::getIndexType(Type *Ty) const {
 770   assert(Ty->isPtrOrPtrVectorTy() &&
 771          "Expected a pointer or pointer vector type.");
 772   unsigned NumBits = getIndexTypeSizeInBits(Ty);
 773   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 774   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 775     return VectorType::get(IntTy, VecTy->getNumElements());
 776   return IntTy;
 777 }
 778
 779 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
 780                                            ArrayRef<Value *> Indices) const {
 781   int64_t Result = 0;
 782
 783   generic_gep_type_iterator<Value* const*>
 784     GTI = gep_type_begin(ElemTy, Indices),
 785     GTE = gep_type_end(ElemTy, Indices);
 786   for (; GTI != GTE; ++GTI) {
 787     Value *Idx = GTI.getOperand();
 788     if (StructType *STy = GTI.getStructTypeOrNull()) {
 789       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
 790       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
 791
 792       // Get structure layout information...
 793       const StructLayout *Layout = getStructLayout(STy);
 794
 795       // Add in the offset, as calculated by the structure layout info...
 796       Result += Layout->getElementOffset(FieldNo);
 797     } else {
 798       // Get the array index and the size of each array element.
 799       if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
 800         Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
 801     }
 802   }
 803
 804   return Result;
 805 }
 806
 807 /// getPreferredAlignment - Return the preferred alignment of the specified
 808 /// global.  This includes an explicitly requested alignment (if the global
 809 /// has one).
 810 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 811   Type *ElemType = GV->getValueType();
 812   unsigned Alignment = getPrefTypeAlignment(ElemType);
 813   unsigned GVAlignment = GV->getAlignment();
 814   if (GVAlignment >= Alignment) {
 815     Alignment = GVAlignment;
 816   } else if (GVAlignment != 0) {
 817     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 818   }
 819
 820   if (GV->hasInitializer() && GVAlignment == 0) {
 821     if (Alignment < 16) {
 822       // If the global is not external, see if it is large.  If so, give it a
 823       // larger alignment.
 824       if (getTypeSizeInBits(ElemType) > 128)
 825         Alignment = 16;    // 16-byte alignment.
 826     }
 827   }
 828   return Alignment;
 829 }
 830
 831 /// getPreferredAlignmentLog - Return the preferred alignment of the
 832 /// specified global, returned in log form.  This includes an explicitly
 833 /// requested alignment (if the global has one).
 834 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 835   return Log2_32(getPreferredAlignment(GV));
 836 }