DataLayout.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
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// Handle the Pass registration stuff necessary to use DataLayout's.
37
38INITIALIZE_PASS(DataLayoutPass, "datalayout", "Data Layout", false, true)
39char DataLayoutPass::ID = 0;
40
41//===----------------------------------------------------------------------===//
42// Support for StructLayout
43//===----------------------------------------------------------------------===//
44
45StructLayout::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.
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.getArch() == Triple::x86 && T.isOSBinFormatCOFF())
159    return "-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  LittleEndian = 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  assert((!Split.second.empty() || Split.first == Str) &&
201         "a trailing separator is not allowed");
202  return Split;
203}
204
205/// Get an unsigned integer, including error checks.
206static unsigned getInt(StringRef R) {
207  unsigned Result;
208  bool error = R.getAsInteger(10, Result); (void)error;
209  if (error)
210    report_fatal_error("not a number, or does not fit in an unsigned int");
211  return Result;
212}
213
214/// Convert bits into bytes. Assert if not a byte width multiple.
215static unsigned inBytes(unsigned Bits) {
216  assert(Bits % 8 == 0 && "number of bits must be a byte width multiple");
217  return Bits / 8;
218}
219
220void DataLayout::parseSpecifier(StringRef Desc) {
221  while (!Desc.empty()) {
222    // Split at '-'.
223    std::pair<StringRef, StringRef> Split = split(Desc, '-');
224    Desc = Split.second;
225
226    // Split at ':'.
227    Split = split(Split.first, ':');
228
229    // Aliases used below.
230    StringRef &Tok  = Split.first;  // Current token.
231    StringRef &Rest = Split.second; // The rest of the string.
232
233    char Specifier = Tok.front();
234    Tok = Tok.substr(1);
235
236    switch (Specifier) {
237    case 's':
238      // Ignored for backward compatibility.
239      // FIXME: remove this on LLVM 4.0.
240      break;
241    case 'E':
242      LittleEndian = false;
243      break;
244    case 'e':
245      LittleEndian = true;
246      break;
247    case 'p': {
248      // Address space.
249      unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
250      assert(AddrSpace < 1 << 24 &&
251             "Invalid address space, must be a 24bit integer");
252
253      // Size.
254      Split = split(Rest, ':');
255      unsigned PointerMemSize = inBytes(getInt(Tok));
256
257      // ABI alignment.
258      Split = split(Rest, ':');
259      unsigned PointerABIAlign = inBytes(getInt(Tok));
260
261      // Preferred alignment.
262      unsigned PointerPrefAlign = PointerABIAlign;
263      if (!Rest.empty()) {
264        Split = split(Rest, ':');
265        PointerPrefAlign = inBytes(getInt(Tok));
266      }
267
268      setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
269                          PointerMemSize);
270      break;
271    }
272    case 'i':
273    case 'v':
274    case 'f':
275    case 'a': {
276      AlignTypeEnum AlignType;
277      switch (Specifier) {
278      default:
279      case 'i': AlignType = INTEGER_ALIGN; break;
280      case 'v': AlignType = VECTOR_ALIGN; break;
281      case 'f': AlignType = FLOAT_ALIGN; break;
282      case 'a': AlignType = AGGREGATE_ALIGN; break;
283      }
284
285      // Bit size.
286      unsigned Size = Tok.empty() ? 0 : getInt(Tok);
287
288      assert((AlignType != AGGREGATE_ALIGN || Size == 0) &&
289             "These specifications don't have a size");
290
291      // ABI alignment.
292      Split = split(Rest, ':');
293      unsigned ABIAlign = inBytes(getInt(Tok));
294
295      // Preferred alignment.
296      unsigned PrefAlign = ABIAlign;
297      if (!Rest.empty()) {
298        Split = split(Rest, ':');
299        PrefAlign = inBytes(getInt(Tok));
300      }
301
302      setAlignment(AlignType, ABIAlign, PrefAlign, Size);
303
304      break;
305    }
306    case 'n':  // Native integer types.
307      for (;;) {
308        unsigned Width = getInt(Tok);
309        assert(Width != 0 && "width must be non-zero");
310        LegalIntWidths.push_back(Width);
311        if (Rest.empty())
312          break;
313        Split = split(Rest, ':');
314      }
315      break;
316    case 'S': { // Stack natural alignment.
317      StackNaturalAlign = inBytes(getInt(Tok));
318      break;
319    }
320    case 'm':
321      assert(Tok.empty());
322      assert(Rest.size() == 1);
323      switch(Rest[0]) {
324      default:
325        llvm_unreachable("Unknown mangling in datalayout string");
326      case 'e':
327        ManglingMode = MM_ELF;
328        break;
329      case 'o':
330        ManglingMode = MM_MachO;
331        break;
332      case 'm':
333        ManglingMode = MM_Mips;
334        break;
335      case 'w':
336        ManglingMode = MM_WINCOFF;
337        break;
338      }
339      break;
340    default:
341      llvm_unreachable("Unknown specifier in datalayout string");
342      break;
343    }
344  }
345}
346
347DataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) {
348  const DataLayout *Other = M->getDataLayout();
349  if (Other)
350    *this = *Other;
351  else
352    reset("");
353}
354
355bool DataLayout::operator==(const DataLayout &Other) const {
356  bool Ret = LittleEndian == Other.LittleEndian &&
357             StackNaturalAlign == Other.StackNaturalAlign &&
358             ManglingMode == Other.ManglingMode &&
359             LegalIntWidths == Other.LegalIntWidths &&
360             Alignments == Other.Alignments && Pointers == Other.Pointers;
361  assert(Ret == (getStringRepresentation() == Other.getStringRepresentation()));
362  return Ret;
363}
364
365void
366DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
367                         unsigned pref_align, uint32_t bit_width) {
368  assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
369  assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
370  assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
371  for (LayoutAlignElem &Elem : Alignments) {
372    if (Elem.AlignType == (unsigned)align_type &&
373        Elem.TypeBitWidth == bit_width) {
374      // Update the abi, preferred alignments.
375      Elem.ABIAlign = abi_align;
376      Elem.PrefAlign = pref_align;
377      return;
378    }
379  }
380
381  Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
382                                            pref_align, bit_width));
383}
384
385DataLayout::PointersTy::iterator
386DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
387  return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
388                          [](const PointerAlignElem &A, uint32_t AddressSpace) {
389    return A.AddressSpace < AddressSpace;
390  });
391}
392
393void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
394                                     unsigned PrefAlign,
395                                     uint32_t TypeByteWidth) {
396  assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
397  PointersTy::iterator I = findPointerLowerBound(AddrSpace);
398  if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
399    Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
400                                             TypeByteWidth));
401  } else {
402    I->ABIAlign = ABIAlign;
403    I->PrefAlign = PrefAlign;
404    I->TypeByteWidth = TypeByteWidth;
405  }
406}
407
408/// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
409/// preferred if ABIInfo = false) the layout wants for the specified datatype.
410unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
411                                      uint32_t BitWidth, bool ABIInfo,
412                                      Type *Ty) const {
413  // Check to see if we have an exact match and remember the best match we see.
414  int BestMatchIdx = -1;
415  int LargestInt = -1;
416  for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
417    if (Alignments[i].AlignType == (unsigned)AlignType &&
418        Alignments[i].TypeBitWidth == BitWidth)
419      return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
420
421    // The best match so far depends on what we're looking for.
422     if (AlignType == INTEGER_ALIGN &&
423         Alignments[i].AlignType == INTEGER_ALIGN) {
424      // The "best match" for integers is the smallest size that is larger than
425      // the BitWidth requested.
426      if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
427          Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
428        BestMatchIdx = i;
429      // However, if there isn't one that's larger, then we must use the
430      // largest one we have (see below)
431      if (LargestInt == -1 ||
432          Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
433        LargestInt = i;
434    }
435  }
436
437  // Okay, we didn't find an exact solution.  Fall back here depending on what
438  // is being looked for.
439  if (BestMatchIdx == -1) {
440    // If we didn't find an integer alignment, fall back on most conservative.
441    if (AlignType == INTEGER_ALIGN) {
442      BestMatchIdx = LargestInt;
443    } else {
444      assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
445
446      // By default, use natural alignment for vector types. This is consistent
447      // with what clang and llvm-gcc do.
448      unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
449      Align *= cast<VectorType>(Ty)->getNumElements();
450      // If the alignment is not a power of 2, round up to the next power of 2.
451      // This happens for non-power-of-2 length vectors.
452      if (Align & (Align-1))
453        Align = NextPowerOf2(Align);
454      return Align;
455    }
456  }
457
458  // Since we got a "best match" index, just return it.
459  return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
460                 : Alignments[BestMatchIdx].PrefAlign;
461}
462
463namespace {
464
465class StructLayoutMap {
466  typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
467  LayoutInfoTy LayoutInfo;
468
469public:
470  ~StructLayoutMap() {
471    // Remove any layouts.
472    for (const auto &I : LayoutInfo) {
473      StructLayout *Value = I.second;
474      Value->~StructLayout();
475      free(Value);
476    }
477  }
478
479  StructLayout *&operator[](StructType *STy) {
480    return LayoutInfo[STy];
481  }
482};
483
484} // end anonymous namespace
485
486void DataLayout::clear() {
487  LegalIntWidths.clear();
488  Alignments.clear();
489  Pointers.clear();
490  delete static_cast<StructLayoutMap *>(LayoutMap);
491  LayoutMap = nullptr;
492}
493
494DataLayout::~DataLayout() {
495  clear();
496}
497
498const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
499  if (!LayoutMap)
500    LayoutMap = new StructLayoutMap();
501
502  StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
503  StructLayout *&SL = (*STM)[Ty];
504  if (SL) return SL;
505
506  // Otherwise, create the struct layout.  Because it is variable length, we
507  // malloc it, then use placement new.
508  int NumElts = Ty->getNumElements();
509  StructLayout *L =
510    (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
511
512  // Set SL before calling StructLayout's ctor.  The ctor could cause other
513  // entries to be added to TheMap, invalidating our reference.
514  SL = L;
515
516  new (L) StructLayout(Ty, *this);
517
518  return L;
519}
520
521std::string DataLayout::getStringRepresentation() const {
522  std::string Result;
523  raw_string_ostream OS(Result);
524
525  OS << (LittleEndian ? "e" : "E");
526
527  switch (ManglingMode) {
528  case MM_None:
529    break;
530  case MM_ELF:
531    OS << "-m:e";
532    break;
533  case MM_MachO:
534    OS << "-m:o";
535    break;
536  case MM_WINCOFF:
537    OS << "-m:w";
538    break;
539  case MM_Mips:
540    OS << "-m:m";
541    break;
542  }
543
544  for (const PointerAlignElem &PI : Pointers) {
545    // Skip default.
546    if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
547        PI.TypeByteWidth == 8)
548      continue;
549
550    OS << "-p";
551    if (PI.AddressSpace) {
552      OS << PI.AddressSpace;
553    }
554    OS << ":" << PI.TypeByteWidth*8 << ':' << PI.ABIAlign*8;
555    if (PI.PrefAlign != PI.ABIAlign)
556      OS << ':' << PI.PrefAlign*8;
557  }
558
559  for (const LayoutAlignElem &AI : Alignments) {
560    if (std::find(std::begin(DefaultAlignments), std::end(DefaultAlignments),
561                  AI) != std::end(DefaultAlignments))
562      continue;
563    OS << '-' << (char)AI.AlignType;
564    if (AI.TypeBitWidth)
565      OS << AI.TypeBitWidth;
566    OS << ':' << AI.ABIAlign*8;
567    if (AI.ABIAlign != AI.PrefAlign)
568      OS << ':' << AI.PrefAlign*8;
569  }
570
571  if (!LegalIntWidths.empty()) {
572    OS << "-n" << (unsigned)LegalIntWidths[0];
573
574    for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
575      OS << ':' << (unsigned)LegalIntWidths[i];
576  }
577
578  if (StackNaturalAlign)
579    OS << "-S" << StackNaturalAlign*8;
580
581  return OS.str();
582}
583
584unsigned DataLayout::getPointerABIAlignment(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->ABIAlign;
591}
592
593unsigned DataLayout::getPointerPrefAlignment(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->PrefAlign;
600}
601
602unsigned DataLayout::getPointerSize(unsigned AS) const {
603  PointersTy::const_iterator I = findPointerLowerBound(AS);
604  if (I == Pointers.end() || I->AddressSpace != AS) {
605    I = findPointerLowerBound(0);
606    assert(I->AddressSpace == 0);
607  }
608  return I->TypeByteWidth;
609}
610
611unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
612  assert(Ty->isPtrOrPtrVectorTy() &&
613         "This should only be called with a pointer or pointer vector type");
614
615  if (Ty->isPointerTy())
616    return getTypeSizeInBits(Ty);
617
618  return getTypeSizeInBits(Ty->getScalarType());
619}
620
621/*!
622  \param abi_or_pref Flag that determines which alignment is returned. true
623  returns the ABI alignment, false returns the preferred alignment.
624  \param Ty The underlying type for which alignment is determined.
625
626  Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
627  == false) for the requested type \a Ty.
628 */
629unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
630  int AlignType = -1;
631
632  assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
633  switch (Ty->getTypeID()) {
634  // Early escape for the non-numeric types.
635  case Type::LabelTyID:
636    return (abi_or_pref
637            ? getPointerABIAlignment(0)
638            : getPointerPrefAlignment(0));
639  case Type::PointerTyID: {
640    unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
641    return (abi_or_pref
642            ? getPointerABIAlignment(AS)
643            : getPointerPrefAlignment(AS));
644    }
645  case Type::ArrayTyID:
646    return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
647
648  case Type::StructTyID: {
649    // Packed structure types always have an ABI alignment of one.
650    if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
651      return 1;
652
653    // Get the layout annotation... which is lazily created on demand.
654    const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
655    unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
656    return std::max(Align, Layout->getAlignment());
657  }
658  case Type::IntegerTyID:
659    AlignType = INTEGER_ALIGN;
660    break;
661  case Type::HalfTyID:
662  case Type::FloatTyID:
663  case Type::DoubleTyID:
664  // PPC_FP128TyID and FP128TyID have different data contents, but the
665  // same size and alignment, so they look the same here.
666  case Type::PPC_FP128TyID:
667  case Type::FP128TyID:
668  case Type::X86_FP80TyID:
669    AlignType = FLOAT_ALIGN;
670    break;
671  case Type::X86_MMXTyID:
672  case Type::VectorTyID:
673    AlignType = VECTOR_ALIGN;
674    break;
675  default:
676    llvm_unreachable("Bad type for getAlignment!!!");
677  }
678
679  return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
680                          abi_or_pref, Ty);
681}
682
683unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
684  return getAlignment(Ty, true);
685}
686
687/// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
688/// an integer type of the specified bitwidth.
689unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
690  return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
691}
692
693unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
694  return getAlignment(Ty, false);
695}
696
697unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
698  unsigned Align = getPrefTypeAlignment(Ty);
699  assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
700  return Log2_32(Align);
701}
702
703IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
704                                       unsigned AddressSpace) const {
705  return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
706}
707
708Type *DataLayout::getIntPtrType(Type *Ty) const {
709  assert(Ty->isPtrOrPtrVectorTy() &&
710         "Expected a pointer or pointer vector type.");
711  unsigned NumBits = getPointerTypeSizeInBits(Ty);
712  IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
713  if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
714    return VectorType::get(IntTy, VecTy->getNumElements());
715  return IntTy;
716}
717
718Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
719  for (unsigned LegalIntWidth : LegalIntWidths)
720    if (Width <= LegalIntWidth)
721      return Type::getIntNTy(C, LegalIntWidth);
722  return nullptr;
723}
724
725unsigned DataLayout::getLargestLegalIntTypeSize() const {
726  auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
727  return Max != LegalIntWidths.end() ? *Max : 0;
728}
729
730uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
731                                      ArrayRef<Value *> Indices) const {
732  Type *Ty = ptrTy;
733  assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
734  uint64_t Result = 0;
735
736  generic_gep_type_iterator<Value* const*>
737    TI = gep_type_begin(ptrTy, Indices);
738  for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
739       ++CurIDX, ++TI) {
740    if (StructType *STy = dyn_cast<StructType>(*TI)) {
741      assert(Indices[CurIDX]->getType() ==
742             Type::getInt32Ty(ptrTy->getContext()) &&
743             "Illegal struct idx");
744      unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
745
746      // Get structure layout information...
747      const StructLayout *Layout = getStructLayout(STy);
748
749      // Add in the offset, as calculated by the structure layout info...
750      Result += Layout->getElementOffset(FieldNo);
751
752      // Update Ty to refer to current element
753      Ty = STy->getElementType(FieldNo);
754    } else {
755      // Update Ty to refer to current element
756      Ty = cast<SequentialType>(Ty)->getElementType();
757
758      // Get the array index and the size of each array element.
759      if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
760        Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
761    }
762  }
763
764  return Result;
765}
766
767/// getPreferredAlignment - Return the preferred alignment of the specified
768/// global.  This includes an explicitly requested alignment (if the global
769/// has one).
770unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
771  Type *ElemType = GV->getType()->getElementType();
772  unsigned Alignment = getPrefTypeAlignment(ElemType);
773  unsigned GVAlignment = GV->getAlignment();
774  if (GVAlignment >= Alignment) {
775    Alignment = GVAlignment;
776  } else if (GVAlignment != 0) {
777    Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
778  }
779
780  if (GV->hasInitializer() && GVAlignment == 0) {
781    if (Alignment < 16) {
782      // If the global is not external, see if it is large.  If so, give it a
783      // larger alignment.
784      if (getTypeSizeInBits(ElemType) > 128)
785        Alignment = 16;    // 16-byte alignment.
786    }
787  }
788  return Alignment;
789}
790
791/// getPreferredAlignmentLog - Return the preferred alignment of the
792/// specified global, returned in log form.  This includes an explicitly
793/// requested alignment (if the global has one).
794unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
795  return Log2_32(getPreferredAlignment(GV));
796}
797
798DataLayoutPass::DataLayoutPass() : ImmutablePass(ID), DL("") {
799  report_fatal_error("Bad DataLayoutPass ctor used. Tool did not specify a "
800                     "DataLayout to use?");
801}
802
803DataLayoutPass::~DataLayoutPass() {}
804
805DataLayoutPass::DataLayoutPass(const DataLayout &DL)
806    : ImmutablePass(ID), DL(DL) {
807  initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
808}
809
810DataLayoutPass::DataLayoutPass(const Module *M) : ImmutablePass(ID), DL(M) {
811  initializeDataLayoutPassPass(*PassRegistry::getPassRegistry());
812}
813