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