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/IR/DataLayout.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/DerivedTypes.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/GetElementPtrTypeIterator.h"
26 #include "llvm/Support/ManagedStatic.h"
27 #include "llvm/Support/MathExtras.h"
28 #include "llvm/Support/Mutex.h"
29 #include "llvm/Support/raw_ostream.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 &DL) {
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 : DL.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 += DL.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 = LayoutAlignElem::get(INVALID_ALIGN, 0, 0, 0);
123 //===----------------------------------------------------------------------===//
124 // PointerAlignElem, PointerAlign support
125 //===----------------------------------------------------------------------===//
128 PointerAlignElem::get(uint32_t addr_space, unsigned abi_align,
129 unsigned pref_align, uint32_t bit_width) {
130 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
131 PointerAlignElem retval;
132 retval.AddressSpace = addr_space;
133 retval.ABIAlign = abi_align;
134 retval.PrefAlign = pref_align;
135 retval.TypeBitWidth = bit_width;
140 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
141 return (ABIAlign == rhs.ABIAlign
142 && AddressSpace == rhs.AddressSpace
143 && PrefAlign == rhs.PrefAlign
144 && TypeBitWidth == rhs.TypeBitWidth);
147 const PointerAlignElem
148 DataLayout::InvalidPointerElem = PointerAlignElem::get(~0U, 0U, 0U, 0U);
150 //===----------------------------------------------------------------------===//
151 // DataLayout Class Implementation
152 //===----------------------------------------------------------------------===//
154 void DataLayout::init(StringRef Desc) {
155 initializeDataLayoutPass(*PassRegistry::getPassRegistry());
158 LittleEndian = false;
159 StackNaturalAlign = 0;
161 // Default alignments
162 setAlignment(INTEGER_ALIGN, 1, 1, 1); // i1
163 setAlignment(INTEGER_ALIGN, 1, 1, 8); // i8
164 setAlignment(INTEGER_ALIGN, 2, 2, 16); // i16
165 setAlignment(INTEGER_ALIGN, 4, 4, 32); // i32
166 setAlignment(INTEGER_ALIGN, 4, 8, 64); // i64
167 setAlignment(FLOAT_ALIGN, 2, 2, 16); // half
168 setAlignment(FLOAT_ALIGN, 4, 4, 32); // float
169 setAlignment(FLOAT_ALIGN, 8, 8, 64); // double
170 setAlignment(FLOAT_ALIGN, 16, 16, 128); // ppcf128, quad, ...
171 setAlignment(VECTOR_ALIGN, 8, 8, 64); // v2i32, v1i64, ...
172 setAlignment(VECTOR_ALIGN, 16, 16, 128); // v16i8, v8i16, v4i32, ...
173 setAlignment(AGGREGATE_ALIGN, 0, 8, 0); // struct
174 setPointerAlignment(0, 8, 8, 8);
176 parseSpecifier(Desc);
179 /// Checked version of split, to ensure mandatory subparts.
180 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
181 assert(!Str.empty() && "parse error, string can't be empty here");
182 std::pair<StringRef, StringRef> Split = Str.split(Separator);
183 assert((!Split.second.empty() || Split.first == Str) &&
184 "a trailing separator is not allowed");
188 /// Get an unsinged integer, including error checks.
189 static unsigned getInt(StringRef R) {
191 bool error = R.getAsInteger(10, Result); (void)error;
192 assert(!error && "not a number, or does not fit in an unsigned int");
196 /// Convert bits into bytes. Assert if not a byte width multiple.
197 static unsigned inBytes(unsigned Bits) {
198 assert(Bits % 8 == 0 && "number of bits must be a byte width multiple");
202 void DataLayout::parseSpecifier(StringRef Desc) {
203 while (!Desc.empty()) {
205 std::pair<StringRef, StringRef> Split = split(Desc, '-');
209 Split = split(Split.first, ':');
211 // Aliases used below.
212 StringRef &Tok = Split.first; // Current token.
213 StringRef &Rest = Split.second; // The rest of the string.
215 char Specifier = Tok.front();
220 LittleEndian = false;
227 unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
228 assert(AddrSpace < 1 << 24 &&
229 "Invalid address space, must be a 24bit integer");
232 Split = split(Rest, ':');
233 unsigned PointerMemSize = inBytes(getInt(Tok));
236 Split = split(Rest, ':');
237 unsigned PointerABIAlign = inBytes(getInt(Tok));
239 // Preferred alignment.
240 unsigned PointerPrefAlign = PointerABIAlign;
242 Split = split(Rest, ':');
243 PointerPrefAlign = inBytes(getInt(Tok));
246 setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
255 AlignTypeEnum AlignType;
258 case 'i': AlignType = INTEGER_ALIGN; break;
259 case 'v': AlignType = VECTOR_ALIGN; break;
260 case 'f': AlignType = FLOAT_ALIGN; break;
261 case 'a': AlignType = AGGREGATE_ALIGN; break;
262 case 's': AlignType = STACK_ALIGN; break;
266 unsigned Size = Tok.empty() ? 0 : getInt(Tok);
269 Split = split(Rest, ':');
270 unsigned ABIAlign = inBytes(getInt(Tok));
272 // Preferred alignment.
273 unsigned PrefAlign = ABIAlign;
275 Split = split(Rest, ':');
276 PrefAlign = inBytes(getInt(Tok));
279 setAlignment(AlignType, ABIAlign, PrefAlign, Size);
283 case 'n': // Native integer types.
285 unsigned Width = getInt(Tok);
286 assert(Width != 0 && "width must be non-zero");
287 LegalIntWidths.push_back(Width);
290 Split = split(Rest, ':');
293 case 'S': { // Stack natural alignment.
294 StackNaturalAlign = inBytes(getInt(Tok));
298 llvm_unreachable("Unknown specifier in datalayout string");
306 /// @note This has to exist, because this is a pass, but it should never be
308 DataLayout::DataLayout() : ImmutablePass(ID) {
309 report_fatal_error("Bad DataLayout ctor used. "
310 "Tool did not specify a DataLayout to use?");
313 DataLayout::DataLayout(const Module *M)
314 : ImmutablePass(ID) {
315 init(M->getDataLayout());
319 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
320 unsigned pref_align, uint32_t bit_width) {
321 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
322 assert(pref_align < (1 << 16) && "Alignment doesn't fit in bitfield");
323 assert(bit_width < (1 << 24) && "Bit width doesn't fit in bitfield");
324 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
325 if (Alignments[i].AlignType == (unsigned)align_type &&
326 Alignments[i].TypeBitWidth == bit_width) {
327 // Update the abi, preferred alignments.
328 Alignments[i].ABIAlign = abi_align;
329 Alignments[i].PrefAlign = pref_align;
334 Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
335 pref_align, bit_width));
339 DataLayout::setPointerAlignment(uint32_t addr_space, unsigned abi_align,
340 unsigned pref_align, uint32_t bit_width) {
341 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
342 DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(addr_space);
343 if (val == Pointers.end()) {
344 Pointers[addr_space] = PointerAlignElem::get(addr_space,
345 abi_align, pref_align, bit_width);
347 val->second.ABIAlign = abi_align;
348 val->second.PrefAlign = pref_align;
349 val->second.TypeBitWidth = bit_width;
353 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
354 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
355 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
356 uint32_t BitWidth, bool ABIInfo,
358 // Check to see if we have an exact match and remember the best match we see.
359 int BestMatchIdx = -1;
361 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
362 if (Alignments[i].AlignType == (unsigned)AlignType &&
363 Alignments[i].TypeBitWidth == BitWidth)
364 return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
366 // The best match so far depends on what we're looking for.
367 if (AlignType == INTEGER_ALIGN &&
368 Alignments[i].AlignType == INTEGER_ALIGN) {
369 // The "best match" for integers is the smallest size that is larger than
370 // the BitWidth requested.
371 if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
372 Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
374 // However, if there isn't one that's larger, then we must use the
375 // largest one we have (see below)
376 if (LargestInt == -1 ||
377 Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
382 // Okay, we didn't find an exact solution. Fall back here depending on what
383 // is being looked for.
384 if (BestMatchIdx == -1) {
385 // If we didn't find an integer alignment, fall back on most conservative.
386 if (AlignType == INTEGER_ALIGN) {
387 BestMatchIdx = LargestInt;
389 assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
391 // By default, use natural alignment for vector types. This is consistent
392 // with what clang and llvm-gcc do.
393 unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
394 Align *= cast<VectorType>(Ty)->getNumElements();
395 // If the alignment is not a power of 2, round up to the next power of 2.
396 // This happens for non-power-of-2 length vectors.
397 if (Align & (Align-1))
398 Align = NextPowerOf2(Align);
403 // Since we got a "best match" index, just return it.
404 return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
405 : Alignments[BestMatchIdx].PrefAlign;
410 class StructLayoutMap {
411 typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
412 LayoutInfoTy LayoutInfo;
415 virtual ~StructLayoutMap() {
416 // Remove any layouts.
417 for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
419 StructLayout *Value = I->second;
420 Value->~StructLayout();
425 StructLayout *&operator[](StructType *STy) {
426 return LayoutInfo[STy];
430 virtual void dump() const {}
433 } // end anonymous namespace
435 DataLayout::~DataLayout() {
436 delete static_cast<StructLayoutMap*>(LayoutMap);
439 bool DataLayout::doFinalization(Module &M) {
440 delete static_cast<StructLayoutMap*>(LayoutMap);
445 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
447 LayoutMap = new StructLayoutMap();
449 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
450 StructLayout *&SL = (*STM)[Ty];
453 // Otherwise, create the struct layout. Because it is variable length, we
454 // malloc it, then use placement new.
455 int NumElts = Ty->getNumElements();
457 (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
459 // Set SL before calling StructLayout's ctor. The ctor could cause other
460 // entries to be added to TheMap, invalidating our reference.
463 new (L) StructLayout(Ty, *this);
468 std::string DataLayout::getStringRepresentation() const {
470 raw_string_ostream OS(Result);
472 OS << (LittleEndian ? "e" : "E");
473 SmallVector<unsigned, 8> addrSpaces;
474 // Lets get all of the known address spaces and sort them
475 // into increasing order so that we can emit the string
476 // in a cleaner format.
477 for (DenseMap<unsigned, PointerAlignElem>::const_iterator
478 pib = Pointers.begin(), pie = Pointers.end();
480 addrSpaces.push_back(pib->first);
482 std::sort(addrSpaces.begin(), addrSpaces.end());
483 for (SmallVectorImpl<unsigned>::iterator asb = addrSpaces.begin(),
484 ase = addrSpaces.end(); asb != ase; ++asb) {
485 const PointerAlignElem &PI = Pointers.find(*asb)->second;
487 if (PI.AddressSpace) {
488 OS << PI.AddressSpace;
490 OS << ":" << PI.TypeBitWidth*8 << ':' << PI.ABIAlign*8
491 << ':' << PI.PrefAlign*8;
493 OS << "-S" << StackNaturalAlign*8;
495 for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
496 const LayoutAlignElem &AI = Alignments[i];
497 OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
498 << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
501 if (!LegalIntWidths.empty()) {
502 OS << "-n" << (unsigned)LegalIntWidths[0];
504 for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
505 OS << ':' << (unsigned)LegalIntWidths[i];
512 \param abi_or_pref Flag that determines which alignment is returned. true
513 returns the ABI alignment, false returns the preferred alignment.
514 \param Ty The underlying type for which alignment is determined.
516 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
517 == false) for the requested type \a Ty.
519 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
522 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
523 switch (Ty->getTypeID()) {
524 // Early escape for the non-numeric types.
525 case Type::LabelTyID:
527 ? getPointerABIAlignment(0)
528 : getPointerPrefAlignment(0));
529 case Type::PointerTyID: {
530 unsigned AS = dyn_cast<PointerType>(Ty)->getAddressSpace();
532 ? getPointerABIAlignment(AS)
533 : getPointerPrefAlignment(AS));
535 case Type::ArrayTyID:
536 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
538 case Type::StructTyID: {
539 // Packed structure types always have an ABI alignment of one.
540 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
543 // Get the layout annotation... which is lazily created on demand.
544 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
545 unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
546 return std::max(Align, Layout->getAlignment());
548 case Type::IntegerTyID:
549 AlignType = INTEGER_ALIGN;
552 case Type::FloatTyID:
553 case Type::DoubleTyID:
554 // PPC_FP128TyID and FP128TyID have different data contents, but the
555 // same size and alignment, so they look the same here.
556 case Type::PPC_FP128TyID:
557 case Type::FP128TyID:
558 case Type::X86_FP80TyID:
559 AlignType = FLOAT_ALIGN;
561 case Type::X86_MMXTyID:
562 case Type::VectorTyID:
563 AlignType = VECTOR_ALIGN;
566 llvm_unreachable("Bad type for getAlignment!!!");
569 return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
573 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
574 return getAlignment(Ty, true);
577 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
578 /// an integer type of the specified bitwidth.
579 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
580 return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
583 unsigned DataLayout::getCallFrameTypeAlignment(Type *Ty) const {
584 for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
585 if (Alignments[i].AlignType == STACK_ALIGN)
586 return Alignments[i].ABIAlign;
588 return getABITypeAlignment(Ty);
591 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
592 return getAlignment(Ty, false);
595 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
596 unsigned Align = getPrefTypeAlignment(Ty);
597 assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
598 return Log2_32(Align);
601 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
602 unsigned AddressSpace) const {
603 return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
606 Type *DataLayout::getIntPtrType(Type *Ty) const {
607 assert(Ty->isPtrOrPtrVectorTy() &&
608 "Expected a pointer or pointer vector type.");
609 unsigned NumBits = getTypeSizeInBits(Ty->getScalarType());
610 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
611 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
612 return VectorType::get(IntTy, VecTy->getNumElements());
616 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
617 for (unsigned i = 0, e = (unsigned)LegalIntWidths.size(); i != e; ++i)
618 if (Width <= LegalIntWidths[i])
619 return Type::getIntNTy(C, LegalIntWidths[i]);
623 uint64_t DataLayout::getIndexedOffset(Type *ptrTy,
624 ArrayRef<Value *> Indices) const {
626 assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
629 generic_gep_type_iterator<Value* const*>
630 TI = gep_type_begin(ptrTy, Indices);
631 for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
633 if (StructType *STy = dyn_cast<StructType>(*TI)) {
634 assert(Indices[CurIDX]->getType() ==
635 Type::getInt32Ty(ptrTy->getContext()) &&
636 "Illegal struct idx");
637 unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
639 // Get structure layout information...
640 const StructLayout *Layout = getStructLayout(STy);
642 // Add in the offset, as calculated by the structure layout info...
643 Result += Layout->getElementOffset(FieldNo);
645 // Update Ty to refer to current element
646 Ty = STy->getElementType(FieldNo);
648 // Update Ty to refer to current element
649 Ty = cast<SequentialType>(Ty)->getElementType();
651 // Get the array index and the size of each array element.
652 if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
653 Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
660 /// getPreferredAlignment - Return the preferred alignment of the specified
661 /// global. This includes an explicitly requested alignment (if the global
663 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
664 Type *ElemType = GV->getType()->getElementType();
665 unsigned Alignment = getPrefTypeAlignment(ElemType);
666 unsigned GVAlignment = GV->getAlignment();
667 if (GVAlignment >= Alignment) {
668 Alignment = GVAlignment;
669 } else if (GVAlignment != 0) {
670 Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
673 if (GV->hasInitializer() && GVAlignment == 0) {
674 if (Alignment < 16) {
675 // If the global is not external, see if it is large. If so, give it a
677 if (getTypeSizeInBits(ElemType) > 128)
678 Alignment = 16; // 16-byte alignment.
684 /// getPreferredAlignmentLog - Return the preferred alignment of the
685 /// specified global, returned in log form. This includes an explicitly
686 /// requested alignment (if the global has one).
687 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
688 return Log2_32(getPreferredAlignment(GV));