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