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