1//===--------- llvm/DataLayout.h - Data size & alignment info ---*- C++ -*-===//
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.  It uses lazy annotations to cache information about how
12// structure types are laid out and used.
13//
14// This structure should be created once, filled in if the defaults are not
15// correct and then passed around by const&.  None of the members functions
16// require modification to the object.
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_IR_DATALAYOUT_H
21#define LLVM_IR_DATALAYOUT_H
22
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/IR/DerivedTypes.h"
26#include "llvm/IR/Type.h"
27#include "llvm/Pass.h"
28#include "llvm/Support/DataTypes.h"
29
30// This needs to be outside of the namespace, to avoid conflict with llvm-c
31// decl.
32typedef struct LLVMOpaqueTargetData *LLVMTargetDataRef;
33
34namespace llvm {
35
36class Value;
37class Type;
38class IntegerType;
39class StructType;
40class StructLayout;
41class Triple;
42class GlobalVariable;
43class LLVMContext;
44template<typename T>
45class ArrayRef;
46
47/// Enum used to categorize the alignment types stored by LayoutAlignElem
48enum AlignTypeEnum {
49  INVALID_ALIGN = 0,
50  INTEGER_ALIGN = 'i',
51  VECTOR_ALIGN = 'v',
52  FLOAT_ALIGN = 'f',
53  AGGREGATE_ALIGN = 'a'
54};
55
56// FIXME: Currently the DataLayout string carries a "preferred alignment"
57// for types. As the DataLayout is module/global, this should likely be
58// sunk down to an FTTI element that is queried rather than a global
59// preference.
60
61/// \brief Layout alignment element.
62///
63/// Stores the alignment data associated with a given alignment type (integer,
64/// vector, float) and type bit width.
65///
66/// \note The unusual order of elements in the structure attempts to reduce
67/// padding and make the structure slightly more cache friendly.
68struct LayoutAlignElem {
69  /// \brief Alignment type from \c AlignTypeEnum
70  unsigned AlignType : 8;
71  unsigned TypeBitWidth : 24;
72  unsigned ABIAlign : 16;
73  unsigned PrefAlign : 16;
74
75  static LayoutAlignElem get(AlignTypeEnum align_type, unsigned abi_align,
76                             unsigned pref_align, uint32_t bit_width);
77  bool operator==(const LayoutAlignElem &rhs) const;
78};
79
80/// \brief Layout pointer alignment element.
81///
82/// Stores the alignment data associated with a given pointer and address space.
83///
84/// \note The unusual order of elements in the structure attempts to reduce
85/// padding and make the structure slightly more cache friendly.
86struct PointerAlignElem {
87  unsigned ABIAlign;
88  unsigned PrefAlign;
89  uint32_t TypeByteWidth;
90  uint32_t AddressSpace;
91
92  /// Initializer
93  static PointerAlignElem get(uint32_t AddressSpace, unsigned ABIAlign,
94                              unsigned PrefAlign, uint32_t TypeByteWidth);
95  bool operator==(const PointerAlignElem &rhs) const;
96};
97
98/// \brief A parsed version of the target data layout string in and methods for
99/// querying it.
100///
101/// The target data layout string is specified *by the target* - a frontend
102/// generating LLVM IR is required to generate the right target data for the
103/// target being codegen'd to.
104class DataLayout {
105private:
106  /// Defaults to false.
107  bool BigEndian;
108
109  unsigned StackNaturalAlign;
110
111  enum ManglingModeT {
112    MM_None,
113    MM_ELF,
114    MM_MachO,
115    MM_WinCOFF,
116    MM_WinCOFFX86,
117    MM_Mips
118  };
119  ManglingModeT ManglingMode;
120
121  SmallVector<unsigned char, 8> LegalIntWidths;
122
123  /// \brief Primitive type alignment data.
124  SmallVector<LayoutAlignElem, 16> Alignments;
125
126  /// \brief The string representation used to create this DataLayout
127  std::string StringRepresentation;
128
129  typedef SmallVector<PointerAlignElem, 8> PointersTy;
130  PointersTy Pointers;
131
132  PointersTy::const_iterator
133  findPointerLowerBound(uint32_t AddressSpace) const {
134    return const_cast<DataLayout *>(this)->findPointerLowerBound(AddressSpace);
135  }
136
137  PointersTy::iterator findPointerLowerBound(uint32_t AddressSpace);
138
139  /// This member is a signal that a requested alignment type and bit width were
140  /// not found in the SmallVector.
141  static const LayoutAlignElem InvalidAlignmentElem;
142
143  /// This member is a signal that a requested pointer type and bit width were
144  /// not found in the DenseSet.
145  static const PointerAlignElem InvalidPointerElem;
146
147  // The StructType -> StructLayout map.
148  mutable void *LayoutMap;
149
150  void setAlignment(AlignTypeEnum align_type, unsigned abi_align,
151                    unsigned pref_align, uint32_t bit_width);
152  unsigned getAlignmentInfo(AlignTypeEnum align_type, uint32_t bit_width,
153                            bool ABIAlign, Type *Ty) const;
154  void setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
155                           unsigned PrefAlign, uint32_t TypeByteWidth);
156
157  /// Internal helper method that returns requested alignment for type.
158  unsigned getAlignment(Type *Ty, bool abi_or_pref) const;
159
160  /// \brief Valid alignment predicate.
161  ///
162  /// Predicate that tests a LayoutAlignElem reference returned by get() against
163  /// InvalidAlignmentElem.
164  bool validAlignment(const LayoutAlignElem &align) const {
165    return &align != &InvalidAlignmentElem;
166  }
167
168  /// \brief Valid pointer predicate.
169  ///
170  /// Predicate that tests a PointerAlignElem reference returned by get()
171  /// against \c InvalidPointerElem.
172  bool validPointer(const PointerAlignElem &align) const {
173    return &align != &InvalidPointerElem;
174  }
175
176  /// Parses a target data specification string. Assert if the string is
177  /// malformed.
178  void parseSpecifier(StringRef LayoutDescription);
179
180  // Free all internal data structures.
181  void clear();
182
183public:
184  /// Constructs a DataLayout from a specification string. See reset().
185  explicit DataLayout(StringRef LayoutDescription) : LayoutMap(nullptr) {
186    reset(LayoutDescription);
187  }
188
189  /// Initialize target data from properties stored in the module.
190  explicit DataLayout(const Module *M);
191
192  void init(const Module *M);
193
194  DataLayout(const DataLayout &DL) : LayoutMap(nullptr) { *this = DL; }
195
196  DataLayout &operator=(const DataLayout &DL) {
197    clear();
198    StringRepresentation = DL.StringRepresentation;
199    BigEndian = DL.isBigEndian();
200    StackNaturalAlign = DL.StackNaturalAlign;
201    ManglingMode = DL.ManglingMode;
202    LegalIntWidths = DL.LegalIntWidths;
203    Alignments = DL.Alignments;
204    Pointers = DL.Pointers;
205    return *this;
206  }
207
208  bool operator==(const DataLayout &Other) const;
209  bool operator!=(const DataLayout &Other) const { return !(*this == Other); }
210
211  ~DataLayout(); // Not virtual, do not subclass this class
212
213  /// Parse a data layout string (with fallback to default values).
214  void reset(StringRef LayoutDescription);
215
216  /// Layout endianness...
217  bool isLittleEndian() const { return !BigEndian; }
218  bool isBigEndian() const { return BigEndian; }
219
220  /// \brief Returns the string representation of the DataLayout.
221  ///
222  /// This representation is in the same format accepted by the string
223  /// constructor above. This should not be used to compare two DataLayout as
224  /// different string can represent the same layout.
225  std::string getStringRepresentation() const { return StringRepresentation; }
226
227  /// \brief Test if the DataLayout was constructed from an empty string.
228  bool isDefault() const { return StringRepresentation.empty(); }
229
230  /// \brief Returns true if the specified type is known to be a native integer
231  /// type supported by the CPU.
232  ///
233  /// For example, i64 is not native on most 32-bit CPUs and i37 is not native
234  /// on any known one. This returns false if the integer width is not legal.
235  ///
236  /// The width is specified in bits.
237  bool isLegalInteger(unsigned Width) const {
238    for (unsigned LegalIntWidth : LegalIntWidths)
239      if (LegalIntWidth == Width)
240        return true;
241    return false;
242  }
243
244  bool isIllegalInteger(unsigned Width) const { return !isLegalInteger(Width); }
245
246  /// Returns true if the given alignment exceeds the natural stack alignment.
247  bool exceedsNaturalStackAlignment(unsigned Align) const {
248    return (StackNaturalAlign != 0) && (Align > StackNaturalAlign);
249  }
250
251  unsigned getStackAlignment() const { return StackNaturalAlign; }
252
253  bool hasMicrosoftFastStdCallMangling() const {
254    return ManglingMode == MM_WinCOFFX86;
255  }
256
257  bool hasLinkerPrivateGlobalPrefix() const { return ManglingMode == MM_MachO; }
258
259  const char *getLinkerPrivateGlobalPrefix() const {
260    if (ManglingMode == MM_MachO)
261      return "l";
262    return "";
263  }
264
265  char getGlobalPrefix() const {
266    switch (ManglingMode) {
267    case MM_None:
268    case MM_ELF:
269    case MM_Mips:
270    case MM_WinCOFF:
271      return '\0';
272    case MM_MachO:
273    case MM_WinCOFFX86:
274      return '_';
275    }
276    llvm_unreachable("invalid mangling mode");
277  }
278
279  const char *getPrivateGlobalPrefix() const {
280    switch (ManglingMode) {
281    case MM_None:
282      return "";
283    case MM_ELF:
284      return ".L";
285    case MM_Mips:
286      return "$";
287    case MM_MachO:
288    case MM_WinCOFF:
289    case MM_WinCOFFX86:
290      return "L";
291    }
292    llvm_unreachable("invalid mangling mode");
293  }
294
295  static const char *getManglingComponent(const Triple &T);
296
297  /// \brief Returns true if the specified type fits in a native integer type
298  /// supported by the CPU.
299  ///
300  /// For example, if the CPU only supports i32 as a native integer type, then
301  /// i27 fits in a legal integer type but i45 does not.
302  bool fitsInLegalInteger(unsigned Width) const {
303    for (unsigned LegalIntWidth : LegalIntWidths)
304      if (Width <= LegalIntWidth)
305        return true;
306    return false;
307  }
308
309  /// Layout pointer alignment
310  /// FIXME: The defaults need to be removed once all of
311  /// the backends/clients are updated.
312  unsigned getPointerABIAlignment(unsigned AS = 0) const;
313
314  /// Return target's alignment for stack-based pointers
315  /// FIXME: The defaults need to be removed once all of
316  /// the backends/clients are updated.
317  unsigned getPointerPrefAlignment(unsigned AS = 0) const;
318
319  /// Layout pointer size
320  /// FIXME: The defaults need to be removed once all of
321  /// the backends/clients are updated.
322  unsigned getPointerSize(unsigned AS = 0) const;
323
324  /// Layout pointer size, in bits
325  /// FIXME: The defaults need to be removed once all of
326  /// the backends/clients are updated.
327  unsigned getPointerSizeInBits(unsigned AS = 0) const {
328    return getPointerSize(AS) * 8;
329  }
330
331  /// Layout pointer size, in bits, based on the type.  If this function is
332  /// called with a pointer type, then the type size of the pointer is returned.
333  /// If this function is called with a vector of pointers, then the type size
334  /// of the pointer is returned.  This should only be called with a pointer or
335  /// vector of pointers.
336  unsigned getPointerTypeSizeInBits(Type *) const;
337
338  unsigned getPointerTypeSize(Type *Ty) const {
339    return getPointerTypeSizeInBits(Ty) / 8;
340  }
341
342  /// Size examples:
343  ///
344  /// Type        SizeInBits  StoreSizeInBits  AllocSizeInBits[*]
345  /// ----        ----------  ---------------  ---------------
346  ///  i1            1           8                8
347  ///  i8            8           8                8
348  ///  i19          19          24               32
349  ///  i32          32          32               32
350  ///  i100        100         104              128
351  ///  i128        128         128              128
352  ///  Float        32          32               32
353  ///  Double       64          64               64
354  ///  X86_FP80     80          80               96
355  ///
356  /// [*] The alloc size depends on the alignment, and thus on the target.
357  ///     These values are for x86-32 linux.
358
359  /// \brief Returns the number of bits necessary to hold the specified type.
360  ///
361  /// For example, returns 36 for i36 and 80 for x86_fp80. The type passed must
362  /// have a size (Type::isSized() must return true).
363  uint64_t getTypeSizeInBits(Type *Ty) const;
364
365  /// \brief Returns the maximum number of bytes that may be overwritten by
366  /// storing the specified type.
367  ///
368  /// For example, returns 5 for i36 and 10 for x86_fp80.
369  uint64_t getTypeStoreSize(Type *Ty) const {
370    return (getTypeSizeInBits(Ty) + 7) / 8;
371  }
372
373  /// \brief Returns the maximum number of bits that may be overwritten by
374  /// storing the specified type; always a multiple of 8.
375  ///
376  /// For example, returns 40 for i36 and 80 for x86_fp80.
377  uint64_t getTypeStoreSizeInBits(Type *Ty) const {
378    return 8 * getTypeStoreSize(Ty);
379  }
380
381  /// \brief Returns the offset in bytes between successive objects of the
382  /// specified type, including alignment padding.
383  ///
384  /// This is the amount that alloca reserves for this type. For example,
385  /// returns 12 or 16 for x86_fp80, depending on alignment.
386  uint64_t getTypeAllocSize(Type *Ty) const {
387    // Round up to the next alignment boundary.
388    return RoundUpToAlignment(getTypeStoreSize(Ty), getABITypeAlignment(Ty));
389  }
390
391  /// \brief Returns the offset in bits between successive objects of the
392  /// specified type, including alignment padding; always a multiple of 8.
393  ///
394  /// This is the amount that alloca reserves for this type. For example,
395  /// returns 96 or 128 for x86_fp80, depending on alignment.
396  uint64_t getTypeAllocSizeInBits(Type *Ty) const {
397    return 8 * getTypeAllocSize(Ty);
398  }
399
400  /// \brief Returns the minimum ABI-required alignment for the specified type.
401  unsigned getABITypeAlignment(Type *Ty) const;
402
403  /// \brief Returns the minimum ABI-required alignment for an integer type of
404  /// the specified bitwidth.
405  unsigned getABIIntegerTypeAlignment(unsigned BitWidth) const;
406
407  /// \brief Returns the preferred stack/global alignment for the specified
408  /// type.
409  ///
410  /// This is always at least as good as the ABI alignment.
411  unsigned getPrefTypeAlignment(Type *Ty) const;
412
413  /// \brief Returns the preferred alignment for the specified type, returned as
414  /// log2 of the value (a shift amount).
415  unsigned getPreferredTypeAlignmentShift(Type *Ty) const;
416
417  /// \brief Returns an integer type with size at least as big as that of a
418  /// pointer in the given address space.
419  IntegerType *getIntPtrType(LLVMContext &C, unsigned AddressSpace = 0) const;
420
421  /// \brief Returns an integer (vector of integer) type with size at least as
422  /// big as that of a pointer of the given pointer (vector of pointer) type.
423  Type *getIntPtrType(Type *) const;
424
425  /// \brief Returns the smallest integer type with size at least as big as
426  /// Width bits.
427  Type *getSmallestLegalIntType(LLVMContext &C, unsigned Width = 0) const;
428
429  /// \brief Returns the largest legal integer type, or null if none are set.
430  Type *getLargestLegalIntType(LLVMContext &C) const {
431    unsigned LargestSize = getLargestLegalIntTypeSize();
432    return (LargestSize == 0) ? nullptr : Type::getIntNTy(C, LargestSize);
433  }
434
435  /// \brief Returns the size of largest legal integer type size, or 0 if none
436  /// are set.
437  unsigned getLargestLegalIntTypeSize() const;
438
439  /// \brief Returns the offset from the beginning of the type for the specified
440  /// indices.
441  ///
442  /// This is used to implement getelementptr.
443  uint64_t getIndexedOffset(Type *Ty, ArrayRef<Value *> Indices) const;
444
445  /// \brief Returns a StructLayout object, indicating the alignment of the
446  /// struct, its size, and the offsets of its fields.
447  ///
448  /// Note that this information is lazily cached.
449  const StructLayout *getStructLayout(StructType *Ty) const;
450
451  /// \brief Returns the preferred alignment of the specified global.
452  ///
453  /// This includes an explicitly requested alignment (if the global has one).
454  unsigned getPreferredAlignment(const GlobalVariable *GV) const;
455
456  /// \brief Returns the preferred alignment of the specified global, returned
457  /// in log form.
458  ///
459  /// This includes an explicitly requested alignment (if the global has one).
460  unsigned getPreferredAlignmentLog(const GlobalVariable *GV) const;
461};
462
463inline DataLayout *unwrap(LLVMTargetDataRef P) {
464  return reinterpret_cast<DataLayout *>(P);
465}
466
467inline LLVMTargetDataRef wrap(const DataLayout *P) {
468  return reinterpret_cast<LLVMTargetDataRef>(const_cast<DataLayout *>(P));
469}
470
471/// Used to lazily calculate structure layout information for a target machine,
472/// based on the DataLayout structure.
473class StructLayout {
474  uint64_t StructSize;
475  unsigned StructAlignment;
476  unsigned NumElements;
477  uint64_t MemberOffsets[1]; // variable sized array!
478public:
479  uint64_t getSizeInBytes() const { return StructSize; }
480
481  uint64_t getSizeInBits() const { return 8 * StructSize; }
482
483  unsigned getAlignment() const { return StructAlignment; }
484
485  /// \brief Given a valid byte offset into the structure, returns the structure
486  /// index that contains it.
487  unsigned getElementContainingOffset(uint64_t Offset) const;
488
489  uint64_t getElementOffset(unsigned Idx) const {
490    assert(Idx < NumElements && "Invalid element idx!");
491    return MemberOffsets[Idx];
492  }
493
494  uint64_t getElementOffsetInBits(unsigned Idx) const {
495    return getElementOffset(Idx) * 8;
496  }
497
498private:
499  friend class DataLayout; // Only DataLayout can create this class
500  StructLayout(StructType *ST, const DataLayout &DL);
501};
502
503// The implementation of this method is provided inline as it is particularly
504// well suited to constant folding when called on a specific Type subclass.
505inline uint64_t DataLayout::getTypeSizeInBits(Type *Ty) const {
506  assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
507  switch (Ty->getTypeID()) {
508  case Type::LabelTyID:
509    return getPointerSizeInBits(0);
510  case Type::PointerTyID:
511    return getPointerSizeInBits(Ty->getPointerAddressSpace());
512  case Type::ArrayTyID: {
513    ArrayType *ATy = cast<ArrayType>(Ty);
514    return ATy->getNumElements() *
515           getTypeAllocSizeInBits(ATy->getElementType());
516  }
517  case Type::StructTyID:
518    // Get the layout annotation... which is lazily created on demand.
519    return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
520  case Type::IntegerTyID:
521    return Ty->getIntegerBitWidth();
522  case Type::HalfTyID:
523    return 16;
524  case Type::FloatTyID:
525    return 32;
526  case Type::DoubleTyID:
527  case Type::X86_MMXTyID:
528    return 64;
529  case Type::PPC_FP128TyID:
530  case Type::FP128TyID:
531    return 128;
532  // In memory objects this is always aligned to a higher boundary, but
533  // only 80 bits contain information.
534  case Type::X86_FP80TyID:
535    return 80;
536  case Type::VectorTyID: {
537    VectorType *VTy = cast<VectorType>(Ty);
538    return VTy->getNumElements() * getTypeSizeInBits(VTy->getElementType());
539  }
540  default:
541    llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type");
542  }
543}
544
545} // End llvm namespace
546
547#endif
548