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