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