Convert gep_type_begin and gep_type_end to use ArrayRef.
[oota-llvm.git] / lib / Target / TargetData.cpp
1 //===-- TargetData.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 target 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/Target/TargetData.h"
20 #include "llvm/Constants.h"
21 #include "llvm/DerivedTypes.h"
22 #include "llvm/Module.h"
23 #include "llvm/Support/GetElementPtrTypeIterator.h"
24 #include "llvm/Support/MathExtras.h"
25 #include "llvm/Support/ManagedStatic.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Support/Mutex.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include <algorithm>
31 #include <cstdlib>
32 using namespace llvm;
33
34 // Handle the Pass registration stuff necessary to use TargetData's.
35
36 // Register the default SparcV9 implementation...
37 INITIALIZE_PASS(TargetData, "targetdata", "Target Data Layout", false, true)
38 char TargetData::ID = 0;
39
40 //===----------------------------------------------------------------------===//
41 // Support for StructLayout
42 //===----------------------------------------------------------------------===//
43
44 StructLayout::StructLayout(StructType *ST, const TargetData &TD) {
45   assert(!ST->isOpaque() && "Cannot get layout of opaque structs");
46   StructAlignment = 0;
47   StructSize = 0;
48   NumElements = ST->getNumElements();
49
50   // Loop over each of the elements, placing them in memory.
51   for (unsigned i = 0, e = NumElements; i != e; ++i) {
52     Type *Ty = ST->getElementType(i);
53     unsigned TyAlign = ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty);
54
55     // Add padding if necessary to align the data element properly.
56     if ((StructSize & (TyAlign-1)) != 0)
57       StructSize = TargetData::RoundUpAlignment(StructSize, TyAlign);
58
59     // Keep track of maximum alignment constraint.
60     StructAlignment = std::max(TyAlign, StructAlignment);
61
62     MemberOffsets[i] = StructSize;
63     StructSize += TD.getTypeAllocSize(Ty); // Consume space for this data item
64   }
65
66   // Empty structures have alignment of 1 byte.
67   if (StructAlignment == 0) StructAlignment = 1;
68
69   // Add padding to the end of the struct so that it could be put in an array
70   // and all array elements would be aligned correctly.
71   if ((StructSize & (StructAlignment-1)) != 0)
72     StructSize = TargetData::RoundUpAlignment(StructSize, StructAlignment);
73 }
74
75
76 /// getElementContainingOffset - Given a valid offset into the structure,
77 /// return the structure index that contains it.
78 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
79   const uint64_t *SI =
80     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
81   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
82   --SI;
83   assert(*SI <= Offset && "upper_bound didn't work");
84   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
85          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
86          "Upper bound didn't work!");
87
88   // Multiple fields can have the same offset if any of them are zero sized.
89   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
90   // at the i32 element, because it is the last element at that offset.  This is
91   // the right one to return, because anything after it will have a higher
92   // offset, implying that this element is non-empty.
93   return SI-&MemberOffsets[0];
94 }
95
96 //===----------------------------------------------------------------------===//
97 // TargetAlignElem, TargetAlign support
98 //===----------------------------------------------------------------------===//
99
100 TargetAlignElem
101 TargetAlignElem::get(AlignTypeEnum align_type, unsigned abi_align,
102                      unsigned pref_align, uint32_t bit_width) {
103   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
104   TargetAlignElem retval;
105   retval.AlignType = align_type;
106   retval.ABIAlign = abi_align;
107   retval.PrefAlign = pref_align;
108   retval.TypeBitWidth = bit_width;
109   return retval;
110 }
111
112 bool
113 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
114   return (AlignType == rhs.AlignType
115           && ABIAlign == rhs.ABIAlign
116           && PrefAlign == rhs.PrefAlign
117           && TypeBitWidth == rhs.TypeBitWidth);
118 }
119
120 const TargetAlignElem TargetData::InvalidAlignmentElem =
121                 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
122
123 //===----------------------------------------------------------------------===//
124 //                       TargetData Class Implementation
125 //===----------------------------------------------------------------------===//
126
127 /// getInt - Get an integer ignoring errors.
128 static unsigned getInt(StringRef R) {
129   unsigned Result = 0;
130   R.getAsInteger(10, Result);
131   return Result;
132 }
133
134 void TargetData::init(StringRef Desc) {
135   initializeTargetDataPass(*PassRegistry::getPassRegistry());
136   
137   LayoutMap = 0;
138   LittleEndian = false;
139   PointerMemSize = 8;
140   PointerABIAlign = 8;
141   PointerPrefAlign = PointerABIAlign;
142
143   // Default alignments
144   setAlignment(INTEGER_ALIGN,   1,  1, 1);   // i1
145   setAlignment(INTEGER_ALIGN,   1,  1, 8);   // i8
146   setAlignment(INTEGER_ALIGN,   2,  2, 16);  // i16
147   setAlignment(INTEGER_ALIGN,   4,  4, 32);  // i32
148   setAlignment(INTEGER_ALIGN,   4,  8, 64);  // i64
149   setAlignment(FLOAT_ALIGN,     4,  4, 32);  // float
150   setAlignment(FLOAT_ALIGN,     8,  8, 64);  // double
151   setAlignment(VECTOR_ALIGN,    8,  8, 64);  // v2i32, v1i64, ...
152   setAlignment(VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
153   setAlignment(AGGREGATE_ALIGN, 0,  8,  0);  // struct
154
155   while (!Desc.empty()) {
156     std::pair<StringRef, StringRef> Split = Desc.split('-');
157     StringRef Token = Split.first;
158     Desc = Split.second;
159
160     if (Token.empty())
161       continue;
162
163     Split = Token.split(':');
164     StringRef Specifier = Split.first;
165     Token = Split.second;
166
167     assert(!Specifier.empty() && "Can't be empty here");
168
169     switch (Specifier[0]) {
170     case 'E':
171       LittleEndian = false;
172       break;
173     case 'e':
174       LittleEndian = true;
175       break;
176     case 'p':
177       Split = Token.split(':');
178       PointerMemSize = getInt(Split.first) / 8;
179       Split = Split.second.split(':');
180       PointerABIAlign = getInt(Split.first) / 8;
181       Split = Split.second.split(':');
182       PointerPrefAlign = getInt(Split.first) / 8;
183       if (PointerPrefAlign == 0)
184         PointerPrefAlign = PointerABIAlign;
185       break;
186     case 'i':
187     case 'v':
188     case 'f':
189     case 'a':
190     case 's': {
191       AlignTypeEnum AlignType;
192       switch (Specifier[0]) {
193       default:
194       case 'i': AlignType = INTEGER_ALIGN; break;
195       case 'v': AlignType = VECTOR_ALIGN; break;
196       case 'f': AlignType = FLOAT_ALIGN; break;
197       case 'a': AlignType = AGGREGATE_ALIGN; break;
198       case 's': AlignType = STACK_ALIGN; break;
199       }
200       unsigned Size = getInt(Specifier.substr(1));
201       Split = Token.split(':');
202       unsigned ABIAlign = getInt(Split.first) / 8;
203
204       Split = Split.second.split(':');
205       unsigned PrefAlign = getInt(Split.first) / 8;
206       if (PrefAlign == 0)
207         PrefAlign = ABIAlign;
208       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
209       break;
210     }
211     case 'n':  // Native integer types.
212       Specifier = Specifier.substr(1);
213       do {
214         if (unsigned Width = getInt(Specifier))
215           LegalIntWidths.push_back(Width);
216         Split = Token.split(':');
217         Specifier = Split.first;
218         Token = Split.second;
219       } while (!Specifier.empty() || !Token.empty());
220       break;
221
222     default:
223       break;
224     }
225   }
226 }
227
228 /// Default ctor.
229 ///
230 /// @note This has to exist, because this is a pass, but it should never be
231 /// used.
232 TargetData::TargetData() : ImmutablePass(ID) {
233   report_fatal_error("Bad TargetData ctor used.  "
234                     "Tool did not specify a TargetData to use?");
235 }
236
237 TargetData::TargetData(const Module *M)
238   : ImmutablePass(ID) {
239   init(M->getDataLayout());
240 }
241
242 void
243 TargetData::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
244                          unsigned pref_align, uint32_t bit_width) {
245   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
246   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
247     if (Alignments[i].AlignType == align_type &&
248         Alignments[i].TypeBitWidth == bit_width) {
249       // Update the abi, preferred alignments.
250       Alignments[i].ABIAlign = abi_align;
251       Alignments[i].PrefAlign = pref_align;
252       return;
253     }
254   }
255
256   Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
257                                             pref_align, bit_width));
258 }
259
260 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
261 /// preferred if ABIInfo = false) the target wants for the specified datatype.
262 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
263                                       uint32_t BitWidth, bool ABIInfo,
264                                       Type *Ty) const {
265   // Check to see if we have an exact match and remember the best match we see.
266   int BestMatchIdx = -1;
267   int LargestInt = -1;
268   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
269     if (Alignments[i].AlignType == AlignType &&
270         Alignments[i].TypeBitWidth == BitWidth)
271       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
272
273     // The best match so far depends on what we're looking for.
274      if (AlignType == INTEGER_ALIGN &&
275          Alignments[i].AlignType == INTEGER_ALIGN) {
276       // The "best match" for integers is the smallest size that is larger than
277       // the BitWidth requested.
278       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
279            Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
280         BestMatchIdx = i;
281       // However, if there isn't one that's larger, then we must use the
282       // largest one we have (see below)
283       if (LargestInt == -1 ||
284           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
285         LargestInt = i;
286     }
287   }
288
289   // Okay, we didn't find an exact solution.  Fall back here depending on what
290   // is being looked for.
291   if (BestMatchIdx == -1) {
292     // If we didn't find an integer alignment, fall back on most conservative.
293     if (AlignType == INTEGER_ALIGN) {
294       BestMatchIdx = LargestInt;
295     } else {
296       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
297
298       // By default, use natural alignment for vector types. This is consistent
299       // with what clang and llvm-gcc do.
300       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
301       Align *= cast<VectorType>(Ty)->getNumElements();
302       // If the alignment is not a power of 2, round up to the next power of 2.
303       // This happens for non-power-of-2 length vectors.
304       if (Align & (Align-1))
305         Align = llvm::NextPowerOf2(Align);
306       return Align;
307     }
308   }
309
310   // Since we got a "best match" index, just return it.
311   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
312                  : Alignments[BestMatchIdx].PrefAlign;
313 }
314
315 namespace {
316
317 class StructLayoutMap {
318   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
319   LayoutInfoTy LayoutInfo;
320
321 public:
322   virtual ~StructLayoutMap() {
323     // Remove any layouts.
324     for (LayoutInfoTy::iterator I = LayoutInfo.begin(), E = LayoutInfo.end();
325          I != E; ++I) {
326       StructLayout *Value = I->second;
327       Value->~StructLayout();
328       free(Value);
329     }
330   }
331
332   StructLayout *&operator[](StructType *STy) {
333     return LayoutInfo[STy];
334   }
335
336   // for debugging...
337   virtual void dump() const {}
338 };
339
340 } // end anonymous namespace
341
342 TargetData::~TargetData() {
343   delete static_cast<StructLayoutMap*>(LayoutMap);
344 }
345
346 const StructLayout *TargetData::getStructLayout(StructType *Ty) const {
347   if (!LayoutMap)
348     LayoutMap = new StructLayoutMap();
349
350   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
351   StructLayout *&SL = (*STM)[Ty];
352   if (SL) return SL;
353
354   // Otherwise, create the struct layout.  Because it is variable length, we
355   // malloc it, then use placement new.
356   int NumElts = Ty->getNumElements();
357   StructLayout *L =
358     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
359
360   // Set SL before calling StructLayout's ctor.  The ctor could cause other
361   // entries to be added to TheMap, invalidating our reference.
362   SL = L;
363
364   new (L) StructLayout(Ty, *this);
365
366   return L;
367 }
368
369 std::string TargetData::getStringRepresentation() const {
370   std::string Result;
371   raw_string_ostream OS(Result);
372
373   OS << (LittleEndian ? "e" : "E")
374      << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
375      << ':' << PointerPrefAlign*8;
376   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
377     const TargetAlignElem &AI = Alignments[i];
378     OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
379        << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
380   }
381
382   if (!LegalIntWidths.empty()) {
383     OS << "-n" << (unsigned)LegalIntWidths[0];
384
385     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
386       OS << ':' << (unsigned)LegalIntWidths[i];
387   }
388   return OS.str();
389 }
390
391
392 uint64_t TargetData::getTypeSizeInBits(Type *Ty) const {
393   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
394   switch (Ty->getTypeID()) {
395   case Type::LabelTyID:
396   case Type::PointerTyID:
397     return getPointerSizeInBits();
398   case Type::ArrayTyID: {
399     ArrayType *ATy = cast<ArrayType>(Ty);
400     return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
401   }
402   case Type::StructTyID:
403     // Get the layout annotation... which is lazily created on demand.
404     return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
405   case Type::IntegerTyID:
406     return cast<IntegerType>(Ty)->getBitWidth();
407   case Type::VoidTyID:
408     return 8;
409   case Type::FloatTyID:
410     return 32;
411   case Type::DoubleTyID:
412   case Type::X86_MMXTyID:
413     return 64;
414   case Type::PPC_FP128TyID:
415   case Type::FP128TyID:
416     return 128;
417   // In memory objects this is always aligned to a higher boundary, but
418   // only 80 bits contain information.
419   case Type::X86_FP80TyID:
420     return 80;
421   case Type::VectorTyID:
422     return cast<VectorType>(Ty)->getBitWidth();
423   default:
424     llvm_unreachable("TargetData::getTypeSizeInBits(): Unsupported type");
425     break;
426   }
427   return 0;
428 }
429
430 /*!
431   \param abi_or_pref Flag that determines which alignment is returned. true
432   returns the ABI alignment, false returns the preferred alignment.
433   \param Ty The underlying type for which alignment is determined.
434
435   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
436   == false) for the requested type \a Ty.
437  */
438 unsigned TargetData::getAlignment(Type *Ty, bool abi_or_pref) const {
439   int AlignType = -1;
440
441   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
442   switch (Ty->getTypeID()) {
443   // Early escape for the non-numeric types.
444   case Type::LabelTyID:
445   case Type::PointerTyID:
446     return (abi_or_pref
447             ? getPointerABIAlignment()
448             : getPointerPrefAlignment());
449   case Type::ArrayTyID:
450     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
451
452   case Type::StructTyID: {
453     // Packed structure types always have an ABI alignment of one.
454     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
455       return 1;
456
457     // Get the layout annotation... which is lazily created on demand.
458     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
459     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
460     return std::max(Align, Layout->getAlignment());
461   }
462   case Type::IntegerTyID:
463   case Type::VoidTyID:
464     AlignType = INTEGER_ALIGN;
465     break;
466   case Type::FloatTyID:
467   case Type::DoubleTyID:
468   // PPC_FP128TyID and FP128TyID have different data contents, but the
469   // same size and alignment, so they look the same here.
470   case Type::PPC_FP128TyID:
471   case Type::FP128TyID:
472   case Type::X86_FP80TyID:
473     AlignType = FLOAT_ALIGN;
474     break;
475   case Type::X86_MMXTyID:
476   case Type::VectorTyID:
477     AlignType = VECTOR_ALIGN;
478     break;
479   default:
480     llvm_unreachable("Bad type for getAlignment!!!");
481     break;
482   }
483
484   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
485                           abi_or_pref, Ty);
486 }
487
488 unsigned TargetData::getABITypeAlignment(Type *Ty) const {
489   return getAlignment(Ty, true);
490 }
491
492 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
493 /// an integer type of the specified bitwidth.
494 unsigned TargetData::getABIIntegerTypeAlignment(unsigned BitWidth) const {
495   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
496 }
497
498
499 unsigned TargetData::getCallFrameTypeAlignment(Type *Ty) const {
500   for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
501     if (Alignments[i].AlignType == STACK_ALIGN)
502       return Alignments[i].ABIAlign;
503
504   return getABITypeAlignment(Ty);
505 }
506
507 unsigned TargetData::getPrefTypeAlignment(Type *Ty) const {
508   return getAlignment(Ty, false);
509 }
510
511 unsigned TargetData::getPreferredTypeAlignmentShift(Type *Ty) const {
512   unsigned Align = getPrefTypeAlignment(Ty);
513   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
514   return Log2_32(Align);
515 }
516
517 /// getIntPtrType - Return an unsigned integer type that is the same size or
518 /// greater to the host pointer size.
519 IntegerType *TargetData::getIntPtrType(LLVMContext &C) const {
520   return IntegerType::get(C, getPointerSizeInBits());
521 }
522
523
524 uint64_t TargetData::getIndexedOffset(Type *ptrTy,
525                                       ArrayRef<Value *> Indices) const {
526   Type *Ty = ptrTy;
527   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
528   uint64_t Result = 0;
529
530   generic_gep_type_iterator<Value* const*>
531     TI = gep_type_begin(ptrTy, Indices);
532   for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX;
533        ++CurIDX, ++TI) {
534     if (StructType *STy = dyn_cast<StructType>(*TI)) {
535       assert(Indices[CurIDX]->getType() ==
536              Type::getInt32Ty(ptrTy->getContext()) &&
537              "Illegal struct idx");
538       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
539
540       // Get structure layout information...
541       const StructLayout *Layout = getStructLayout(STy);
542
543       // Add in the offset, as calculated by the structure layout info...
544       Result += Layout->getElementOffset(FieldNo);
545
546       // Update Ty to refer to current element
547       Ty = STy->getElementType(FieldNo);
548     } else {
549       // Update Ty to refer to current element
550       Ty = cast<SequentialType>(Ty)->getElementType();
551
552       // Get the array index and the size of each array element.
553       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
554         Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty);
555     }
556   }
557
558   return Result;
559 }
560
561 /// getPreferredAlignment - Return the preferred alignment of the specified
562 /// global.  This includes an explicitly requested alignment (if the global
563 /// has one).
564 unsigned TargetData::getPreferredAlignment(const GlobalVariable *GV) const {
565   Type *ElemType = GV->getType()->getElementType();
566   unsigned Alignment = getPrefTypeAlignment(ElemType);
567   unsigned GVAlignment = GV->getAlignment();
568   if (GVAlignment >= Alignment) {
569     Alignment = GVAlignment;
570   } else if (GVAlignment != 0) {
571     Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType));
572   }
573
574   if (GV->hasInitializer() && GVAlignment == 0) {
575     if (Alignment < 16) {
576       // If the global is not external, see if it is large.  If so, give it a
577       // larger alignment.
578       if (getTypeSizeInBits(ElemType) > 128)
579         Alignment = 16;    // 16-byte alignment.
580     }
581   }
582   return Alignment;
583 }
584
585 /// getPreferredAlignmentLog - Return the preferred alignment of the
586 /// specified global, returned in log form.  This includes an explicitly
587 /// requested alignment (if the global has one).
588 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
589   return Log2_32(getPreferredAlignment(GV));
590 }