lib/IR/DataLayout.cpp

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