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 INITIALIZE_PASS(DataLayoutPass, "datalayout", "Data Layout", false, true)
  39 char DataLayoutPass::ID = 0;
  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   NumElements = ST->getNumElements();
  50
  51   // Loop over each of the elements, placing them in memory.
  52   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  53     Type *Ty = ST->getElementType(i);
  54     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
  55
  56     // Add padding if necessary to align the data element properly.
  57     if ((StructSize & (TyAlign-1)) != 0)
  58       StructSize = DataLayout::RoundUpAlignment(StructSize, TyAlign);
  59
  60     // Keep track of maximum alignment constraint.
  61     StructAlignment = std::max(TyAlign, StructAlignment);
  62
  63     MemberOffsets[i] = StructSize;
  64     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
  65   }
  66
  67   // Empty structures have alignment of 1 byte.
  68   if (StructAlignment == 0) StructAlignment = 1;
  69
  70   // Add padding to the end of the struct so that it could be put in an array
  71   // and all array elements would be aligned correctly.
  72   if ((StructSize & (StructAlignment-1)) != 0)
  73     StructSize = DataLayout::RoundUpAlignment(StructSize, StructAlignment);
  74 }
  75
  76
  77 /// getElementContainingOffset - Given a valid offset into the structure,
  78 /// return the structure index that contains it.
  79 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  80   const uint64_t *SI =
  81     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  82   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  83   --SI;
  84   assert(*SI <= Offset && "upper_bound didn't work");
  85   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  86          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  87          "Upper bound didn't work!");
  88
  89   // Multiple fields can have the same offset if any of them are zero sized.
  90   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  91   // at the i32 element, because it is the last element at that offset.  This is
  92   // the right one to return, because anything after it will have a higher
  93   // offset, implying that this element is non-empty.
  94   return SI-&MemberOffsets[0];
  95 }
  96
  97 //===----------------------------------------------------------------------===//
  98 // LayoutAlignElem, LayoutAlign support
  99 //===----------------------------------------------------------------------===//
 100
 101 LayoutAlignElem
 102 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
 103                      unsigned pref_align, uint32_t bit_width) {
 104   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 105   LayoutAlignElem retval;
 106   retval.AlignType = align_type;
 107   retval.ABIAlign = abi_align;
 108   retval.PrefAlign = pref_align;
 109   retval.TypeBitWidth = bit_width;
 110   return retval;
 111 }
 112
 113 bool
 114 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
 115   return (AlignType == rhs.AlignType
 116           && ABIAlign == rhs.ABIAlign
 117           && PrefAlign == rhs.PrefAlign
 118           && TypeBitWidth == rhs.TypeBitWidth);
 119 }
 120
 121 const LayoutAlignElem
 122 DataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 };
 123
 124 //===----------------------------------------------------------------------===//
 125 // PointerAlignElem, PointerAlign support
 126 //===----------------------------------------------------------------------===//
 127
 128 PointerAlignElem
 129 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
 130                       unsigned PrefAlign, uint32_t TypeByteWidth) {
 131   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 132   PointerAlignElem retval;
 133   retval.AddressSpace = AddressSpace;
 134   retval.ABIAlign = ABIAlign;
 135   retval.PrefAlign = PrefAlign;
 136   retval.TypeByteWidth = TypeByteWidth;
 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           && TypeByteWidth == rhs.TypeByteWidth);
 146 }
 147
 148 const PointerAlignElem
 149 DataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U };
 150
 151 //===----------------------------------------------------------------------===//
 152 //                       DataLayout Class Implementation
 153 //===----------------------------------------------------------------------===//
 154
 155 const char *DataLayout::getManglingComponent(const Triple &T) {
 156   if (T.isOSBinFormatMachO())
 157     return "-m:o";
 158   if (T.isOSBinFormatELF() || T.isArch64Bit())
 159     return "-m:e";
 160   assert(T.isOSBinFormatCOFF());
 161   return "-m:w";
 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 = 0;
 183   LittleEndian = false;
 184   StackNaturalAlign = 0;
 185   ManglingMode = MM_None;
 186
 187   // Default alignments
 188   for (int I = 0, N = array_lengthof(DefaultAlignments); I < N; ++I) {
 189     const LayoutAlignElem &E = DefaultAlignments[I];
 190     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
 191                  E.TypeBitWidth);
 192   }
 193   setPointerAlignment(0, 8, 8, 8);
 194
 195   parseSpecifier(Desc);
 196 }
 197
 198 /// Checked version of split, to ensure mandatory subparts.
 199 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
 200   assert(!Str.empty() && "parse error, string can't be empty here");
 201   std::pair<StringRef, StringRef> Split = Str.split(Separator);
 202   assert((!Split.second.empty() || Split.first == Str) &&
 203          "a trailing separator is not allowed");
 204   return Split;
 205 }
 206
 207 /// Get an unsigned integer, including error checks.
 208 static unsigned getInt(StringRef R) {
 209   unsigned Result;
 210   bool error = R.getAsInteger(10, Result); (void)error;
 211   if (error)
 212     report_fatal_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 'w':
 338         ManglingMode = MM_WINCOFF;
 339         break;
 340       }
 341       break;
 342     default:
 343       llvm_unreachable("Unknown specifier in datalayout string");
 344       break;
 345     }
 346   }
 347 }
 348
 349 DataLayout::DataLayout(const Module *M) : LayoutMap(0) {
 350   const DataLayout *Other = M->getDataLayout();
 351   if (Other)
 352     *this = *Other;
 353   else
 354     reset("");
 355 }
 356
 357 void
 358 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
 359                          unsigned pref_align, uint32_t bit_width) {
 360   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 361   assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
 362   assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
 363   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 364     if (Alignments[i].AlignType == (unsigned)align_type &&
 365         Alignments[i].TypeBitWidth == bit_width) {
 366       // Update the abi, preferred alignments.
 367       Alignments[i].ABIAlign = abi_align;
 368       Alignments[i].PrefAlign = pref_align;
 369       return;
 370     }
 371   }
 372
 373   Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
 374                                             pref_align, bit_width));
 375 }
 376
 377 static bool comparePointerAlignElem(const PointerAlignElem &A,
 378                                     uint32_t AddressSpace) {
 379   return A.AddressSpace < AddressSpace;
 380 }
 381
 382 DataLayout::PointersTy::iterator
 383 DataLayout::findPoiterLowerBound(uint32_t AddressSpace) {
 384   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
 385                           comparePointerAlignElem);
 386 }
 387
 388 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
 389                                      unsigned PrefAlign,
 390                                      uint32_t TypeByteWidth) {
 391   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
 392   PointersTy::iterator I = findPoiterLowerBound(AddrSpace);
 393   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
 394     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
 395                                              TypeByteWidth));
 396   } else {
 397     I->ABIAlign = ABIAlign;
 398     I->PrefAlign = PrefAlign;
 399     I->TypeByteWidth = TypeByteWidth;
 400   }
 401 }
 402
 403 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 404 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 405 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
 406                                       uint32_t BitWidth, bool ABIInfo,
 407                                       Type *Ty) const {
 408   // Check to see if we have an exact match and remember the best match we see.
 409   int BestMatchIdx = -1;
 410   int LargestInt = -1;
 411   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 412     if (Alignments[i].AlignType == (unsigned)AlignType &&
 413         Alignments[i].TypeBitWidth == BitWidth)
 414       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 415
 416     // The best match so far depends on what we're looking for.
 417      if (AlignType == INTEGER_ALIGN &&
 418          Alignments[i].AlignType == INTEGER_ALIGN) {
 419       // The "best match" for integers is the smallest size that is larger than
 420       // the BitWidth requested.
 421       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 422           Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 423         BestMatchIdx = i;
 424       // However, if there isn't one that's larger, then we must use the
 425       // largest one we have (see below)
 426       if (LargestInt == -1 ||
 427           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 428         LargestInt = i;
 429     }
 430   }
 431
 432   // Okay, we didn't find an exact solution.  Fall back here depending on what
 433   // is being looked for.
 434   if (BestMatchIdx == -1) {
 435     // If we didn't find an integer alignment, fall back on most conservative.
 436     if (AlignType == INTEGER_ALIGN) {
 437       BestMatchIdx = LargestInt;
 438     } else {
 439       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 440
 441       // By default, use natural alignment for vector types. This is consistent
 442       // with what clang and llvm-gcc do.
 443       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 444       Align *= cast<VectorType>(Ty)->getNumElements();
 445       // If the alignment is not a power of 2, round up to the next power of 2.
 446       // This happens for non-power-of-2 length vectors.
 447       if (Align & (Align-1))
 448         Align = NextPowerOf2(Align);
 449       return Align;
 450     }
 451   }
 452
 453   // Since we got a "best match" index, just return it.
 454   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 455                  : Alignments[BestMatchIdx].PrefAlign;
 456 }
 457
 458 namespace {
 459
 460 class StructLayoutMap {
 461   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
 462   LayoutInfoTy LayoutInfo;
 463
 464 public:
 465   virtual ~StructLayoutMap() {
 466     // Remove any layouts.
 467     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
 468          I != E; ++I) {
 469       StructLayout *Value = I->second;
 470       Value->~StructLayout();
 471       free(Value);
 472     }
 473   }
 474
 475   StructLayout *&operator[](StructType *STy) {
 476     return LayoutInfo[STy];
 477   }
 478
 479   // for debugging...
 480   virtual void dump() const {}
 481 };
 482
 483 } // end anonymous namespace
 484
 485 void DataLayout::clear() {
 486   LegalIntWidths.clear();
 487   Alignments.clear();
 488   Pointers.clear();
 489   delete static_cast<StructLayoutMap *>(LayoutMap);
 490   LayoutMap = 0;
 491 }
 492
 493 DataLayout::~DataLayout() {
 494   clear();
 495 }
 496
 497 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
 498   if (!LayoutMap)
 499     LayoutMap = new StructLayoutMap();
 500
 501   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 502   StructLayout *&SL = (*STM)[Ty];
 503   if (SL) return SL;
 504
 505   // Otherwise, create the struct layout.  Because it is variable length, we
 506   // malloc it, then use placement new.
 507   int NumElts = Ty->getNumElements();
 508   StructLayout *L =
 509     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 510
 511   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 512   // entries to be added to TheMap, invalidating our reference.
 513   SL = L;
 514
 515   new (L) StructLayout(Ty, *this);
 516
 517   return L;
 518 }
 519
 520 std::string DataLayout::getStringRepresentation() const {
 521   std::string Result;
 522   raw_string_ostream OS(Result);
 523
 524   OS << (LittleEndian ? "e" : "E");
 525
 526   switch (ManglingMode) {
 527   case MM_None:
 528     break;
 529   case MM_ELF:
 530     OS << "-m:e";
 531     break;
 532   case MM_MachO:
 533     OS << "-m:o";
 534     break;
 535   case MM_WINCOFF:
 536     OS << "-m:w";
 537     break;
 538   case MM_Mips:
 539     OS << "-m:m";
 540     break;
 541   }
 542
 543   for (PointersTy::const_iterator I = Pointers.begin(), E = Pointers.end();
 544        I != E; ++I) {
 545     const PointerAlignElem &PI = *I;
 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::getPointerABIAlignment(unsigned AS) const {
 590   PointersTy::const_iterator I = findPoiterLowerBound(AS);
 591   if (I == Pointers.end() || I->AddressSpace != AS) {
 592     I = findPoiterLowerBound(0);
 593     assert(I->AddressSpace == 0);
 594   }
 595   return I->ABIAlign;
 596 }
 597
 598 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
 599   PointersTy::const_iterator I = findPoiterLowerBound(AS);
 600   if (I == Pointers.end() || I->AddressSpace != AS) {
 601     I = findPoiterLowerBound(0);
 602     assert(I->AddressSpace == 0);
 603   }
 604   return I->PrefAlign;
 605 }
 606
 607 unsigned DataLayout::getPointerSize(unsigned AS) const {
 608   PointersTy::const_iterator I = findPoiterLowerBound(AS);
 609   if (I == Pointers.end() || I->AddressSpace != AS) {
 610     I = findPoiterLowerBound(0);
 611     assert(I->AddressSpace == 0);
 612   }
 613   return I->TypeByteWidth;
 614 }
 615
 616 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
 617   assert(Ty->isPtrOrPtrVectorTy() &&
 618          "This should only be called with a pointer or pointer vector type");
 619
 620   if (Ty->isPointerTy())
 621     return getTypeSizeInBits(Ty);
 622
 623   return getTypeSizeInBits(Ty->getScalarType());
 624 }
 625
 626 /*!
 627   \param abi_or_pref Flag that determines which alignment is returned. true
 628   returns the ABI alignment, false returns the preferred alignment.
 629   \param Ty The underlying type for which alignment is determined.
 630
 631   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 632   == false) for the requested type \a Ty.
 633  */
 634 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
 635   int AlignType = -1;
 636
 637   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 638   switch (Ty->getTypeID()) {
 639   // Early escape for the non-numeric types.
 640   case Type::LabelTyID:
 641     return (abi_or_pref
 642             ? getPointerABIAlignment(0)
 643             : getPointerPrefAlignment(0));
 644   case Type::PointerTyID: {
 645     unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
 646     return (abi_or_pref
 647             ? getPointerABIAlignment(AS)
 648             : getPointerPrefAlignment(AS));
 649     }
 650   case Type::ArrayTyID:
 651     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 652
 653   case Type::StructTyID: {
 654     // Packed structure types always have an ABI alignment of one.
 655     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 656       return 1;
 657
 658     // Get the layout annotation... which is lazily created on demand.
 659     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 660     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 661     return std::max(Align, Layout->getAlignment());
 662   }
 663   case Type::IntegerTyID:
 664     AlignType = INTEGER_ALIGN;
 665     break;
 666   case Type::HalfTyID:
 667   case Type::FloatTyID:
 668   case Type::DoubleTyID:
 669   // PPC_FP128TyID and FP128TyID have different data contents, but the
 670   // same size and alignment, so they look the same here.
 671   case Type::PPC_FP128TyID:
 672   case Type::FP128TyID:
 673   case Type::X86_FP80TyID:
 674     AlignType = FLOAT_ALIGN;
 675     break;
 676   case Type::X86_MMXTyID:
 677   case Type::VectorTyID:
 678     AlignType = VECTOR_ALIGN;
 679     break;
 680   default:
 681     llvm_unreachable("Bad type for getAlignment!!!");
 682   }
 683
 684   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 685                           abi_or_pref, Ty);
 686 }
 687
 688 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
 689   return getAlignment(Ty, true);
 690 }
 691
 692 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 693 /// an integer type of the specified bitwidth.
 694 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 695   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 696 }
 697
 698 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
 699   return getAlignment(Ty, false);
 700 }
 701
 702 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
 703   unsigned Align = getPrefTypeAlignment(Ty);
 704   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 705   return Log2_32(Align);
 706 }
 707
 708 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
 709                                        unsigned AddressSpace) const {
 710   return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
 711 }
 712
 713 Type *DataLayout::getIntPtrType(Type *Ty) const {
 714   assert(Ty->isPtrOrPtrVectorTy() &&
 715          "Expected a pointer or pointer vector type.");
 716   unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
 717   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
 718   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
 719     return VectorType::get(IntTy, VecTy->getNumElements());
 720   return IntTy;
 721 }
 722
 723 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
 724   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 725     if (Width <= LegalIntWidths[i])
 726       return Type::getIntNTy(C, LegalIntWidths[i]);
 727   return 0;
 728 }
 729
 730 unsigned DataLayout::getLargestLegalIntTypeSize() const {
 731   unsigned MaxWidth = 0;
 732   for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
 733     MaxWidth = std::max<unsigned>(MaxWidth, LegalIntWidths[i]);
 734   return MaxWidth;
 735 }
 736
 737 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
 738                                       ArrayRef<Value *> Indices) const {
 739   Type *Ty = ptrTy;
 740   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 741   uint64_t Result = 0;
 742
 743   generic_gep_type_iterator<Value* const*>
 744     TI = gep_type_begin(ptrTy, Indices);
 745   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
 746        ++CurIDX, ++TI) {
 747     if (StructType *STy = dyn_cast<StructType>(*TI)) {
 748       assert(Indices[CurIDX]->getType() ==
 749              Type::getInt32Ty(ptrTy->getContext()) &&
 750              "Illegal struct idx");
 751       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 752
 753       // Get structure layout information...
 754       const StructLayout *Layout = getStructLayout(STy);
 755
 756       // Add in the offset, as calculated by the structure layout info...
 757       Result += Layout->getElementOffset(FieldNo);
 758
 759       // Update Ty to refer to current element
 760       Ty = STy->getElementType(FieldNo);
 761     } else {
 762       // Update Ty to refer to current element
 763       Ty = cast<SequentialType>(Ty)->getElementType();
 764
 765       // Get the array index and the size of each array element.
 766       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 767         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
 768     }
 769   }
 770
 771   return Result;
 772 }
 773
 774 /// getPreferredAlignment - Return the preferred alignment of the specified
 775 /// global.  This includes an explicitly requested alignment (if the global
 776 /// has one).
 777 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
 778   Type *ElemType = GV->getType()->getElementType();
 779   unsigned Alignment = getPrefTypeAlignment(ElemType);
 780   unsigned GVAlignment = GV->getAlignment();
 781   if (GVAlignment >= Alignment) {
 782     Alignment = GVAlignment;
 783   } else if (GVAlignment != 0) {
 784     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
 785   }
 786
 787   if (GV->hasInitializer() && GVAlignment == 0) {
 788     if (Alignment < 16) {
 789       // If the global is not external, see if it is large.  If so, give it a
 790       // larger alignment.
 791       if (getTypeSizeInBits(ElemType) > 128)
 792         Alignment = 16;    // 16-byte alignment.
 793     }
 794   }
 795   return Alignment;
 796 }
 797
 798 /// getPreferredAlignmentLog - Return the preferred alignment of the
 799 /// specified global, returned in log form.  This includes an explicitly
 800 /// requested alignment (if the global has one).
 801 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 802   return Log2_32(getPreferredAlignment(GV));
 803 }
 804
 805 DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
 806   report_fatal_error("Bad DataLayoutPass ctor used. Tool did not specify a "
 807                      "DataLayout to use?");
 808 }
 809
 810 DataLayoutPass::~DataLayoutPass() {}
 811
 812 DataLayoutPass::DataLayoutPass(const DataLayout &DL)
 813     : ImmutablePass(ID), DL(DL) {
 814   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 815 }
 816
 817 DataLayoutPass::DataLayoutPass(const Module *M) : ImmutablePass(ID), DL(M) {
 818   initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
 819 }