xref: /freebsd/contrib/llvm-project/llvm/lib/IR/DataLayout.cpp (revision 7029da5c36f2d3cf6bb6c81bf551229f416399e8)
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/ErrorHandling.h"
31 #include "llvm/Support/MathExtras.h"
32 #include <algorithm>
33 #include <cassert>
34 #include <cstdint>
35 #include <cstdlib>
36 #include <tuple>
37 #include <utility>
38 
39 using namespace llvm;
40 
41 //===----------------------------------------------------------------------===//
42 // Support for StructLayout
43 //===----------------------------------------------------------------------===//
44 
45 StructLayout::StructLayout(StructType *ST, const DataLayout &DL) {
46   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
47   StructAlignment = 0;
48   StructSize = 0;
49   IsPadded = false;
50   NumElements = ST->getNumElements();
51 
52   // Loop over each of the elements, placing them in memory.
53   for (unsigned i = 0, e = NumElements; i != e; ++i) {
54     Type *Ty = ST->getElementType(i);
55     unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty);
56 
57     // Add padding if necessary to align the data element properly.
58     if ((StructSize & (TyAlign-1)) != 0) {
59       IsPadded = true;
60       StructSize = alignTo(StructSize, TyAlign);
61     }
62 
63     // Keep track of maximum alignment constraint.
64     StructAlignment = std::max(TyAlign, StructAlignment);
65 
66     MemberOffsets[i] = StructSize;
67     StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
68   }
69 
70   // Empty structures have alignment of 1 byte.
71   if (StructAlignment == 0) StructAlignment = 1;
72 
73   // Add padding to the end of the struct so that it could be put in an array
74   // and all array elements would be aligned correctly.
75   if ((StructSize & (StructAlignment-1)) != 0) {
76     IsPadded = true;
77     StructSize = alignTo(StructSize, StructAlignment);
78   }
79 }
80 
81 /// getElementContainingOffset - Given a valid offset into the structure,
82 /// return the structure index that contains it.
83 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
84   const uint64_t *SI =
85     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
86   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
87   --SI;
88   assert(*SI <= Offset && "upper_bound didn't work");
89   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
90          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
91          "Upper bound didn't work!");
92 
93   // Multiple fields can have the same offset if any of them are zero sized.
94   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
95   // at the i32 element, because it is the last element at that offset.  This is
96   // the right one to return, because anything after it will have a higher
97   // offset, implying that this element is non-empty.
98   return SI-&MemberOffsets[0];
99 }
100 
101 //===----------------------------------------------------------------------===//
102 // LayoutAlignElem, LayoutAlign support
103 //===----------------------------------------------------------------------===//
104 
105 LayoutAlignElem
106 LayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
107                      unsigned pref_align, uint32_t bit_width) {
108   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
109   LayoutAlignElem retval;
110   retval.AlignType = align_type;
111   retval.ABIAlign = abi_align;
112   retval.PrefAlign = pref_align;
113   retval.TypeBitWidth = bit_width;
114   return retval;
115 }
116 
117 bool
118 LayoutAlignElem::operator==(const LayoutAlignElem &rhs) const {
119   return (AlignType == rhs.AlignType
120           && ABIAlign == rhs.ABIAlign
121           && PrefAlign == rhs.PrefAlign
122           && TypeBitWidth == rhs.TypeBitWidth);
123 }
124 
125 //===----------------------------------------------------------------------===//
126 // PointerAlignElem, PointerAlign support
127 //===----------------------------------------------------------------------===//
128 
129 PointerAlignElem
130 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
131                       unsigned PrefAlign, uint32_t TypeByteWidth,
132                       uint32_t IndexWidth) {
133   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
134   PointerAlignElem retval;
135   retval.AddressSpace = AddressSpace;
136   retval.ABIAlign = ABIAlign;
137   retval.PrefAlign = PrefAlign;
138   retval.TypeByteWidth = TypeByteWidth;
139   retval.IndexWidth = IndexWidth;
140   return retval;
141 }
142 
143 bool
144 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
145   return (ABIAlign == rhs.ABIAlign
146           && AddressSpace == rhs.AddressSpace
147           && PrefAlign == rhs.PrefAlign
148           && TypeByteWidth == rhs.TypeByteWidth
149           && IndexWidth == rhs.IndexWidth);
150 }
151 
152 //===----------------------------------------------------------------------===//
153 //                       DataLayout Class Implementation
154 //===----------------------------------------------------------------------===//
155 
156 const char *DataLayout::getManglingComponent(const Triple &T) {
157   if (T.isOSBinFormatMachO())
158     return "-m:o";
159   if (T.isOSWindows() && T.isOSBinFormatCOFF())
160     return T.getArch() == Triple::x86 ? "-m:x" : "-m:w";
161   return "-m:e";
162 }
163 
164 static const LayoutAlignElem DefaultAlignments[] = {
165   { INTEGER_ALIGN, 1, 1, 1 },    // i1
166   { INTEGER_ALIGN, 8, 1, 1 },    // i8
167   { INTEGER_ALIGN, 16, 2, 2 },   // i16
168   { INTEGER_ALIGN, 32, 4, 4 },   // i32
169   { INTEGER_ALIGN, 64, 4, 8 },   // i64
170   { FLOAT_ALIGN, 16, 2, 2 },     // half
171   { FLOAT_ALIGN, 32, 4, 4 },     // float
172   { FLOAT_ALIGN, 64, 8, 8 },     // double
173   { FLOAT_ALIGN, 128, 16, 16 },  // ppcf128, quad, ...
174   { VECTOR_ALIGN, 64, 8, 8 },    // v2i32, v1i64, ...
175   { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ...
176   { AGGREGATE_ALIGN, 0, 0, 8 }   // struct
177 };
178 
179 void DataLayout::reset(StringRef Desc) {
180   clear();
181 
182   LayoutMap = nullptr;
183   BigEndian = false;
184   AllocaAddrSpace = 0;
185   StackNaturalAlign = 0;
186   ProgramAddrSpace = 0;
187   FunctionPtrAlign = 0;
188   TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
189   ManglingMode = MM_None;
190   NonIntegralAddressSpaces.clear();
191 
192   // Default alignments
193   for (const LayoutAlignElem &E : DefaultAlignments) {
194     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
195                  E.TypeBitWidth);
196   }
197   setPointerAlignment(0, 8, 8, 8, 8);
198 
199   parseSpecifier(Desc);
200 }
201 
202 /// Checked version of split, to ensure mandatory subparts.
203 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
204   assert(!Str.empty() && "parse error, string can't be empty here");
205   std::pair<StringRef, StringRef> Split = Str.split(Separator);
206   if (Split.second.empty() && Split.first != Str)
207     report_fatal_error("Trailing separator in datalayout string");
208   if (!Split.second.empty() && Split.first.empty())
209     report_fatal_error("Expected token before separator in datalayout string");
210   return Split;
211 }
212 
213 /// Get an unsigned integer, including error checks.
214 static unsigned getInt(StringRef R) {
215   unsigned Result;
216   bool error = R.getAsInteger(10, Result); (void)error;
217   if (error)
218     report_fatal_error("not a number, or does not fit in an unsigned int");
219   return Result;
220 }
221 
222 /// Convert bits into bytes. Assert if not a byte width multiple.
223 static unsigned inBytes(unsigned Bits) {
224   if (Bits % 8)
225     report_fatal_error("number of bits must be a byte width multiple");
226   return Bits / 8;
227 }
228 
229 static unsigned getAddrSpace(StringRef R) {
230   unsigned AddrSpace = getInt(R);
231   if (!isUInt<24>(AddrSpace))
232     report_fatal_error("Invalid address space, must be a 24-bit integer");
233   return AddrSpace;
234 }
235 
236 void DataLayout::parseSpecifier(StringRef Desc) {
237   StringRepresentation = Desc;
238   while (!Desc.empty()) {
239     // Split at '-'.
240     std::pair<StringRef, StringRef> Split = split(Desc, '-');
241     Desc = Split.second;
242 
243     // Split at ':'.
244     Split = split(Split.first, ':');
245 
246     // Aliases used below.
247     StringRef &Tok  = Split.first;  // Current token.
248     StringRef &Rest = Split.second; // The rest of the string.
249 
250     if (Tok == "ni") {
251       do {
252         Split = split(Rest, ':');
253         Rest = Split.second;
254         unsigned AS = getInt(Split.first);
255         if (AS == 0)
256           report_fatal_error("Address space 0 can never be non-integral");
257         NonIntegralAddressSpaces.push_back(AS);
258       } while (!Rest.empty());
259 
260       continue;
261     }
262 
263     char Specifier = Tok.front();
264     Tok = Tok.substr(1);
265 
266     switch (Specifier) {
267     case 's':
268       // Ignored for backward compatibility.
269       // FIXME: remove this on LLVM 4.0.
270       break;
271     case 'E':
272       BigEndian = true;
273       break;
274     case 'e':
275       BigEndian = false;
276       break;
277     case 'p': {
278       // Address space.
279       unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok);
280       if (!isUInt<24>(AddrSpace))
281         report_fatal_error("Invalid address space, must be a 24bit integer");
282 
283       // Size.
284       if (Rest.empty())
285         report_fatal_error(
286             "Missing size specification for pointer in datalayout string");
287       Split = split(Rest, ':');
288       unsigned PointerMemSize = inBytes(getInt(Tok));
289       if (!PointerMemSize)
290         report_fatal_error("Invalid pointer size of 0 bytes");
291 
292       // ABI alignment.
293       if (Rest.empty())
294         report_fatal_error(
295             "Missing alignment specification for pointer in datalayout string");
296       Split = split(Rest, ':');
297       unsigned PointerABIAlign = inBytes(getInt(Tok));
298       if (!isPowerOf2_64(PointerABIAlign))
299         report_fatal_error(
300             "Pointer ABI alignment must be a power of 2");
301 
302       // Size of index used in GEP for address calculation.
303       // The parameter is optional. By default it is equal to size of pointer.
304       unsigned IndexSize = PointerMemSize;
305 
306       // Preferred alignment.
307       unsigned PointerPrefAlign = PointerABIAlign;
308       if (!Rest.empty()) {
309         Split = split(Rest, ':');
310         PointerPrefAlign = inBytes(getInt(Tok));
311         if (!isPowerOf2_64(PointerPrefAlign))
312           report_fatal_error(
313             "Pointer preferred alignment must be a power of 2");
314 
315         // Now read the index. It is the second optional parameter here.
316         if (!Rest.empty()) {
317           Split = split(Rest, ':');
318           IndexSize = inBytes(getInt(Tok));
319           if (!IndexSize)
320             report_fatal_error("Invalid index size of 0 bytes");
321         }
322       }
323       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
324                           PointerMemSize, IndexSize);
325       break;
326     }
327     case 'i':
328     case 'v':
329     case 'f':
330     case 'a': {
331       AlignTypeEnum AlignType;
332       switch (Specifier) {
333       default: llvm_unreachable("Unexpected specifier!");
334       case 'i': AlignType = INTEGER_ALIGN; break;
335       case 'v': AlignType = VECTOR_ALIGN; break;
336       case 'f': AlignType = FLOAT_ALIGN; break;
337       case 'a': AlignType = AGGREGATE_ALIGN; break;
338       }
339 
340       // Bit size.
341       unsigned Size = Tok.empty() ? 0 : getInt(Tok);
342 
343       if (AlignType == AGGREGATE_ALIGN && Size != 0)
344         report_fatal_error(
345             "Sized aggregate specification in datalayout string");
346 
347       // ABI alignment.
348       if (Rest.empty())
349         report_fatal_error(
350             "Missing alignment specification in datalayout string");
351       Split = split(Rest, ':');
352       unsigned ABIAlign = inBytes(getInt(Tok));
353       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
354         report_fatal_error(
355             "ABI alignment specification must be >0 for non-aggregate types");
356 
357       // Preferred alignment.
358       unsigned PrefAlign = ABIAlign;
359       if (!Rest.empty()) {
360         Split = split(Rest, ':');
361         PrefAlign = inBytes(getInt(Tok));
362       }
363 
364       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
365 
366       break;
367     }
368     case 'n':  // Native integer types.
369       while (true) {
370         unsigned Width = getInt(Tok);
371         if (Width == 0)
372           report_fatal_error(
373               "Zero width native integer type in datalayout string");
374         LegalIntWidths.push_back(Width);
375         if (Rest.empty())
376           break;
377         Split = split(Rest, ':');
378       }
379       break;
380     case 'S': { // Stack natural alignment.
381       StackNaturalAlign = inBytes(getInt(Tok));
382       break;
383     }
384     case 'F': {
385       switch (Tok.front()) {
386       case 'i':
387         TheFunctionPtrAlignType = FunctionPtrAlignType::Independent;
388         break;
389       case 'n':
390         TheFunctionPtrAlignType = FunctionPtrAlignType::MultipleOfFunctionAlign;
391         break;
392       default:
393         report_fatal_error("Unknown function pointer alignment type in "
394                            "datalayout string");
395       }
396       Tok = Tok.substr(1);
397       FunctionPtrAlign = inBytes(getInt(Tok));
398       break;
399     }
400     case 'P': { // Function address space.
401       ProgramAddrSpace = getAddrSpace(Tok);
402       break;
403     }
404     case 'A': { // Default stack/alloca address space.
405       AllocaAddrSpace = getAddrSpace(Tok);
406       break;
407     }
408     case 'm':
409       if (!Tok.empty())
410         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
411       if (Rest.empty())
412         report_fatal_error("Expected mangling specifier in datalayout string");
413       if (Rest.size() > 1)
414         report_fatal_error("Unknown mangling specifier in datalayout string");
415       switch(Rest[0]) {
416       default:
417         report_fatal_error("Unknown mangling in datalayout string");
418       case 'e':
419         ManglingMode = MM_ELF;
420         break;
421       case 'o':
422         ManglingMode = MM_MachO;
423         break;
424       case 'm':
425         ManglingMode = MM_Mips;
426         break;
427       case 'w':
428         ManglingMode = MM_WinCOFF;
429         break;
430       case 'x':
431         ManglingMode = MM_WinCOFFX86;
432         break;
433       }
434       break;
435     default:
436       report_fatal_error("Unknown specifier in datalayout string");
437       break;
438     }
439   }
440 }
441 
442 DataLayout::DataLayout(const Module *M) {
443   init(M);
444 }
445 
446 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
447 
448 bool DataLayout::operator==(const DataLayout &Other) const {
449   bool Ret = BigEndian == Other.BigEndian &&
450              AllocaAddrSpace == Other.AllocaAddrSpace &&
451              StackNaturalAlign == Other.StackNaturalAlign &&
452              ProgramAddrSpace == Other.ProgramAddrSpace &&
453              FunctionPtrAlign == Other.FunctionPtrAlign &&
454              TheFunctionPtrAlignType == Other.TheFunctionPtrAlignType &&
455              ManglingMode == Other.ManglingMode &&
456              LegalIntWidths == Other.LegalIntWidths &&
457              Alignments == Other.Alignments && Pointers == Other.Pointers;
458   // Note: getStringRepresentation() might differs, it is not canonicalized
459   return Ret;
460 }
461 
462 DataLayout::AlignmentsTy::iterator
463 DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType,
464                                     uint32_t BitWidth) {
465   auto Pair = std::make_pair((unsigned)AlignType, BitWidth);
466   return partition_point(Alignments, [=](const LayoutAlignElem &E) {
467     return std::make_pair(E.AlignType, E.TypeBitWidth) < Pair;
468   });
469 }
470 
471 void
472 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
473                          unsigned pref_align, uint32_t bit_width) {
474   if (!isUInt<24>(bit_width))
475     report_fatal_error("Invalid bit width, must be a 24bit integer");
476   if (!isUInt<16>(abi_align))
477     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
478   if (!isUInt<16>(pref_align))
479     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
480   if (abi_align != 0 && !isPowerOf2_64(abi_align))
481     report_fatal_error("Invalid ABI alignment, must be a power of 2");
482   if (pref_align != 0 && !isPowerOf2_64(pref_align))
483     report_fatal_error("Invalid preferred alignment, must be a power of 2");
484 
485   if (pref_align < abi_align)
486     report_fatal_error(
487         "Preferred alignment cannot be less than the ABI alignment");
488 
489   AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width);
490   if (I != Alignments.end() &&
491       I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) {
492     // Update the abi, preferred alignments.
493     I->ABIAlign = abi_align;
494     I->PrefAlign = pref_align;
495   } else {
496     // Insert before I to keep the vector sorted.
497     Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
498                                               pref_align, bit_width));
499   }
500 }
501 
502 DataLayout::PointersTy::iterator
503 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
504   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
505                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
506     return A.AddressSpace < AddressSpace;
507   });
508 }
509 
510 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
511                                      unsigned PrefAlign, uint32_t TypeByteWidth,
512                                      uint32_t IndexWidth) {
513   if (PrefAlign < ABIAlign)
514     report_fatal_error(
515         "Preferred alignment cannot be less than the ABI alignment");
516 
517   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
518   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
519     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
520                                              TypeByteWidth, IndexWidth));
521   } else {
522     I->ABIAlign = ABIAlign;
523     I->PrefAlign = PrefAlign;
524     I->TypeByteWidth = TypeByteWidth;
525     I->IndexWidth = IndexWidth;
526   }
527 }
528 
529 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
530 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
531 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
532                                       uint32_t BitWidth, bool ABIInfo,
533                                       Type *Ty) const {
534   AlignmentsTy::const_iterator I = findAlignmentLowerBound(AlignType, BitWidth);
535   // See if we found an exact match. Of if we are looking for an integer type,
536   // but don't have an exact match take the next largest integer. This is where
537   // the lower_bound will point to when it fails an exact match.
538   if (I != Alignments.end() && I->AlignType == (unsigned)AlignType &&
539       (I->TypeBitWidth == BitWidth || AlignType == INTEGER_ALIGN))
540     return ABIInfo ? I->ABIAlign : I->PrefAlign;
541 
542   if (AlignType == INTEGER_ALIGN) {
543     // If we didn't have a larger value try the largest value we have.
544     if (I != Alignments.begin()) {
545       --I; // Go to the previous entry and see if its an integer.
546       if (I->AlignType == INTEGER_ALIGN)
547         return ABIInfo ? I->ABIAlign : I->PrefAlign;
548     }
549   } else if (AlignType == VECTOR_ALIGN) {
550     // By default, use natural alignment for vector types. This is consistent
551     // with what clang and llvm-gcc do.
552     unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
553     Align *= cast<VectorType>(Ty)->getNumElements();
554     Align = PowerOf2Ceil(Align);
555     return Align;
556    }
557 
558   // If we still couldn't find a reasonable default alignment, fall back
559   // to a simple heuristic that the alignment is the first power of two
560   // greater-or-equal to the store size of the type.  This is a reasonable
561   // approximation of reality, and if the user wanted something less
562   // less conservative, they should have specified it explicitly in the data
563   // layout.
564   unsigned Align = getTypeStoreSize(Ty);
565   Align = PowerOf2Ceil(Align);
566   return Align;
567 }
568 
569 namespace {
570 
571 class StructLayoutMap {
572   using LayoutInfoTy = DenseMap<StructType*, StructLayout*>;
573   LayoutInfoTy LayoutInfo;
574 
575 public:
576   ~StructLayoutMap() {
577     // Remove any layouts.
578     for (const auto &I : LayoutInfo) {
579       StructLayout *Value = I.second;
580       Value->~StructLayout();
581       free(Value);
582     }
583   }
584 
585   StructLayout *&operator[](StructType *STy) {
586     return LayoutInfo[STy];
587   }
588 };
589 
590 } // end anonymous namespace
591 
592 void DataLayout::clear() {
593   LegalIntWidths.clear();
594   Alignments.clear();
595   Pointers.clear();
596   delete static_cast<StructLayoutMap *>(LayoutMap);
597   LayoutMap = nullptr;
598 }
599 
600 DataLayout::~DataLayout() {
601   clear();
602 }
603 
604 const StructLayout *DataLayout::getStructLayout(StructType *Ty) const {
605   if (!LayoutMap)
606     LayoutMap = new StructLayoutMap();
607 
608   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
609   StructLayout *&SL = (*STM)[Ty];
610   if (SL) return SL;
611 
612   // Otherwise, create the struct layout.  Because it is variable length, we
613   // malloc it, then use placement new.
614   int NumElts = Ty->getNumElements();
615   StructLayout *L = (StructLayout *)
616       safe_malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
617 
618   // Set SL before calling StructLayout's ctor.  The ctor could cause other
619   // entries to be added to TheMap, invalidating our reference.
620   SL = L;
621 
622   new (L) StructLayout(Ty, *this);
623 
624   return L;
625 }
626 
627 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
628   PointersTy::const_iterator I = findPointerLowerBound(AS);
629   if (I == Pointers.end() || I->AddressSpace != AS) {
630     I = findPointerLowerBound(0);
631     assert(I->AddressSpace == 0);
632   }
633   return I->ABIAlign;
634 }
635 
636 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
637   PointersTy::const_iterator I = findPointerLowerBound(AS);
638   if (I == Pointers.end() || I->AddressSpace != AS) {
639     I = findPointerLowerBound(0);
640     assert(I->AddressSpace == 0);
641   }
642   return I->PrefAlign;
643 }
644 
645 unsigned DataLayout::getPointerSize(unsigned AS) const {
646   PointersTy::const_iterator I = findPointerLowerBound(AS);
647   if (I == Pointers.end() || I->AddressSpace != AS) {
648     I = findPointerLowerBound(0);
649     assert(I->AddressSpace == 0);
650   }
651   return I->TypeByteWidth;
652 }
653 
654 unsigned DataLayout::getMaxPointerSize() const {
655   unsigned MaxPointerSize = 0;
656   for (auto &P : Pointers)
657     MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth);
658 
659   return MaxPointerSize;
660 }
661 
662 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
663   assert(Ty->isPtrOrPtrVectorTy() &&
664          "This should only be called with a pointer or pointer vector type");
665   Ty = Ty->getScalarType();
666   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
667 }
668 
669 unsigned DataLayout::getIndexSize(unsigned AS) const {
670   PointersTy::const_iterator I = findPointerLowerBound(AS);
671   if (I == Pointers.end() || I->AddressSpace != AS) {
672     I = findPointerLowerBound(0);
673     assert(I->AddressSpace == 0);
674   }
675   return I->IndexWidth;
676 }
677 
678 unsigned DataLayout::getIndexTypeSizeInBits(Type *Ty) const {
679   assert(Ty->isPtrOrPtrVectorTy() &&
680          "This should only be called with a pointer or pointer vector type");
681   Ty = Ty->getScalarType();
682   return getIndexSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
683 }
684 
685 /*!
686   \param abi_or_pref Flag that determines which alignment is returned. true
687   returns the ABI alignment, false returns the preferred alignment.
688   \param Ty The underlying type for which alignment is determined.
689 
690   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
691   == false) for the requested type \a Ty.
692  */
693 unsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const {
694   AlignTypeEnum AlignType;
695 
696   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
697   switch (Ty->getTypeID()) {
698   // Early escape for the non-numeric types.
699   case Type::LabelTyID:
700     return (abi_or_pref
701             ? getPointerABIAlignment(0)
702             : getPointerPrefAlignment(0));
703   case Type::PointerTyID: {
704     unsigned AS = cast<PointerType>(Ty)->getAddressSpace();
705     return (abi_or_pref
706             ? getPointerABIAlignment(AS)
707             : getPointerPrefAlignment(AS));
708     }
709   case Type::ArrayTyID:
710     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
711 
712   case Type::StructTyID: {
713     // Packed structure types always have an ABI alignment of one.
714     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
715       return 1;
716 
717     // Get the layout annotation... which is lazily created on demand.
718     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
719     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
720     return std::max(Align, Layout->getAlignment());
721   }
722   case Type::IntegerTyID:
723     AlignType = INTEGER_ALIGN;
724     break;
725   case Type::HalfTyID:
726   case Type::FloatTyID:
727   case Type::DoubleTyID:
728   // PPC_FP128TyID and FP128TyID have different data contents, but the
729   // same size and alignment, so they look the same here.
730   case Type::PPC_FP128TyID:
731   case Type::FP128TyID:
732   case Type::X86_FP80TyID:
733     AlignType = FLOAT_ALIGN;
734     break;
735   case Type::X86_MMXTyID:
736   case Type::VectorTyID:
737     AlignType = VECTOR_ALIGN;
738     break;
739   default:
740     llvm_unreachable("Bad type for getAlignment!!!");
741   }
742 
743   return getAlignmentInfo(AlignType, getTypeSizeInBits(Ty), abi_or_pref, Ty);
744 }
745 
746 unsigned DataLayout::getABITypeAlignment(Type *Ty) const {
747   return getAlignment(Ty, true);
748 }
749 
750 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
751 /// an integer type of the specified bitwidth.
752 unsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const {
753   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr);
754 }
755 
756 unsigned DataLayout::getPrefTypeAlignment(Type *Ty) const {
757   return getAlignment(Ty, false);
758 }
759 
760 unsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const {
761   unsigned Align = getPrefTypeAlignment(Ty);
762   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
763   return Log2_32(Align);
764 }
765 
766 IntegerType *DataLayout::getIntPtrType(LLVMContext &C,
767                                        unsigned AddressSpace) const {
768   return IntegerType::get(C, getIndexSizeInBits(AddressSpace));
769 }
770 
771 Type *DataLayout::getIntPtrType(Type *Ty) const {
772   assert(Ty->isPtrOrPtrVectorTy() &&
773          "Expected a pointer or pointer vector type.");
774   unsigned NumBits = getIndexTypeSizeInBits(Ty);
775   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
776   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
777     return VectorType::get(IntTy, VecTy->getNumElements());
778   return IntTy;
779 }
780 
781 Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
782   for (unsigned LegalIntWidth : LegalIntWidths)
783     if (Width <= LegalIntWidth)
784       return Type::getIntNTy(C, LegalIntWidth);
785   return nullptr;
786 }
787 
788 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
789   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
790   return Max != LegalIntWidths.end() ? *Max : 0;
791 }
792 
793 Type *DataLayout::getIndexType(Type *Ty) const {
794   assert(Ty->isPtrOrPtrVectorTy() &&
795          "Expected a pointer or pointer vector type.");
796   unsigned NumBits = getIndexTypeSizeInBits(Ty);
797   IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
798   if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
799     return VectorType::get(IntTy, VecTy->getNumElements());
800   return IntTy;
801 }
802 
803 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
804                                            ArrayRef<Value *> Indices) const {
805   int64_t Result = 0;
806 
807   generic_gep_type_iterator<Value* const*>
808     GTI = gep_type_begin(ElemTy, Indices),
809     GTE = gep_type_end(ElemTy, Indices);
810   for (; GTI != GTE; ++GTI) {
811     Value *Idx = GTI.getOperand();
812     if (StructType *STy = GTI.getStructTypeOrNull()) {
813       assert(Idx->getType()->isIntegerTy(32) && "Illegal struct idx");
814       unsigned FieldNo = cast<ConstantInt>(Idx)->getZExtValue();
815 
816       // Get structure layout information...
817       const StructLayout *Layout = getStructLayout(STy);
818 
819       // Add in the offset, as calculated by the structure layout info...
820       Result += Layout->getElementOffset(FieldNo);
821     } else {
822       // Get the array index and the size of each array element.
823       if (int64_t arrayIdx = cast<ConstantInt>(Idx)->getSExtValue())
824         Result += arrayIdx * getTypeAllocSize(GTI.getIndexedType());
825     }
826   }
827 
828   return Result;
829 }
830 
831 /// getPreferredAlignment - Return the preferred alignment of the specified
832 /// global.  This includes an explicitly requested alignment (if the global
833 /// has one).
834 unsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const {
835   unsigned GVAlignment = GV->getAlignment();
836   // If a section is specified, always precisely honor explicit alignment,
837   // so we don't insert padding into a section we don't control.
838   if (GVAlignment && GV->hasSection())
839     return GVAlignment;
840 
841   // If no explicit alignment is specified, compute the alignment based on
842   // the IR type. If an alignment is specified, increase it to match the ABI
843   // alignment of the IR type.
844   //
845   // FIXME: Not sure it makes sense to use the alignment of the type if
846   // there's already an explicit alignment specification.
847   Type *ElemType = GV->getValueType();
848   unsigned Alignment = getPrefTypeAlignment(ElemType);
849   if (GVAlignment >= Alignment) {
850     Alignment = GVAlignment;
851   } else if (GVAlignment != 0) {
852     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
853   }
854 
855   // If no explicit alignment is specified, and the global is large, increase
856   // the alignment to 16.
857   // FIXME: Why 16, specifically?
858   if (GV->hasInitializer() && GVAlignment == 0) {
859     if (Alignment < 16) {
860       // If the global is not external, see if it is large.  If so, give it a
861       // larger alignment.
862       if (getTypeSizeInBits(ElemType) > 128)
863         Alignment = 16;    // 16-byte alignment.
864     }
865   }
866   return Alignment;
867 }
868 
869 /// getPreferredAlignmentLog - Return the preferred alignment of the
870 /// specified global, returned in log form.  This includes an explicitly
871 /// requested alignment (if the global has one).
872 unsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const {
873   return Log2_32(getPreferredAlignment(GV));
874 }
875