1 //===- DataLayout.cpp - Data size & alignment routines ---------------------==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines layout properties related to datatype size/offset/alignment
10 // information.
11 //
12 // This structure should be created once, filled in if the defaults are not
13 // correct and then passed around by const&. None of the members functions
14 // require modification to the object.
15 //
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/Triple.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/GetElementPtrTypeIterator.h"
25 #include "llvm/IR/GlobalVariable.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/IR/Type.h"
28 #include "llvm/IR/Value.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/Error.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include "llvm/Support/MathExtras.h"
33 #include "llvm/Support/TypeSize.h"
34 #include <algorithm>
35 #include <cassert>
36 #include <cstdint>
37 #include <cstdlib>
38 #include <tuple>
39 #include <utility>
40
41 using namespace llvm;
42
43 //===----------------------------------------------------------------------===//
44 // Support for StructLayout
45 //===----------------------------------------------------------------------===//
46
StructLayout(StructType * ST,const DataLayout & DL)47 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
48 assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
49 StructSize = 0;
50 IsPadded = false;
51 NumElements = ST->getNumElements();
52
53 // Loop over each of the elements, placing them in memory.
54 for (unsigned i = 0, e = NumElements; i != e; ++i) {
55 Type *Ty = ST->getElementType(i);
56 const Align TyAlign = ST->isPacked() ? Align(1) : DL.getABITypeAlign(Ty);
57
58 // Add padding if necessary to align the data element properly.
59 if (!isAligned(TyAlign, StructSize)) {
60 IsPadded = true;
61 StructSize = alignTo(StructSize, TyAlign);
62 }
63
64 // Keep track of maximum alignment constraint.
65 StructAlignment = std::max(TyAlign, StructAlignment);
66
67 getMemberOffsets()[i] = StructSize;
68 // Consume space for this data item
69 StructSize += DL.getTypeAllocSize(Ty).getFixedValue();
70 }
71
72 // Add padding to the end of the struct so that it could be put in an array
73 // and all array elements would be aligned correctly.
74 if (!isAligned(StructAlignment, StructSize)) {
75 IsPadded = true;
76 StructSize = alignTo(StructSize, StructAlignment);
77 }
78 }
79
80 /// getElementContainingOffset - Given a valid offset into the structure,
81 /// return the structure index that contains it.
getElementContainingOffset(uint64_t Offset) const82 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
83 ArrayRef<uint64_t> MemberOffsets = getMemberOffsets();
84 auto SI = llvm::upper_bound(MemberOffsets, Offset);
85 assert(SI != MemberOffsets.begin() && "Offset not in structure type!");
86 --SI;
87 assert(*SI <= Offset && "upper_bound didn't work");
88 assert((SI == MemberOffsets.begin() || *(SI - 1) <= Offset) &&
89 (SI + 1 == MemberOffsets.end() || *(SI + 1) > Offset) &&
90 "Upper bound didn't work!");
91
92 // Multiple fields can have the same offset if any of them are zero sized.
93 // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
94 // at the i32 element, because it is the last element at that offset. This is
95 // the right one to return, because anything after it will have a higher
96 // offset, implying that this element is non-empty.
97 return SI - MemberOffsets.begin();
98 }
99
100 //===----------------------------------------------------------------------===//
101 // LayoutAlignElem, LayoutAlign support
102 //===----------------------------------------------------------------------===//
103
get(AlignTypeEnum align_type,Align abi_align,Align pref_align,uint32_t bit_width)104 LayoutAlignElem LayoutAlignElem::get(AlignTypeEnum align_type, Align abi_align,
105 Align pref_align, uint32_t bit_width) {
106 assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
107 LayoutAlignElem retval;
108 retval.AlignType = align_type;
109 retval.ABIAlign = abi_align;
110 retval.PrefAlign = pref_align;
111 retval.TypeBitWidth = bit_width;
112 return retval;
113 }
114
115 bool
operator ==(const LayoutAlignElem & rhs) const116 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
117 return (AlignType == rhs.AlignType
118 && ABIAlign == rhs.ABIAlign
119 && PrefAlign == rhs.PrefAlign
120 && TypeBitWidth == rhs.TypeBitWidth);
121 }
122
123 //===----------------------------------------------------------------------===//
124 // PointerAlignElem, PointerAlign support
125 //===----------------------------------------------------------------------===//
126
get(uint32_t AddressSpace,Align ABIAlign,Align PrefAlign,uint32_t TypeByteWidth,uint32_t IndexWidth)127 PointerAlignElem PointerAlignElem::get(uint32_t AddressSpace, Align ABIAlign,
128 Align PrefAlign, uint32_t TypeByteWidth,
129 uint32_t IndexWidth) {
130 assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
131 PointerAlignElem retval;
132 retval.AddressSpace = AddressSpace;
133 retval.ABIAlign = ABIAlign;
134 retval.PrefAlign = PrefAlign;
135 retval.TypeByteWidth = TypeByteWidth;
136 retval.IndexWidth = IndexWidth;
137 return retval;
138 }
139
140 bool
operator ==(const PointerAlignElem & rhs) const141 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
142 return (ABIAlign == rhs.ABIAlign
143 && AddressSpace == rhs.AddressSpace
144 && PrefAlign == rhs.PrefAlign
145 && TypeByteWidth == rhs.TypeByteWidth
146 && IndexWidth == rhs.IndexWidth);
147 }
148
149 //===----------------------------------------------------------------------===//
150 // DataLayout Class Implementation
151 //===----------------------------------------------------------------------===//
152
getManglingComponent(const Triple & T)153 const char *DataLayout::getManglingComponent(const Triple &T) {
154 if (T.isOSBinFormatMachO())
155 return "-m:o";
156 if (T.isOSWindows() && T.isOSBinFormatCOFF())
157 return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
158 if (T.isOSBinFormatXCOFF())
159 return "-m:a";
160 return "-m:e";
161 }
162
163 static const LayoutAlignElem DefaultAlignments[] = {
164 {INTEGER_ALIGN, 1, Align(1), Align(1)}, // i1
165 {INTEGER_ALIGN, 8, Align(1), Align(1)}, // i8
166 {INTEGER_ALIGN, 16, Align(2), Align(2)}, // i16
167 {INTEGER_ALIGN, 32, Align(4), Align(4)}, // i32
168 {INTEGER_ALIGN, 64, Align(4), Align(8)}, // i64
169 {FLOAT_ALIGN, 16, Align(2), Align(2)}, // half, bfloat
170 {FLOAT_ALIGN, 32, Align(4), Align(4)}, // float
171 {FLOAT_ALIGN, 64, Align(8), Align(8)}, // double
172 {FLOAT_ALIGN, 128, Align(16), Align(16)}, // ppcf128, quad, ...
173 {VECTOR_ALIGN, 64, Align(8), Align(8)}, // v2i32, v1i64, ...
174 {VECTOR_ALIGN, 128, Align(16), Align(16)}, // v16i8, v8i16, v4i32, ...
175 {AGGREGATE_ALIGN, 0, Align(1), Align(8)} // struct
176 };
177
reset(StringRef Desc)178 void DataLayout::reset(StringRef Desc) {
179 clear();
180
181 LayoutMap = nullptr;
182 BigEndian = false;
183 AllocaAddrSpace = 0;
184 StackNaturalAlign.reset();
185 ProgramAddrSpace = 0;
186 DefaultGlobalsAddrSpace = 0;
187 FunctionPtrAlign.reset();
188 TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
189 ManglingMode = MM_None;
190 NonIntegralAddressSpaces.clear();
191
192 // Default alignments
193 for (const LayoutAlignElem &E : DefaultAlignments) {
194 if (Error Err = setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign,
195 E.PrefAlign, E.TypeBitWidth))
196 return report_fatal_error(std::move(Err));
197 }
198 if (Error Err = setPointerAlignment(0, Align(8), Align(8), 8, 8))
199 return report_fatal_error(std::move(Err));
200
201 if (Error Err = parseSpecifier(Desc))
202 return report_fatal_error(std::move(Err));
203 }
204
parse(StringRef LayoutDescription)205 Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) {
206 DataLayout Layout("");
207 if (Error Err = Layout.parseSpecifier(LayoutDescription))
208 return std::move(Err);
209 return Layout;
210 }
211
reportError(const Twine & Message)212 static Error reportError(const Twine &Message) {
213 return createStringError(inconvertibleErrorCode(), Message);
214 }
215
216 /// Checked version of split, to ensure mandatory subparts.
split(StringRef Str,char Separator,std::pair<StringRef,StringRef> & Split)217 static Error split(StringRef Str, char Separator,
218 std::pair<StringRef, StringRef> &Split) {
219 assert(!Str.empty() && "parse error, string can't be empty here");
220 Split = Str.split(Separator);
221 if (Split.second.empty() && Split.first != Str)
222 return reportError("Trailing separator in datalayout string");
223 if (!Split.second.empty() && Split.first.empty())
224 return reportError("Expected token before separator in datalayout string");
225 return Error::success();
226 }
227
228 /// Get an unsigned integer, including error checks.
getInt(StringRef R,IntTy & Result)229 template <typename IntTy> static Error getInt(StringRef R, IntTy &Result) {
230 bool error = R.getAsInteger(10, Result); (void)error;
231 if (error)
232 return reportError("not a number, or does not fit in an unsigned int");
233 return Error::success();
234 }
235
236 /// Get an unsigned integer representing the number of bits and convert it into
237 /// bytes. Error out of not a byte width multiple.
238 template <typename IntTy>
getIntInBytes(StringRef R,IntTy & Result)239 static Error getIntInBytes(StringRef R, IntTy &Result) {
240 if (Error Err = getInt<IntTy>(R, Result))
241 return Err;
242 if (Result % 8)
243 return reportError("number of bits must be a byte width multiple");
244 Result /= 8;
245 return Error::success();
246 }
247
getAddrSpace(StringRef R,unsigned & AddrSpace)248 static Error getAddrSpace(StringRef R, unsigned &AddrSpace) {
249 if (Error Err = getInt(R, AddrSpace))
250 return Err;
251 if (!isUInt<24>(AddrSpace))
252 return reportError("Invalid address space, must be a 24-bit integer");
253 return Error::success();
254 }
255
parseSpecifier(StringRef Desc)256 Error DataLayout::parseSpecifier(StringRef Desc) {
257 StringRepresentation = std::string(Desc);
258 while (!Desc.empty()) {
259 // Split at '-'.
260 std::pair<StringRef, StringRef> Split;
261 if (Error Err = split(Desc, '-', Split))
262 return Err;
263 Desc = Split.second;
264
265 // Split at ':'.
266 if (Error Err = split(Split.first, ':', Split))
267 return Err;
268
269 // Aliases used below.
270 StringRef &Tok = Split.first; // Current token.
271 StringRef &Rest = Split.second; // The rest of the string.
272
273 if (Tok == "ni") {
274 do {
275 if (Error Err = split(Rest, ':', Split))
276 return Err;
277 Rest = Split.second;
278 unsigned AS;
279 if (Error Err = getInt(Split.first, AS))
280 return Err;
281 if (AS == 0)
282 return reportError("Address space 0 can never be non-integral");
283 NonIntegralAddressSpaces.push_back(AS);
284 } while (!Rest.empty());
285
286 continue;
287 }
288
289 char Specifier = Tok.front();
290 Tok = Tok.substr(1);
291
292 switch (Specifier) {
293 case 's':
294 // Deprecated, but ignoring here to preserve loading older textual llvm
295 // ASM file
296 break;
297 case 'E':
298 BigEndian = true;
299 break;
300 case 'e':
301 BigEndian = false;
302 break;
303 case 'p': {
304 // Address space.
305 unsigned AddrSpace = 0;
306 if (!Tok.empty())
307 if (Error Err = getInt(Tok, AddrSpace))
308 return Err;
309 if (!isUInt<24>(AddrSpace))
310 return reportError("Invalid address space, must be a 24bit integer");
311
312 // Size.
313 if (Rest.empty())
314 return reportError(
315 "Missing size specification for pointer in datalayout string");
316 if (Error Err = split(Rest, ':', Split))
317 return Err;
318 unsigned PointerMemSize;
319 if (Error Err = getIntInBytes(Tok, PointerMemSize))
320 return Err;
321 if (!PointerMemSize)
322 return reportError("Invalid pointer size of 0 bytes");
323
324 // ABI alignment.
325 if (Rest.empty())
326 return reportError(
327 "Missing alignment specification for pointer in datalayout string");
328 if (Error Err = split(Rest, ':', Split))
329 return Err;
330 unsigned PointerABIAlign;
331 if (Error Err = getIntInBytes(Tok, PointerABIAlign))
332 return Err;
333 if (!isPowerOf2_64(PointerABIAlign))
334 return reportError("Pointer ABI alignment must be a power of 2");
335
336 // Size of index used in GEP for address calculation.
337 // The parameter is optional. By default it is equal to size of pointer.
338 unsigned IndexSize = PointerMemSize;
339
340 // Preferred alignment.
341 unsigned PointerPrefAlign = PointerABIAlign;
342 if (!Rest.empty()) {
343 if (Error Err = split(Rest, ':', Split))
344 return Err;
345 if (Error Err = getIntInBytes(Tok, PointerPrefAlign))
346 return Err;
347 if (!isPowerOf2_64(PointerPrefAlign))
348 return reportError(
349 "Pointer preferred alignment must be a power of 2");
350
351 // Now read the index. It is the second optional parameter here.
352 if (!Rest.empty()) {
353 if (Error Err = split(Rest, ':', Split))
354 return Err;
355 if (Error Err = getIntInBytes(Tok, IndexSize))
356 return Err;
357 if (!IndexSize)
358 return reportError("Invalid index size of 0 bytes");
359 }
360 }
361 if (Error Err = setPointerAlignment(
362 AddrSpace, assumeAligned(PointerABIAlign),
363 assumeAligned(PointerPrefAlign), PointerMemSize, IndexSize))
364 return Err;
365 break;
366 }
367 case 'i':
368 case 'v':
369 case 'f':
370 case 'a': {
371 AlignTypeEnum AlignType;
372 switch (Specifier) {
373 default: llvm_unreachable("Unexpected specifier!");
374 case 'i': AlignType = INTEGER_ALIGN; break;
375 case 'v': AlignType = VECTOR_ALIGN; break;
376 case 'f': AlignType = FLOAT_ALIGN; break;
377 case 'a': AlignType = AGGREGATE_ALIGN; break;
378 }
379
380 // Bit size.
381 unsigned Size = 0;
382 if (!Tok.empty())
383 if (Error Err = getInt(Tok, Size))
384 return Err;
385
386 if (AlignType == AGGREGATE_ALIGN && Size != 0)
387 return reportError(
388 "Sized aggregate specification in datalayout string");
389
390 // ABI alignment.
391 if (Rest.empty())
392 return reportError(
393 "Missing alignment specification in datalayout string");
394 if (Error Err = split(Rest, ':', Split))
395 return Err;
396 unsigned ABIAlign;
397 if (Error Err = getIntInBytes(Tok, ABIAlign))
398 return Err;
399 if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
400 return reportError(
401 "ABI alignment specification must be >0 for non-aggregate types");
402
403 if (!isUInt<16>(ABIAlign))
404 return reportError("Invalid ABI alignment, must be a 16bit integer");
405 if (ABIAlign != 0 && !isPowerOf2_64(ABIAlign))
406 return reportError("Invalid ABI alignment, must be a power of 2");
407
408 // Preferred alignment.
409 unsigned PrefAlign = ABIAlign;
410 if (!Rest.empty()) {
411 if (Error Err = split(Rest, ':', Split))
412 return Err;
413 if (Error Err = getIntInBytes(Tok, PrefAlign))
414 return Err;
415 }
416
417 if (!isUInt<16>(PrefAlign))
418 return reportError(
419 "Invalid preferred alignment, must be a 16bit integer");
420 if (PrefAlign != 0 && !isPowerOf2_64(PrefAlign))
421 return reportError("Invalid preferred alignment, must be a power of 2");
422
423 if (Error Err = setAlignment(AlignType, assumeAligned(ABIAlign),
424 assumeAligned(PrefAlign), Size))
425 return Err;
426
427 break;
428 }
429 case 'n': // Native integer types.
430 while (true) {
431 unsigned Width;
432 if (Error Err = getInt(Tok, Width))
433 return Err;
434 if (Width == 0)
435 return reportError(
436 "Zero width native integer type in datalayout string");
437 LegalIntWidths.push_back(Width);
438 if (Rest.empty())
439 break;
440 if (Error Err = split(Rest, ':', Split))
441 return Err;
442 }
443 break;
444 case 'S': { // Stack natural alignment.
445 uint64_t Alignment;
446 if (Error Err = getIntInBytes(Tok, Alignment))
447 return Err;
448 if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
449 return reportError("Alignment is neither 0 nor a power of 2");
450 StackNaturalAlign = MaybeAlign(Alignment);
451 break;
452 }
453 case 'F': {
454 switch (Tok.front()) {
455 case 'i':
456 TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
457 break;
458 case 'n':
459 TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;
460 break;
461 default:
462 return reportError("Unknown function pointer alignment type in "
463 "datalayout string");
464 }
465 Tok = Tok.substr(1);
466 uint64_t Alignment;
467 if (Error Err = getIntInBytes(Tok, Alignment))
468 return Err;
469 if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
470 return reportError("Alignment is neither 0 nor a power of 2");
471 FunctionPtrAlign = MaybeAlign(Alignment);
472 break;
473 }
474 case 'P': { // Function address space.
475 if (Error Err = getAddrSpace(Tok, ProgramAddrSpace))
476 return Err;
477 break;
478 }
479 case 'A': { // Default stack/alloca address space.
480 if (Error Err = getAddrSpace(Tok, AllocaAddrSpace))
481 return Err;
482 break;
483 }
484 case 'G': { // Default address space for global variables.
485 if (Error Err = getAddrSpace(Tok, DefaultGlobalsAddrSpace))
486 return Err;
487 break;
488 }
489 case 'm':
490 if (!Tok.empty())
491 return reportError("Unexpected trailing characters after mangling "
492 "specifier in datalayout string");
493 if (Rest.empty())
494 return reportError("Expected mangling specifier in datalayout string");
495 if (Rest.size() > 1)
496 return reportError("Unknown mangling specifier in datalayout string");
497 switch(Rest[0]) {
498 default:
499 return reportError("Unknown mangling in datalayout string");
500 case 'e':
501 ManglingMode = MM_ELF;
502 break;
503 case 'o':
504 ManglingMode = MM_MachO;
505 break;
506 case 'm':
507 ManglingMode = MM_Mips;
508 break;
509 case 'w':
510 ManglingMode = MM_WinCOFF;
511 break;
512 case 'x':
513 ManglingMode = MM_WinCOFFX86;
514 break;
515 case 'a':
516 ManglingMode = MM_XCOFF;
517 break;
518 }
519 break;
520 default:
521 return reportError("Unknown specifier in datalayout string");
522 break;
523 }
524 }
525
526 return Error::success();
527 }
528
DataLayout(const Module * M)529 DataLayout::DataLayout(const Module *M) {
530 init(M);
531 }
532
init(const Module * M)533 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
534
operator ==(const DataLayout & Other) const535 bool DataLayout::operator==(const DataLayout &Other) const {
536 bool Ret = BigEndian == Other.BigEndian &&
537 AllocaAddrSpace == Other.AllocaAddrSpace &&
538 StackNaturalAlign == Other.StackNaturalAlign &&
539 ProgramAddrSpace == Other.ProgramAddrSpace &&
540 DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace &&
541 FunctionPtrAlign == Other.FunctionPtrAlign &&
542 TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&
543 ManglingMode == Other.ManglingMode &&
544 LegalIntWidths == Other.LegalIntWidths &&
545 Alignments == Other.Alignments && Pointers == Other.Pointers;
546 // Note: getStringRepresentation() might differs, it is not canonicalized
547 return Ret;
548 }
549
550 DataLayout::AlignmentsTy::iterator
findAlignmentLowerBound(AlignTypeEnum AlignType,uint32_t BitWidth)551 DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType,
552 uint32_t BitWidth) {
553 auto Pair = std::make_pair((unsigned)AlignType, BitWidth);
554 return partition_point(Alignments, [=](const LayoutAlignElem &E) {
555 return std::make_pair(E.AlignType, E.TypeBitWidth) < Pair;
556 });
557 }
558
setAlignment(AlignTypeEnum align_type,Align abi_align,Align pref_align,uint32_t bit_width)559 Error DataLayout::setAlignment(AlignTypeEnum align_type, Align abi_align,
560 Align pref_align, uint32_t bit_width) {
561 // AlignmentsTy::ABIAlign and AlignmentsTy::PrefAlign were once stored as
562 // uint16_t, it is unclear if there are requirements for alignment to be less
563 // than 2^16 other than storage. In the meantime we leave the restriction as
564 // an assert. See D67400 for context.
565 assert(Log2(abi_align) < 16 && Log2(pref_align) < 16 && "Alignment too big");
566 if (!isUInt<24>(bit_width))
567 return reportError("Invalid bit width, must be a 24bit integer");
568 if (pref_align < abi_align)
569 return reportError(
570 "Preferred alignment cannot be less than the ABI alignment");
571
572 AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width);
573 if (I != Alignments.end() &&
574 I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) {
575 // Update the abi, preferred alignments.
576 I->ABIAlign = abi_align;
577 I->PrefAlign = pref_align;
578 } else {
579 // Insert before I to keep the vector sorted.
580 Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
581 pref_align, bit_width));
582 }
583 return Error::success();
584 }
585
586 const PointerAlignElem &
getPointerAlignElem(uint32_t AddressSpace) const587 DataLayout::getPointerAlignElem(uint32_t AddressSpace) const {
588 if (AddressSpace != 0) {
589 auto I = lower_bound(Pointers, AddressSpace,
590 [](const PointerAlignElem &A, uint32_t AddressSpace) {
591 return A.AddressSpace < AddressSpace;
592 });
593 if (I != Pointers.end() && I->AddressSpace == AddressSpace)
594 return *I;
595 }
596
597 assert(Pointers[0].AddressSpace == 0);
598 return Pointers[0];
599 }
600
setPointerAlignment(uint32_t AddrSpace,Align ABIAlign,Align PrefAlign,uint32_t TypeByteWidth,uint32_t IndexWidth)601 Error DataLayout::setPointerAlignment(uint32_t AddrSpace, Align ABIAlign,
602 Align PrefAlign, uint32_t TypeByteWidth,
603 uint32_t IndexWidth) {
604 if (PrefAlign < ABIAlign)
605 return reportError(
606 "Preferred alignment cannot be less than the ABI alignment");
607
608 auto I = lower_bound(Pointers, AddrSpace,
609 [](const PointerAlignElem &A, uint32_t AddressSpace) {
610 return A.AddressSpace < AddressSpace;
611 });
612 if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
613 Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
614 TypeByteWidth, IndexWidth));
615 } else {
616 I->ABIAlign = ABIAlign;
617 I->PrefAlign = PrefAlign;
618 I->TypeByteWidth = TypeByteWidth;
619 I->IndexWidth = IndexWidth;
620 }
621 return Error::success();
622 }
623
getIntegerAlignment(uint32_t BitWidth,bool abi_or_pref) const624 Align DataLayout::getIntegerAlignment(uint32_t BitWidth,
625 bool abi_or_pref) const {
626 auto I = findAlignmentLowerBound(INTEGER_ALIGN, BitWidth);
627 // If we don't have an exact match, use alignment of next larger integer
628 // type. If there is none, use alignment of largest integer type by going
629 // back one element.
630 if (I == Alignments.end() || I->AlignType != INTEGER_ALIGN)
631 --I;
632 assert(I->AlignType == INTEGER_ALIGN && "Must be integer alignment");
633 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
634 }
635
636 namespace {
637
638 class StructLayoutMap {
639 using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
640 LayoutInfoTy LayoutInfo;
641
642 public:
~StructLayoutMap()643 ~StructLayoutMap() {
644 // Remove any layouts.
645 for (const auto &I : LayoutInfo) {
646 StructLayout *Value = I.second;
647 Value->~StructLayout();
648 free(Value);
649 }
650 }
651
operator [](StructType * STy)652 StructLayout *&operator[](StructType *STy) {
653 return LayoutInfo[STy];
654 }
655 };
656
657 } // end anonymous namespace
658
clear()659 void DataLayout::clear() {
660 LegalIntWidths.clear();
661 Alignments.clear();
662 Pointers.clear();
663 delete static_cast<StructLayoutMap *>(LayoutMap);
664 LayoutMap = nullptr;
665 }
666
~DataLayout()667 DataLayout::~DataLayout() {
668 clear();
669 }
670
getStructLayout(StructType * Ty) const671 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
672 if (!LayoutMap)
673 LayoutMap = new StructLayoutMap();
674
675 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
676 StructLayout *&SL = (*STM)[Ty];
677 if (SL) return SL;
678
679 // Otherwise, create the struct layout. Because it is variable length, we
680 // malloc it, then use placement new.
681 StructLayout *L = (StructLayout *)safe_malloc(
682 StructLayout::totalSizeToAlloc<uint64_t>(Ty->getNumElements()));
683
684 // Set SL before calling StructLayout's ctor. The ctor could cause other
685 // entries to be added to TheMap, invalidating our reference.
686 SL = L;
687
688 new (L) StructLayout(Ty, *this);
689
690 return L;
691 }
692
getPointerABIAlignment(unsigned AS) const693 Align DataLayout::getPointerABIAlignment(unsigned AS) const {
694 return getPointerAlignElem(AS).ABIAlign;
695 }
696
getPointerPrefAlignment(unsigned AS) const697 Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
698 return getPointerAlignElem(AS).PrefAlign;
699 }
700
getPointerSize(unsigned AS) const701 unsigned DataLayout::getPointerSize(unsigned AS) const {
702 return getPointerAlignElem(AS).TypeByteWidth;
703 }
704
getMaxPointerSize() const705 unsigned DataLayout::getMaxPointerSize() const {
706 unsigned MaxPointerSize = 0;
707 for (auto &P : Pointers)
708 MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth);
709
710 return MaxPointerSize;
711 }
712
getPointerTypeSizeInBits(Type * Ty) const713 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
714 assert(Ty->isPtrOrPtrVectorTy() &&
715 "This should only be called with a pointer or pointer vector type");
716 Ty = Ty->getScalarType();
717 return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
718 }
719
getIndexSize(unsigned AS) const720 unsigned DataLayout::getIndexSize(unsigned AS) const {
721 return getPointerAlignElem(AS).IndexWidth;
722 }
723
getIndexTypeSizeInBits(Type * Ty) const724 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
725 assert(Ty->isPtrOrPtrVectorTy() &&
726 "This should only be called with a pointer or pointer vector type");
727 Ty = Ty->getScalarType();
728 return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
729 }
730
731 /*!
732 \param abi_or_pref Flag that determines which alignment is returned. true
733 returns the ABI alignment, false returns the preferred alignment.
734 \param Ty The underlying type for which alignment is determined.
735
736 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
737 == false) for the requested type \a Ty.
738 */
getAlignment(Type * Ty,bool abi_or_pref) const739 Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
740 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
741 switch (Ty->getTypeID()) {
742 // Early escape for the non-numeric types.
743 case Type::LabelTyID:
744 return abi_or_pref ? getPointerABIAlignment(0) : getPointerPrefAlignment(0);
745 case Type::PointerTyID: {
746 unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
747 return abi_or_pref ? getPointerABIAlignment(AS)
748 : getPointerPrefAlignment(AS);
749 }
750 case Type::ArrayTyID:
751 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
752
753 case Type::StructTyID: {
754 // Packed structure types always have an ABI alignment of one.
755 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
756 return Align(1);
757
758 // Get the layout annotation... which is lazily created on demand.
759 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
760 const LayoutAlignElem &AggregateAlign = Alignments[0];
761 assert(AggregateAlign.AlignType == AGGREGATE_ALIGN &&
762 "Aggregate alignment must be first alignment entry");
763 const Align Align =
764 abi_or_pref ? AggregateAlign.ABIAlign : AggregateAlign.PrefAlign;
765 return std::max(Align, Layout->getAlignment());
766 }
767 case Type::IntegerTyID:
768 return getIntegerAlignment(Ty->getIntegerBitWidth(), abi_or_pref);
769 case Type::HalfTyID:
770 case Type::BFloatTyID:
771 case Type::FloatTyID:
772 case Type::DoubleTyID:
773 // PPC_FP128TyID and FP128TyID have different data contents, but the
774 // same size and alignment, so they look the same here.
775 case Type::PPC_FP128TyID:
776 case Type::FP128TyID:
777 case Type::X86_FP80TyID: {
778 unsigned BitWidth = getTypeSizeInBits(Ty).getFixedSize();
779 auto I = findAlignmentLowerBound(FLOAT_ALIGN, BitWidth);
780 if (I != Alignments.end() && I->AlignType == FLOAT_ALIGN &&
781 I->TypeBitWidth == BitWidth)
782 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
783
784 // If we still couldn't find a reasonable default alignment, fall back
785 // to a simple heuristic that the alignment is the first power of two
786 // greater-or-equal to the store size of the type. This is a reasonable
787 // approximation of reality, and if the user wanted something less
788 // less conservative, they should have specified it explicitly in the data
789 // layout.
790 return Align(PowerOf2Ceil(BitWidth / 8));
791 }
792 case Type::X86_MMXTyID:
793 case Type::FixedVectorTyID:
794 case Type::ScalableVectorTyID: {
795 unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinSize();
796 auto I = findAlignmentLowerBound(VECTOR_ALIGN, BitWidth);
797 if (I != Alignments.end() && I->AlignType == VECTOR_ALIGN &&
798 I->TypeBitWidth == BitWidth)
799 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
800
801 // By default, use natural alignment for vector types. This is consistent
802 // with what clang and llvm-gcc do.
803 // TODO: This should probably not be using the alloc size.
804 unsigned Alignment =
805 getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
806 // We're only calculating a natural alignment, so it doesn't have to be
807 // based on the full size for scalable vectors. Using the minimum element
808 // count should be enough here.
809 Alignment *= cast<VectorType>(Ty)->getElementCount().getKnownMinValue();
810 Alignment = PowerOf2Ceil(Alignment);
811 return Align(Alignment);
812 }
813 case Type::X86_AMXTyID:
814 return Align(64);
815 default:
816 llvm_unreachable("Bad type for getAlignment!!!");
817 }
818 }
819
820 /// TODO: Remove this function once the transition to Align is over.
getABITypeAlignment(Type * Ty) const821 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
822 return getABITypeAlign(Ty).value();
823 }
824
getABITypeAlign(Type * Ty) const825 Align DataLayout::getABITypeAlign(Type *Ty) const {
826 return getAlignment(Ty, true);
827 }
828
829 /// TODO: Remove this function once the transition to Align is over.
getPrefTypeAlignment(Type * Ty) const830 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
831 return getPrefTypeAlign(Ty).value();
832 }
833
getPrefTypeAlign(Type * Ty) const834 Align DataLayout::getPrefTypeAlign(Type *Ty) const {
835 return getAlignment(Ty, false);
836 }
837
getIntPtrType(LLVMContext & C,unsigned AddressSpace) const838 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
839 unsigned AddressSpace) const {
840 return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
841 }
842
getIntPtrType(Type * Ty) const843 Type *DataLayout::getIntPtrType(Type *Ty) const {
844 assert(Ty->isPtrOrPtrVectorTy() &&
845 "Expected a pointer or pointer vector type.");
846 unsigned NumBits = getPointerTypeSizeInBits(Ty);
847 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
848 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
849 return VectorType::get(IntTy, VecTy);
850 return IntTy;
851 }
852
getSmallestLegalIntType(LLVMContext & C,unsigned Width) const853 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
854 for (unsigned LegalIntWidth : LegalIntWidths)
855 if (Width <= LegalIntWidth)
856 return Type::getIntNTy(C, LegalIntWidth);
857 return nullptr;
858 }
859
getLargestLegalIntTypeSizeInBits() const860 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
861 auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
862 return Max != LegalIntWidths.end() ? *Max : 0;
863 }
864
getIndexType(Type * Ty) const865 Type *DataLayout::getIndexType(Type *Ty) const {
866 assert(Ty->isPtrOrPtrVectorTy() &&
867 "Expected a pointer or pointer vector type.");
868 unsigned NumBits = getIndexTypeSizeInBits(Ty);
869 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
870 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
871 return VectorType::get(IntTy, VecTy);
872 return IntTy;
873 }
874
getIndexedOffsetInType(Type * ElemTy,ArrayRef<Value * > Indices) const875 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
876 ArrayRef<Value *> Indices) const {
877 int64_t Result = 0;
878
879 generic_gep_type_iterator<Value* const*>
880 GTI = gep_type_begin(ElemTy, Indices),
881 GTE = gep_type_end(ElemTy, Indices);
882 for (; GTI != GTE; ++GTI) {
883 Value *Idx = GTI.getOperand();
884 if (StructType *STy = GTI.getStructTypeOrNull()) {
885 assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
886 unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
887
888 // Get structure layout information...
889 const StructLayout *Layout = getStructLayout(STy);
890
891 // Add in the offset, as calculated by the structure layout info...
892 Result += Layout->getElementOffset(FieldNo);
893 } else {
894 // Get the array index and the size of each array element.
895 if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
896 Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
897 }
898 }
899
900 return Result;
901 }
902
903 /// getPreferredAlign - Return the preferred alignment of the specified global.
904 /// This includes an explicitly requested alignment (if the global has one).
getPreferredAlign(const GlobalVariable * GV) const905 Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {
906 MaybeAlign GVAlignment = GV->getAlign();
907 // If a section is specified, always precisely honor explicit alignment,
908 // so we don't insert padding into a section we don't control.
909 if (GVAlignment && GV->hasSection())
910 return *GVAlignment;
911
912 // If no explicit alignment is specified, compute the alignment based on
913 // the IR type. If an alignment is specified, increase it to match the ABI
914 // alignment of the IR type.
915 //
916 // FIXME: Not sure it makes sense to use the alignment of the type if
917 // there's already an explicit alignment specification.
918 Type *ElemType = GV->getValueType();
919 Align Alignment = getPrefTypeAlign(ElemType);
920 if (GVAlignment) {
921 if (*GVAlignment >= Alignment)
922 Alignment = *GVAlignment;
923 else
924 Alignment = std::max(*GVAlignment, getABITypeAlign(ElemType));
925 }
926
927 // If no explicit alignment is specified, and the global is large, increase
928 // the alignment to 16.
929 // FIXME: Why 16, specifically?
930 if (GV->hasInitializer() && !GVAlignment) {
931 if (Alignment < Align(16)) {
932 // If the global is not external, see if it is large. If so, give it a
933 // larger alignment.
934 if (getTypeSizeInBits(ElemType) > 128)
935 Alignment = Align(16); // 16-byte alignment.
936 }
937 }
938 return Alignment;
939 }
940