TargetData.cpp revision ae6f1fa36b020c89b0f44c4b4222d0f5fd9b6326 
1//===-- TargetData.cpp - Data size & alignment routines --------------------==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines target 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/Target/TargetData.h"
20#include "llvm/Module.h"
21#include "llvm/DerivedTypes.h"
22#include "llvm/Constants.h"
23#include "llvm/Support/GetElementPtrTypeIterator.h"
24#include "llvm/Support/MathExtras.h"
25#include "llvm/Support/ManagedStatic.h"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/StringExtras.h"
28#include <algorithm>
29#include <cstdlib>
30#include <sstream>
31using namespace llvm;
32
33// Handle the Pass registration stuff necessary to use TargetData's.
34namespace {
35  // Register the default SparcV9 implementation...
36  RegisterPass<TargetData> X("targetdata", "Target Data Layout");
37}
38
39//===----------------------------------------------------------------------===//
40// Support for StructLayout
41//===----------------------------------------------------------------------===//
42
43StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
44  StructAlignment = 0;
45  StructSize = 0;
46  NumElements = ST->getNumElements();
47
48  // Loop over each of the elements, placing them in memory...
49  for (unsigned i = 0, e = NumElements; i != e; ++i) {
50    const Type *Ty = ST->getElementType(i);
51    unsigned TyAlign;
52    uint64_t TySize;
53    TyAlign = (ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty));
54    TySize = TD.getTypeSize(Ty);
55
56    // Add padding if necessary to make the data element aligned properly...
57    if (StructSize % TyAlign != 0)
58      StructSize = (StructSize/TyAlign + 1) * TyAlign;   // Add padding...
59
60    // Keep track of maximum alignment constraint
61    StructAlignment = std::max(TyAlign, StructAlignment);
62
63    MemberOffsets[i] = StructSize;
64    StructSize += TySize;                 // 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 != 0)
73    StructSize = (StructSize/StructAlignment + 1) * 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  return SI-&MemberOffsets[0];
89}
90
91//===----------------------------------------------------------------------===//
92// TargetAlignElem, TargetAlign support
93//===----------------------------------------------------------------------===//
94
95TargetAlignElem
96TargetAlignElem::get(AlignTypeEnum align_type, unsigned char abi_align,
97                     unsigned char pref_align, short bit_width) {
98  TargetAlignElem retval;
99  retval.AlignType = align_type;
100  retval.ABIAlign = abi_align;
101  retval.PrefAlign = pref_align;
102  retval.TypeBitWidth = bit_width;
103  return retval;
104}
105
106bool
107TargetAlignElem::operator<(const TargetAlignElem &rhs) const {
108  return ((AlignType < rhs.AlignType)
109          || (AlignType == rhs.AlignType && TypeBitWidth < rhs.TypeBitWidth));
110}
111
112bool
113TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
114  return (AlignType == rhs.AlignType
115          && ABIAlign == rhs.ABIAlign
116          && PrefAlign == rhs.PrefAlign
117          && TypeBitWidth == rhs.TypeBitWidth);
118}
119
120std::ostream &
121TargetAlignElem::dump(std::ostream &os) const {
122  return os << AlignType
123            << TypeBitWidth
124            << ":" << (int) (ABIAlign * 8)
125            << ":" << (int) (PrefAlign * 8);
126}
127
128const TargetAlignElem TargetData::InvalidAlignmentElem =
129                TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
130
131//===----------------------------------------------------------------------===//
132//                       TargetData Class Implementation
133//===----------------------------------------------------------------------===//
134
135/*!
136 A TargetDescription string consists of a sequence of hyphen-delimited
137 specifiers for target endianness, pointer size and alignments, and various
138 primitive type sizes and alignments. A typical string looks something like:
139 <br><br>
140 "E-p:32:32:32-i1:8:8-i8:8:8-i32:32:32-i64:32:64-f32:32:32-f64:32:64"
141 <br><br>
142 (note: this string is not fully specified and is only an example.)
143 \p
144 Alignments come in two flavors: ABI and preferred. ABI alignment (abi_align,
145 below) dictates how a type will be aligned within an aggregate and when used
146 as an argument.  Preferred alignment (pref_align, below) determines a type's
147 alignment when emitted as a global.
148 \p
149 Specifier string details:
150 <br><br>
151 <i>[E|e]</i>: Endianness. "E" specifies a big-endian target data model, "e"
152 specifies a little-endian target data model.
153 <br><br>
154 <i>p:<size>:<abi_align>:<pref_align></i>: Pointer size, ABI and preferred
155 alignment.
156 <br><br>
157 <i><type><size>:<abi_align>:<pref_align></i>: Numeric type alignment. Type is
158 one of <i>i|f|v|a</i>, corresponding to integer, floating point, vector (aka
159 packed) or aggregate.  Size indicates the size, e.g., 32 or 64 bits.
160 \p
161 The default string, fully specified is:
162 <br><br>
163 "E-p:64:64:64-a0:0:0-f32:32:32-f64:0:64"
164 "-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:0:64"
165 "-v64:64:64-v128:128:128"
166 <br><br>
167 Note that in the case of aggregates, 0 is the default ABI and preferred
168 alignment. This is a special case, where the aggregate's computed worst-case
169 alignment will be used.
170 */
171void TargetData::init(const std::string &TargetDescription) {
172  std::string temp = TargetDescription;
173
174  LittleEndian = false;
175  PointerMemSize = 8;
176  PointerABIAlign   = 8;
177  PointerPrefAlign = PointerABIAlign;
178
179  // Default alignments
180  setAlignment(INTEGER_ALIGN,   1,  1, 1);   // Bool
181  setAlignment(INTEGER_ALIGN,   1,  1, 8);   // Byte
182  setAlignment(INTEGER_ALIGN,   2,  2, 16);  // short
183  setAlignment(INTEGER_ALIGN,   4,  4, 32);  // int
184  setAlignment(INTEGER_ALIGN,   4,  8, 64);  // long
185  setAlignment(FLOAT_ALIGN,     4,  4, 32);  // float
186  setAlignment(FLOAT_ALIGN,     8,  8, 64);  // double
187  setAlignment(VECTOR_ALIGN,    8,  8, 64);  // v2i32
188  setAlignment(VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
189  setAlignment(AGGREGATE_ALIGN, 0,  0,  0);  // struct, union, class, ...
190
191  while (!temp.empty()) {
192    std::string token = getToken(temp, "-");
193
194    std::string arg0 = getToken(token, ":");
195    const char *p = arg0.c_str();
196    AlignTypeEnum align_type;
197    short size;
198    unsigned char abi_align;
199    unsigned char pref_align;
200
201    switch(*p) {
202    case 'E':
203      LittleEndian = false;
204      break;
205    case 'e':
206      LittleEndian = true;
207      break;
208    case 'p':
209      PointerMemSize = atoi(getToken(token,":").c_str()) / 8;
210      PointerABIAlign = atoi(getToken(token,":").c_str()) / 8;
211      PointerPrefAlign = atoi(getToken(token,":").c_str()) / 8;
212      if (PointerPrefAlign == 0)
213        PointerPrefAlign = PointerABIAlign;
214      break;
215    case 'i':
216    case 'v':
217    case 'f':
218    case 'a': {
219      align_type = (*p == 'i' ? INTEGER_ALIGN :
220                    (*p == 'f' ? FLOAT_ALIGN :
221                     (*p == 'v' ? VECTOR_ALIGN : AGGREGATE_ALIGN)));
222      size = (short) atoi(++p);
223      abi_align = atoi(getToken(token, ":").c_str()) / 8;
224      pref_align = atoi(getToken(token, ":").c_str()) / 8;
225      if (pref_align == 0)
226        pref_align = abi_align;
227      setAlignment(align_type, abi_align, pref_align, size);
228      break;
229    }
230    default:
231      break;
232    }
233  }
234}
235
236TargetData::TargetData(const Module *M) {
237  init(M->getDataLayout());
238}
239
240void
241TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
242                         unsigned char pref_align, short bit_width) {
243  TargetAlignElem elt = TargetAlignElem::get(align_type, abi_align,
244                                             pref_align, bit_width);
245  std::pair<align_iterator, align_iterator> ins_result =
246            std::equal_range(Alignments.begin(), Alignments.end(), elt);
247  align_iterator I = ins_result.first;
248  if (I != Alignments.end() && I->AlignType == align_type &&
249      I->TypeBitWidth == bit_width) {
250    // Update the abi, preferred alignments.
251    I->ABIAlign = abi_align;
252    I->PrefAlign = pref_align;
253  } else
254    Alignments.insert(I, elt);
255
256#if 0
257  // Keep around for debugging and testing...
258  align_iterator E = ins_result.second;
259
260  cerr << "setAlignment(" << elt << ")\n";
261  cerr << "I = " << (I - Alignments.begin())
262       << ", E = " << (E - Alignments.begin()) << "\n";
263  std::copy(Alignments.begin(), Alignments.end(),
264            std::ostream_iterator<TargetAlignElem>(*cerr, "\n"));
265  cerr << "=====\n";
266#endif
267}
268
269const TargetAlignElem &
270TargetData::getAlignment(AlignTypeEnum align_type, short bit_width) const
271{
272  std::pair<align_const_iterator, align_const_iterator> find_result =
273                std::equal_range(Alignments.begin(), Alignments.end(),
274                                 TargetAlignElem::get(align_type, 0, 0,
275                                                      bit_width));
276  align_const_iterator I = find_result.first;
277
278  // Note: This may not be reasonable if variable-width integer sizes are
279  // passed, at which point, more sophisticated searching will need to be done.
280  return *I;
281}
282
283/// LayoutInfo - The lazy cache of structure layout information maintained by
284/// TargetData.  Note that the struct types must have been free'd before
285/// llvm_shutdown is called (and thus this is deallocated) because all the
286/// targets with cached elements should have been destroyed.
287///
288typedef std::pair<const TargetData*,const StructType*> LayoutKey;
289
290struct DenseMapLayoutKeyInfo {
291  static inline LayoutKey getEmptyKey() { return LayoutKey(0, 0); }
292  static inline LayoutKey getTombstoneKey() {
293    return LayoutKey((TargetData*)(intptr_t)-1, 0);
294  }
295  static unsigned getHashValue(const LayoutKey &Val) {
296    return DenseMapKeyInfo<void*>::getHashValue(Val.first) ^
297           DenseMapKeyInfo<void*>::getHashValue(Val.second);
298  }
299  static bool isPod() { return true; }
300};
301
302typedef DenseMap<LayoutKey, StructLayout*, DenseMapLayoutKeyInfo> LayoutInfoTy;
303static ManagedStatic<LayoutInfoTy> LayoutInfo;
304
305
306TargetData::~TargetData() {
307  if (LayoutInfo.isConstructed()) {
308    // Remove any layouts for this TD.
309    LayoutInfoTy &TheMap = *LayoutInfo;
310    for (LayoutInfoTy::iterator I = TheMap.begin(), E = TheMap.end();
311         I != E; ) {
312      if (I->first.first == this) {
313        I->second->~StructLayout();
314        free(I->second);
315        TheMap.erase(I++);
316      } else {
317        ++I;
318      }
319    }
320  }
321}
322
323const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
324  LayoutInfoTy &TheMap = *LayoutInfo;
325
326  StructLayout *&SL = TheMap[LayoutKey(this, Ty)];
327  if (SL) return SL;
328
329  // Otherwise, create the struct layout.  Because it is variable length, we
330  // malloc it, then use placement new.
331  unsigned NumElts = Ty->getNumElements();
332  StructLayout *L =
333    (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1)*sizeof(uint64_t));
334
335  // Set SL before calling StructLayout's ctor.  The ctor could cause other
336  // entries to be added to TheMap, invalidating our reference.
337  SL = L;
338
339  new (L) StructLayout(Ty, *this);
340
341  return L;
342}
343
344/// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
345/// objects.  If a TargetData object is alive when types are being refined and
346/// removed, this method must be called whenever a StructType is removed to
347/// avoid a dangling pointer in this cache.
348void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
349  if (!LayoutInfo.isConstructed()) return;  // No cache.
350
351  LayoutInfoTy::iterator I = LayoutInfo->find(LayoutKey(this, Ty));
352  if (I != LayoutInfo->end()) {
353    I->second->~StructLayout();
354    free(I->second);
355    LayoutInfo->erase(I);
356  }
357}
358
359
360std::string TargetData::getStringRepresentation() const {
361  std::string repr;
362  repr.append(LittleEndian ? "e" : "E");
363  repr.append("-p:").append(itostr((int64_t) (PointerMemSize * 8))).
364      append(":").append(itostr((int64_t) (PointerABIAlign * 8))).
365      append(":").append(itostr((int64_t) (PointerPrefAlign * 8)));
366  for (align_const_iterator I = Alignments.begin();
367       I != Alignments.end();
368       ++I) {
369    repr.append("-").append(1, (char) I->AlignType).
370      append(utostr((int64_t) I->TypeBitWidth)).
371      append(":").append(utostr((uint64_t) (I->ABIAlign * 8))).
372      append(":").append(utostr((uint64_t) (I->PrefAlign * 8)));
373  }
374  return repr;
375}
376
377
378uint64_t TargetData::getTypeSize(const Type *Ty) const {
379  assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
380  switch (Ty->getTypeID()) {
381  case Type::LabelTyID:
382  case Type::PointerTyID:
383    return getPointerSize();
384  case Type::ArrayTyID: {
385    const ArrayType *ATy = cast<ArrayType>(Ty);
386    uint64_t Size;
387    unsigned char Alignment;
388    Size = getTypeSize(ATy->getElementType());
389    Alignment = getABITypeAlignment(ATy->getElementType());
390    unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
391    return AlignedSize*ATy->getNumElements();
392  }
393  case Type::StructTyID: {
394    // Get the layout annotation... which is lazily created on demand.
395    const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
396    return Layout->getSizeInBytes();
397  }
398  case Type::IntegerTyID: {
399    unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
400    if (BitWidth <= 8) {
401      return 1;
402    } else if (BitWidth <= 16) {
403      return 2;
404    } else if (BitWidth <= 32) {
405      return 4;
406    } else if (BitWidth <= 64) {
407      return 8;
408    } else
409      assert(0 && "Integer types > 64 bits not supported.");
410    break;
411  }
412  case Type::VoidTyID:
413    return 1;
414  case Type::FloatTyID:
415    return 4;
416  case Type::DoubleTyID:
417    return 8;
418  case Type::VectorTyID: {
419    const VectorType *PTy = cast<VectorType>(Ty);
420    return PTy->getBitWidth() / 8;
421  }
422  default:
423    assert(0 && "TargetData::getTypeSize(): Unsupported type");
424    break;
425  }
426  return 0;
427}
428
429uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
430  if (Ty->isInteger())
431    return cast<IntegerType>(Ty)->getBitWidth();
432  else
433    return getTypeSize(Ty) * 8;
434}
435
436
437/*!
438  \param abi_or_pref Flag that determines which alignment is returned. true
439  returns the ABI alignment, false returns the preferred alignment.
440  \param Ty The underlying type for which alignment is determined.
441
442  Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
443  == false) for the requested type \a Ty.
444 */
445unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
446  int AlignType = -1;
447
448  assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
449  switch (Ty->getTypeID()) {
450  /* Early escape for the non-numeric types */
451  case Type::LabelTyID:
452  case Type::PointerTyID:
453    return (abi_or_pref
454            ? getPointerABIAlignment()
455            : getPointerPrefAlignment());
456  case Type::ArrayTyID:
457    return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
458
459  case Type::StructTyID: {
460    // Packed structure types always have an ABI alignment of one.
461    if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
462      return 1;
463
464    // Get the layout annotation... which is lazily created on demand.
465    const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
466    const TargetAlignElem &elem = getAlignment(AGGREGATE_ALIGN, 0);
467    assert(validAlignment(elem)
468           && "Aggregate alignment return invalid in getAlignment");
469    unsigned Align = abi_or_pref ? elem.ABIAlign : elem.PrefAlign;
470    return Align < Layout->getAlignment() ? Layout->StructAlignment : Align;
471  }
472  case Type::IntegerTyID:
473  case Type::VoidTyID:
474    AlignType = INTEGER_ALIGN;
475    break;
476  case Type::FloatTyID:
477  case Type::DoubleTyID:
478    AlignType = FLOAT_ALIGN;
479    break;
480  case Type::VectorTyID:
481    AlignType = VECTOR_ALIGN;
482    break;
483  default:
484    assert(0 && "Bad type for getAlignment!!!");
485    break;
486  }
487
488  const TargetAlignElem &elem = getAlignment((AlignTypeEnum) AlignType,
489                                             getTypeSize(Ty) * 8);
490  if (validAlignment(elem))
491    return (abi_or_pref ? elem.ABIAlign : elem.PrefAlign);
492  else {
493    cerr << "TargetData::getAlignment: align type " << AlignType
494         << " size " << getTypeSize(Ty) << " not found in Alignments.\n";
495    abort();
496    /*NOTREACHED*/
497    return 0;
498  }
499}
500
501unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
502  return getAlignment(Ty, true);
503}
504
505unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
506  return getAlignment(Ty, false);
507}
508
509unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
510  unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
511  assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
512  return Log2_32(Align);
513}
514
515/// getIntPtrType - Return an unsigned integer type that is the same size or
516/// greater to the host pointer size.
517const Type *TargetData::getIntPtrType() const {
518  switch (getPointerSize()) {
519  default: assert(0 && "Unknown pointer size!");
520  case 2: return Type::Int16Ty;
521  case 4: return Type::Int32Ty;
522  case 8: return Type::Int64Ty;
523  }
524}
525
526
527uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
528                                      unsigned NumIndices) const {
529  const Type *Ty = ptrTy;
530  assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
531  uint64_t Result = 0;
532
533  generic_gep_type_iterator<Value* const*>
534    TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
535  for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
536    if (const StructType *STy = dyn_cast<StructType>(*TI)) {
537      assert(Indices[CurIDX]->getType() == Type::Int32Ty &&"Illegal struct idx");
538      unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
539
540      // Get structure layout information...
541      const StructLayout *Layout = getStructLayout(STy);
542
543      // Add in the offset, as calculated by the structure layout info...
544      Result += Layout->getElementOffset(FieldNo);
545
546      // Update Ty to refer to current element
547      Ty = STy->getElementType(FieldNo);
548    } else {
549      // Update Ty to refer to current element
550      Ty = cast<SequentialType>(Ty)->getElementType();
551
552      // Get the array index and the size of each array element.
553      int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
554      Result += arrayIdx * (int64_t)getTypeSize(Ty);
555    }
556  }
557
558  return Result;
559}
560
561/// getPreferredAlignmentLog - Return the preferred alignment of the
562/// specified global, returned in log form.  This includes an explicitly
563/// requested alignment (if the global has one).
564unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
565  const Type *ElemType = GV->getType()->getElementType();
566  unsigned Alignment = getPreferredTypeAlignmentShift(ElemType);
567  if (GV->getAlignment() > (1U << Alignment))
568    Alignment = Log2_32(GV->getAlignment());
569
570  if (GV->hasInitializer()) {
571    if (Alignment < 4) {
572      // If the global is not external, see if it is large.  If so, give it a
573      // larger alignment.
574      if (getTypeSize(ElemType) > 128)
575        Alignment = 4;    // 16-byte alignment.
576    }
577  }
578  return Alignment;
579}
580