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