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