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