1 //===-- TargetData.cpp - Data size & alignment routines --------------------==//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file defines target properties related to datatype size/offset/alignment
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.
17 //===----------------------------------------------------------------------===//
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"
33 // Handle the Pass registration stuff necessary to use TargetData's.
35 // Register the default SparcV9 implementation...
36 RegisterPass<TargetData> X("targetdata", "Target Data Layout");
38 char TargetData::ID = 0;
40 //===----------------------------------------------------------------------===//
41 // Support for StructLayout
42 //===----------------------------------------------------------------------===//
44 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
47 NumElements = ST->getNumElements();
49 // Loop over each of the elements, placing them in memory...
50 for (unsigned i = 0, e = NumElements; i != e; ++i) {
51 const Type *Ty = ST->getElementType(i);
54 TyAlign = (ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty));
55 TySize = TD.getTypeSize(Ty);
57 // Add padding if necessary to make the data element aligned properly...
58 if (StructSize % TyAlign != 0)
59 StructSize = (StructSize/TyAlign + 1) * TyAlign; // Add padding...
61 // Keep track of maximum alignment constraint
62 StructAlignment = std::max(TyAlign, StructAlignment);
64 MemberOffsets[i] = StructSize;
65 StructSize += TySize; // Consume space for this data item
68 // Empty structures have alignment of 1 byte.
69 if (StructAlignment == 0) StructAlignment = 1;
71 // Add padding to the end of the struct so that it could be put in an array
72 // and all array elements would be aligned correctly.
73 if (StructSize % StructAlignment != 0)
74 StructSize = (StructSize/StructAlignment + 1) * StructAlignment;
78 /// getElementContainingOffset - Given a valid offset into the structure,
79 /// return the structure index that contains it.
80 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
82 std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
83 assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
85 assert(*SI <= Offset && "upper_bound didn't work");
86 assert((SI == &MemberOffsets[0] || *(SI-1) < Offset) &&
87 (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
88 "Upper bound didn't work!");
89 return SI-&MemberOffsets[0];
92 //===----------------------------------------------------------------------===//
93 // TargetAlignElem, TargetAlign support
94 //===----------------------------------------------------------------------===//
97 TargetAlignElem::get(AlignTypeEnum align_type, unsigned char abi_align,
98 unsigned char pref_align, uint32_t bit_width) {
99 TargetAlignElem retval;
100 retval.AlignType = align_type;
101 retval.ABIAlign = abi_align;
102 retval.PrefAlign = pref_align;
103 retval.TypeBitWidth = bit_width;
108 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
109 return (AlignType == rhs.AlignType
110 && ABIAlign == rhs.ABIAlign
111 && PrefAlign == rhs.PrefAlign
112 && TypeBitWidth == rhs.TypeBitWidth);
116 TargetAlignElem::dump(std::ostream &os) const {
117 return os << AlignType
119 << ":" << (int) (ABIAlign * 8)
120 << ":" << (int) (PrefAlign * 8);
123 const TargetAlignElem TargetData::InvalidAlignmentElem =
124 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
126 //===----------------------------------------------------------------------===//
127 // TargetData Class Implementation
128 //===----------------------------------------------------------------------===//
131 A TargetDescription string consists of a sequence of hyphen-delimited
132 specifiers for target endianness, pointer size and alignments, and various
133 primitive type sizes and alignments. A typical string looks something like:
135 "E-p:32:32:32-i1:8:8-i8:8:8-i32:32:32-i64:32:64-f32:32:32-f64:32:64"
137 (note: this string is not fully specified and is only an example.)
139 Alignments come in two flavors: ABI and preferred. ABI alignment (abi_align,
140 below) dictates how a type will be aligned within an aggregate and when used
141 as an argument. Preferred alignment (pref_align, below) determines a type's
142 alignment when emitted as a global.
144 Specifier string details:
146 <i>[E|e]</i>: Endianness. "E" specifies a big-endian target data model, "e"
147 specifies a little-endian target data model.
149 <i>p:@verbatim<size>:<abi_align>:<pref_align>@endverbatim</i>: Pointer size,
150 ABI and preferred alignment.
152 <i>@verbatim<type><size>:<abi_align>:<pref_align>@endverbatim</i>: Numeric type alignment. Type is
153 one of <i>i|f|v|a</i>, corresponding to integer, floating point, vector (aka
154 packed) or aggregate. Size indicates the size, e.g., 32 or 64 bits.
156 The default string, fully specified is:
158 "E-p:64:64:64-a0:0:0-f32:32:32-f64:0:64"
159 "-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:0:64"
160 "-v64:64:64-v128:128:128"
162 Note that in the case of aggregates, 0 is the default ABI and preferred
163 alignment. This is a special case, where the aggregate's computed worst-case
164 alignment will be used.
166 void TargetData::init(const std::string &TargetDescription) {
167 std::string temp = TargetDescription;
169 LittleEndian = false;
172 PointerPrefAlign = PointerABIAlign;
174 // Default alignments
175 setAlignment(INTEGER_ALIGN, 1, 1, 1); // Bool
176 setAlignment(INTEGER_ALIGN, 1, 1, 8); // Byte
177 setAlignment(INTEGER_ALIGN, 2, 2, 16); // short
178 setAlignment(INTEGER_ALIGN, 4, 4, 32); // int
179 setAlignment(INTEGER_ALIGN, 4, 8, 64); // long
180 setAlignment(FLOAT_ALIGN, 4, 4, 32); // float
181 setAlignment(FLOAT_ALIGN, 8, 8, 64); // double
182 setAlignment(VECTOR_ALIGN, 8, 8, 64); // v2i32
183 setAlignment(VECTOR_ALIGN, 16, 16, 128); // v16i8, v8i16, v4i32, ...
184 setAlignment(AGGREGATE_ALIGN, 0, 8, 0); // struct, union, class, ...
186 while (!temp.empty()) {
187 std::string token = getToken(temp, "-");
188 std::string arg0 = getToken(token, ":");
189 const char *p = arg0.c_str();
192 LittleEndian = false;
198 PointerMemSize = atoi(getToken(token,":").c_str()) / 8;
199 PointerABIAlign = atoi(getToken(token,":").c_str()) / 8;
200 PointerPrefAlign = atoi(getToken(token,":").c_str()) / 8;
201 if (PointerPrefAlign == 0)
202 PointerPrefAlign = PointerABIAlign;
209 AlignTypeEnum align_type;
211 case 'i': align_type = INTEGER_ALIGN; break;
212 case 'v': align_type = VECTOR_ALIGN; break;
213 case 'f': align_type = FLOAT_ALIGN; break;
214 case 'a': align_type = AGGREGATE_ALIGN; break;
215 case 's': align_type = STACK_ALIGN; break;
217 uint32_t size = (uint32_t) atoi(++p);
218 unsigned char abi_align = atoi(getToken(token, ":").c_str()) / 8;
219 unsigned char pref_align = atoi(getToken(token, ":").c_str()) / 8;
221 pref_align = abi_align;
222 setAlignment(align_type, abi_align, pref_align, size);
231 TargetData::TargetData(const Module *M)
232 : ImmutablePass((intptr_t)&ID) {
233 init(M->getDataLayout());
237 TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
238 unsigned char pref_align, uint32_t bit_width) {
239 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
240 if (Alignments[i].AlignType == align_type &&
241 Alignments[i].TypeBitWidth == bit_width) {
242 // Update the abi, preferred alignments.
243 Alignments[i].ABIAlign = abi_align;
244 Alignments[i].PrefAlign = pref_align;
249 Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
250 pref_align, bit_width));
253 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
254 /// preferred if ABIInfo = false) the target wants for the specified datatype.
255 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
256 uint32_t BitWidth, bool ABIInfo) const {
257 // Check to see if we have an exact match and remember the best match we see.
258 int BestMatchIdx = -1;
260 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
261 if (Alignments[i].AlignType == AlignType &&
262 Alignments[i].TypeBitWidth == BitWidth)
263 return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
265 // The best match so far depends on what we're looking for.
266 if (AlignType == VECTOR_ALIGN) {
267 // If this is a specification for a smaller vector type, we will fall back
268 // to it. This happens because <128 x double> can be implemented in terms
269 // of 64 <2 x double>.
270 if (Alignments[i].AlignType == VECTOR_ALIGN &&
271 Alignments[i].TypeBitWidth < BitWidth) {
272 // Verify that we pick the biggest of the fallbacks.
273 if (BestMatchIdx == -1 ||
274 Alignments[BestMatchIdx].TypeBitWidth < BitWidth)
277 } else if (AlignType == INTEGER_ALIGN &&
278 Alignments[i].AlignType == INTEGER_ALIGN) {
279 // The "best match" for integers is the smallest size that is larger than
280 // the BitWidth requested.
281 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
282 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
284 // However, if there isn't one that's larger, then we must use the
285 // largest one we have (see below)
286 if (LargestInt == -1 ||
287 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
292 // For integers, if we didn't find a best match, use the largest one found.
293 if (BestMatchIdx == -1)
294 BestMatchIdx = LargestInt;
296 // Okay, we didn't find an exact solution. Fall back here depending on what
297 // is being looked for.
298 assert(BestMatchIdx != -1 && "Didn't find alignment info for this datatype!");
300 // Since we got a "best match" index, just return it.
301 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
302 : Alignments[BestMatchIdx].PrefAlign;
305 /// LayoutInfo - The lazy cache of structure layout information maintained by
306 /// TargetData. Note that the struct types must have been free'd before
307 /// llvm_shutdown is called (and thus this is deallocated) because all the
308 /// targets with cached elements should have been destroyed.
310 typedef std::pair<const TargetData*,const StructType*> LayoutKey;
312 struct DenseMapLayoutKeyInfo {
313 static inline LayoutKey getEmptyKey() { return LayoutKey(0, 0); }
314 static inline LayoutKey getTombstoneKey() {
315 return LayoutKey((TargetData*)(intptr_t)-1, 0);
317 static unsigned getHashValue(const LayoutKey &Val) {
318 return DenseMapInfo<void*>::getHashValue(Val.first) ^
319 DenseMapInfo<void*>::getHashValue(Val.second);
321 static bool isEqual(const LayoutKey &LHS, const LayoutKey &RHS) {
325 static bool isPod() { return true; }
328 typedef DenseMap<LayoutKey, StructLayout*, DenseMapLayoutKeyInfo> LayoutInfoTy;
329 static ManagedStatic<LayoutInfoTy> LayoutInfo;
332 TargetData::~TargetData() {
333 if (LayoutInfo.isConstructed()) {
334 // Remove any layouts for this TD.
335 LayoutInfoTy &TheMap = *LayoutInfo;
336 for (LayoutInfoTy::iterator I = TheMap.begin(), E = TheMap.end();
338 if (I->first.first == this) {
339 I->second->~StructLayout();
349 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
350 LayoutInfoTy &TheMap = *LayoutInfo;
352 StructLayout *&SL = TheMap[LayoutKey(this, Ty)];
355 // Otherwise, create the struct layout. Because it is variable length, we
356 // malloc it, then use placement new.
357 int NumElts = Ty->getNumElements();
359 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1)*sizeof(uint64_t));
361 // Set SL before calling StructLayout's ctor. The ctor could cause other
362 // entries to be added to TheMap, invalidating our reference.
365 new (L) StructLayout(Ty, *this);
369 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
370 /// objects. If a TargetData object is alive when types are being refined and
371 /// removed, this method must be called whenever a StructType is removed to
372 /// avoid a dangling pointer in this cache.
373 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
374 if (!LayoutInfo.isConstructed()) return; // No cache.
376 LayoutInfoTy::iterator I = LayoutInfo->find(LayoutKey(this, Ty));
377 if (I != LayoutInfo->end()) {
378 I->second->~StructLayout();
380 LayoutInfo->erase(I);
385 std::string TargetData::getStringRepresentation() const {
387 repr.append(LittleEndian ? "e" : "E");
388 repr.append("-p:").append(itostr((int64_t) (PointerMemSize * 8))).
389 append(":").append(itostr((int64_t) (PointerABIAlign * 8))).
390 append(":").append(itostr((int64_t) (PointerPrefAlign * 8)));
391 for (align_const_iterator I = Alignments.begin();
392 I != Alignments.end();
394 repr.append("-").append(1, (char) I->AlignType).
395 append(utostr((int64_t) I->TypeBitWidth)).
396 append(":").append(utostr((uint64_t) (I->ABIAlign * 8))).
397 append(":").append(utostr((uint64_t) (I->PrefAlign * 8)));
403 uint64_t TargetData::getTypeSize(const Type *Ty) const {
404 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
405 switch (Ty->getTypeID()) {
406 case Type::LabelTyID:
407 case Type::PointerTyID:
408 return getPointerSize();
409 case Type::ArrayTyID: {
410 const ArrayType *ATy = cast<ArrayType>(Ty);
412 unsigned char Alignment;
413 Size = getTypeSize(ATy->getElementType());
414 Alignment = getABITypeAlignment(ATy->getElementType());
415 uint64_t AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
416 return AlignedSize*ATy->getNumElements();
418 case Type::StructTyID: {
419 // Get the layout annotation... which is lazily created on demand.
420 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
421 return Layout->getSizeInBytes();
423 case Type::IntegerTyID: {
424 unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
427 } else if (BitWidth <= 16) {
429 } else if (BitWidth <= 32) {
431 } else if (BitWidth <= 64) {
434 // The size of this > 64 bit type is chosen as a multiple of the
435 // preferred alignment of the largest "native" size the target supports.
436 // We first obtain the the alignment info for this type and then compute
437 // the next largest multiple of that size.
438 uint64_t size = getAlignmentInfo(INTEGER_ALIGN, BitWidth, false) * 8;
439 return (((BitWidth / (size)) + (BitWidth % size != 0)) * size) / 8;
445 case Type::FloatTyID:
447 case Type::DoubleTyID:
449 case Type::PPC_FP128TyID:
450 case Type::FP128TyID:
452 // In memory objects this is always aligned to a higher boundary, but
453 // only 10 bytes contain information.
454 case Type::X86_FP80TyID:
456 case Type::VectorTyID: {
457 const VectorType *PTy = cast<VectorType>(Ty);
458 return PTy->getBitWidth() / 8;
461 assert(0 && "TargetData::getTypeSize(): Unsupported type");
467 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
469 return cast<IntegerType>(Ty)->getBitWidth();
471 return getTypeSize(Ty) * 8;
474 uint64_t TargetData::getABITypeSizeInBits(const Type *Ty) const {
476 return cast<IntegerType>(Ty)->getBitWidth();
478 return getABITypeSize(Ty) * 8;
481 \param abi_or_pref Flag that determines which alignment is returned. true
482 returns the ABI alignment, false returns the preferred alignment.
483 \param Ty The underlying type for which alignment is determined.
485 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
486 == false) for the requested type \a Ty.
488 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
491 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
492 switch (Ty->getTypeID()) {
493 /* Early escape for the non-numeric types */
494 case Type::LabelTyID:
495 case Type::PointerTyID:
497 ? getPointerABIAlignment()
498 : getPointerPrefAlignment());
499 case Type::ArrayTyID:
500 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
502 case Type::StructTyID: {
503 // Packed structure types always have an ABI alignment of one.
504 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
507 // Get the layout annotation... which is lazily created on demand.
508 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
509 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref);
510 return std::max(Align, (unsigned)Layout->getAlignment());
512 case Type::IntegerTyID:
514 AlignType = INTEGER_ALIGN;
516 case Type::FloatTyID:
517 case Type::DoubleTyID:
518 // PPC_FP128TyID and FP128TyID have different data contents, but the
519 // same size and alignment, so they look the same here.
520 case Type::PPC_FP128TyID:
521 case Type::FP128TyID:
522 case Type::X86_FP80TyID:
523 AlignType = FLOAT_ALIGN;
525 case Type::VectorTyID: {
526 const VectorType *VTy = cast<VectorType>(Ty);
527 // Degenerate vectors are assumed to be scalar-ized
528 if (VTy->getNumElements() == 1)
529 return getAlignment(VTy->getElementType(), abi_or_pref);
531 AlignType = VECTOR_ALIGN;
535 assert(0 && "Bad type for getAlignment!!!");
539 return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSize(Ty) * 8,
543 unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
544 return getAlignment(Ty, true);
547 unsigned char TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
548 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
549 if (Alignments[i].AlignType == STACK_ALIGN)
550 return Alignments[i].ABIAlign;
552 return getABITypeAlignment(Ty);
555 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
556 return getAlignment(Ty, false);
559 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
560 unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
561 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
562 return Log2_32(Align);
565 /// getIntPtrType - Return an unsigned integer type that is the same size or
566 /// greater to the host pointer size.
567 const Type *TargetData::getIntPtrType() const {
568 switch (getPointerSize()) {
569 default: assert(0 && "Unknown pointer size!");
570 case 2: return Type::Int16Ty;
571 case 4: return Type::Int32Ty;
572 case 8: return Type::Int64Ty;
577 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
578 unsigned NumIndices) const {
579 const Type *Ty = ptrTy;
580 assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
583 generic_gep_type_iterator<Value* const*>
584 TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
585 for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
586 if (const StructType *STy = dyn_cast<StructType>(*TI)) {
587 assert(Indices[CurIDX]->getType() == Type::Int32Ty &&
588 "Illegal struct idx");
589 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
591 // Get structure layout information...
592 const StructLayout *Layout = getStructLayout(STy);
594 // Add in the offset, as calculated by the structure layout info...
595 Result += Layout->getElementOffset(FieldNo);
597 // Update Ty to refer to current element
598 Ty = STy->getElementType(FieldNo);
600 // Update Ty to refer to current element
601 Ty = cast<SequentialType>(Ty)->getElementType();
603 // Get the array index and the size of each array element.
604 int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
605 Result += arrayIdx * (int64_t)getTypeSize(Ty);
612 /// getPreferredAlignmentLog - Return the preferred alignment of the
613 /// specified global, returned in log form. This includes an explicitly
614 /// requested alignment (if the global has one).
615 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
616 const Type *ElemType = GV->getType()->getElementType();
617 unsigned Alignment = getPreferredTypeAlignmentShift(ElemType);
618 if (GV->getAlignment() > (1U << Alignment))
619 Alignment = Log2_32(GV->getAlignment());
621 if (GV->hasInitializer()) {
623 // If the global is not external, see if it is large. If so, give it a
625 if (getTypeSize(ElemType) > 128)
626 Alignment = 4; // 16-byte alignment.