1 //===-- TargetData.cpp - Data size & alignment routines --------------------==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // 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/Constants.h"
21 #include "llvm/DerivedTypes.h"
22 #include "llvm/Module.h"
23 #include "llvm/Support/GetElementPtrTypeIterator.h"
24 #include "llvm/Support/MathExtras.h"
25 #include "llvm/Support/ManagedStatic.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/System/Mutex.h"
29 #include "llvm/ADT/DenseMap.h"
34 // Handle the Pass registration stuff necessary to use TargetData's.
36 // Register the default SparcV9 implementation...
37 INITIALIZE_PASS(TargetData, "targetdata", "Target Data Layout", false, true);
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);
52 unsigned TyAlign = ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty);
54 // Add padding if necessary to align the data element properly.
55 if ((StructSize & (TyAlign-1)) != 0)
56 StructSize = TargetData::RoundUpAlignment(StructSize, TyAlign);
58 // Keep track of maximum alignment constraint.
59 StructAlignment = std::max(TyAlign, StructAlignment);
61 MemberOffsets[i] = StructSize;
62 StructSize += TD.getTypeAllocSize(Ty); // Consume space for this data item
65 // Empty structures have alignment of 1 byte.
66 if (StructAlignment == 0) StructAlignment = 1;
68 // Add padding to the end of the struct so that it could be put in an array
69 // and all array elements would be aligned correctly.
70 if ((StructSize & (StructAlignment-1)) != 0)
71 StructSize = TargetData::RoundUpAlignment(StructSize, StructAlignment);
75 /// getElementContainingOffset - Given a valid offset into the structure,
76 /// return the structure index that contains it.
77 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
79 std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
80 assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
82 assert(*SI <= Offset && "upper_bound didn't work");
83 assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
84 (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
85 "Upper bound didn't work!");
87 // Multiple fields can have the same offset if any of them are zero sized.
88 // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
89 // at the i32 element, because it is the last element at that offset. This is
90 // the right one to return, because anything after it will have a higher
91 // offset, implying that this element is non-empty.
92 return SI-&MemberOffsets[0];
95 //===----------------------------------------------------------------------===//
96 // TargetAlignElem, TargetAlign support
97 //===----------------------------------------------------------------------===//
100 TargetAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
101 unsigned pref_align, uint32_t bit_width) {
102 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
103 TargetAlignElem retval;
104 retval.AlignType = align_type;
105 retval.ABIAlign = abi_align;
106 retval.PrefAlign = pref_align;
107 retval.TypeBitWidth = bit_width;
112 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
113 return (AlignType == rhs.AlignType
114 && ABIAlign == rhs.ABIAlign
115 && PrefAlign == rhs.PrefAlign
116 && TypeBitWidth == rhs.TypeBitWidth);
119 const TargetAlignElem TargetData::InvalidAlignmentElem =
120 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
122 //===----------------------------------------------------------------------===//
123 // TargetData Class Implementation
124 //===----------------------------------------------------------------------===//
126 /// getInt - Get an integer ignoring errors.
127 static unsigned getInt(StringRef R) {
129 R.getAsInteger(10, Result);
133 void TargetData::init(StringRef Desc) {
135 LittleEndian = false;
138 PointerPrefAlign = PointerABIAlign;
140 // Default alignments
141 setAlignment(INTEGER_ALIGN, 1, 1, 1); // i1
142 setAlignment(INTEGER_ALIGN, 1, 1, 8); // i8
143 setAlignment(INTEGER_ALIGN, 2, 2, 16); // i16
144 setAlignment(INTEGER_ALIGN, 4, 4, 32); // i32
145 setAlignment(INTEGER_ALIGN, 4, 8, 64); // i64
146 setAlignment(FLOAT_ALIGN, 4, 4, 32); // float
147 setAlignment(FLOAT_ALIGN, 8, 8, 64); // double
148 setAlignment(VECTOR_ALIGN, 8, 8, 64); // v2i32, v1i64, ...
149 setAlignment(VECTOR_ALIGN, 16, 16, 128); // v16i8, v8i16, v4i32, ...
150 setAlignment(AGGREGATE_ALIGN, 0, 8, 0); // struct
152 while (!Desc.empty()) {
153 std::pair<StringRef, StringRef> Split = Desc.split('-');
154 StringRef Token = Split.first;
160 Split = Token.split(':');
161 StringRef Specifier = Split.first;
162 Token = Split.second;
164 assert(!Specifier.empty() && "Can't be empty here");
166 switch (Specifier[0]) {
168 LittleEndian = false;
174 Split = Token.split(':');
175 PointerMemSize = getInt(Split.first) / 8;
176 Split = Split.second.split(':');
177 PointerABIAlign = getInt(Split.first) / 8;
178 Split = Split.second.split(':');
179 PointerPrefAlign = getInt(Split.first) / 8;
180 if (PointerPrefAlign == 0)
181 PointerPrefAlign = PointerABIAlign;
188 AlignTypeEnum AlignType;
189 switch (Specifier[0]) {
191 case 'i': AlignType = INTEGER_ALIGN; break;
192 case 'v': AlignType = VECTOR_ALIGN; break;
193 case 'f': AlignType = FLOAT_ALIGN; break;
194 case 'a': AlignType = AGGREGATE_ALIGN; break;
195 case 's': AlignType = STACK_ALIGN; break;
197 unsigned Size = getInt(Specifier.substr(1));
198 Split = Token.split(':');
199 unsigned ABIAlign = getInt(Split.first) / 8;
201 Split = Split.second.split(':');
202 unsigned PrefAlign = getInt(Split.first) / 8;
204 PrefAlign = ABIAlign;
205 setAlignment(AlignType, ABIAlign, PrefAlign, Size);
208 case 'n': // Native integer types.
209 Specifier = Specifier.substr(1);
211 if (unsigned Width = getInt(Specifier))
212 LegalIntWidths.push_back(Width);
213 Split = Token.split(':');
214 Specifier = Split.first;
215 Token = Split.second;
216 } while (!Specifier.empty() || !Token.empty());
227 /// @note This has to exist, because this is a pass, but it should never be
229 TargetData::TargetData() : ImmutablePass(ID) {
230 report_fatal_error("Bad TargetData ctor used. "
231 "Tool did not specify a TargetData to use?");
234 TargetData::TargetData(const Module *M)
235 : ImmutablePass(ID) {
236 init(M->getDataLayout());
240 TargetData::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
241 unsigned pref_align, uint32_t bit_width) {
242 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
243 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
244 if (Alignments[i].AlignType == align_type &&
245 Alignments[i].TypeBitWidth == bit_width) {
246 // Update the abi, preferred alignments.
247 Alignments[i].ABIAlign = abi_align;
248 Alignments[i].PrefAlign = pref_align;
253 Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
254 pref_align, bit_width));
257 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
258 /// preferred if ABIInfo = false) the target wants for the specified datatype.
259 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
260 uint32_t BitWidth, bool ABIInfo,
261 const Type *Ty) const {
262 // Check to see if we have an exact match and remember the best match we see.
263 int BestMatchIdx = -1;
265 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
266 if (Alignments[i].AlignType == AlignType &&
267 Alignments[i].TypeBitWidth == BitWidth)
268 return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
270 // The best match so far depends on what we're looking for.
271 if (AlignType == INTEGER_ALIGN &&
272 Alignments[i].AlignType == INTEGER_ALIGN) {
273 // The "best match" for integers is the smallest size that is larger than
274 // the BitWidth requested.
275 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
276 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
278 // However, if there isn't one that's larger, then we must use the
279 // largest one we have (see below)
280 if (LargestInt == -1 ||
281 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
286 // Okay, we didn't find an exact solution. Fall back here depending on what
287 // is being looked for.
288 if (BestMatchIdx == -1) {
289 // If we didn't find an integer alignment, fall back on most conservative.
290 if (AlignType == INTEGER_ALIGN) {
291 BestMatchIdx = LargestInt;
293 assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
295 // By default, use natural alignment for vector types. This is consistent
296 // with what clang and llvm-gcc do.
297 unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
298 Align *= cast<VectorType>(Ty)->getNumElements();
299 // If the alignment is not a power of 2, round up to the next power of 2.
300 // This happens for non-power-of-2 length vectors.
301 if (Align & (Align-1))
302 Align = llvm::NextPowerOf2(Align);
307 // Since we got a "best match" index, just return it.
308 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
309 : Alignments[BestMatchIdx].PrefAlign;
314 class StructLayoutMap : public AbstractTypeUser {
315 typedef DenseMap<const StructType*, StructLayout*> LayoutInfoTy;
316 LayoutInfoTy LayoutInfo;
318 void RemoveEntry(LayoutInfoTy::iterator I, bool WasAbstract) {
319 I->second->~StructLayout();
322 I->first->removeAbstractTypeUser(this);
327 /// refineAbstractType - The callback method invoked when an abstract type is
328 /// resolved to another type. An object must override this method to update
329 /// its internal state to reference NewType instead of OldType.
331 virtual void refineAbstractType(const DerivedType *OldTy,
333 LayoutInfoTy::iterator I = LayoutInfo.find(cast<const StructType>(OldTy));
334 assert(I != LayoutInfo.end() && "Using type but not in map?");
335 RemoveEntry(I, true);
338 /// typeBecameConcrete - The other case which AbstractTypeUsers must be aware
339 /// of is when a type makes the transition from being abstract (where it has
340 /// clients on its AbstractTypeUsers list) to concrete (where it does not).
341 /// This method notifies ATU's when this occurs for a type.
343 virtual void typeBecameConcrete(const DerivedType *AbsTy) {
344 LayoutInfoTy::iterator I = LayoutInfo.find(cast<const StructType>(AbsTy));
345 assert(I != LayoutInfo.end() && "Using type but not in map?");
346 RemoveEntry(I, true);
350 virtual ~StructLayoutMap() {
351 // Remove any layouts.
352 for (LayoutInfoTy::iterator
353 I = LayoutInfo.begin(), E = LayoutInfo.end(); I != E; ++I) {
354 const Type *Key = I->first;
355 StructLayout *Value = I->second;
357 if (Key->isAbstract())
358 Key->removeAbstractTypeUser(this);
360 Value->~StructLayout();
365 void InvalidateEntry(const StructType *Ty) {
366 LayoutInfoTy::iterator I = LayoutInfo.find(Ty);
367 if (I == LayoutInfo.end()) return;
368 RemoveEntry(I, Ty->isAbstract());
371 StructLayout *&operator[](const StructType *STy) {
372 return LayoutInfo[STy];
376 virtual void dump() const {}
379 } // end anonymous namespace
381 TargetData::~TargetData() {
382 delete static_cast<StructLayoutMap*>(LayoutMap);
385 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
387 LayoutMap = new StructLayoutMap();
389 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
390 StructLayout *&SL = (*STM)[Ty];
393 // Otherwise, create the struct layout. Because it is variable length, we
394 // malloc it, then use placement new.
395 int NumElts = Ty->getNumElements();
397 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
399 // Set SL before calling StructLayout's ctor. The ctor could cause other
400 // entries to be added to TheMap, invalidating our reference.
403 new (L) StructLayout(Ty, *this);
405 if (Ty->isAbstract())
406 Ty->addAbstractTypeUser(STM);
411 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
412 /// objects. If a TargetData object is alive when types are being refined and
413 /// removed, this method must be called whenever a StructType is removed to
414 /// avoid a dangling pointer in this cache.
415 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
416 if (!LayoutMap) return; // No cache.
418 static_cast<StructLayoutMap*>(LayoutMap)->InvalidateEntry(Ty);
421 std::string TargetData::getStringRepresentation() const {
423 raw_string_ostream OS(Result);
425 OS << (LittleEndian ? "e" : "E")
426 << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
427 << ':' << PointerPrefAlign*8;
428 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
429 const TargetAlignElem &AI = Alignments[i];
430 OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
431 << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
434 if (!LegalIntWidths.empty()) {
435 OS << "-n" << (unsigned)LegalIntWidths[0];
437 for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
438 OS << ':' << (unsigned)LegalIntWidths[i];
444 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
445 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
446 switch (Ty->getTypeID()) {
447 case Type::LabelTyID:
448 case Type::PointerTyID:
449 return getPointerSizeInBits();
450 case Type::ArrayTyID: {
451 const ArrayType *ATy = cast<ArrayType>(Ty);
452 return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
454 case Type::StructTyID:
455 // Get the layout annotation... which is lazily created on demand.
456 return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
457 case Type::UnionTyID: {
458 const UnionType *UnTy = cast<UnionType>(Ty);
460 for (UnionType::element_iterator i = UnTy->element_begin(),
461 e = UnTy->element_end(); i != e; ++i) {
462 Size = std::max(Size, getTypeSizeInBits(*i));
466 case Type::IntegerTyID:
467 return cast<IntegerType>(Ty)->getBitWidth();
470 case Type::FloatTyID:
472 case Type::DoubleTyID:
474 case Type::PPC_FP128TyID:
475 case Type::FP128TyID:
477 // In memory objects this is always aligned to a higher boundary, but
478 // only 80 bits contain information.
479 case Type::X86_FP80TyID:
481 case Type::VectorTyID:
482 return cast<VectorType>(Ty)->getBitWidth();
484 llvm_unreachable("TargetData::getTypeSizeInBits(): Unsupported type");
491 \param abi_or_pref Flag that determines which alignment is returned. true
492 returns the ABI alignment, false returns the preferred alignment.
493 \param Ty The underlying type for which alignment is determined.
495 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
496 == false) for the requested type \a Ty.
498 unsigned TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
501 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
502 switch (Ty->getTypeID()) {
503 // Early escape for the non-numeric types.
504 case Type::LabelTyID:
505 case Type::PointerTyID:
507 ? getPointerABIAlignment()
508 : getPointerPrefAlignment());
509 case Type::ArrayTyID:
510 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
512 case Type::StructTyID: {
513 // Packed structure types always have an ABI alignment of one.
514 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
517 // Get the layout annotation... which is lazily created on demand.
518 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
519 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
520 return std::max(Align, Layout->getAlignment());
522 case Type::UnionTyID: {
523 const UnionType *UnTy = cast<UnionType>(Ty);
526 // Unions need the maximum alignment of all their entries
527 for (UnionType::element_iterator i = UnTy->element_begin(),
528 e = UnTy->element_end(); i != e; ++i) {
529 Align = std::max(Align, getAlignment(*i, abi_or_pref));
533 case Type::IntegerTyID:
535 AlignType = INTEGER_ALIGN;
537 case Type::FloatTyID:
538 case Type::DoubleTyID:
539 // PPC_FP128TyID and FP128TyID have different data contents, but the
540 // same size and alignment, so they look the same here.
541 case Type::PPC_FP128TyID:
542 case Type::FP128TyID:
543 case Type::X86_FP80TyID:
544 AlignType = FLOAT_ALIGN;
546 case Type::VectorTyID:
547 AlignType = VECTOR_ALIGN;
550 llvm_unreachable("Bad type for getAlignment!!!");
554 return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
558 unsigned TargetData::getABITypeAlignment(const Type *Ty) const {
559 return getAlignment(Ty, true);
562 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
563 /// an integer type of the specified bitwidth.
564 unsigned TargetData::getABIIntegerTypeAlignment(unsigned BitWidth) const {
565 return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
569 unsigned TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
570 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
571 if (Alignments[i].AlignType == STACK_ALIGN)
572 return Alignments[i].ABIAlign;
574 return getABITypeAlignment(Ty);
577 unsigned TargetData::getPrefTypeAlignment(const Type *Ty) const {
578 return getAlignment(Ty, false);
581 unsigned TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
582 unsigned Align = getPrefTypeAlignment(Ty);
583 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
584 return Log2_32(Align);
587 /// getIntPtrType - Return an unsigned integer type that is the same size or
588 /// greater to the host pointer size.
589 const IntegerType *TargetData::getIntPtrType(LLVMContext &C) const {
590 return IntegerType::get(C, getPointerSizeInBits());
594 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
595 unsigned NumIndices) const {
596 const Type *Ty = ptrTy;
597 assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
600 generic_gep_type_iterator<Value* const*>
601 TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
602 for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
603 if (const StructType *STy = dyn_cast<StructType>(*TI)) {
604 assert(Indices[CurIDX]->getType() ==
605 Type::getInt32Ty(ptrTy->getContext()) &&
606 "Illegal struct idx");
607 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
609 // Get structure layout information...
610 const StructLayout *Layout = getStructLayout(STy);
612 // Add in the offset, as calculated by the structure layout info...
613 Result += Layout->getElementOffset(FieldNo);
615 // Update Ty to refer to current element
616 Ty = STy->getElementType(FieldNo);
617 } else if (const UnionType *UnTy = dyn_cast<UnionType>(*TI)) {
618 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
620 // Offset into union is canonically 0, but type changes
621 Ty = UnTy->getElementType(FieldNo);
623 // Update Ty to refer to current element
624 Ty = cast<SequentialType>(Ty)->getElementType();
626 // Get the array index and the size of each array element.
627 if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
628 Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
635 /// getPreferredAlignment - Return the preferred alignment of the specified
636 /// global. This includes an explicitly requested alignment (if the global
638 unsigned TargetData::getPreferredAlignment(const GlobalVariable *GV) const {
639 const Type *ElemType = GV->getType()->getElementType();
640 unsigned Alignment = getPrefTypeAlignment(ElemType);
641 if (GV->getAlignment() > Alignment)
642 Alignment = GV->getAlignment();
644 if (GV->hasInitializer()) {
645 if (Alignment < 16) {
646 // If the global is not external, see if it is large. If so, give it a
648 if (getTypeSizeInBits(ElemType) > 128)
649 Alignment = 16; // 16-byte alignment.
655 /// getPreferredAlignmentLog - Return the preferred alignment of the
656 /// specified global, returned in log form. This includes an explicitly
657 /// requested alignment (if the global has one).
658 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
659 return Log2_32(getPreferredAlignment(GV));