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 MemberOffsets[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 const uint64_t *SI =
84 std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
85 assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
86 --SI;
87 assert(*SI <= Offset && "upper_bound didn't work");
88 assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
89 (SI+1 == &MemberOffsets[NumElements] || *(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[0];
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 int NumElts = Ty->getNumElements();
682 StructLayout *L = (StructLayout *)
683 safe_malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
684
685 // Set SL before calling StructLayout's ctor. The ctor could cause other
686 // entries to be added to TheMap, invalidating our reference.
687 SL = L;
688
689 new (L) StructLayout(Ty, *this);
690
691 return L;
692 }
693
getPointerABIAlignment(unsigned AS) const694 Align DataLayout::getPointerABIAlignment(unsigned AS) const {
695 return getPointerAlignElem(AS).ABIAlign;
696 }
697
getPointerPrefAlignment(unsigned AS) const698 Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
699 return getPointerAlignElem(AS).PrefAlign;
700 }
701
getPointerSize(unsigned AS) const702 unsigned DataLayout::getPointerSize(unsigned AS) const {
703 return getPointerAlignElem(AS).TypeByteWidth;
704 }
705
getMaxPointerSize() const706 unsigned DataLayout::getMaxPointerSize() const {
707 unsigned MaxPointerSize = 0;
708 for (auto &P : Pointers)
709 MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth);
710
711 return MaxPointerSize;
712 }
713
getPointerTypeSizeInBits(Type * Ty) const714 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
715 assert(Ty->isPtrOrPtrVectorTy() &&
716 "This should only be called with a pointer or pointer vector type");
717 Ty = Ty->getScalarType();
718 return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
719 }
720
getIndexSize(unsigned AS) const721 unsigned DataLayout::getIndexSize(unsigned AS) const {
722 return getPointerAlignElem(AS).IndexWidth;
723 }
724
getIndexTypeSizeInBits(Type * Ty) const725 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
726 assert(Ty->isPtrOrPtrVectorTy() &&
727 "This should only be called with a pointer or pointer vector type");
728 Ty = Ty->getScalarType();
729 return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
730 }
731
732 /*!
733 \param abi_or_pref Flag that determines which alignment is returned. true
734 returns the ABI alignment, false returns the preferred alignment.
735 \param Ty The underlying type for which alignment is determined.
736
737 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
738 == false) for the requested type \a Ty.
739 */
getAlignment(Type * Ty,bool abi_or_pref) const740 Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
741 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
742 switch (Ty->getTypeID()) {
743 // Early escape for the non-numeric types.
744 case Type::LabelTyID:
745 return abi_or_pref ? getPointerABIAlignment(0) : getPointerPrefAlignment(0);
746 case Type::PointerTyID: {
747 unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
748 return abi_or_pref ? getPointerABIAlignment(AS)
749 : getPointerPrefAlignment(AS);
750 }
751 case Type::ArrayTyID:
752 return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
753
754 case Type::StructTyID: {
755 // Packed structure types always have an ABI alignment of one.
756 if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
757 return Align(1);
758
759 // Get the layout annotation... which is lazily created on demand.
760 const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
761 const LayoutAlignElem &AggregateAlign = Alignments[0];
762 assert(AggregateAlign.AlignType == AGGREGATE_ALIGN &&
763 "Aggregate alignment must be first alignment entry");
764 const Align Align =
765 abi_or_pref ? AggregateAlign.ABIAlign : AggregateAlign.PrefAlign;
766 return std::max(Align, Layout->getAlignment());
767 }
768 case Type::IntegerTyID:
769 return getIntegerAlignment(Ty->getIntegerBitWidth(), abi_or_pref);
770 case Type::HalfTyID:
771 case Type::BFloatTyID:
772 case Type::FloatTyID:
773 case Type::DoubleTyID:
774 // PPC_FP128TyID and FP128TyID have different data contents, but the
775 // same size and alignment, so they look the same here.
776 case Type::PPC_FP128TyID:
777 case Type::FP128TyID:
778 case Type::X86_FP80TyID: {
779 unsigned BitWidth = getTypeSizeInBits(Ty).getFixedSize();
780 auto I = findAlignmentLowerBound(FLOAT_ALIGN, BitWidth);
781 if (I != Alignments.end() && I->AlignType == FLOAT_ALIGN &&
782 I->TypeBitWidth == BitWidth)
783 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
784
785 // If we still couldn't find a reasonable default alignment, fall back
786 // to a simple heuristic that the alignment is the first power of two
787 // greater-or-equal to the store size of the type. This is a reasonable
788 // approximation of reality, and if the user wanted something less
789 // less conservative, they should have specified it explicitly in the data
790 // layout.
791 return Align(PowerOf2Ceil(BitWidth / 8));
792 }
793 case Type::X86_MMXTyID:
794 case Type::FixedVectorTyID:
795 case Type::ScalableVectorTyID: {
796 unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinSize();
797 auto I = findAlignmentLowerBound(VECTOR_ALIGN, BitWidth);
798 if (I != Alignments.end() && I->AlignType == VECTOR_ALIGN &&
799 I->TypeBitWidth == BitWidth)
800 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
801
802 // By default, use natural alignment for vector types. This is consistent
803 // with what clang and llvm-gcc do.
804 // TODO: This should probably not be using the alloc size.
805 unsigned Alignment =
806 getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
807 // We're only calculating a natural alignment, so it doesn't have to be
808 // based on the full size for scalable vectors. Using the minimum element
809 // count should be enough here.
810 Alignment *= cast<VectorType>(Ty)->getElementCount().getKnownMinValue();
811 Alignment = PowerOf2Ceil(Alignment);
812 return Align(Alignment);
813 }
814 case Type::X86_AMXTyID:
815 return Align(64);
816 default:
817 llvm_unreachable("Bad type for getAlignment!!!");
818 }
819 }
820
821 /// TODO: Remove this function once the transition to Align is over.
getABITypeAlignment(Type * Ty) const822 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
823 return getABITypeAlign(Ty).value();
824 }
825
getABITypeAlign(Type * Ty) const826 Align DataLayout::getABITypeAlign(Type *Ty) const {
827 return getAlignment(Ty, true);
828 }
829
830 /// TODO: Remove this function once the transition to Align is over.
getPrefTypeAlignment(Type * Ty) const831 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
832 return getPrefTypeAlign(Ty).value();
833 }
834
getPrefTypeAlign(Type * Ty) const835 Align DataLayout::getPrefTypeAlign(Type *Ty) const {
836 return getAlignment(Ty, false);
837 }
838
getIntPtrType(LLVMContext & C,unsigned AddressSpace) const839 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
840 unsigned AddressSpace) const {
841 return IntegerType::get(C, getPointerSizeInBits(AddressSpace));
842 }
843
getIntPtrType(Type * Ty) const844 Type *DataLayout::getIntPtrType(Type *Ty) const {
845 assert(Ty->isPtrOrPtrVectorTy() &&
846 "Expected a pointer or pointer vector type.");
847 unsigned NumBits = getPointerTypeSizeInBits(Ty);
848 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
849 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
850 return VectorType::get(IntTy, VecTy);
851 return IntTy;
852 }
853
getSmallestLegalIntType(LLVMContext & C,unsigned Width) const854 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
855 for (unsigned LegalIntWidth : LegalIntWidths)
856 if (Width <= LegalIntWidth)
857 return Type::getIntNTy(C, LegalIntWidth);
858 return nullptr;
859 }
860
getLargestLegalIntTypeSizeInBits() const861 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
862 auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
863 return Max != LegalIntWidths.end() ? *Max : 0;
864 }
865
getIndexType(Type * Ty) const866 Type *DataLayout::getIndexType(Type *Ty) const {
867 assert(Ty->isPtrOrPtrVectorTy() &&
868 "Expected a pointer or pointer vector type.");
869 unsigned NumBits = getIndexTypeSizeInBits(Ty);
870 IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
871 if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
872 return VectorType::get(IntTy, VecTy);
873 return IntTy;
874 }
875
getIndexedOffsetInType(Type * ElemTy,ArrayRef<Value * > Indices) const876 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
877 ArrayRef<Value *> Indices) const {
878 int64_t Result = 0;
879
880 generic_gep_type_iterator<Value* const*>
881 GTI = gep_type_begin(ElemTy, Indices),
882 GTE = gep_type_end(ElemTy, Indices);
883 for (; GTI != GTE; ++GTI) {
884 Value *Idx = GTI.getOperand();
885 if (StructType *STy = GTI.getStructTypeOrNull()) {
886 assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
887 unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
888
889 // Get structure layout information...
890 const StructLayout *Layout = getStructLayout(STy);
891
892 // Add in the offset, as calculated by the structure layout info...
893 Result += Layout->getElementOffset(FieldNo);
894 } else {
895 // Get the array index and the size of each array element.
896 if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
897 Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
898 }
899 }
900
901 return Result;
902 }
903
904 /// getPreferredAlign - Return the preferred alignment of the specified global.
905 /// This includes an explicitly requested alignment (if the global has one).
getPreferredAlign(const GlobalVariable * GV) const906 Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {
907 MaybeAlign GVAlignment = GV->getAlign();
908 // If a section is specified, always precisely honor explicit alignment,
909 // so we don't insert padding into a section we don't control.
910 if (GVAlignment && GV->hasSection())
911 return *GVAlignment;
912
913 // If no explicit alignment is specified, compute the alignment based on
914 // the IR type. If an alignment is specified, increase it to match the ABI
915 // alignment of the IR type.
916 //
917 // FIXME: Not sure it makes sense to use the alignment of the type if
918 // there's already an explicit alignment specification.
919 Type *ElemType = GV->getValueType();
920 Align Alignment = getPrefTypeAlign(ElemType);
921 if (GVAlignment) {
922 if (*GVAlignment >= Alignment)
923 Alignment = *GVAlignment;
924 else
925 Alignment = std::max(*GVAlignment, getABITypeAlign(ElemType));
926 }
927
928 // If no explicit alignment is specified, and the global is large, increase
929 // the alignment to 16.
930 // FIXME: Why 16, specifically?
931 if (GV->hasInitializer() && !GVAlignment) {
932 if (Alignment < Align(16)) {
933 // If the global is not external, see if it is large. If so, give it a
934 // larger alignment.
935 if (getTypeSizeInBits(ElemType) > 128)
936 Alignment = Align(16); // 16-byte alignment.
937 }
938 }
939 return Alignment;
940 }
941