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);
121 TargetAlignElem::dump(std::ostream &os) const {
122 return os << AlignType
124 << ":" << (int) (ABIAlign * 8)
125 << ":" << (int) (PrefAlign * 8);
128 const TargetAlignElem TargetData::InvalidAlignmentElem =
129 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
131 //===----------------------------------------------------------------------===//
132 // TargetData Class Implementation
133 //===----------------------------------------------------------------------===//
135 /// getInt - Get an integer ignoring errors.
136 static unsigned getInt(StringRef R) {
138 R.getAsInteger(10, Result);
142 void TargetData::init(StringRef Desc) {
144 LittleEndian = false;
147 PointerPrefAlign = PointerABIAlign;
149 // Default alignments
150 setAlignment(INTEGER_ALIGN, 1, 1, 1); // i1
151 setAlignment(INTEGER_ALIGN, 1, 1, 8); // i8
152 setAlignment(INTEGER_ALIGN, 2, 2, 16); // i16
153 setAlignment(INTEGER_ALIGN, 4, 4, 32); // i32
154 setAlignment(INTEGER_ALIGN, 4, 8, 64); // i64
155 setAlignment(FLOAT_ALIGN, 4, 4, 32); // float
156 setAlignment(FLOAT_ALIGN, 8, 8, 64); // double
157 setAlignment(VECTOR_ALIGN, 8, 8, 64); // v2i32, v1i64, ...
158 setAlignment(VECTOR_ALIGN, 16, 16, 128); // v16i8, v8i16, v4i32, ...
159 setAlignment(AGGREGATE_ALIGN, 0, 8, 0); // struct
161 while (!Desc.empty()) {
162 std::pair<StringRef, StringRef> Split = Desc.split('-');
163 StringRef Token = Split.first;
169 Split = Token.split(':');
170 StringRef Specifier = Split.first;
171 Token = Split.second;
173 assert(!Specifier.empty() && "Can't be empty here");
175 switch (Specifier[0]) {
177 LittleEndian = false;
183 Split = Token.split(':');
184 PointerMemSize = getInt(Split.first) / 8;
185 Split = Split.second.split(':');
186 PointerABIAlign = getInt(Split.first) / 8;
187 Split = Split.second.split(':');
188 PointerPrefAlign = getInt(Split.first) / 8;
189 if (PointerPrefAlign == 0)
190 PointerPrefAlign = PointerABIAlign;
197 AlignTypeEnum AlignType;
198 switch (Specifier[0]) {
200 case 'i': AlignType = INTEGER_ALIGN; break;
201 case 'v': AlignType = VECTOR_ALIGN; break;
202 case 'f': AlignType = FLOAT_ALIGN; break;
203 case 'a': AlignType = AGGREGATE_ALIGN; break;
204 case 's': AlignType = STACK_ALIGN; break;
206 unsigned Size = getInt(Specifier.substr(1));
207 Split = Token.split(':');
208 unsigned char ABIAlign = getInt(Split.first) / 8;
210 Split = Split.second.split(':');
211 unsigned char PrefAlign = getInt(Split.first) / 8;
213 PrefAlign = ABIAlign;
214 setAlignment(AlignType, ABIAlign, PrefAlign, Size);
217 case 'n': // Native integer types.
218 Specifier = Specifier.substr(1);
220 if (unsigned Width = getInt(Specifier))
221 LegalIntWidths.push_back(Width);
222 Split = Token.split(':');
223 Specifier = Split.first;
224 Token = Split.second;
225 } while (!Specifier.empty() || !Token.empty());
236 /// @note This has to exist, because this is a pass, but it should never be
238 TargetData::TargetData() : ImmutablePass(&ID) {
239 llvm_report_error("Bad TargetData ctor used. "
240 "Tool did not specify a TargetData to use?");
243 TargetData::TargetData(const Module *M)
244 : ImmutablePass(&ID) {
245 init(M->getDataLayout());
249 TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
250 unsigned char pref_align, uint32_t bit_width) {
251 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
252 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
253 if (Alignments[i].AlignType == align_type &&
254 Alignments[i].TypeBitWidth == bit_width) {
255 // Update the abi, preferred alignments.
256 Alignments[i].ABIAlign = abi_align;
257 Alignments[i].PrefAlign = pref_align;
262 Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
263 pref_align, bit_width));
266 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
267 /// preferred if ABIInfo = false) the target wants for the specified datatype.
268 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
269 uint32_t BitWidth, bool ABIInfo,
270 const Type *Ty) const {
271 // Check to see if we have an exact match and remember the best match we see.
272 int BestMatchIdx = -1;
274 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
275 if (Alignments[i].AlignType == AlignType &&
276 Alignments[i].TypeBitWidth == BitWidth)
277 return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
279 // The best match so far depends on what we're looking for.
280 if (AlignType == VECTOR_ALIGN && Alignments[i].AlignType == VECTOR_ALIGN) {
281 // If this is a specification for a smaller vector type, we will fall back
282 // to it. This happens because <128 x double> can be implemented in terms
283 // of 64 <2 x double>.
284 if (Alignments[i].TypeBitWidth < BitWidth) {
285 // Verify that we pick the biggest of the fallbacks.
286 if (BestMatchIdx == -1 ||
287 Alignments[BestMatchIdx].TypeBitWidth < Alignments[i].TypeBitWidth)
290 } else if (AlignType == INTEGER_ALIGN &&
291 Alignments[i].AlignType == INTEGER_ALIGN) {
292 // The "best match" for integers is the smallest size that is larger than
293 // the BitWidth requested.
294 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
295 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
297 // However, if there isn't one that's larger, then we must use the
298 // largest one we have (see below)
299 if (LargestInt == -1 ||
300 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
305 // Okay, we didn't find an exact solution. Fall back here depending on what
306 // is being looked for.
307 if (BestMatchIdx == -1) {
308 // If we didn't find an integer alignment, fall back on most conservative.
309 if (AlignType == INTEGER_ALIGN) {
310 BestMatchIdx = LargestInt;
312 assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
314 // If we didn't find a vector size that is smaller or equal to this type,
315 // then we will end up scalarizing this to its element type. Just return
316 // the alignment of the element.
317 return getAlignment(cast<VectorType>(Ty)->getElementType(), ABIInfo);
321 // Since we got a "best match" index, just return it.
322 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
323 : Alignments[BestMatchIdx].PrefAlign;
326 typedef DenseMap<const StructType*, StructLayout*> LayoutInfoTy;
330 class StructLayoutMap : public AbstractTypeUser {
331 LayoutInfoTy LayoutInfo;
333 /// refineAbstractType - The callback method invoked when an abstract type is
334 /// resolved to another type. An object must override this method to update
335 /// its internal state to reference NewType instead of OldType.
337 virtual void refineAbstractType(const DerivedType *OldTy,
339 const StructType *STy = dyn_cast<const StructType>(OldTy);
341 OldTy->removeAbstractTypeUser(this);
345 StructLayout *SL = LayoutInfo[STy];
349 LayoutInfo[STy] = NULL;
352 OldTy->removeAbstractTypeUser(this);
355 /// typeBecameConcrete - The other case which AbstractTypeUsers must be aware
356 /// of is when a type makes the transition from being abstract (where it has
357 /// clients on its AbstractTypeUsers list) to concrete (where it does not).
358 /// This method notifies ATU's when this occurs for a type.
360 virtual void typeBecameConcrete(const DerivedType *AbsTy) {
361 const StructType *STy = dyn_cast<const StructType>(AbsTy);
363 AbsTy->removeAbstractTypeUser(this);
367 StructLayout *SL = LayoutInfo[STy];
371 LayoutInfo[STy] = NULL;
374 AbsTy->removeAbstractTypeUser(this);
377 bool insert(const Type *Ty) {
378 if (Ty->isAbstract())
379 Ty->addAbstractTypeUser(this);
384 virtual ~StructLayoutMap() {
385 // Remove any layouts.
386 for (LayoutInfoTy::iterator
387 I = LayoutInfo.begin(), E = LayoutInfo.end(); I != E; ++I)
388 if (StructLayout *SL = I->second) {
394 inline LayoutInfoTy::iterator begin() {
395 return LayoutInfo.begin();
397 inline LayoutInfoTy::iterator end() {
398 return LayoutInfo.end();
400 inline LayoutInfoTy::const_iterator begin() const {
401 return LayoutInfo.begin();
403 inline LayoutInfoTy::const_iterator end() const {
404 return LayoutInfo.end();
407 LayoutInfoTy::iterator find(const StructType *&Val) {
408 return LayoutInfo.find(Val);
410 LayoutInfoTy::const_iterator find(const StructType *&Val) const {
411 return LayoutInfo.find(Val);
414 bool erase(const StructType *&Val) {
415 return LayoutInfo.erase(Val);
417 bool erase(LayoutInfoTy::iterator I) {
418 return LayoutInfo.erase(I);
421 StructLayout *&operator[](const Type *Key) {
422 const StructType *STy = dyn_cast<const StructType>(Key);
423 assert(STy && "Trying to access the struct layout map with a non-struct!");
425 return LayoutInfo[STy];
429 virtual void dump() const {}
432 } // end namespace llvm
434 TargetData::~TargetData() {
438 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
440 LayoutMap = new StructLayoutMap();
442 StructLayout *&SL = (*LayoutMap)[Ty];
445 // Otherwise, create the struct layout. Because it is variable length, we
446 // malloc it, then use placement new.
447 int NumElts = Ty->getNumElements();
449 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
451 // Set SL before calling StructLayout's ctor. The ctor could cause other
452 // entries to be added to TheMap, invalidating our reference.
455 new (L) StructLayout(Ty, *this);
459 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
460 /// objects. If a TargetData object is alive when types are being refined and
461 /// removed, this method must be called whenever a StructType is removed to
462 /// avoid a dangling pointer in this cache.
463 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
464 if (!LayoutMap) return; // No cache.
466 DenseMap<const StructType*, StructLayout*>::iterator I = LayoutMap->find(Ty);
467 if (I == LayoutMap->end()) return;
469 I->second->~StructLayout();
475 std::string TargetData::getStringRepresentation() const {
477 raw_string_ostream OS(Result);
479 OS << (LittleEndian ? "e" : "E")
480 << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
481 << ':' << PointerPrefAlign*8;
482 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
483 const TargetAlignElem &AI = Alignments[i];
484 OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
485 << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
488 if (!LegalIntWidths.empty()) {
489 OS << "-n" << (unsigned)LegalIntWidths[0];
491 for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
492 OS << ':' << (unsigned)LegalIntWidths[i];
498 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
499 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
500 switch (Ty->getTypeID()) {
501 case Type::LabelTyID:
502 case Type::PointerTyID:
503 return getPointerSizeInBits();
504 case Type::ArrayTyID: {
505 const ArrayType *ATy = cast<ArrayType>(Ty);
506 return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
508 case Type::StructTyID:
509 // Get the layout annotation... which is lazily created on demand.
510 return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
511 case Type::IntegerTyID:
512 return cast<IntegerType>(Ty)->getBitWidth();
515 case Type::FloatTyID:
517 case Type::DoubleTyID:
519 case Type::PPC_FP128TyID:
520 case Type::FP128TyID:
522 // In memory objects this is always aligned to a higher boundary, but
523 // only 80 bits contain information.
524 case Type::X86_FP80TyID:
526 case Type::VectorTyID:
527 return cast<VectorType>(Ty)->getBitWidth();
529 llvm_unreachable("TargetData::getTypeSizeInBits(): Unsupported type");
536 \param abi_or_pref Flag that determines which alignment is returned. true
537 returns the ABI alignment, false returns the preferred alignment.
538 \param Ty The underlying type for which alignment is determined.
540 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
541 == false) for the requested type \a Ty.
543 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
546 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
547 switch (Ty->getTypeID()) {
548 // Early escape for the non-numeric types.
549 case Type::LabelTyID:
550 case Type::PointerTyID:
552 ? getPointerABIAlignment()
553 : getPointerPrefAlignment());
554 case Type::ArrayTyID:
555 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
557 case Type::StructTyID: {
558 // Packed structure types always have an ABI alignment of one.
559 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
562 // Get the layout annotation... which is lazily created on demand.
563 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
564 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
565 return std::max(Align, (unsigned)Layout->getAlignment());
567 case Type::IntegerTyID:
569 AlignType = INTEGER_ALIGN;
571 case Type::FloatTyID:
572 case Type::DoubleTyID:
573 // PPC_FP128TyID and FP128TyID have different data contents, but the
574 // same size and alignment, so they look the same here.
575 case Type::PPC_FP128TyID:
576 case Type::FP128TyID:
577 case Type::X86_FP80TyID:
578 AlignType = FLOAT_ALIGN;
580 case Type::VectorTyID:
581 AlignType = VECTOR_ALIGN;
584 llvm_unreachable("Bad type for getAlignment!!!");
588 return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
592 unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
593 return getAlignment(Ty, true);
596 unsigned char TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
597 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
598 if (Alignments[i].AlignType == STACK_ALIGN)
599 return Alignments[i].ABIAlign;
601 return getABITypeAlignment(Ty);
604 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
605 return getAlignment(Ty, false);
608 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
609 unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
610 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
611 return Log2_32(Align);
614 /// getIntPtrType - Return an unsigned integer type that is the same size or
615 /// greater to the host pointer size.
616 const IntegerType *TargetData::getIntPtrType(LLVMContext &C) const {
617 return IntegerType::get(C, getPointerSizeInBits());
621 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
622 unsigned NumIndices) const {
623 const Type *Ty = ptrTy;
624 assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
627 generic_gep_type_iterator<Value* const*>
628 TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
629 for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
630 if (const StructType *STy = dyn_cast<StructType>(*TI)) {
631 assert(Indices[CurIDX]->getType() ==
632 Type::getInt32Ty(ptrTy->getContext()) &&
633 "Illegal struct idx");
634 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
636 // Get structure layout information...
637 const StructLayout *Layout = getStructLayout(STy);
639 // Add in the offset, as calculated by the structure layout info...
640 Result += Layout->getElementOffset(FieldNo);
642 // Update Ty to refer to current element
643 Ty = STy->getElementType(FieldNo);
645 // Update Ty to refer to current element
646 Ty = cast<SequentialType>(Ty)->getElementType();
648 // Get the array index and the size of each array element.
649 int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
650 Result += arrayIdx * (int64_t)getTypeAllocSize(Ty);
657 /// getPreferredAlignment - Return the preferred alignment of the specified
658 /// global. This includes an explicitly requested alignment (if the global
660 unsigned TargetData::getPreferredAlignment(const GlobalVariable *GV) const {
661 const Type *ElemType = GV->getType()->getElementType();
662 unsigned Alignment = getPrefTypeAlignment(ElemType);
663 if (GV->getAlignment() > Alignment)
664 Alignment = GV->getAlignment();
666 if (GV->hasInitializer()) {
667 if (Alignment < 16) {
668 // If the global is not external, see if it is large. If so, give it a
670 if (getTypeSizeInBits(ElemType) > 128)
671 Alignment = 16; // 16-byte alignment.
677 /// getPreferredAlignmentLog - Return the preferred alignment of the
678 /// specified global, returned in log form. This includes an explicitly
679 /// requested alignment (if the global has one).
680 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
681 return Log2_32(getPreferredAlignment(GV));