1 //===-- DataLayout.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 layout 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/DataLayout.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/Support/Mutex.h"
29 #include "llvm/ADT/DenseMap.h"
34 // Handle the Pass registration stuff necessary to use DataLayout's.
36 // Register the default SparcV9 implementation...
37 INITIALIZE_PASS(DataLayout, "datalayout", "Data Layout", false, true)
38 char DataLayout::ID = 0;
40 //===----------------------------------------------------------------------===//
41 // Support for StructLayout
42 //===----------------------------------------------------------------------===//
44 StructLayout::StructLayout(StructType *ST, const DataLayout &TD) {
45 assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
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 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 = DataLayout::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 = DataLayout::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 // LayoutAlignElem, LayoutAlign support
98 //===----------------------------------------------------------------------===//
101 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
102 unsigned pref_align, uint32_t bit_width) {
103 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
104 LayoutAlignElem retval;
105 retval.AlignType = align_type;
106 retval.ABIAlign = abi_align;
107 retval.PrefAlign = pref_align;
108 retval.TypeBitWidth = bit_width;
113 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
114 return (AlignType == rhs.AlignType
115 && ABIAlign == rhs.ABIAlign
116 && PrefAlign == rhs.PrefAlign
117 && TypeBitWidth == rhs.TypeBitWidth);
120 const LayoutAlignElem
121 DataLayout::InvalidAlignmentElem = { (AlignTypeEnum)0xFF, 0, 0, 0 };
123 //===----------------------------------------------------------------------===//
124 // DataLayout Class Implementation
125 //===----------------------------------------------------------------------===//
127 /// getInt - Get an integer ignoring errors.
128 static int getInt(StringRef R) {
130 R.getAsInteger(10, Result);
134 void DataLayout::init() {
135 initializeDataLayoutPass(*PassRegistry::getPassRegistry());
138 LittleEndian = false;
141 PointerPrefAlign = PointerABIAlign;
142 StackNaturalAlign = 0;
144 // Default alignments
145 setAlignment(INTEGER_ALIGN, 1, 1, 1); // i1
146 setAlignment(INTEGER_ALIGN, 1, 1, 8); // i8
147 setAlignment(INTEGER_ALIGN, 2, 2, 16); // i16
148 setAlignment(INTEGER_ALIGN, 4, 4, 32); // i32
149 setAlignment(INTEGER_ALIGN, 4, 8, 64); // i64
150 setAlignment(FLOAT_ALIGN, 2, 2, 16); // half
151 setAlignment(FLOAT_ALIGN, 4, 4, 32); // float
152 setAlignment(FLOAT_ALIGN, 8, 8, 64); // double
153 setAlignment(FLOAT_ALIGN, 16, 16, 128); // ppcf128, quad, ...
154 setAlignment(VECTOR_ALIGN, 8, 8, 64); // v2i32, v1i64, ...
155 setAlignment(VECTOR_ALIGN, 16, 16, 128); // v16i8, v8i16, v4i32, ...
156 setAlignment(AGGREGATE_ALIGN, 0, 8, 0); // struct
159 std::string DataLayout::parseSpecifier(StringRef Desc, DataLayout *td) {
164 while (!Desc.empty()) {
165 std::pair<StringRef, StringRef> Split = Desc.split('-');
166 StringRef Token = Split.first;
172 Split = Token.split(':');
173 StringRef Specifier = Split.first;
174 Token = Split.second;
176 assert(!Specifier.empty() && "Can't be empty here");
178 switch (Specifier[0]) {
181 td->LittleEndian = false;
185 td->LittleEndian = true;
189 Split = Token.split(':');
190 int PointerMemSizeBits = getInt(Split.first);
191 if (PointerMemSizeBits < 0 || PointerMemSizeBits % 8 != 0)
192 return "invalid pointer size, must be a positive 8-bit multiple";
194 td->PointerMemSize = PointerMemSizeBits / 8;
196 // Pointer ABI alignment.
197 Split = Split.second.split(':');
198 int PointerABIAlignBits = getInt(Split.first);
199 if (PointerABIAlignBits < 0 || PointerABIAlignBits % 8 != 0) {
200 return "invalid pointer ABI alignment, "
201 "must be a positive 8-bit multiple";
204 td->PointerABIAlign = PointerABIAlignBits / 8;
206 // Pointer preferred alignment.
207 Split = Split.second.split(':');
208 int PointerPrefAlignBits = getInt(Split.first);
209 if (PointerPrefAlignBits < 0 || PointerPrefAlignBits % 8 != 0) {
210 return "invalid pointer preferred alignment, "
211 "must be a positive 8-bit multiple";
214 td->PointerPrefAlign = PointerPrefAlignBits / 8;
215 if (td->PointerPrefAlign == 0)
216 td->PointerPrefAlign = td->PointerABIAlign;
225 AlignTypeEnum AlignType;
226 char field = Specifier[0];
229 case 'i': AlignType = INTEGER_ALIGN; break;
230 case 'v': AlignType = VECTOR_ALIGN; break;
231 case 'f': AlignType = FLOAT_ALIGN; break;
232 case 'a': AlignType = AGGREGATE_ALIGN; break;
233 case 's': AlignType = STACK_ALIGN; break;
235 int Size = getInt(Specifier.substr(1));
237 return std::string("invalid ") + field + "-size field, "
241 Split = Token.split(':');
242 int ABIAlignBits = getInt(Split.first);
243 if (ABIAlignBits < 0 || ABIAlignBits % 8 != 0) {
244 return std::string("invalid ") + field +"-abi-alignment field, "
245 "must be a positive 8-bit multiple";
247 unsigned ABIAlign = ABIAlignBits / 8;
249 Split = Split.second.split(':');
251 int PrefAlignBits = getInt(Split.first);
252 if (PrefAlignBits < 0 || PrefAlignBits % 8 != 0) {
253 return std::string("invalid ") + field +"-preferred-alignment field, "
254 "must be a positive 8-bit multiple";
256 unsigned PrefAlign = PrefAlignBits / 8;
258 PrefAlign = ABIAlign;
261 td->setAlignment(AlignType, ABIAlign, PrefAlign, Size);
264 case 'n': // Native integer types.
265 Specifier = Specifier.substr(1);
267 int Width = getInt(Specifier);
269 return std::string("invalid native integer size \'") +
270 Specifier.str() + "\', must be a positive integer.";
272 if (td && Width != 0)
273 td->LegalIntWidths.push_back(Width);
274 Split = Token.split(':');
275 Specifier = Split.first;
276 Token = Split.second;
277 } while (!Specifier.empty() || !Token.empty());
279 case 'S': { // Stack natural alignment.
280 int StackNaturalAlignBits = getInt(Specifier.substr(1));
281 if (StackNaturalAlignBits < 0 || StackNaturalAlignBits % 8 != 0) {
282 return "invalid natural stack alignment (S-field), "
283 "must be a positive 8-bit multiple";
286 td->StackNaturalAlign = StackNaturalAlignBits / 8;
299 /// @note This has to exist, because this is a pass, but it should never be
301 DataLayout::DataLayout() : ImmutablePass(ID) {
302 report_fatal_error("Bad DataLayout ctor used. "
303 "Tool did not specify a DataLayout to use?");
306 DataLayout::DataLayout(const Module *M)
307 : ImmutablePass(ID) {
308 std::string errMsg = parseSpecifier(M->getDataLayout(), this);
309 assert(errMsg == "" && "Module M has malformed data layout string.");
314 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
315 unsigned pref_align, uint32_t bit_width) {
316 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
317 assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
318 assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
319 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
320 if (Alignments[i].AlignType == align_type &&
321 Alignments[i].TypeBitWidth == bit_width) {
322 // Update the abi, preferred alignments.
323 Alignments[i].ABIAlign = abi_align;
324 Alignments[i].PrefAlign = pref_align;
329 Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
330 pref_align, bit_width));
333 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
334 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
335 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
336 uint32_t BitWidth, bool ABIInfo,
338 // Check to see if we have an exact match and remember the best match we see.
339 int BestMatchIdx = -1;
341 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
342 if (Alignments[i].AlignType == AlignType &&
343 Alignments[i].TypeBitWidth == BitWidth)
344 return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
346 // The best match so far depends on what we're looking for.
347 if (AlignType == INTEGER_ALIGN &&
348 Alignments[i].AlignType == INTEGER_ALIGN) {
349 // The "best match" for integers is the smallest size that is larger than
350 // the BitWidth requested.
351 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
352 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
354 // However, if there isn't one that's larger, then we must use the
355 // largest one we have (see below)
356 if (LargestInt == -1 ||
357 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
362 // Okay, we didn't find an exact solution. Fall back here depending on what
363 // is being looked for.
364 if (BestMatchIdx == -1) {
365 // If we didn't find an integer alignment, fall back on most conservative.
366 if (AlignType == INTEGER_ALIGN) {
367 BestMatchIdx = LargestInt;
369 assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
371 // By default, use natural alignment for vector types. This is consistent
372 // with what clang and llvm-gcc do.
373 unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
374 Align *= cast<VectorType>(Ty)->getNumElements();
375 // If the alignment is not a power of 2, round up to the next power of 2.
376 // This happens for non-power-of-2 length vectors.
377 if (Align & (Align-1))
378 Align = NextPowerOf2(Align);
383 // Since we got a "best match" index, just return it.
384 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
385 : Alignments[BestMatchIdx].PrefAlign;
390 class StructLayoutMap {
391 typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
392 LayoutInfoTy LayoutInfo;
395 virtual ~StructLayoutMap() {
396 // Remove any layouts.
397 for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
399 StructLayout *Value = I->second;
400 Value->~StructLayout();
405 StructLayout *&operator[](StructType *STy) {
406 return LayoutInfo[STy];
410 virtual void dump() const {}
413 } // end anonymous namespace
415 DataLayout::~DataLayout() {
416 delete static_cast<StructLayoutMap*>(LayoutMap);
419 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
421 LayoutMap = new StructLayoutMap();
423 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
424 StructLayout *&SL = (*STM)[Ty];
427 // Otherwise, create the struct layout. Because it is variable length, we
428 // malloc it, then use placement new.
429 int NumElts = Ty->getNumElements();
431 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
433 // Set SL before calling StructLayout's ctor. The ctor could cause other
434 // entries to be added to TheMap, invalidating our reference.
437 new (L) StructLayout(Ty, *this);
442 std::string DataLayout::getStringRepresentation() const {
444 raw_string_ostream OS(Result);
446 OS << (LittleEndian ? "e" : "E")
447 << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
448 << ':' << PointerPrefAlign*8
449 << "-S" << StackNaturalAlign*8;
451 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
452 const LayoutAlignElem &AI = Alignments[i];
453 OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
454 << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
457 if (!LegalIntWidths.empty()) {
458 OS << "-n" << (unsigned)LegalIntWidths[0];
460 for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
461 OS << ':' << (unsigned)LegalIntWidths[i];
467 uint64_t DataLayout::getTypeSizeInBits(Type *Ty) const {
468 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
469 switch (Ty->getTypeID()) {
470 case Type::LabelTyID:
471 case Type::PointerTyID:
472 return getPointerSizeInBits();
473 case Type::ArrayTyID: {
474 ArrayType *ATy = cast<ArrayType>(Ty);
475 return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
477 case Type::StructTyID:
478 // Get the layout annotation... which is lazily created on demand.
479 return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
480 case Type::IntegerTyID:
481 return cast<IntegerType>(Ty)->getBitWidth();
486 case Type::FloatTyID:
488 case Type::DoubleTyID:
489 case Type::X86_MMXTyID:
491 case Type::PPC_FP128TyID:
492 case Type::FP128TyID:
494 // In memory objects this is always aligned to a higher boundary, but
495 // only 80 bits contain information.
496 case Type::X86_FP80TyID:
498 case Type::VectorTyID:
499 return cast<VectorType>(Ty)->getBitWidth();
501 llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type");
506 \param abi_or_pref Flag that determines which alignment is returned. true
507 returns the ABI alignment, false returns the preferred alignment.
508 \param Ty The underlying type for which alignment is determined.
510 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
511 == false) for the requested type \a Ty.
513 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
516 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
517 switch (Ty->getTypeID()) {
518 // Early escape for the non-numeric types.
519 case Type::LabelTyID:
520 case Type::PointerTyID:
522 ? getPointerABIAlignment()
523 : getPointerPrefAlignment());
524 case Type::ArrayTyID:
525 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
527 case Type::StructTyID: {
528 // Packed structure types always have an ABI alignment of one.
529 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
532 // Get the layout annotation... which is lazily created on demand.
533 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
534 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
535 return std::max(Align, Layout->getAlignment());
537 case Type::IntegerTyID:
539 AlignType = INTEGER_ALIGN;
542 case Type::FloatTyID:
543 case Type::DoubleTyID:
544 // PPC_FP128TyID and FP128TyID have different data contents, but the
545 // same size and alignment, so they look the same here.
546 case Type::PPC_FP128TyID:
547 case Type::FP128TyID:
548 case Type::X86_FP80TyID:
549 AlignType = FLOAT_ALIGN;
551 case Type::X86_MMXTyID:
552 case Type::VectorTyID:
553 AlignType = VECTOR_ALIGN;
556 llvm_unreachable("Bad type for getAlignment!!!");
559 return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
563 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
564 return getAlignment(Ty, true);
567 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
568 /// an integer type of the specified bitwidth.
569 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
570 return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
574 unsigned DataLayout::getCallFrameTypeAlignment(Type *Ty) const {
575 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
576 if (Alignments[i].AlignType == STACK_ALIGN)
577 return Alignments[i].ABIAlign;
579 return getABITypeAlignment(Ty);
582 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
583 return getAlignment(Ty, false);
586 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
587 unsigned Align = getPrefTypeAlignment(Ty);
588 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
589 return Log2_32(Align);
592 /// getIntPtrType - Return an unsigned integer type that is the same size or
593 /// greater to the host pointer size.
594 IntegerType *DataLayout::getIntPtrType(LLVMContext &C) const {
595 return IntegerType::get(C, getPointerSizeInBits());
599 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
600 ArrayRef<Value *> Indices) const {
602 assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
605 generic_gep_type_iterator<Value* const*>
606 TI = gep_type_begin(ptrTy, Indices);
607 for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
609 if (StructType *STy = dyn_cast<StructType>(*TI)) {
610 assert(Indices[CurIDX]->getType() ==
611 Type::getInt32Ty(ptrTy->getContext()) &&
612 "Illegal struct idx");
613 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
615 // Get structure layout information...
616 const StructLayout *Layout = getStructLayout(STy);
618 // Add in the offset, as calculated by the structure layout info...
619 Result += Layout->getElementOffset(FieldNo);
621 // Update Ty to refer to current element
622 Ty = STy->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 += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
636 /// getPreferredAlignment - Return the preferred alignment of the specified
637 /// global. This includes an explicitly requested alignment (if the global
639 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
640 Type *ElemType = GV->getType()->getElementType();
641 unsigned Alignment = getPrefTypeAlignment(ElemType);
642 unsigned GVAlignment = GV->getAlignment();
643 if (GVAlignment >= Alignment) {
644 Alignment = GVAlignment;
645 } else if (GVAlignment != 0) {
646 Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
649 if (GV->hasInitializer() && GVAlignment == 0) {
650 if (Alignment < 16) {
651 // If the global is not external, see if it is large. If so, give it a
653 if (getTypeSizeInBits(ElemType) > 128)
654 Alignment = 16; // 16-byte alignment.
660 /// getPreferredAlignmentLog - Return the preferred alignment of the
661 /// specified global, returned in log form. This includes an explicitly
662 /// requested alignment (if the global has one).
663 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
664 return Log2_32(getPreferredAlignment(GV));