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/StringExtras.h"
21#include "llvm/ADT/StringRef.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/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 = llvm::upper_bound(Range&: MemberOffsets, Value&: Offset,
100 C: [](TypeSize LHS, TypeSize RHS) -> bool {
101 return TypeSize::isKnownLT(LHS, RHS);
102 });
103 assert(SI != MemberOffsets.begin() && "Offset not in structure type!");
104 --SI;
105 assert(TypeSize::isKnownLE(*SI, Offset) && "upper_bound didn't work");
106 assert(
107 (SI == MemberOffsets.begin() || TypeSize::isKnownLE(*(SI - 1), Offset)) &&
108 (SI + 1 == MemberOffsets.end() ||
109 TypeSize::isKnownGT(*(SI + 1), Offset)) &&
110 "Upper bound didn't work!");
111
112 // Multiple fields can have the same offset if any of them are zero sized.
113 // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
114 // at the i32 element, because it is the last element at that offset. This is
115 // the right one to return, because anything after it will have a higher
116 // offset, implying that this element is non-empty.
117 return SI - MemberOffsets.begin();
118}
119
120namespace {
121
122class StructLayoutMap {
123 using LayoutInfoTy = DenseMap<StructType *, StructLayout *>;
124 LayoutInfoTy LayoutInfo;
125
126public:
127 ~StructLayoutMap() {
128 // Remove any layouts.
129 for (const auto &I : LayoutInfo) {
130 StructLayout *Value = I.second;
131 Value->~StructLayout();
132 free(ptr: Value);
133 }
134 }
135
136 StructLayout *&operator[](StructType *STy) { return LayoutInfo[STy]; }
137};
138
139} // end anonymous namespace
140
141//===----------------------------------------------------------------------===//
142// DataLayout Class Implementation
143//===----------------------------------------------------------------------===//
144
145bool DataLayout::PrimitiveSpec::operator==(const PrimitiveSpec &Other) const {
146 return BitWidth == Other.BitWidth && ABIAlign == Other.ABIAlign &&
147 PrefAlign == Other.PrefAlign;
148}
149
150bool DataLayout::PointerSpec::operator==(const PointerSpec &Other) const {
151 return AddrSpace == Other.AddrSpace && BitWidth == Other.BitWidth &&
152 ABIAlign == Other.ABIAlign && PrefAlign == Other.PrefAlign &&
153 IndexBitWidth == Other.IndexBitWidth &&
154 IsNonIntegral == Other.IsNonIntegral;
155}
156
157namespace {
158/// Predicate to sort primitive specs by bit width.
159struct LessPrimitiveBitWidth {
160 bool operator()(const DataLayout::PrimitiveSpec &LHS,
161 unsigned RHSBitWidth) const {
162 return LHS.BitWidth < RHSBitWidth;
163 }
164};
165
166/// Predicate to sort pointer specs by address space number.
167struct LessPointerAddrSpace {
168 bool operator()(const DataLayout::PointerSpec &LHS,
169 unsigned RHSAddrSpace) const {
170 return LHS.AddrSpace < RHSAddrSpace;
171 }
172};
173} // namespace
174
175const char *DataLayout::getManglingComponent(const Triple &T) {
176 if (T.isOSBinFormatGOFF())
177 return "-m:l";
178 if (T.isOSBinFormatMachO())
179 return "-m:o";
180 if ((T.isOSWindows() || T.isUEFI()) && T.isOSBinFormatCOFF())
181 return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
182 if (T.isOSBinFormatXCOFF())
183 return "-m:a";
184 return "-m:e";
185}
186
187// Default primitive type specifications.
188// NOTE: These arrays must be sorted by type bit width.
189constexpr DataLayout::PrimitiveSpec DefaultIntSpecs[] = {
190 {.BitWidth: 1, .ABIAlign: Align::Constant<1>(), .PrefAlign: Align::Constant<1>()}, // i1:8:8
191 {.BitWidth: 8, .ABIAlign: Align::Constant<1>(), .PrefAlign: Align::Constant<1>()}, // i8:8:8
192 {.BitWidth: 16, .ABIAlign: Align::Constant<2>(), .PrefAlign: Align::Constant<2>()}, // i16:16:16
193 {.BitWidth: 32, .ABIAlign: Align::Constant<4>(), .PrefAlign: Align::Constant<4>()}, // i32:32:32
194 {.BitWidth: 64, .ABIAlign: Align::Constant<4>(), .PrefAlign: Align::Constant<8>()}, // i64:32:64
195};
196constexpr DataLayout::PrimitiveSpec DefaultFloatSpecs[] = {
197 {.BitWidth: 16, .ABIAlign: Align::Constant<2>(), .PrefAlign: Align::Constant<2>()}, // f16:16:16
198 {.BitWidth: 32, .ABIAlign: Align::Constant<4>(), .PrefAlign: Align::Constant<4>()}, // f32:32:32
199 {.BitWidth: 64, .ABIAlign: Align::Constant<8>(), .PrefAlign: Align::Constant<8>()}, // f64:64:64
200 {.BitWidth: 128, .ABIAlign: Align::Constant<16>(), .PrefAlign: Align::Constant<16>()}, // f128:128:128
201};
202constexpr DataLayout::PrimitiveSpec DefaultVectorSpecs[] = {
203 {.BitWidth: 64, .ABIAlign: Align::Constant<8>(), .PrefAlign: Align::Constant<8>()}, // v64:64:64
204 {.BitWidth: 128, .ABIAlign: Align::Constant<16>(), .PrefAlign: Align::Constant<16>()}, // v128:128:128
205};
206
207// Default pointer type specifications.
208constexpr DataLayout::PointerSpec DefaultPointerSpecs[] = {
209 // p0:64:64:64:64
210 {.AddrSpace: 0, .BitWidth: 64, .ABIAlign: Align::Constant<8>(), .PrefAlign: Align::Constant<8>(), .IndexBitWidth: 64, .IsNonIntegral: false},
211};
212
213DataLayout::DataLayout()
214 : IntSpecs(ArrayRef(DefaultIntSpecs)),
215 FloatSpecs(ArrayRef(DefaultFloatSpecs)),
216 VectorSpecs(ArrayRef(DefaultVectorSpecs)),
217 PointerSpecs(ArrayRef(DefaultPointerSpecs)) {}
218
219DataLayout::DataLayout(StringRef LayoutString) : DataLayout() {
220 if (Error Err = parseLayoutString(LayoutString))
221 report_fatal_error(Err: std::move(Err));
222}
223
224DataLayout &DataLayout::operator=(const DataLayout &Other) {
225 delete static_cast<StructLayoutMap *>(LayoutMap);
226 LayoutMap = nullptr;
227 StringRepresentation = Other.StringRepresentation;
228 BigEndian = Other.BigEndian;
229 AllocaAddrSpace = Other.AllocaAddrSpace;
230 ProgramAddrSpace = Other.ProgramAddrSpace;
231 DefaultGlobalsAddrSpace = Other.DefaultGlobalsAddrSpace;
232 StackNaturalAlign = Other.StackNaturalAlign;
233 FunctionPtrAlign = Other.FunctionPtrAlign;
234 TheFunctionPtrAlignType = Other.TheFunctionPtrAlignType;
235 ManglingMode = Other.ManglingMode;
236 LegalIntWidths = Other.LegalIntWidths;
237 IntSpecs = Other.IntSpecs;
238 FloatSpecs = Other.FloatSpecs;
239 VectorSpecs = Other.VectorSpecs;
240 PointerSpecs = Other.PointerSpecs;
241 StructABIAlignment = Other.StructABIAlignment;
242 StructPrefAlignment = Other.StructPrefAlignment;
243 return *this;
244}
245
246bool DataLayout::operator==(const DataLayout &Other) const {
247 // NOTE: StringRepresentation might differ, it is not canonicalized.
248 return BigEndian == Other.BigEndian &&
249 AllocaAddrSpace == Other.AllocaAddrSpace &&
250 ProgramAddrSpace == Other.ProgramAddrSpace &&
251 DefaultGlobalsAddrSpace == Other.DefaultGlobalsAddrSpace &&
252 StackNaturalAlign == Other.StackNaturalAlign &&
253 FunctionPtrAlign == Other.FunctionPtrAlign &&
254 TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&
255 ManglingMode == Other.ManglingMode &&
256 LegalIntWidths == Other.LegalIntWidths && IntSpecs == Other.IntSpecs &&
257 FloatSpecs == Other.FloatSpecs && VectorSpecs == Other.VectorSpecs &&
258 PointerSpecs == Other.PointerSpecs &&
259 StructABIAlignment == Other.StructABIAlignment &&
260 StructPrefAlignment == Other.StructPrefAlignment;
261}
262
263Expected<DataLayout> DataLayout::parse(StringRef LayoutString) {
264 DataLayout Layout;
265 if (Error Err = Layout.parseLayoutString(LayoutString))
266 return std::move(Err);
267 return Layout;
268}
269
270static Error createSpecFormatError(Twine Format) {
271 return createStringError(S: "malformed specification, must be of the form \"" +
272 Format + "\"");
273}
274
275/// Attempts to parse an address space component of a specification.
276static Error parseAddrSpace(StringRef Str, unsigned &AddrSpace) {
277 if (Str.empty())
278 return createStringError(Fmt: "address space component cannot be empty");
279
280 if (!to_integer(S: Str, Num&: AddrSpace, Base: 10) || !isUInt<24>(x: AddrSpace))
281 return createStringError(Fmt: "address space must be a 24-bit integer");
282
283 return Error::success();
284}
285
286/// Attempts to parse a size component of a specification.
287static Error parseSize(StringRef Str, unsigned &BitWidth,
288 StringRef Name = "size") {
289 if (Str.empty())
290 return createStringError(S: Name + " component cannot be empty");
291
292 if (!to_integer(S: Str, Num&: BitWidth, Base: 10) || BitWidth == 0 || !isUInt<24>(x: BitWidth))
293 return createStringError(S: Name + " must be a non-zero 24-bit integer");
294
295 return Error::success();
296}
297
298/// Attempts to parse an alignment component of a specification.
299///
300/// On success, returns the value converted to byte amount in \p Alignment.
301/// If the value is zero and \p AllowZero is true, \p Alignment is set to one.
302///
303/// Return an error in a number of cases:
304/// - \p Str is empty or contains characters other than decimal digits;
305/// - the value is zero and \p AllowZero is false;
306/// - the value is too large;
307/// - the value is not a multiple of the byte width;
308/// - the value converted to byte amount is not not a power of two.
309static Error parseAlignment(StringRef Str, Align &Alignment, StringRef Name,
310 bool AllowZero = false) {
311 if (Str.empty())
312 return createStringError(S: Name + " alignment component cannot be empty");
313
314 unsigned Value;
315 if (!to_integer(S: Str, Num&: Value, Base: 10) || !isUInt<16>(x: Value))
316 return createStringError(S: Name + " alignment must be a 16-bit integer");
317
318 if (Value == 0) {
319 if (!AllowZero)
320 return createStringError(S: Name + " alignment must be non-zero");
321 Alignment = Align(1);
322 return Error::success();
323 }
324
325 constexpr unsigned ByteWidth = 8;
326 if (Value % ByteWidth || !isPowerOf2_32(Value: Value / ByteWidth))
327 return createStringError(
328 S: Name + " alignment must be a power of two times the byte width");
329
330 Alignment = Align(Value / ByteWidth);
331 return Error::success();
332}
333
334Error DataLayout::parsePrimitiveSpec(StringRef Spec) {
335 // [ifv]<size>:<abi>[:<pref>]
336 SmallVector<StringRef, 3> Components;
337 char Specifier = Spec.front();
338 assert(Specifier == 'i' || Specifier == 'f' || Specifier == 'v');
339 Spec.drop_front().split(A&: Components, Separator: ':');
340
341 if (Components.size() < 2 || Components.size() > 3)
342 return createSpecFormatError(Format: Twine(Specifier) + "<size>:<abi>[:<pref>]");
343
344 // Size. Required, cannot be zero.
345 unsigned BitWidth;
346 if (Error Err = parseSize(Str: Components[0], BitWidth))
347 return Err;
348
349 // ABI alignment.
350 Align ABIAlign;
351 if (Error Err = parseAlignment(Str: Components[1], Alignment&: ABIAlign, Name: "ABI"))
352 return Err;
353
354 if (Specifier == 'i' && BitWidth == 8 && ABIAlign != 1)
355 return createStringError(Fmt: "i8 must be 8-bit aligned");
356
357 // Preferred alignment. Optional, defaults to the ABI alignment.
358 Align PrefAlign = ABIAlign;
359 if (Components.size() > 2)
360 if (Error Err = parseAlignment(Str: Components[2], Alignment&: PrefAlign, Name: "preferred"))
361 return Err;
362
363 if (PrefAlign < ABIAlign)
364 return createStringError(
365 Fmt: "preferred alignment cannot be less than the ABI alignment");
366
367 setPrimitiveSpec(Specifier, BitWidth, ABIAlign, PrefAlign);
368 return Error::success();
369}
370
371Error DataLayout::parseAggregateSpec(StringRef Spec) {
372 // a<size>:<abi>[:<pref>]
373 SmallVector<StringRef, 3> Components;
374 assert(Spec.front() == 'a');
375 Spec.drop_front().split(A&: Components, Separator: ':');
376
377 if (Components.size() < 2 || Components.size() > 3)
378 return createSpecFormatError(Format: "a:<abi>[:<pref>]");
379
380 // According to LangRef, <size> component must be absent altogether.
381 // For backward compatibility, allow it to be specified, but require
382 // it to be zero.
383 if (!Components[0].empty()) {
384 unsigned BitWidth;
385 if (!to_integer(S: Components[0], Num&: BitWidth, Base: 10) || BitWidth != 0)
386 return createStringError(Fmt: "size must be zero");
387 }
388
389 // ABI alignment. Required. Can be zero, meaning use one byte alignment.
390 Align ABIAlign;
391 if (Error Err =
392 parseAlignment(Str: Components[1], Alignment&: ABIAlign, Name: "ABI", /*AllowZero=*/true))
393 return Err;
394
395 // Preferred alignment. Optional, defaults to the ABI alignment.
396 Align PrefAlign = ABIAlign;
397 if (Components.size() > 2)
398 if (Error Err = parseAlignment(Str: Components[2], Alignment&: PrefAlign, Name: "preferred"))
399 return Err;
400
401 if (PrefAlign < ABIAlign)
402 return createStringError(
403 Fmt: "preferred alignment cannot be less than the ABI alignment");
404
405 StructABIAlignment = ABIAlign;
406 StructPrefAlignment = PrefAlign;
407 return Error::success();
408}
409
410Error DataLayout::parsePointerSpec(StringRef Spec) {
411 // p[<n>]:<size>:<abi>[:<pref>[:<idx>]]
412 SmallVector<StringRef, 5> Components;
413 assert(Spec.front() == 'p');
414 Spec.drop_front().split(A&: Components, Separator: ':');
415
416 if (Components.size() < 3 || Components.size() > 5)
417 return createSpecFormatError(Format: "p[<n>]:<size>:<abi>[:<pref>[:<idx>]]");
418
419 // Address space. Optional, defaults to 0.
420 unsigned AddrSpace = 0;
421 if (!Components[0].empty())
422 if (Error Err = parseAddrSpace(Str: Components[0], AddrSpace))
423 return Err;
424
425 // Size. Required, cannot be zero.
426 unsigned BitWidth;
427 if (Error Err = parseSize(Str: Components[1], BitWidth, Name: "pointer size"))
428 return Err;
429
430 // ABI alignment. Required, cannot be zero.
431 Align ABIAlign;
432 if (Error Err = parseAlignment(Str: Components[2], Alignment&: ABIAlign, Name: "ABI"))
433 return Err;
434
435 // Preferred alignment. Optional, defaults to the ABI alignment.
436 // Cannot be zero.
437 Align PrefAlign = ABIAlign;
438 if (Components.size() > 3)
439 if (Error Err = parseAlignment(Str: Components[3], Alignment&: PrefAlign, Name: "preferred"))
440 return Err;
441
442 if (PrefAlign < ABIAlign)
443 return createStringError(
444 Fmt: "preferred alignment cannot be less than the ABI alignment");
445
446 // Index size. Optional, defaults to pointer size. Cannot be zero.
447 unsigned IndexBitWidth = BitWidth;
448 if (Components.size() > 4)
449 if (Error Err = parseSize(Str: Components[4], BitWidth&: IndexBitWidth, Name: "index size"))
450 return Err;
451
452 if (IndexBitWidth > BitWidth)
453 return createStringError(
454 Fmt: "index size cannot be larger than the pointer size");
455
456 setPointerSpec(AddrSpace, BitWidth, ABIAlign, PrefAlign, IndexBitWidth,
457 IsNonIntegral: false);
458 return Error::success();
459}
460
461Error DataLayout::parseSpecification(
462 StringRef Spec, SmallVectorImpl<unsigned> &NonIntegralAddressSpaces) {
463 // The "ni" specifier is the only two-character specifier. Handle it first.
464 if (Spec.starts_with(Prefix: "ni")) {
465 // ni:<address space>[:<address space>]...
466 StringRef Rest = Spec.drop_front(N: 2);
467
468 // Drop the first ':', then split the rest of the string the usual way.
469 if (!Rest.consume_front(Prefix: ":"))
470 return createSpecFormatError(Format: "ni:<address space>[:<address space>]...");
471
472 for (StringRef Str : split(Str: Rest, Separator: ':')) {
473 unsigned AddrSpace;
474 if (Error Err = parseAddrSpace(Str, AddrSpace))
475 return Err;
476 if (AddrSpace == 0)
477 return createStringError(Fmt: "address space 0 cannot be non-integral");
478 NonIntegralAddressSpaces.push_back(Elt: AddrSpace);
479 }
480 return Error::success();
481 }
482
483 // The rest of the specifiers are single-character.
484 assert(!Spec.empty() && "Empty specification is handled by the caller");
485 char Specifier = Spec.front();
486
487 if (Specifier == 'i' || Specifier == 'f' || Specifier == 'v')
488 return parsePrimitiveSpec(Spec);
489
490 if (Specifier == 'a')
491 return parseAggregateSpec(Spec);
492
493 if (Specifier == 'p')
494 return parsePointerSpec(Spec);
495
496 StringRef Rest = Spec.drop_front();
497 switch (Specifier) {
498 case 's':
499 // Deprecated, but ignoring here to preserve loading older textual llvm
500 // ASM file
501 break;
502 case 'e':
503 case 'E':
504 if (!Rest.empty())
505 return createStringError(
506 Fmt: "malformed specification, must be just 'e' or 'E'");
507 BigEndian = Specifier == 'E';
508 break;
509 case 'n': // Native integer types.
510 // n<size>[:<size>]...
511 for (StringRef Str : split(Str: Rest, Separator: ':')) {
512 unsigned BitWidth;
513 if (Error Err = parseSize(Str, BitWidth))
514 return Err;
515 LegalIntWidths.push_back(Elt: BitWidth);
516 }
517 break;
518 case 'S': { // Stack natural alignment.
519 // S<size>
520 if (Rest.empty())
521 return createSpecFormatError(Format: "S<size>");
522 Align Alignment;
523 if (Error Err = parseAlignment(Str: Rest, Alignment, Name: "stack natural"))
524 return Err;
525 StackNaturalAlign = Alignment;
526 break;
527 }
528 case 'F': {
529 // F<type><abi>
530 if (Rest.empty())
531 return createSpecFormatError(Format: "F<type><abi>");
532 char Type = Rest.front();
533 Rest = Rest.drop_front();
534 switch (Type) {
535 case 'i':
536 TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
537 break;
538 case 'n':
539 TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;
540 break;
541 default:
542 return createStringError(S: "unknown function pointer alignment type '" +
543 Twine(Type) + "'");
544 }
545 Align Alignment;
546 if (Error Err = parseAlignment(Str: Rest, Alignment, Name: "ABI"))
547 return Err;
548 FunctionPtrAlign = Alignment;
549 break;
550 }
551 case 'P': { // Function address space.
552 if (Rest.empty())
553 return createSpecFormatError(Format: "P<address space>");
554 if (Error Err = parseAddrSpace(Str: Rest, AddrSpace&: ProgramAddrSpace))
555 return Err;
556 break;
557 }
558 case 'A': { // Default stack/alloca address space.
559 if (Rest.empty())
560 return createSpecFormatError(Format: "A<address space>");
561 if (Error Err = parseAddrSpace(Str: Rest, AddrSpace&: AllocaAddrSpace))
562 return Err;
563 break;
564 }
565 case 'G': { // Default address space for global variables.
566 if (Rest.empty())
567 return createSpecFormatError(Format: "G<address space>");
568 if (Error Err = parseAddrSpace(Str: Rest, AddrSpace&: DefaultGlobalsAddrSpace))
569 return Err;
570 break;
571 }
572 case 'm':
573 if (!Rest.consume_front(Prefix: ":") || Rest.empty())
574 return createSpecFormatError(Format: "m:<mangling>");
575 if (Rest.size() > 1)
576 return createStringError(Fmt: "unknown mangling mode");
577 switch (Rest[0]) {
578 default:
579 return createStringError(Fmt: "unknown mangling mode");
580 case 'e':
581 ManglingMode = MM_ELF;
582 break;
583 case 'l':
584 ManglingMode = MM_GOFF;
585 break;
586 case 'o':
587 ManglingMode = MM_MachO;
588 break;
589 case 'm':
590 ManglingMode = MM_Mips;
591 break;
592 case 'w':
593 ManglingMode = MM_WinCOFF;
594 break;
595 case 'x':
596 ManglingMode = MM_WinCOFFX86;
597 break;
598 case 'a':
599 ManglingMode = MM_XCOFF;
600 break;
601 }
602 break;
603 default:
604 return createStringError(S: "unknown specifier '" + Twine(Specifier) + "'");
605 }
606
607 return Error::success();
608}
609
610Error DataLayout::parseLayoutString(StringRef LayoutString) {
611 StringRepresentation = std::string(LayoutString);
612
613 if (LayoutString.empty())
614 return Error::success();
615
616 // Split the data layout string into specifications separated by '-' and
617 // parse each specification individually, updating internal data structures.
618 SmallVector<unsigned, 8> NonIntegralAddressSpaces;
619 for (StringRef Spec : split(Str: LayoutString, Separator: '-')) {
620 if (Spec.empty())
621 return createStringError(Fmt: "empty specification is not allowed");
622 if (Error Err = parseSpecification(Spec, NonIntegralAddressSpaces))
623 return Err;
624 }
625 // Mark all address spaces that were qualified as non-integral now. This has
626 // to be done later since the non-integral property is not part of the data
627 // layout pointer specification.
628 for (unsigned AS : NonIntegralAddressSpaces) {
629 // If there is no special spec for a given AS, getPointerSpec(AS) returns
630 // the spec for AS0, and we then update that to mark it non-integral.
631 const PointerSpec &PS = getPointerSpec(AddrSpace: AS);
632 setPointerSpec(AddrSpace: AS, BitWidth: PS.BitWidth, ABIAlign: PS.ABIAlign, PrefAlign: PS.PrefAlign, IndexBitWidth: PS.IndexBitWidth,
633 IsNonIntegral: true);
634 }
635
636 return Error::success();
637}
638
639void DataLayout::setPrimitiveSpec(char Specifier, uint32_t BitWidth,
640 Align ABIAlign, Align PrefAlign) {
641 SmallVectorImpl<PrimitiveSpec> *Specs;
642 switch (Specifier) {
643 default:
644 llvm_unreachable("Unexpected specifier");
645 case 'i':
646 Specs = &IntSpecs;
647 break;
648 case 'f':
649 Specs = &FloatSpecs;
650 break;
651 case 'v':
652 Specs = &VectorSpecs;
653 break;
654 }
655
656 auto I = lower_bound(Range&: *Specs, Value&: BitWidth, C: LessPrimitiveBitWidth());
657 if (I != Specs->end() && I->BitWidth == BitWidth) {
658 // Update the abi, preferred alignments.
659 I->ABIAlign = ABIAlign;
660 I->PrefAlign = PrefAlign;
661 } else {
662 // Insert before I to keep the vector sorted.
663 Specs->insert(I, Elt: PrimitiveSpec{.BitWidth: BitWidth, .ABIAlign: ABIAlign, .PrefAlign: PrefAlign});
664 }
665}
666
667const DataLayout::PointerSpec &
668DataLayout::getPointerSpec(uint32_t AddrSpace) const {
669 if (AddrSpace != 0) {
670 auto I = lower_bound(Range: PointerSpecs, Value&: AddrSpace, C: LessPointerAddrSpace());
671 if (I != PointerSpecs.end() && I->AddrSpace == AddrSpace)
672 return *I;
673 }
674
675 assert(PointerSpecs[0].AddrSpace == 0);
676 return PointerSpecs[0];
677}
678
679void DataLayout::setPointerSpec(uint32_t AddrSpace, uint32_t BitWidth,
680 Align ABIAlign, Align PrefAlign,
681 uint32_t IndexBitWidth, bool IsNonIntegral) {
682 auto I = lower_bound(Range&: PointerSpecs, Value&: AddrSpace, C: LessPointerAddrSpace());
683 if (I == PointerSpecs.end() || I->AddrSpace != AddrSpace) {
684 PointerSpecs.insert(I, Elt: PointerSpec{.AddrSpace: AddrSpace, .BitWidth: BitWidth, .ABIAlign: ABIAlign, .PrefAlign: PrefAlign,
685 .IndexBitWidth: IndexBitWidth, .IsNonIntegral: IsNonIntegral});
686 } else {
687 I->BitWidth = BitWidth;
688 I->ABIAlign = ABIAlign;
689 I->PrefAlign = PrefAlign;
690 I->IndexBitWidth = IndexBitWidth;
691 I->IsNonIntegral = IsNonIntegral;
692 }
693}
694
695Align DataLayout::getIntegerAlignment(uint32_t BitWidth,
696 bool abi_or_pref) const {
697 auto I = lower_bound(Range: IntSpecs, Value&: BitWidth, C: LessPrimitiveBitWidth());
698 // If we don't have an exact match, use alignment of next larger integer
699 // type. If there is none, use alignment of largest integer type by going
700 // back one element.
701 if (I == IntSpecs.end())
702 --I;
703 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
704}
705
706DataLayout::~DataLayout() { delete static_cast<StructLayoutMap *>(LayoutMap); }
707
708const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
709 if (!LayoutMap)
710 LayoutMap = new StructLayoutMap();
711
712 StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
713 StructLayout *&SL = (*STM)[Ty];
714 if (SL) return SL;
715
716 // Otherwise, create the struct layout. Because it is variable length, we
717 // malloc it, then use placement new.
718 StructLayout *L = (StructLayout *)safe_malloc(
719 Sz: StructLayout::totalSizeToAlloc<TypeSize>(Counts: Ty->getNumElements()));
720
721 // Set SL before calling StructLayout's ctor. The ctor could cause other
722 // entries to be added to TheMap, invalidating our reference.
723 SL = L;
724
725 new (L) StructLayout(Ty, *this);
726
727 return L;
728}
729
730Align DataLayout::getPointerABIAlignment(unsigned AS) const {
731 return getPointerSpec(AddrSpace: AS).ABIAlign;
732}
733
734Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
735 return getPointerSpec(AddrSpace: AS).PrefAlign;
736}
737
738unsigned DataLayout::getPointerSize(unsigned AS) const {
739 return divideCeil(Numerator: getPointerSpec(AddrSpace: AS).BitWidth, Denominator: 8);
740}
741
742unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
743 assert(Ty->isPtrOrPtrVectorTy() &&
744 "This should only be called with a pointer or pointer vector type");
745 Ty = Ty->getScalarType();
746 return getPointerSizeInBits(AS: cast<PointerType>(Val: Ty)->getAddressSpace());
747}
748
749unsigned DataLayout::getIndexSize(unsigned AS) const {
750 return divideCeil(Numerator: getPointerSpec(AddrSpace: AS).IndexBitWidth, Denominator: 8);
751}
752
753unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
754 assert(Ty->isPtrOrPtrVectorTy() &&
755 "This should only be called with a pointer or pointer vector type");
756 Ty = Ty->getScalarType();
757 return getIndexSizeInBits(AS: cast<PointerType>(Val: Ty)->getAddressSpace());
758}
759
760/*!
761 \param abi_or_pref Flag that determines which alignment is returned. true
762 returns the ABI alignment, false returns the preferred alignment.
763 \param Ty The underlying type for which alignment is determined.
764
765 Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
766 == false) for the requested type \a Ty.
767 */
768Align DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
769 assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
770 switch (Ty->getTypeID()) {
771 // Early escape for the non-numeric types.
772 case Type::LabelTyID:
773 return abi_or_pref ? getPointerABIAlignment(AS: 0) : getPointerPrefAlignment(AS: 0);
774 case Type::PointerTyID: {
775 unsigned AS = cast<PointerType>(Val: Ty)->getAddressSpace();
776 return abi_or_pref ? getPointerABIAlignment(AS)
777 : getPointerPrefAlignment(AS);
778 }
779 case Type::ArrayTyID:
780 return getAlignment(Ty: cast<ArrayType>(Val: Ty)->getElementType(), abi_or_pref);
781
782 case Type::StructTyID: {
783 // Packed structure types always have an ABI alignment of one.
784 if (cast<StructType>(Val: Ty)->isPacked() && abi_or_pref)
785 return Align(1);
786
787 // Get the layout annotation... which is lazily created on demand.
788 const StructLayout *Layout = getStructLayout(Ty: cast<StructType>(Val: Ty));
789 const Align Align = abi_or_pref ? StructABIAlignment : StructPrefAlignment;
790 return std::max(a: Align, b: Layout->getAlignment());
791 }
792 case Type::IntegerTyID:
793 return getIntegerAlignment(BitWidth: Ty->getIntegerBitWidth(), abi_or_pref);
794 case Type::HalfTyID:
795 case Type::BFloatTyID:
796 case Type::FloatTyID:
797 case Type::DoubleTyID:
798 // PPC_FP128TyID and FP128TyID have different data contents, but the
799 // same size and alignment, so they look the same here.
800 case Type::PPC_FP128TyID:
801 case Type::FP128TyID:
802 case Type::X86_FP80TyID: {
803 unsigned BitWidth = getTypeSizeInBits(Ty).getFixedValue();
804 auto I = lower_bound(Range: FloatSpecs, Value&: BitWidth, C: LessPrimitiveBitWidth());
805 if (I != FloatSpecs.end() && I->BitWidth == BitWidth)
806 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
807
808 // If we still couldn't find a reasonable default alignment, fall back
809 // to a simple heuristic that the alignment is the first power of two
810 // greater-or-equal to the store size of the type. This is a reasonable
811 // approximation of reality, and if the user wanted something less
812 // less conservative, they should have specified it explicitly in the data
813 // layout.
814 return Align(PowerOf2Ceil(A: BitWidth / 8));
815 }
816 case Type::FixedVectorTyID:
817 case Type::ScalableVectorTyID: {
818 unsigned BitWidth = getTypeSizeInBits(Ty).getKnownMinValue();
819 auto I = lower_bound(Range: VectorSpecs, Value&: BitWidth, C: LessPrimitiveBitWidth());
820 if (I != VectorSpecs.end() && I->BitWidth == BitWidth)
821 return abi_or_pref ? I->ABIAlign : I->PrefAlign;
822
823 // By default, use natural alignment for vector types. This is consistent
824 // with what clang and llvm-gcc do.
825 //
826 // We're only calculating a natural alignment, so it doesn't have to be
827 // based on the full size for scalable vectors. Using the minimum element
828 // count should be enough here.
829 return Align(PowerOf2Ceil(A: getTypeStoreSize(Ty).getKnownMinValue()));
830 }
831 case Type::X86_AMXTyID:
832 return Align(64);
833 case Type::TargetExtTyID: {
834 Type *LayoutTy = cast<TargetExtType>(Val: Ty)->getLayoutType();
835 return getAlignment(Ty: LayoutTy, abi_or_pref);
836 }
837 default:
838 llvm_unreachable("Bad type for getAlignment!!!");
839 }
840}
841
842Align DataLayout::getABITypeAlign(Type *Ty) const {
843 return getAlignment(Ty, abi_or_pref: true);
844}
845
846Align DataLayout::getPrefTypeAlign(Type *Ty) const {
847 return getAlignment(Ty, abi_or_pref: false);
848}
849
850IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
851 unsigned AddressSpace) const {
852 return IntegerType::get(C, NumBits: getPointerSizeInBits(AS: AddressSpace));
853}
854
855Type *DataLayout::getIntPtrType(Type *Ty) const {
856 assert(Ty->isPtrOrPtrVectorTy() &&
857 "Expected a pointer or pointer vector type.");
858 unsigned NumBits = getPointerTypeSizeInBits(Ty);
859 IntegerType *IntTy = IntegerType::get(C&: Ty->getContext(), NumBits);
860 if (VectorType *VecTy = dyn_cast<VectorType>(Val: Ty))
861 return VectorType::get(ElementType: IntTy, Other: VecTy);
862 return IntTy;
863}
864
865Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
866 for (unsigned LegalIntWidth : LegalIntWidths)
867 if (Width <= LegalIntWidth)
868 return Type::getIntNTy(C, N: LegalIntWidth);
869 return nullptr;
870}
871
872unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
873 auto Max = llvm::max_element(Range: LegalIntWidths);
874 return Max != LegalIntWidths.end() ? *Max : 0;
875}
876
877IntegerType *DataLayout::getIndexType(LLVMContext &C,
878 unsigned AddressSpace) const {
879 return IntegerType::get(C, NumBits: getIndexSizeInBits(AS: AddressSpace));
880}
881
882Type *DataLayout::getIndexType(Type *Ty) const {
883 assert(Ty->isPtrOrPtrVectorTy() &&
884 "Expected a pointer or pointer vector type.");
885 unsigned NumBits = getIndexTypeSizeInBits(Ty);
886 IntegerType *IntTy = IntegerType::get(C&: Ty->getContext(), NumBits);
887 if (VectorType *VecTy = dyn_cast<VectorType>(Val: Ty))
888 return VectorType::get(ElementType: IntTy, Other: VecTy);
889 return IntTy;
890}
891
892int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
893 ArrayRef<Value *> Indices) const {
894 int64_t Result = 0;
895
896 generic_gep_type_iterator<Value* const*>
897 GTI = gep_type_begin(Op0: ElemTy, A: Indices),
898 GTE = gep_type_end(ElemTy, A: Indices);
899 for (; GTI != GTE; ++GTI) {
900 Value *Idx = GTI.getOperand();
901 if (StructType *STy = GTI.getStructTypeOrNull()) {
902 assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
903 unsigned FieldNo = cast<ConstantInt>(Val: Idx)->getZExtValue();
904
905 // Get structure layout information...
906 const StructLayout *Layout = getStructLayout(Ty: STy);
907
908 // Add in the offset, as calculated by the structure layout info...
909 Result += Layout->getElementOffset(Idx: FieldNo);
910 } else {
911 if (int64_t ArrayIdx = cast<ConstantInt>(Val: Idx)->getSExtValue())
912 Result += ArrayIdx * GTI.getSequentialElementStride(DL: *this);
913 }
914 }
915
916 return Result;
917}
918
919static APInt getElementIndex(TypeSize ElemSize, APInt &Offset) {
920 // Skip over scalable or zero size elements. Also skip element sizes larger
921 // than the positive index space, because the arithmetic below may not be
922 // correct in that case.
923 unsigned BitWidth = Offset.getBitWidth();
924 if (ElemSize.isScalable() || ElemSize == 0 ||
925 !isUIntN(N: BitWidth - 1, x: ElemSize)) {
926 return APInt::getZero(numBits: BitWidth);
927 }
928
929 APInt Index = Offset.sdiv(RHS: ElemSize);
930 Offset -= Index * ElemSize;
931 if (Offset.isNegative()) {
932 // Prefer a positive remaining offset to allow struct indexing.
933 --Index;
934 Offset += ElemSize;
935 assert(Offset.isNonNegative() && "Remaining offset shouldn't be negative");
936 }
937 return Index;
938}
939
940std::optional<APInt> DataLayout::getGEPIndexForOffset(Type *&ElemTy,
941 APInt &Offset) const {
942 if (auto *ArrTy = dyn_cast<ArrayType>(Val: ElemTy)) {
943 ElemTy = ArrTy->getElementType();
944 return getElementIndex(ElemSize: getTypeAllocSize(Ty: ElemTy), Offset);
945 }
946
947 if (isa<VectorType>(Val: ElemTy)) {
948 // Vector GEPs are partially broken (e.g. for overaligned element types),
949 // and may be forbidden in the future, so avoid generating GEPs into
950 // vectors. See https://discourse.llvm.org/t/67497
951 return std::nullopt;
952 }
953
954 if (auto *STy = dyn_cast<StructType>(Val: ElemTy)) {
955 const StructLayout *SL = getStructLayout(Ty: STy);
956 uint64_t IntOffset = Offset.getZExtValue();
957 if (IntOffset >= SL->getSizeInBytes())
958 return std::nullopt;
959
960 unsigned Index = SL->getElementContainingOffset(FixedOffset: IntOffset);
961 Offset -= SL->getElementOffset(Idx: Index);
962 ElemTy = STy->getElementType(N: Index);
963 return APInt(32, Index);
964 }
965
966 // Non-aggregate type.
967 return std::nullopt;
968}
969
970SmallVector<APInt> DataLayout::getGEPIndicesForOffset(Type *&ElemTy,
971 APInt &Offset) const {
972 assert(ElemTy->isSized() && "Element type must be sized");
973 SmallVector<APInt> Indices;
974 Indices.push_back(Elt: getElementIndex(ElemSize: getTypeAllocSize(Ty: ElemTy), Offset));
975 while (Offset != 0) {
976 std::optional<APInt> Index = getGEPIndexForOffset(ElemTy, Offset);
977 if (!Index)
978 break;
979 Indices.push_back(Elt: *Index);
980 }
981
982 return Indices;
983}
984
985/// getPreferredAlign - Return the preferred alignment of the specified global.
986/// This includes an explicitly requested alignment (if the global has one).
987Align DataLayout::getPreferredAlign(const GlobalVariable *GV) const {
988 MaybeAlign GVAlignment = GV->getAlign();
989 // If a section is specified, always precisely honor explicit alignment,
990 // so we don't insert padding into a section we don't control.
991 if (GVAlignment && GV->hasSection())
992 return *GVAlignment;
993
994 // If no explicit alignment is specified, compute the alignment based on
995 // the IR type. If an alignment is specified, increase it to match the ABI
996 // alignment of the IR type.
997 //
998 // FIXME: Not sure it makes sense to use the alignment of the type if
999 // there's already an explicit alignment specification.
1000 Type *ElemType = GV->getValueType();
1001 Align Alignment = getPrefTypeAlign(Ty: ElemType);
1002 if (GVAlignment) {
1003 if (*GVAlignment >= Alignment)
1004 Alignment = *GVAlignment;
1005 else
1006 Alignment = std::max(a: *GVAlignment, b: getABITypeAlign(Ty: ElemType));
1007 }
1008
1009 // If no explicit alignment is specified, and the global is large, increase
1010 // the alignment to 16.
1011 // FIXME: Why 16, specifically?
1012 if (GV->hasInitializer() && !GVAlignment) {
1013 if (Alignment < Align(16)) {
1014 // If the global is not external, see if it is large. If so, give it a
1015 // larger alignment.
1016 if (getTypeSizeInBits(Ty: ElemType) > 128)
1017 Alignment = Align(16); // 16-byte alignment.
1018 }
1019 }
1020 return Alignment;
1021}
1022