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 static RegisterPass<TargetData> X("targetdata", "Target Data Layout", false,
39 char TargetData::ID = 0;
41 //===----------------------------------------------------------------------===//
42 // Support for StructLayout
43 //===----------------------------------------------------------------------===//
45 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
48 NumElements = ST->getNumElements();
50 // Loop over each of the elements, placing them in memory.
51 for (unsigned i = 0, e = NumElements; i != e; ++i) {
52 const Type *Ty = ST->getElementType(i);
53 unsigned TyAlign = ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty);
55 // Add padding if necessary to align the data element properly.
56 if ((StructSize & (TyAlign-1)) != 0)
57 StructSize = TargetData::RoundUpAlignment(StructSize, TyAlign);
59 // Keep track of maximum alignment constraint.
60 StructAlignment = std::max(TyAlign, StructAlignment);
62 MemberOffsets[i] = StructSize;
63 StructSize += TD.getTypeAllocSize(Ty); // Consume space for this data item
66 // Empty structures have alignment of 1 byte.
67 if (StructAlignment == 0) StructAlignment = 1;
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 = TargetData::RoundUpAlignment(StructSize, StructAlignment);
76 /// getElementContainingOffset - Given a valid offset into the structure,
77 /// return the structure index that contains it.
78 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
80 std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
81 assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
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!");
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];
96 //===----------------------------------------------------------------------===//
97 // TargetAlignElem, TargetAlign support
98 //===----------------------------------------------------------------------===//
101 TargetAlignElem::get(AlignTypeEnum align_type, unsigned char abi_align,
102 unsigned char pref_align, uint32_t bit_width) {
103 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
104 TargetAlignElem retval;
105 retval.AlignType = align_type;
106 retval.ABIAlign = abi_align;
107 retval.PrefAlign = pref_align;
108 retval.TypeBitWidth = bit_width;
113 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
114 return (AlignType == rhs.AlignType
115 && ABIAlign == rhs.ABIAlign
116 && PrefAlign == rhs.PrefAlign
117 && TypeBitWidth == rhs.TypeBitWidth);
120 const TargetAlignElem TargetData::InvalidAlignmentElem =
121 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
123 //===----------------------------------------------------------------------===//
124 // TargetData Class Implementation
125 //===----------------------------------------------------------------------===//
127 /// getInt - Get an integer ignoring errors.
128 static unsigned getInt(StringRef R) {
130 R.getAsInteger(10, Result);
134 void TargetData::init(StringRef Desc) {
136 LittleEndian = false;
139 PointerPrefAlign = PointerABIAlign;
141 // Default alignments
142 setAlignment(INTEGER_ALIGN, 1, 1, 1); // i1
143 setAlignment(INTEGER_ALIGN, 1, 1, 8); // i8
144 setAlignment(INTEGER_ALIGN, 2, 2, 16); // i16
145 setAlignment(INTEGER_ALIGN, 4, 4, 32); // i32
146 setAlignment(INTEGER_ALIGN, 4, 8, 64); // i64
147 setAlignment(FLOAT_ALIGN, 4, 4, 32); // float
148 setAlignment(FLOAT_ALIGN, 8, 8, 64); // double
149 setAlignment(VECTOR_ALIGN, 8, 8, 64); // v2i32, v1i64, ...
150 setAlignment(VECTOR_ALIGN, 16, 16, 128); // v16i8, v8i16, v4i32, ...
151 setAlignment(AGGREGATE_ALIGN, 0, 8, 0); // struct
153 while (!Desc.empty()) {
154 std::pair<StringRef, StringRef> Split = Desc.split('-');
155 StringRef Token = Split.first;
161 Split = Token.split(':');
162 StringRef Specifier = Split.first;
163 Token = Split.second;
165 assert(!Specifier.empty() && "Can't be empty here");
167 switch (Specifier[0]) {
169 LittleEndian = false;
175 Split = Token.split(':');
176 PointerMemSize = getInt(Split.first) / 8;
177 Split = Split.second.split(':');
178 PointerABIAlign = getInt(Split.first) / 8;
179 Split = Split.second.split(':');
180 PointerPrefAlign = getInt(Split.first) / 8;
181 if (PointerPrefAlign == 0)
182 PointerPrefAlign = PointerABIAlign;
189 AlignTypeEnum AlignType;
190 switch (Specifier[0]) {
192 case 'i': AlignType = INTEGER_ALIGN; break;
193 case 'v': AlignType = VECTOR_ALIGN; break;
194 case 'f': AlignType = FLOAT_ALIGN; break;
195 case 'a': AlignType = AGGREGATE_ALIGN; break;
196 case 's': AlignType = STACK_ALIGN; break;
198 unsigned Size = getInt(Specifier.substr(1));
199 Split = Token.split(':');
200 unsigned char ABIAlign = getInt(Split.first) / 8;
202 Split = Split.second.split(':');
203 unsigned char PrefAlign = getInt(Split.first) / 8;
205 PrefAlign = ABIAlign;
206 setAlignment(AlignType, ABIAlign, PrefAlign, Size);
209 case 'n': // Native integer types.
210 Specifier = Specifier.substr(1);
212 if (unsigned Width = getInt(Specifier))
213 LegalIntWidths.push_back(Width);
214 Split = Token.split(':');
215 Specifier = Split.first;
216 Token = Split.second;
217 } while (!Specifier.empty() || !Token.empty());
228 /// @note This has to exist, because this is a pass, but it should never be
230 TargetData::TargetData() : ImmutablePass(&ID) {
231 report_fatal_error("Bad TargetData ctor used. "
232 "Tool did not specify a TargetData to use?");
235 TargetData::TargetData(const Module *M)
236 : ImmutablePass(&ID) {
237 init(M->getDataLayout());
241 TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
242 unsigned char pref_align, uint32_t bit_width) {
243 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
244 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
245 if (Alignments[i].AlignType == align_type &&
246 Alignments[i].TypeBitWidth == bit_width) {
247 // Update the abi, preferred alignments.
248 Alignments[i].ABIAlign = abi_align;
249 Alignments[i].PrefAlign = pref_align;
254 Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
255 pref_align, bit_width));
258 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
259 /// preferred if ABIInfo = false) the target wants for the specified datatype.
260 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
261 uint32_t BitWidth, bool ABIInfo,
262 const Type *Ty) const {
263 // Check to see if we have an exact match and remember the best match we see.
264 int BestMatchIdx = -1;
266 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
267 if (Alignments[i].AlignType == AlignType &&
268 Alignments[i].TypeBitWidth == BitWidth)
269 return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
271 // The best match so far depends on what we're looking for.
272 if (AlignType == INTEGER_ALIGN &&
273 Alignments[i].AlignType == INTEGER_ALIGN) {
274 // The "best match" for integers is the smallest size that is larger than
275 // the BitWidth requested.
276 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
277 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
279 // However, if there isn't one that's larger, then we must use the
280 // largest one we have (see below)
281 if (LargestInt == -1 ||
282 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
287 // Okay, we didn't find an exact solution. Fall back here depending on what
288 // is being looked for.
289 if (BestMatchIdx == -1) {
290 // If we didn't find an integer alignment, fall back on most conservative.
291 if (AlignType == INTEGER_ALIGN) {
292 BestMatchIdx = LargestInt;
294 assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
296 // By default, use natural alignment for vector types. This is consistent
297 // with what clang and llvm-gcc do.
298 unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
299 Align *= cast<VectorType>(Ty)->getNumElements();
300 // If the alignment is not a power of 2, round up to the next power of 2.
301 // This happens for non-power-of-2 length vectors.
302 if (Align & (Align-1))
303 Align = llvm::NextPowerOf2(Align);
308 // Since we got a "best match" index, just return it.
309 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
310 : Alignments[BestMatchIdx].PrefAlign;
315 class StructLayoutMap : public AbstractTypeUser {
316 typedef DenseMap<const StructType*, StructLayout*> LayoutInfoTy;
317 LayoutInfoTy LayoutInfo;
319 void RemoveEntry(LayoutInfoTy::iterator I, bool WasAbstract) {
320 I->second->~StructLayout();
323 I->first->removeAbstractTypeUser(this);
328 /// refineAbstractType - The callback method invoked when an abstract type is
329 /// resolved to another type. An object must override this method to update
330 /// its internal state to reference NewType instead of OldType.
332 virtual void refineAbstractType(const DerivedType *OldTy,
334 LayoutInfoTy::iterator I = LayoutInfo.find(cast<const StructType>(OldTy));
335 assert(I != LayoutInfo.end() && "Using type but not in map?");
336 RemoveEntry(I, true);
339 /// typeBecameConcrete - The other case which AbstractTypeUsers must be aware
340 /// of is when a type makes the transition from being abstract (where it has
341 /// clients on its AbstractTypeUsers list) to concrete (where it does not).
342 /// This method notifies ATU's when this occurs for a type.
344 virtual void typeBecameConcrete(const DerivedType *AbsTy) {
345 LayoutInfoTy::iterator I = LayoutInfo.find(cast<const StructType>(AbsTy));
346 assert(I != LayoutInfo.end() && "Using type but not in map?");
347 RemoveEntry(I, true);
351 virtual ~StructLayoutMap() {
352 // Remove any layouts.
353 for (LayoutInfoTy::iterator
354 I = LayoutInfo.begin(), E = LayoutInfo.end(); I != E; ++I) {
355 const Type *Key = I->first;
356 StructLayout *Value = I->second;
358 if (Key->isAbstract())
359 Key->removeAbstractTypeUser(this);
361 Value->~StructLayout();
366 void InvalidateEntry(const StructType *Ty) {
367 LayoutInfoTy::iterator I = LayoutInfo.find(Ty);
368 if (I == LayoutInfo.end()) return;
369 RemoveEntry(I, Ty->isAbstract());
372 StructLayout *&operator[](const StructType *STy) {
373 return LayoutInfo[STy];
377 virtual void dump() const {}
380 } // end anonymous namespace
382 TargetData::~TargetData() {
383 delete static_cast<StructLayoutMap*>(LayoutMap);
386 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
388 LayoutMap = new StructLayoutMap();
390 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
391 StructLayout *&SL = (*STM)[Ty];
394 // Otherwise, create the struct layout. Because it is variable length, we
395 // malloc it, then use placement new.
396 int NumElts = Ty->getNumElements();
398 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
400 // Set SL before calling StructLayout's ctor. The ctor could cause other
401 // entries to be added to TheMap, invalidating our reference.
404 new (L) StructLayout(Ty, *this);
406 if (Ty->isAbstract())
407 Ty->addAbstractTypeUser(STM);
412 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
413 /// objects. If a TargetData object is alive when types are being refined and
414 /// removed, this method must be called whenever a StructType is removed to
415 /// avoid a dangling pointer in this cache.
416 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
417 if (!LayoutMap) return; // No cache.
419 static_cast<StructLayoutMap*>(LayoutMap)->InvalidateEntry(Ty);
422 std::string TargetData::getStringRepresentation() const {
424 raw_string_ostream OS(Result);
426 OS << (LittleEndian ? "e" : "E")
427 << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
428 << ':' << PointerPrefAlign*8;
429 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
430 const TargetAlignElem &AI = Alignments[i];
431 OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
432 << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
435 if (!LegalIntWidths.empty()) {
436 OS << "-n" << (unsigned)LegalIntWidths[0];
438 for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
439 OS << ':' << (unsigned)LegalIntWidths[i];
445 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
446 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
447 switch (Ty->getTypeID()) {
448 case Type::LabelTyID:
449 case Type::PointerTyID:
450 return getPointerSizeInBits();
451 case Type::ArrayTyID: {
452 const ArrayType *ATy = cast<ArrayType>(Ty);
453 return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
455 case Type::StructTyID:
456 // Get the layout annotation... which is lazily created on demand.
457 return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
458 case Type::UnionTyID: {
459 const UnionType *UnTy = cast<UnionType>(Ty);
461 for (UnionType::element_iterator i = UnTy->element_begin(),
462 e = UnTy->element_end(); i != e; ++i) {
463 Size = std::max(Size, getTypeSizeInBits(*i));
467 case Type::IntegerTyID:
468 return cast<IntegerType>(Ty)->getBitWidth();
471 case Type::FloatTyID:
473 case Type::DoubleTyID:
475 case Type::PPC_FP128TyID:
476 case Type::FP128TyID:
478 // In memory objects this is always aligned to a higher boundary, but
479 // only 80 bits contain information.
480 case Type::X86_FP80TyID:
482 case Type::VectorTyID:
483 return cast<VectorType>(Ty)->getBitWidth();
485 llvm_unreachable("TargetData::getTypeSizeInBits(): Unsupported type");
492 \param abi_or_pref Flag that determines which alignment is returned. true
493 returns the ABI alignment, false returns the preferred alignment.
494 \param Ty The underlying type for which alignment is determined.
496 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
497 == false) for the requested type \a Ty.
499 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
502 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
503 switch (Ty->getTypeID()) {
504 // Early escape for the non-numeric types.
505 case Type::LabelTyID:
506 case Type::PointerTyID:
508 ? getPointerABIAlignment()
509 : getPointerPrefAlignment());
510 case Type::ArrayTyID:
511 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
513 case Type::StructTyID: {
514 // Packed structure types always have an ABI alignment of one.
515 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
518 // Get the layout annotation... which is lazily created on demand.
519 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
520 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
521 return std::max(Align, (unsigned)Layout->getAlignment());
523 case Type::UnionTyID: {
524 const UnionType *UnTy = cast<UnionType>(Ty);
527 // Unions need the maximum alignment of all their entries
528 for (UnionType::element_iterator i = UnTy->element_begin(),
529 e = UnTy->element_end(); i != e; ++i) {
530 Align = std::max(Align, (unsigned)getAlignment(*i, abi_or_pref));
534 case Type::IntegerTyID:
536 AlignType = INTEGER_ALIGN;
538 case Type::FloatTyID:
539 case Type::DoubleTyID:
540 // PPC_FP128TyID and FP128TyID have different data contents, but the
541 // same size and alignment, so they look the same here.
542 case Type::PPC_FP128TyID:
543 case Type::FP128TyID:
544 case Type::X86_FP80TyID:
545 AlignType = FLOAT_ALIGN;
547 case Type::VectorTyID:
548 AlignType = VECTOR_ALIGN;
551 llvm_unreachable("Bad type for getAlignment!!!");
555 return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
559 unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
560 return getAlignment(Ty, true);
563 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
564 /// an integer type of the specified bitwidth.
565 unsigned char TargetData::getABIIntegerTypeAlignment(unsigned BitWidth) const {
566 return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
570 unsigned char TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
571 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
572 if (Alignments[i].AlignType == STACK_ALIGN)
573 return Alignments[i].ABIAlign;
575 return getABITypeAlignment(Ty);
578 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
579 return getAlignment(Ty, false);
582 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
583 unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
584 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
585 return Log2_32(Align);
588 /// getIntPtrType - Return an unsigned integer type that is the same size or
589 /// greater to the host pointer size.
590 const IntegerType *TargetData::getIntPtrType(LLVMContext &C) const {
591 return IntegerType::get(C, getPointerSizeInBits());
595 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
596 unsigned NumIndices) const {
597 const Type *Ty = ptrTy;
598 assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
601 generic_gep_type_iterator<Value* const*>
602 TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
603 for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
604 if (const StructType *STy = dyn_cast<StructType>(*TI)) {
605 assert(Indices[CurIDX]->getType() ==
606 Type::getInt32Ty(ptrTy->getContext()) &&
607 "Illegal struct idx");
608 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
610 // Get structure layout information...
611 const StructLayout *Layout = getStructLayout(STy);
613 // Add in the offset, as calculated by the structure layout info...
614 Result += Layout->getElementOffset(FieldNo);
616 // Update Ty to refer to current element
617 Ty = STy->getElementType(FieldNo);
618 } else if (const UnionType *UnTy = dyn_cast<UnionType>(*TI)) {
619 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
621 // Offset into union is canonically 0, but type changes
622 Ty = UnTy->getElementType(FieldNo);
624 // Update Ty to refer to current element
625 Ty = cast<SequentialType>(Ty)->getElementType();
627 // Get the array index and the size of each array element.
628 if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
629 Result += arrayIdx * (int64_t)getTypeAllocSize(Ty);
636 /// getPreferredAlignment - Return the preferred alignment of the specified
637 /// global. This includes an explicitly requested alignment (if the global
639 unsigned TargetData::getPreferredAlignment(const GlobalVariable *GV) const {
640 const Type *ElemType = GV->getType()->getElementType();
641 unsigned Alignment = getPrefTypeAlignment(ElemType);
642 if (GV->getAlignment() > Alignment)
643 Alignment = GV->getAlignment();
645 if (GV->hasInitializer()) {
646 if (Alignment < 16) {
647 // If the global is not external, see if it is large. If so, give it a
649 if (getTypeSizeInBits(ElemType) > 128)
650 Alignment = 16; // 16-byte alignment.
656 /// getPreferredAlignmentLog - Return the preferred alignment of the
657 /// specified global, returned in log form. This includes an explicitly
658 /// requested alignment (if the global has one).
659 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
660 return Log2_32(getPreferredAlignment(GV));