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(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(i);
57    if (i == 0 && Ty->isScalableTy())
58      StructSize = TypeSize::getScalable(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(TyAlign, StructSize)) {
70      IsPadded = true;
71      StructSize = TypeSize::getFixed(alignTo(StructSize, TyAlign));
72    }
73
74    // Keep track of maximum alignment constraint.
75    StructAlignment = std::max(TyAlign, 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(StructAlignment, StructSize)) {
85    IsPadded = true;
86    StructSize = TypeSize::getFixed(alignTo(StructSize, 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(FixedOffset);
97  ArrayRef<TypeSize> MemberOffsets = getMemberOffsets();
98
99  const auto *SI =
100      std::upper_bound(MemberOffsets.begin(), MemberOffsets.end(), Offset,
101                       [](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, {1, Align(1), Align(1)}},    // i1
183    {INTEGER_ALIGN, {8, Align(1), Align(1)}},    // i8
184    {INTEGER_ALIGN, {16, Align(2), Align(2)}},   // i16
185    {INTEGER_ALIGN, {32, Align(4), Align(4)}},   // i32
186    {INTEGER_ALIGN, {64, Align(4), Align(8)}},   // i64
187    {FLOAT_ALIGN, {16, Align(2), Align(2)}},     // half, bfloat
188    {FLOAT_ALIGN, {32, Align(4), Align(4)}},     // float
189    {FLOAT_ALIGN, {64, Align(8), Align(8)}},     // double
190    {FLOAT_ALIGN, {128, Align(16), Align(16)}},  // ppcf128, quad, ...
191    {VECTOR_ALIGN, {64, Align(8), Align(8)}},    // v2i32, v1i64, ...
192    {VECTOR_ALIGN, {128, Align(16), 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(Align(1), Align(8), 0);
209
210  // Default alignments
211  for (const auto &[Kind, Layout] : DefaultAlignments) {
212    if (Error Err = setAlignment(Kind, Layout.ABIAlign, Layout.PrefAlign,
213                                 Layout.TypeBitWidth))
214      return report_fatal_error(std::move(Err));
215  }
216  if (Error Err = setPointerAlignmentInBits(0, Align(8), Align(8), 64, 64))
217    return report_fatal_error(std::move(Err));
218
219  if (Error Err = parseSpecifier(Desc))
220    return report_fatal_error(std::move(Err));
221}
222
223Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) {
224  DataLayout Layout("");
225  if (Error Err = Layout.parseSpecifier(LayoutDescription))
226    return std::move(Err);
227  return Layout;
228}
229
230static Error reportError(const Twine &Message) {
231  return createStringError(inconvertibleErrorCode(), 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("Trailing separator in datalayout string");
241  if (!Split.second.empty() && Split.first.empty())
242    return reportError("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("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("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, AddrSpace))
268    return Err;
269  if (!isUInt<24>(AddrSpace))
270    return reportError("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(Desc, '-', Split))
280      return Err;
281    Desc = Split.second;
282
283    // Split at ':'.
284    if (Error Err = ::split(Split.first, ':', 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(Rest, ':', Split))
294          return Err;
295        Rest = Split.second;
296        unsigned AS;
297        if (Error Err = getInt(Split.first, AS))
298          return Err;
299        if (AS == 0)
300          return reportError("Address space 0 can never be non-integral");
301        NonIntegralAddressSpaces.push_back(AS);
302      } while (!Rest.empty());
303
304      continue;
305    }
306
307    char Specifier = Tok.front();
308    Tok = Tok.substr(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(Tok, AddrSpace))
326          return Err;
327      if (!isUInt<24>(AddrSpace))
328        return reportError("Invalid address space, must be a 24-bit integer");
329
330      // Size.
331      if (Rest.empty())
332        return reportError(
333            "Missing size specification for pointer in datalayout string");
334      if (Error Err = ::split(Rest, ':', Split))
335        return Err;
336      unsigned PointerMemSize;
337      if (Error Err = getInt(Tok, PointerMemSize))
338        return Err;
339      if (!PointerMemSize)
340        return reportError("Invalid pointer size of 0 bytes");
341
342      // ABI alignment.
343      if (Rest.empty())
344        return reportError(
345            "Missing alignment specification for pointer in datalayout string");
346      if (Error Err = ::split(Rest, ':', Split))
347        return Err;
348      unsigned PointerABIAlign;
349      if (Error Err = getIntInBytes(Tok, PointerABIAlign))
350        return Err;
351      if (!isPowerOf2_64(PointerABIAlign))
352        return reportError("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(Rest, ':', Split))
362          return Err;
363        if (Error Err = getIntInBytes(Tok, PointerPrefAlign))
364          return Err;
365        if (!isPowerOf2_64(PointerPrefAlign))
366          return reportError(
367              "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(Rest, ':', Split))
372            return Err;
373          if (Error Err = getInt(Tok, IndexSize))
374            return Err;
375          if (!IndexSize)
376            return reportError("Invalid index size of 0 bytes");
377        }
378      }
379      if (Error Err = setPointerAlignmentInBits(
380              AddrSpace, assumeAligned(PointerABIAlign),
381              assumeAligned(PointerPrefAlign), PointerMemSize, 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(Tok, Size))
402          return Err;
403
404      if (AlignType == AGGREGATE_ALIGN && Size != 0)
405        return reportError(
406            "Sized aggregate specification in datalayout string");
407
408      // ABI alignment.
409      if (Rest.empty())
410        return reportError(
411            "Missing alignment specification in datalayout string");
412      if (Error Err = ::split(Rest, ':', Split))
413        return Err;
414      unsigned ABIAlign;
415      if (Error Err = getIntInBytes(Tok, ABIAlign))
416        return Err;
417      if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
418        return reportError(
419            "ABI alignment specification must be >0 for non-aggregate types");
420
421      if (!isUInt<16>(ABIAlign))
422        return reportError("Invalid ABI alignment, must be a 16bit integer");
423      if (ABIAlign != 0 && !isPowerOf2_64(ABIAlign))
424        return reportError("Invalid ABI alignment, must be a power of 2");
425      if (AlignType == INTEGER_ALIGN && Size == 8 && ABIAlign != 1)
426        return reportError(
427            "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(Rest, ':', Split))
433          return Err;
434        if (Error Err = getIntInBytes(Tok, PrefAlign))
435          return Err;
436      }
437
438      if (!isUInt<16>(PrefAlign))
439        return reportError(
440            "Invalid preferred alignment, must be a 16bit integer");
441      if (PrefAlign != 0 && !isPowerOf2_64(PrefAlign))
442        return reportError("Invalid preferred alignment, must be a power of 2");
443
444      if (Error Err = setAlignment(AlignType, assumeAligned(ABIAlign),
445                                   assumeAligned(PrefAlign), 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(Tok, Width))
454          return Err;
455        if (Width == 0)
456          return reportError(
457              "Zero width native integer type in datalayout string");
458        LegalIntWidths.push_back(Width);
459        if (Rest.empty())
460          break;
461        if (Error Err = ::split(Rest, ':', Split))
462          return Err;
463      }
464      break;
465    case 'S': { // Stack natural alignment.
466      uint64_t Alignment;
467      if (Error Err = getIntInBytes(Tok, Alignment))
468        return Err;
469      if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
470        return reportError("Alignment is neither 0 nor a power of 2");
471      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("Unknown function pointer alignment type in "
484                           "datalayout string");
485      }
486      Tok = Tok.substr(1);
487      uint64_t Alignment;
488      if (Error Err = getIntInBytes(Tok, Alignment))
489        return Err;
490      if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))
491        return reportError("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(Tok, ProgramAddrSpace))
497        return Err;
498      break;
499    }
500    case 'A': { // Default stack/alloca address space.
501      if (Error Err = getAddrSpace(Tok, AllocaAddrSpace))
502        return Err;
503      break;
504    }
505    case 'G': { // Default address space for global variables.
506      if (Error Err = getAddrSpace(Tok, DefaultGlobalsAddrSpace))
507        return Err;
508      break;
509    }
510    case 'm':
511      if (!Tok.empty())
512        return reportError("Unexpected trailing characters after mangling "
513                           "specifier in datalayout string");
514      if (Rest.empty())
515        return reportError("Expected mangling specifier in datalayout string");
516      if (Rest.size() > 1)
517        return reportError("Unknown mangling specifier in datalayout string");
518      switch(Rest[0]) {
519      default:
520        return reportError("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("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(Alignments, [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>(BitWidth))
594    return reportError("Invalid bit width, must be a 24-bit integer");
595  if (PrefAlign < ABIAlign)
596    return reportError(
597        "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(*Alignments, [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, 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(Pointers, AddressSpace,
634                         [](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        "Preferred alignment cannot be less than the ABI alignment");
652  if (IndexBitWidth > TypeBitWidth)
653    return reportError("Index width cannot be larger than pointer width");
654
655  auto I = lower_bound(Pointers, AddrSpace,
656                       [](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                    PointerAlignElem::getInBits(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(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(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      StructLayout::totalSizeToAlloc<TypeSize>(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(AS).ABIAlign;
744}
745
746Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
747  return getPointerAlignElem(AS).PrefAlign;
748}
749
750unsigned DataLayout::getPointerSize(unsigned AS) const {
751  return divideCeil(getPointerAlignElem(AS).TypeBitWidth, 8);
752}
753
754unsigned DataLayout::getMaxIndexSize() const {
755  unsigned MaxIndexSize = 0;
756  for (auto &P : Pointers)
757    MaxIndexSize =
758        std::max(MaxIndexSize, (unsigned)divideCeil(P.TypeBitWidth, 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(cast<PointerType>(Ty)->getAddressSpace());
768}
769
770unsigned DataLayout::getIndexSize(unsigned AS) const {
771  return divideCeil(getPointerAlignElem(AS).IndexBitWidth, 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(cast<PointerType>(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(0) : getPointerPrefAlignment(0);
795  case Type::PointerTyID: {
796    unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
797    return abi_or_pref ? getPointerABIAlignment(AS)
798                       : getPointerPrefAlignment(AS);
799    }
800  case Type::ArrayTyID:
801    return getAlignment(cast<ArrayType>(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>(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(cast<StructType>(Ty));
810    const Align Align =
811        abi_or_pref ? StructAlignment.ABIAlign : StructAlignment.PrefAlign;
812    return std::max(Align, Layout->getAlignment());
813  }
814  case Type::IntegerTyID:
815    return getIntegerAlignment(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(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(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(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(getTypeStoreSize(Ty).getKnownMinValue()));
853  }
854  case Type::X86_AMXTyID:
855    return Align(64);
856  case Type::TargetExtTyID: {
857    Type *LayoutTy = cast<TargetExtType>(Ty)->getLayoutType();
858    return getAlignment(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, 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, false);
876}
877
878IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
879                                       unsigned AddressSpace) const {
880  return IntegerType::get(C, getPointerSizeInBits(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(Ty->getContext(), NumBits);
888  if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
889    return VectorType::get(IntTy, 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, LegalIntWidth);
897  return nullptr;
898}
899
900unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
901  auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
902  return Max != LegalIntWidths.end() ? *Max : 0;
903}
904
905IntegerType *DataLayout::getIndexType(LLVMContext &C,
906                                      unsigned AddressSpace) const {
907  return IntegerType::get(C, getIndexSizeInBits(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(Ty->getContext(), NumBits);
915  if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
916    return VectorType::get(IntTy, 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(ElemTy, Indices),
926    GTE = gep_type_end(ElemTy, 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>(Idx)->getZExtValue();
932
933      // Get structure layout information...
934      const StructLayout *Layout = getStructLayout(STy);
935
936      // Add in the offset, as calculated by the structure layout info...
937      Result += Layout->getElementOffset(FieldNo);
938    } else {
939      if (int64_t ArrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
940        Result += ArrayIdx * GTI.getSequentialElementStride(*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(BitWidth - 1, ElemSize)) {
954    return APInt::getZero(BitWidth);
955  }
956
957  APInt Index = Offset.sdiv(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>(ElemTy)) {
971    ElemTy = ArrTy->getElementType();
972    return getElementIndex(getTypeAllocSize(ElemTy), Offset);
973  }
974
975  if (isa<VectorType>(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>(ElemTy)) {
983    const StructLayout *SL = getStructLayout(STy);
984    uint64_t IntOffset = Offset.getZExtValue();
985    if (IntOffset >= SL->getSizeInBytes())
986      return std::nullopt;
987
988    unsigned Index = SL->getElementContainingOffset(IntOffset);
989    Offset -= SL->getElementOffset(Index);
990    ElemTy = STy->getElementType(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(getElementIndex(getTypeAllocSize(ElemTy), Offset));
1003  while (Offset != 0) {
1004    std::optional<APInt> Index = getGEPIndexForOffset(ElemTy, Offset);
1005    if (!Index)
1006      break;
1007    Indices.push_back(*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(ElemType);
1030  if (GVAlignment) {
1031    if (*GVAlignment >= Alignment)
1032      Alignment = *GVAlignment;
1033    else
1034      Alignment = std::max(*GVAlignment, getABITypeAlign(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(ElemType) > 128)
1045        Alignment = Align(16); // 16-byte alignment.
1046    }
1047  }
1048  return Alignment;
1049}
1050