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/Module.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/GetElementPtrTypeIterator.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 // Register the default SparcV9 implementation...
  39 INITIALIZE_PASS(DataLayout, "datalayout", "Data Layout", false, true)
  40 char DataLayout::ID = 0;
  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   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       StructSize = DataLayout::RoundUpAlignment(StructSize, TyAlign);
  60
  61     // Keep track of maximum alignment constraint.
  62     StructAlignment = std::max(TyAlign, StructAlignment);
  63
  64     MemberOffsets[i] = StructSize;
  65     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  66   }
  67
  68   // Empty structures have alignment of 1 byte.
  69   if (StructAlignment == 0) StructAlignment = 1;
  70
  71   // Add padding to the end of the struct so that it could be put in an array
  72   // and all array elements would be aligned correctly.
  73   if ((StructSize & (StructAlignment-1)) != 0)
  74     StructSize = DataLayout::RoundUpAlignment(StructSize, StructAlignment);
  75 }
  76
  77
  78 /// getElementContainingOffset - Given a valid offset into the structure,
  79 /// return the structure index that contains it.
  80 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  81   const uint64_t *SI =
  82     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  83   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  84   --SI;
  85   assert(*SI <= Offset && "upper_bound didn't work");
  86   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  87          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  88          "Upper bound didn't work!");
  89
  90   // Multiple fields can have the same offset if any of them are zero sized.
  91   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  92   // at the i32 element, because it is the last element at that offset.  This is
  93   // the right one to return, because anything after it will have a higher
  94   // offset, implying that this element is non-empty.
  95   return SI-&MemberOffsets[0];
  96 }
  97
  98 //===----------------------------------------------------------------------===//
  99 // LayoutAlignElem, LayoutAlign support
 100 //===----------------------------------------------------------------------===//
 101
 102 LayoutAlignElem
 103 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
 104                      unsigned pref_align, uint32_t bit_width) {
 105   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 106   LayoutAlignElem retval;
 107   retval.AlignType = align_type;
 108   retval.ABIAlign = abi_align;
 109   retval.PrefAlign = pref_align;
 110   retval.TypeBitWidth = bit_width;
 111   return retval;
 112 }
 113
 114 bool
 115 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 116   return (AlignType == rhs.AlignType
 117           && ABIAlign == rhs.ABIAlign
 118           && PrefAlign == rhs.PrefAlign
 119           && TypeBitWidth == rhs.TypeBitWidth);
 120 }
 121
 122 const LayoutAlignElem
 123 DataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 };
 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   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 133   PointerAlignElem retval;
 134   retval.AddressSpace = AddressSpace;
 135   retval.ABIAlign = ABIAlign;
 136   retval.PrefAlign = PrefAlign;
 137   retval.TypeByteWidth = TypeByteWidth;
 138   return retval;
 139 }
 140
 141 bool
 142 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
 143   return (ABIAlign == rhs.ABIAlign
 144           && AddressSpace == rhs.AddressSpace
 145           && PrefAlign == rhs.PrefAlign
 146           && TypeByteWidth == rhs.TypeByteWidth);
 147 }
 148
 149 const PointerAlignElem
 150 DataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U };
 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.isOSBinFormatELF() || T.isArch64Bit())
 160     return "-m:e";
 161   assert(T.isOSBinFormatCOFF());
 162   return "-m:c";
 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::init(StringRef Desc) {
 181   initializeDataLayoutPass(*PassRegistry::getPassRegistry());
 182
 183   LayoutMap = 0;
 184   LittleEndian = false;
 185   StackNaturalAlign = 0;
 186   ManglingMode = MM_None;
 187
 188   // Default alignments
 189   for (int I = 0, N = array_lengthof(DefaultAlignments); I < N; ++I) {
 190     const LayoutAlignElem &E = DefaultAlignments[I];
 191     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
 192                  E.TypeBitWidth);
 193   }
 194   setPointerAlignment(0, 8, 8, 8);
 195
 196   parseSpecifier(Desc);
 197 }
 198
 199 /// Checked version of split, to ensure mandatory subparts.
 200 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
 201   assert(!Str.empty() && "parse error, string can't be empty here");
 202   std::pair<StringRef, StringRef> Split = Str.split(Separator);
 203   assert((!Split.second.empty() || Split.first == Str) &&
 204          "a trailing separator is not allowed");
 205   return Split;
 206 }
 207
 208 /// Get an unsigned integer, including error checks.
 209 static unsigned getInt(StringRef R) {
 210   unsigned Result = 0;
 211   bool error = R.getAsInteger(10, Result); (void)error;
 212   assert(!error && "not a number, or does not fit in an unsigned int");
 213   return Result;
 214 }
 215
 216 /// Convert bits into bytes. Assert if not a byte width multiple.
 217 static unsigned inBytes(unsigned Bits) {
 218   assert(Bits % 8 == 0 && "number of bits must be a byte width multiple");
 219   return Bits / 8;
 220 }
 221
 222 void DataLayout::parseSpecifier(StringRef Desc) {
 223   while (!Desc.empty()) {
 224     // Split at '-'.
 225     std::pair<StringRef, StringRef> Split = split(Desc, '-');
 226     Desc = Split.second;
 227
 228     // Split at ':'.
 229     Split = split(Split.first, ':');
 230
 231     // Aliases used below.
 232     StringRef &Tok  = Split.first;  // Current token.
 233     StringRef &Rest = Split.second; // The rest of the string.
 234
 235     char Specifier = Tok.front();
 236     Tok = Tok.substr(1);
 237
 238     switch (Specifier) {
 239     case 's':
 240       // Ignored for backward compatibility.
 241       // FIXME: remove this on LLVM 4.0.
 242       break;
 243     case 'E':
 244       LittleEndian = false;
 245       break;
 246     case 'e':
 247       LittleEndian = true;
 248       break;
 249     case 'p': {
 250       // Address space.
 251       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
 252       assert(AddrSpace < 1 << 24 &&
 253              "Invalid address space, must be a 24bit integer");
 254
 255       // Size.
 256       Split = split(Rest, ':');
 257       unsigned PointerMemSize = inBytes(getInt(Tok));
 258
 259       // ABI alignment.
 260       Split = split(Rest, ':');
 261       unsigned PointerABIAlign = inBytes(getInt(Tok));
 262
 263       // Preferred alignment.
 264       unsigned PointerPrefAlign = PointerABIAlign;
 265       if (!Rest.empty()) {
 266         Split = split(Rest, ':');
 267         PointerPrefAlign = inBytes(getInt(Tok));
 268       }
 269
 270       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
 271                           PointerMemSize);
 272       break;
 273     }
 274     case 'i':
 275     case 'v':
 276     case 'f':
 277     case 'a': {
 278       AlignTypeEnum AlignType;
 279       switch (Specifier) {
 280       default:
 281       case 'i': AlignType = INTEGER_ALIGN; break;
 282       case 'v': AlignType = VECTOR_ALIGN; break;
 283       case 'f': AlignType = FLOAT_ALIGN; break;
 284       case 'a': AlignType = AGGREGATE_ALIGN; break;
 285       }
 286
 287       // Bit size.
 288       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
 289
 290       assert((AlignType != AGGREGATE_ALIGN || Size == 0) &&
 291              "These specifications don't have a size");
 292
 293       // ABI alignment.
 294       Split = split(Rest, ':');
 295       unsigned ABIAlign = inBytes(getInt(Tok));
 296
 297       // Preferred alignment.
 298       unsigned PrefAlign = ABIAlign;
 299       if (!Rest.empty()) {
 300         Split = split(Rest, ':');
 301         PrefAlign = inBytes(getInt(Tok));
 302       }
 303
 304       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 305
 306       break;
 307     }
 308     case 'n':  // Native integer types.
 309       for (;;) {
 310         unsigned Width = getInt(Tok);
 311         assert(Width != 0 && "width must be non-zero");
 312         LegalIntWidths.push_back(Width);
 313         if (Rest.empty())
 314           break;
 315         Split = split(Rest, ':');
 316       }
 317       break;
 318     case 'S': { // Stack natural alignment.
 319       StackNaturalAlign = inBytes(getInt(Tok));
 320       break;
 321     }
 322     case 'm':
 323       assert(Tok.empty());
 324       assert(Rest.size() == 1);
 325       switch(Rest[0]) {
 326       default:
 327         llvm_unreachable("Unknown mangling in datalayout string");
 328       case 'e':
 329         ManglingMode = MM_ELF;
 330         break;
 331       case 'o':
 332         ManglingMode = MM_MachO;
 333         break;
 334       case 'm':
 335         ManglingMode = MM_Mips;
 336         break;
 337       case 'c':
 338         ManglingMode = MM_COFF;
 339         break;
 340       }
 341       break;
 342     default:
 343       llvm_unreachable("Unknown specifier in datalayout string");
 344       break;
 345     }
 346   }
 347 }
 348
 349 /// Default ctor.
 350 ///
 351 /// @note This has to exist, because this is a pass, but it should never be
 352 /// used.
 353 DataLayout::DataLayout() : ImmutablePass(ID) {
 354   report_fatal_error("Bad DataLayout ctor used.  "
 355                      "Tool did not specify a DataLayout to use?");
 356 }
 357
 358 DataLayout::DataLayout(const Module *M)
 359   : ImmutablePass(ID) {
 360   init(M->getDataLayout());
 361 }
 362
 363 void
 364 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 365                          unsigned pref_align, uint32_t bit_width) {
 366   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 367   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
 368   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
 369   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 370     if (Alignments[i].AlignType == (unsigned)align_type &&
 371         Alignments[i].TypeBitWidth == bit_width) {
 372       // Update the abi, preferred alignments.
 373       Alignments[i].ABIAlign = abi_align;
 374       Alignments[i].PrefAlign = pref_align;
 375       return;
 376     }
 377   }
 378
 379   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 380                                             pref_align, bit_width));
 381 }
 382
 383 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 384                                      unsigned PrefAlign,
 385                                      uint32_t TypeByteWidth) {
 386   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 387   DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(AddrSpace);
 388   if (val == Pointers.end()) {
 389     Pointers[AddrSpace] =
 390         PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, TypeByteWidth);
 391   } else {
 392     val->second.ABIAlign = ABIAlign;
 393     val->second.PrefAlign = PrefAlign;
 394     val->second.TypeByteWidth = TypeByteWidth;
 395   }
 396 }
 397
 398 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 399 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 400 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 401                                       uint32_t BitWidth, bool ABIInfo,
 402                                       Type *Ty) const {
 403   // Check to see if we have an exact match and remember the best match we see.
 404   int BestMatchIdx = -1;
 405   int LargestInt = -1;
 406   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 407     if (Alignments[i].AlignType == (unsigned)AlignType &&
 408         Alignments[i].TypeBitWidth == BitWidth)
 409       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 410
 411     // The best match so far depends on what we're looking for.
 412      if (AlignType == INTEGER_ALIGN &&
 413          Alignments[i].AlignType == INTEGER_ALIGN) {
 414       // The "best match" for integers is the smallest size that is larger than
 415       // the BitWidth requested.
 416       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 417           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 418         BestMatchIdx = i;
 419       // However, if there isn't one that's larger, then we must use the
 420       // largest one we have (see below)
 421       if (LargestInt == -1 ||
 422           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 423         LargestInt = i;
 424     }
 425   }
 426
 427   // Okay, we didn't find an exact solution.  Fall back here depending on what
 428   // is being looked for.
 429   if (BestMatchIdx == -1) {
 430     // If we didn't find an integer alignment, fall back on most conservative.
 431     if (AlignType == INTEGER_ALIGN) {
 432       BestMatchIdx = LargestInt;
 433     } else {
 434       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 435
 436       // By default, use natural alignment for vector types. This is consistent
 437       // with what clang and llvm-gcc do.
 438       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 439       Align *= cast<VectorType>(Ty)->getNumElements();
 440       // If the alignment is not a power of 2, round up to the next power of 2.
 441       // This happens for non-power-of-2 length vectors.
 442       if (Align & (Align-1))
 443         Align = NextPowerOf2(Align);
 444       return Align;
 445     }
 446   }
 447
 448   // Since we got a "best match" index, just return it.
 449   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 450                  : Alignments[BestMatchIdx].PrefAlign;
 451 }
 452
 453 namespace {
 454
 455 class StructLayoutMap {
 456   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 457   LayoutInfoTy LayoutInfo;
 458
 459 public:
 460   virtual ~StructLayoutMap() {
 461     // Remove any layouts.
 462     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
 463          I != E; ++I) {
 464       StructLayout *Value = I->second;
 465       Value->~StructLayout();
 466       free(Value);
 467     }
 468   }
 469
 470   StructLayout *&operator[](StructType *STy) {
 471     return LayoutInfo[STy];
 472   }
 473
 474   // for debugging...
 475   virtual void dump() const {}
 476 };
 477
 478 } // end anonymous namespace
 479
 480 DataLayout::~DataLayout() {
 481   delete static_cast<StructLayoutMap*>(LayoutMap);
 482 }
 483
 484 bool DataLayout::doFinalization(Module &M) {
 485   delete static_cast<StructLayoutMap*>(LayoutMap);
 486   LayoutMap = 0;
 487   return false;
 488 }
 489
 490 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 491   if (!LayoutMap)
 492     LayoutMap = new StructLayoutMap();
 493
 494   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 495   StructLayout *&SL = (*STM)[Ty];
 496   if (SL) return SL;
 497
 498   // Otherwise, create the struct layout.  Because it is variable length, we
 499   // malloc it, then use placement new.
 500   int NumElts = Ty->getNumElements();
 501   StructLayout *L =
 502     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 503
 504   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 505   // entries to be added to TheMap, invalidating our reference.
 506   SL = L;
 507
 508   new (L) StructLayout(Ty, *this);
 509
 510   return L;
 511 }
 512
 513 std::string DataLayout::getStringRepresentation() const {
 514   std::string Result;
 515   raw_string_ostream OS(Result);
 516
 517   OS << (LittleEndian ? "e" : "E");
 518
 519   switch (ManglingMode) {
 520   case MM_None:
 521     break;
 522   case MM_ELF:
 523     OS << "-m:e";
 524     break;
 525   case MM_MachO:
 526     OS << "-m:o";
 527     break;
 528   case MM_COFF:
 529     OS << "-m:c";
 530     break;
 531   case MM_Mips:
 532     OS << "-m:m";
 533     break;
 534   }
 535
 536   SmallVector<unsigned, 8> addrSpaces;
 537   // Lets get all of the known address spaces and sort them
 538   // into increasing order so that we can emit the string
 539   // in a cleaner format.
 540   for (DenseMap<unsigned, PointerAlignElem>::const_iterator
 541       pib = Pointers.begin(), pie = Pointers.end();
 542       pib != pie; ++pib) {
 543     addrSpaces.push_back(pib->first);
 544   }
 545   std::sort(addrSpaces.begin(), addrSpaces.end());
 546   for (SmallVectorImpl<unsigned>::iterator asb = addrSpaces.begin(),
 547       ase = addrSpaces.end(); asb != ase; ++asb) {
 548     const PointerAlignElem &PI = Pointers.find(*asb)->second;
 549
 550     // Skip default.
 551     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
 552         PI.TypeByteWidth == 8)
 553       continue;
 554
 555     OS << "-p";
 556     if (PI.AddressSpace) {
 557       OS << PI.AddressSpace;
 558     }
 559     OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
 560     if (PI.PrefAlign != PI.ABIAlign)
 561       OS << ':' << PI.PrefAlign*8;
 562   }
 563
 564   const LayoutAlignElem *DefaultStart = DefaultAlignments;
 565   const LayoutAlignElem *DefaultEnd =
 566       DefaultStart + array_lengthof(DefaultAlignments);
 567   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 568     const LayoutAlignElem &AI = Alignments[i];
 569     if (std::find(DefaultStart, DefaultEnd, AI) != DefaultEnd)
 570       continue;
 571     OS << '-' << (char)AI.AlignType;
 572     if (AI.TypeBitWidth)
 573       OS << AI.TypeBitWidth;
 574     OS << ':' << AI.ABIAlign*8;
 575     if (AI.ABIAlign != AI.PrefAlign)
 576       OS << ':' << AI.PrefAlign*8;
 577   }
 578
 579   if (!LegalIntWidths.empty()) {
 580     OS << "-n" << (unsigned)LegalIntWidths[0];
 581
 582     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 583       OS << ':' << (unsigned)LegalIntWidths[i];
 584   }
 585
 586   if (StackNaturalAlign)
 587     OS << "-S" << StackNaturalAlign*8;
 588
 589   return OS.str();
 590 }
 591
 592 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 593   assert(Ty->isPtrOrPtrVectorTy() &&
 594          "This should only be called with a pointer or pointer vector type");
 595
 596   if (Ty->isPointerTy())
 597     return getTypeSizeInBits(Ty);
 598
 599   return getTypeSizeInBits(Ty->getScalarType());
 600 }
 601
 602 /*!
 603   \param abi_or_pref Flag that determines which alignment is returned. true
 604   returns the ABI alignment, false returns the preferred alignment.
 605   \param Ty The underlying type for which alignment is determined.
 606
 607   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 608   == false) for the requested type \a Ty.
 609  */
 610 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 611   int AlignType = -1;
 612
 613   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 614   switch (Ty->getTypeID()) {
 615   // Early escape for the non-numeric types.
 616   case Type::LabelTyID:
 617     return (abi_or_pref
 618             ? getPointerABIAlignment(0)
 619             : getPointerPrefAlignment(0));
 620   case Type::PointerTyID: {
 621     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 622     return (abi_or_pref
 623             ? getPointerABIAlignment(AS)
 624             : getPointerPrefAlignment(AS));
 625     }
 626   case Type::ArrayTyID:
 627     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 628
 629   case Type::StructTyID: {
 630     // Packed structure types always have an ABI alignment of one.
 631     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 632       return 1;
 633
 634     // Get the layout annotation... which is lazily created on demand.
 635     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 636     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 637     return std::max(Align, Layout->getAlignment());
 638   }
 639   case Type::IntegerTyID:
 640     AlignType = INTEGER_ALIGN;
 641     break;
 642   case Type::HalfTyID:
 643   case Type::FloatTyID:
 644   case Type::DoubleTyID:
 645   // PPC_FP128TyID and FP128TyID have different data contents, but the
 646   // same size and alignment, so they look the same here.
 647   case Type::PPC_FP128TyID:
 648   case Type::FP128TyID:
 649   case Type::X86_FP80TyID:
 650     AlignType = FLOAT_ALIGN;
 651     break;
 652   case Type::X86_MMXTyID:
 653   case Type::VectorTyID:
 654     AlignType = VECTOR_ALIGN;
 655     break;
 656   default:
 657     llvm_unreachable("Bad type for getAlignment!!!");
 658   }
 659
 660   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 661                           abi_or_pref, Ty);
 662 }
 663
 664 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 665   return getAlignment(Ty, true);
 666 }
 667
 668 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 669 /// an integer type of the specified bitwidth.
 670 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 671   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 672 }
 673
 674 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 675   return getAlignment(Ty, false);
 676 }
 677
 678 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 679   unsigned Align = getPrefTypeAlignment(Ty);
 680   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 681   return Log2_32(Align);
 682 }
 683
 684 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 685                                        unsigned AddressSpace) const {
 686   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 687 }
 688
 689 Type *DataLayout::getIntPtrType(Type *Ty) const {
 690   assert(Ty->isPtrOrPtrVectorTy() &&
 691          "Expected a pointer or pointer vector type.");
 692   unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
 693   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 694   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 695     return VectorType::get(IntTy, VecTy->getNumElements());
 696   return IntTy;
 697 }
 698
 699 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 700   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 701     if (Width <= LegalIntWidths[i])
 702       return Type::getIntNTy(C, LegalIntWidths[i]);
 703   return 0;
 704 }
 705
 706 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 707   unsigned MaxWidth = 0;
 708   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 709     MaxWidth = std::max<unsigned>(MaxWidth, LegalIntWidths[i]);
 710   return MaxWidth;
 711 }
 712
 713 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 714                                       ArrayRef<Value *> Indices) const {
 715   Type *Ty = ptrTy;
 716   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 717   uint64_t Result = 0;
 718
 719   generic_gep_type_iterator<Value* const*>
 720     TI = gep_type_begin(ptrTy, Indices);
 721   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 722        ++CurIDX, ++TI) {
 723     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 724       assert(Indices[CurIDX]->getType() ==
 725              Type::getInt32Ty(ptrTy->getContext()) &&
 726              "Illegal struct idx");
 727       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 728
 729       // Get structure layout information...
 730       const StructLayout *Layout = getStructLayout(STy);
 731
 732       // Add in the offset, as calculated by the structure layout info...
 733       Result += Layout->getElementOffset(FieldNo);
 734
 735       // Update Ty to refer to current element
 736       Ty = STy->getElementType(FieldNo);
 737     } else {
 738       // Update Ty to refer to current element
 739       Ty = cast<SequentialType>(Ty)->getElementType();
 740
 741       // Get the array index and the size of each array element.
 742       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 743         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 744     }
 745   }
 746
 747   return Result;
 748 }
 749
 750 /// getPreferredAlignment - Return the preferred alignment of the specified
 751 /// global.  This includes an explicitly requested alignment (if the global
 752 /// has one).
 753 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 754   Type *ElemType = GV->getType()->getElementType();
 755   unsigned Alignment = getPrefTypeAlignment(ElemType);
 756   unsigned GVAlignment = GV->getAlignment();
 757   if (GVAlignment >= Alignment) {
 758     Alignment = GVAlignment;
 759   } else if (GVAlignment != 0) {
 760     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 761   }
 762
 763   if (GV->hasInitializer() && GVAlignment == 0) {
 764     if (Alignment < 16) {
 765       // If the global is not external, see if it is large.  If so, give it a
 766       // larger alignment.
 767       if (getTypeSizeInBits(ElemType) > 128)
 768         Alignment = 16;    // 16-byte alignment.
 769     }
 770   }
 771   return Alignment;
 772 }
 773
 774 /// getPreferredAlignmentLog - Return the preferred alignment of the
 775 /// specified global, returned in log form.  This includes an explicitly
 776 /// requested alignment (if the global has one).
 777 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 778   return Log2_32(getPreferredAlignment(GV));
 779 }