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 llvm_report_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 == VECTOR_ALIGN && Alignments[i].AlignType == VECTOR_ALIGN) {
273 // If this is a specification for a smaller vector type, we will fall back
274 // to it. This happens because <128 x double> can be implemented in terms
275 // of 64 <2 x double>.
276 if (Alignments[i].TypeBitWidth < BitWidth) {
277 // Verify that we pick the biggest of the fallbacks.
278 if (BestMatchIdx == -1 ||
279 Alignments[BestMatchIdx].TypeBitWidth < Alignments[i].TypeBitWidth)
282 } else if (AlignType == INTEGER_ALIGN &&
283 Alignments[i].AlignType == INTEGER_ALIGN) {
284 // The "best match" for integers is the smallest size that is larger than
285 // the BitWidth requested.
286 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
287 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
289 // However, if there isn't one that's larger, then we must use the
290 // largest one we have (see below)
291 if (LargestInt == -1 ||
292 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
297 // Okay, we didn't find an exact solution. Fall back here depending on what
298 // is being looked for.
299 if (BestMatchIdx == -1) {
300 // If we didn't find an integer alignment, fall back on most conservative.
301 if (AlignType == INTEGER_ALIGN) {
302 BestMatchIdx = LargestInt;
304 assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
306 // If we didn't find a vector size that is smaller or equal to this type,
307 // then we will end up scalarizing this to its element type. Just return
308 // the alignment of the element.
309 return getAlignment(cast<VectorType>(Ty)->getElementType(), ABIInfo);
313 // Since we got a "best match" index, just return it.
314 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
315 : Alignments[BestMatchIdx].PrefAlign;
320 class StructLayoutMap : public AbstractTypeUser {
322 typedef DenseMap<const StructType*, StructLayout*> LayoutInfoTy;
324 LayoutInfoTy LayoutInfo;
326 /// refineAbstractType - The callback method invoked when an abstract type is
327 /// resolved to another type. An object must override this method to update
328 /// its internal state to reference NewType instead of OldType.
330 virtual void refineAbstractType(const DerivedType *OldTy,
332 const StructType *STy = cast<const StructType>(OldTy);
333 LayoutInfoTy::iterator Iter = LayoutInfo.find(STy);
334 Iter->second->~StructLayout();
336 LayoutInfo.erase(Iter);
337 OldTy->removeAbstractTypeUser(this);
340 /// typeBecameConcrete - The other case which AbstractTypeUsers must be aware
341 /// of is when a type makes the transition from being abstract (where it has
342 /// clients on its AbstractTypeUsers list) to concrete (where it does not).
343 /// This method notifies ATU's when this occurs for a type.
345 virtual void typeBecameConcrete(const DerivedType *AbsTy) {
346 const StructType *STy = cast<const StructType>(AbsTy);
347 LayoutInfoTy::iterator Iter = LayoutInfo.find(STy);
348 Iter->second->~StructLayout();
350 LayoutInfo.erase(Iter);
351 AbsTy->removeAbstractTypeUser(this);
355 virtual ~StructLayoutMap() {
356 // Remove any layouts.
357 for (LayoutInfoTy::iterator
358 I = LayoutInfo.begin(), E = LayoutInfo.end(); I != E; ++I) {
359 const Type *Key = I->first;
360 StructLayout *Value = I->second;
362 if (Key->isAbstract())
363 Key->removeAbstractTypeUser(this);
365 Value->~StructLayout();
370 LayoutInfoTy::iterator end() {
371 return LayoutInfo.end();
374 LayoutInfoTy::iterator find(const StructType *&Val) {
375 return LayoutInfo.find(Val);
378 bool erase(LayoutInfoTy::iterator I) {
379 return LayoutInfo.erase(I);
382 StructLayout *&operator[](const StructType *STy) {
383 return LayoutInfo[STy];
387 virtual void dump() const {}
390 } // end anonymous namespace
392 TargetData::~TargetData() {
393 delete static_cast<StructLayoutMap*>(LayoutMap);
396 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
398 LayoutMap = new StructLayoutMap();
400 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
401 StructLayout *&SL = (*STM)[Ty];
404 // Otherwise, create the struct layout. Because it is variable length, we
405 // malloc it, then use placement new.
406 int NumElts = Ty->getNumElements();
408 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
410 // Set SL before calling StructLayout's ctor. The ctor could cause other
411 // entries to be added to TheMap, invalidating our reference.
414 new (L) StructLayout(Ty, *this);
416 if (Ty->isAbstract())
417 Ty->addAbstractTypeUser(STM);
422 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
423 /// objects. If a TargetData object is alive when types are being refined and
424 /// removed, this method must be called whenever a StructType is removed to
425 /// avoid a dangling pointer in this cache.
426 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
427 if (!LayoutMap) return; // No cache.
429 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
430 StructLayoutMap::LayoutInfoTy::iterator I = STM->find(Ty);
431 if (I == STM->end()) return;
433 I->second->~StructLayout();
437 if (Ty->isAbstract())
438 Ty->removeAbstractTypeUser(STM);
441 std::string TargetData::getStringRepresentation() const {
443 raw_string_ostream OS(Result);
445 OS << (LittleEndian ? "e" : "E")
446 << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
447 << ':' << PointerPrefAlign*8;
448 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
449 const TargetAlignElem &AI = Alignments[i];
450 OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
451 << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
454 if (!LegalIntWidths.empty()) {
455 OS << "-n" << (unsigned)LegalIntWidths[0];
457 for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
458 OS << ':' << (unsigned)LegalIntWidths[i];
464 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
465 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
466 switch (Ty->getTypeID()) {
467 case Type::LabelTyID:
468 case Type::PointerTyID:
469 return getPointerSizeInBits();
470 case Type::ArrayTyID: {
471 const ArrayType *ATy = cast<ArrayType>(Ty);
472 return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
474 case Type::StructTyID:
475 // Get the layout annotation... which is lazily created on demand.
476 return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
477 case Type::IntegerTyID:
478 return cast<IntegerType>(Ty)->getBitWidth();
481 case Type::FloatTyID:
483 case Type::DoubleTyID:
485 case Type::PPC_FP128TyID:
486 case Type::FP128TyID:
488 // In memory objects this is always aligned to a higher boundary, but
489 // only 80 bits contain information.
490 case Type::X86_FP80TyID:
492 case Type::VectorTyID:
493 return cast<VectorType>(Ty)->getBitWidth();
495 llvm_unreachable("TargetData::getTypeSizeInBits(): Unsupported type");
502 \param abi_or_pref Flag that determines which alignment is returned. true
503 returns the ABI alignment, false returns the preferred alignment.
504 \param Ty The underlying type for which alignment is determined.
506 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
507 == false) for the requested type \a Ty.
509 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
512 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
513 switch (Ty->getTypeID()) {
514 // Early escape for the non-numeric types.
515 case Type::LabelTyID:
516 case Type::PointerTyID:
518 ? getPointerABIAlignment()
519 : getPointerPrefAlignment());
520 case Type::ArrayTyID:
521 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
523 case Type::StructTyID: {
524 // Packed structure types always have an ABI alignment of one.
525 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
528 // Get the layout annotation... which is lazily created on demand.
529 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
530 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
531 return std::max(Align, (unsigned)Layout->getAlignment());
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 char TargetData::getABITypeAlignment(const Type *Ty) const {
559 return getAlignment(Ty, true);
562 unsigned char TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
563 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
564 if (Alignments[i].AlignType == STACK_ALIGN)
565 return Alignments[i].ABIAlign;
567 return getABITypeAlignment(Ty);
570 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
571 return getAlignment(Ty, false);
574 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
575 unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
576 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
577 return Log2_32(Align);
580 /// getIntPtrType - Return an unsigned integer type that is the same size or
581 /// greater to the host pointer size.
582 const IntegerType *TargetData::getIntPtrType(LLVMContext &C) const {
583 return IntegerType::get(C, getPointerSizeInBits());
587 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
588 unsigned NumIndices) const {
589 const Type *Ty = ptrTy;
590 assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
593 generic_gep_type_iterator<Value* const*>
594 TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
595 for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
596 if (const StructType *STy = dyn_cast<StructType>(*TI)) {
597 assert(Indices[CurIDX]->getType() ==
598 Type::getInt32Ty(ptrTy->getContext()) &&
599 "Illegal struct idx");
600 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
602 // Get structure layout information...
603 const StructLayout *Layout = getStructLayout(STy);
605 // Add in the offset, as calculated by the structure layout info...
606 Result += Layout->getElementOffset(FieldNo);
608 // Update Ty to refer to current element
609 Ty = STy->getElementType(FieldNo);
611 // Update Ty to refer to current element
612 Ty = cast<SequentialType>(Ty)->getElementType();
614 // Get the array index and the size of each array element.
615 int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
616 Result += arrayIdx * (int64_t)getTypeAllocSize(Ty);
623 /// getPreferredAlignment - Return the preferred alignment of the specified
624 /// global. This includes an explicitly requested alignment (if the global
626 unsigned TargetData::getPreferredAlignment(const GlobalVariable *GV) const {
627 const Type *ElemType = GV->getType()->getElementType();
628 unsigned Alignment = getPrefTypeAlignment(ElemType);
629 if (GV->getAlignment() > Alignment)
630 Alignment = GV->getAlignment();
632 if (GV->hasInitializer()) {
633 if (Alignment < 16) {
634 // If the global is not external, see if it is large. If so, give it a
636 if (getTypeSizeInBits(ElemType) > 128)
637 Alignment = 16; // 16-byte alignment.
643 /// getPreferredAlignmentLog - Return the preferred alignment of the
644 /// specified global, returned in log form. This includes an explicitly
645 /// requested alignment (if the global has one).
646 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
647 return Log2_32(getPreferredAlignment(GV));