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