lib/Target/TargetData.cpp

   1 //===-- TargetData.cpp - Data size & alignment routines --------------------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/Module.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Support/GetElementPtrTypeIterator.h"
  24 #include "llvm/Support/MathExtras.h"
  25 #include "llvm/Support/ManagedStatic.h"
  26 #include "llvm/ADT/DenseMap.h"
  27 #include "llvm/ADT/StringExtras.h"
  28 #include <algorithm>
  29 #include <cstdlib>
  30 #include <sstream>
  31 using namespace llvm;
  32
  33 // Handle the Pass registration stuff necessary to use TargetData's.
  34 namespace {
  35   // Register the default SparcV9 implementation...
  36   RegisterPass<TargetData> X("targetdata", "Target Data Layout");
  37 }
  38
  39 //===----------------------------------------------------------------------===//
  40 // Support for StructLayout
  41 //===----------------------------------------------------------------------===//
  42
  43 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
  44   StructAlignment = 0;
  45   StructSize = 0;
  46   NumElements = ST->getNumElements();
  47
  48   // Loop over each of the elements, placing them in memory...
  49   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  50     const Type *Ty = ST->getElementType(i);
  51     unsigned TyAlign;
  52     uint64_t TySize;
  53     TyAlign = (ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty));
  54     TySize = TD.getTypeSize(Ty);
  55
  56     // Add padding if necessary to make the data element aligned properly...
  57     if (StructSize % TyAlign != 0)
  58       StructSize = (StructSize/TyAlign + 1) * TyAlign;   // Add padding...
  59
  60     // Keep track of maximum alignment constraint
  61     StructAlignment = std::max(TyAlign, StructAlignment);
  62
  63     MemberOffsets[i] = StructSize;
  64     StructSize += TySize;                 // Consume space for this data item
  65   }
  66
  67   // Empty structures have alignment of 1 byte.
  68   if (StructAlignment == 0) StructAlignment = 1;
  69
  70   // Add padding to the end of the struct so that it could be put in an array
  71   // and all array elements would be aligned correctly.
  72   if (StructSize % StructAlignment != 0)
  73     StructSize = (StructSize/StructAlignment + 1) * StructAlignment;
  74 }
  75
  76
  77 /// getElementContainingOffset - Given a valid offset into the structure,
  78 /// return the structure index that contains it.
  79 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  80   const uint64_t *SI =
  81     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  82   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  83   --SI;
  84   assert(*SI <= Offset && "upper_bound didn't work");
  85   assert((SI == &MemberOffsets[0] || *(SI-1) < Offset) &&
  86          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  87          "Upper bound didn't work!");
  88   return SI-&MemberOffsets[0];
  89 }
  90
  91 //===----------------------------------------------------------------------===//
  92 // TargetAlignElem, TargetAlign support
  93 //===----------------------------------------------------------------------===//
  94
  95 TargetAlignElem
  96 TargetAlignElem::get(AlignTypeEnum align_type, unsigned char abi_align,
  97                      unsigned char pref_align, short bit_width) {
  98   TargetAlignElem retval;
  99   retval.AlignType = align_type;
 100   retval.ABIAlign = abi_align;
 101   retval.PrefAlign = pref_align;
 102   retval.TypeBitWidth = bit_width;
 103   return retval;
 104 }
 105
 106 bool
 107 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
 108   return (AlignType == rhs.AlignType
 109           && ABIAlign == rhs.ABIAlign
 110           && PrefAlign == rhs.PrefAlign
 111           && TypeBitWidth == rhs.TypeBitWidth);
 112 }
 113
 114 std::ostream &
 115 TargetAlignElem::dump(std::ostream &os) const {
 116   return os << AlignType
 117             << TypeBitWidth
 118             << ":" << (int) (ABIAlign * 8)
 119             << ":" << (int) (PrefAlign * 8);
 120 }
 121
 122 const TargetAlignElem TargetData::InvalidAlignmentElem =
 123                 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
 124
 125 //===----------------------------------------------------------------------===//
 126 //                       TargetData Class Implementation
 127 //===----------------------------------------------------------------------===//
 128
 129 /*!
 130  A TargetDescription string consists of a sequence of hyphen-delimited
 131  specifiers for target endianness, pointer size and alignments, and various
 132  primitive type sizes and alignments. A typical string looks something like:
 133  <br><br>
 134  "E-p:32:32:32-i1:8:8-i8:8:8-i32:32:32-i64:32:64-f32:32:32-f64:32:64"
 135  <br><br>
 136  (note: this string is not fully specified and is only an example.)
 137  \p
 138  Alignments come in two flavors: ABI and preferred. ABI alignment (abi_align,
 139  below) dictates how a type will be aligned within an aggregate and when used
 140  as an argument.  Preferred alignment (pref_align, below) determines a type's
 141  alignment when emitted as a global.
 142  \p
 143  Specifier string details:
 144  <br><br>
 145  <i>[E|e]</i>: Endianness. "E" specifies a big-endian target data model, "e"
 146  specifies a little-endian target data model.
 147  <br><br>
 148  <i>p:<size>:<abi_align>:<pref_align></i>: Pointer size, ABI and preferred
 149  alignment.
 150  <br><br>
 151  <i><type><size>:<abi_align>:<pref_align></i>: Numeric type alignment. Type is
 152  one of <i>i|f|v|a</i>, corresponding to integer, floating point, vector (aka
 153  packed) or aggregate.  Size indicates the size, e.g., 32 or 64 bits.
 154  \p
 155  The default string, fully specified is:
 156  <br><br>
 157  "E-p:64:64:64-a0:0:0-f32:32:32-f64:0:64"
 158  "-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:0:64"
 159  "-v64:64:64-v128:128:128"
 160  <br><br>
 161  Note that in the case of aggregates, 0 is the default ABI and preferred
 162  alignment. This is a special case, where the aggregate's computed worst-case
 163  alignment will be used.
 164  */
 165 void TargetData::init(const std::string &TargetDescription) {
 166   std::string temp = TargetDescription;
 167
 168   LittleEndian = false;
 169   PointerMemSize = 8;
 170   PointerABIAlign   = 8;
 171   PointerPrefAlign = PointerABIAlign;
 172
 173   // Default alignments
 174   setAlignment(INTEGER_ALIGN,   1,  1, 1);   // Bool
 175   setAlignment(INTEGER_ALIGN,   1,  1, 8);   // Byte
 176   setAlignment(INTEGER_ALIGN,   2,  2, 16);  // short
 177   setAlignment(INTEGER_ALIGN,   4,  4, 32);  // int
 178   setAlignment(INTEGER_ALIGN,   4,  8, 64);  // long
 179   setAlignment(FLOAT_ALIGN,     4,  4, 32);  // float
 180   setAlignment(FLOAT_ALIGN,     8,  8, 64);  // double
 181   setAlignment(VECTOR_ALIGN,    8,  8, 64);  // v2i32
 182   setAlignment(VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
 183   setAlignment(AGGREGATE_ALIGN, 0,  8,  0);  // struct, union, class, ...
 184
 185   while (!temp.empty()) {
 186     std::string token = getToken(temp, "-");
 187
 188     std::string arg0 = getToken(token, ":");
 189     const char *p = arg0.c_str();
 190     AlignTypeEnum align_type;
 191     short size;
 192     unsigned char abi_align;
 193     unsigned char pref_align;
 194
 195     switch(*p) {
 196     case 'E':
 197       LittleEndian = false;
 198       break;
 199     case 'e':
 200       LittleEndian = true;
 201       break;
 202     case 'p':
 203       PointerMemSize = atoi(getToken(token,":").c_str()) / 8;
 204       PointerABIAlign = atoi(getToken(token,":").c_str()) / 8;
 205       PointerPrefAlign = atoi(getToken(token,":").c_str()) / 8;
 206       if (PointerPrefAlign == 0)
 207         PointerPrefAlign = PointerABIAlign;
 208       break;
 209     case 'i':
 210     case 'v':
 211     case 'f':
 212     case 'a': {
 213       align_type = (*p == 'i' ? INTEGER_ALIGN :
 214                     (*p == 'f' ? FLOAT_ALIGN :
 215                      (*p == 'v' ? VECTOR_ALIGN : AGGREGATE_ALIGN)));
 216       size = (short) atoi(++p);
 217       abi_align = atoi(getToken(token, ":").c_str()) / 8;
 218       pref_align = atoi(getToken(token, ":").c_str()) / 8;
 219       if (pref_align == 0)
 220         pref_align = abi_align;
 221       setAlignment(align_type, abi_align, pref_align, size);
 222       break;
 223     }
 224     default:
 225       break;
 226     }
 227   }
 228 }
 229
 230 TargetData::TargetData(const Module *M) {
 231   init(M->getDataLayout());
 232 }
 233
 234 void
 235 TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
 236                          unsigned char pref_align, short bit_width) {
 237   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 238     if (Alignments[i].AlignType == align_type &&
 239         Alignments[i].TypeBitWidth == bit_width) {
 240       // Update the abi, preferred alignments.
 241       Alignments[i].ABIAlign = abi_align;
 242       Alignments[i].PrefAlign = pref_align;
 243       return;
 244     }
 245   }
 246
 247   Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
 248                                             pref_align, bit_width));
 249 }
 250
 251 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 252 /// preferred if ABIInfo = false) the target wants for the specified datatype.
 253 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType, short BitWidth,
 254                                       bool ABIInfo) const {
 255   // Check to see if we have an exact match and remember the best match we see.
 256   int BestMatchIdx = -1;
 257   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 258     if (Alignments[i].AlignType == AlignType &&
 259         Alignments[i].TypeBitWidth == BitWidth)
 260       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 261
 262     // The best match so far depends on what we're looking for.
 263     if (AlignType == VECTOR_ALIGN) {
 264       // If this is a specification for a smaller vector type, we will fall back
 265       // to it.  This happens because <128 x double> can be implemented in terms
 266       // of 64 <2 x double>.
 267       if (Alignments[i].AlignType == VECTOR_ALIGN &&
 268           Alignments[i].TypeBitWidth < BitWidth) {
 269         // Verify that we pick the biggest of the fallbacks.
 270         if (BestMatchIdx == -1 ||
 271             Alignments[BestMatchIdx].TypeBitWidth < BitWidth)
 272           BestMatchIdx = i;
 273       }
 274     }
 275
 276     // FIXME: handle things like i37.
 277   }
 278
 279   // Okay, we didn't find an exact solution.  Fall back here depending on what
 280   // is being looked for.
 281   assert(BestMatchIdx != -1 && "Didn't find alignment info for this datatype!");
 282   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 283                  : Alignments[BestMatchIdx].PrefAlign;
 284 }
 285
 286 /// LayoutInfo - The lazy cache of structure layout information maintained by
 287 /// TargetData.  Note that the struct types must have been free'd before
 288 /// llvm_shutdown is called (and thus this is deallocated) because all the
 289 /// targets with cached elements should have been destroyed.
 290 ///
 291 typedef std::pair<const TargetData*,const StructType*> LayoutKey;
 292
 293 struct DenseMapLayoutKeyInfo {
 294   static inline LayoutKey getEmptyKey() { return LayoutKey(0, 0); }
 295   static inline LayoutKey getTombstoneKey() {
 296     return LayoutKey((TargetData*)(intptr_t)-1, 0);
 297   }
 298   static unsigned getHashValue(const LayoutKey &Val) {
 299     return DenseMapKeyInfo<void*>::getHashValue(Val.first) ^
 300            DenseMapKeyInfo<void*>::getHashValue(Val.second);
 301   }
 302   static bool isPod() { return true; }
 303 };
 304
 305 typedef DenseMap<LayoutKey, StructLayout*, DenseMapLayoutKeyInfo> LayoutInfoTy;
 306 static ManagedStatic<LayoutInfoTy> LayoutInfo;
 307
 308
 309 TargetData::~TargetData() {
 310   if (LayoutInfo.isConstructed()) {
 311     // Remove any layouts for this TD.
 312     LayoutInfoTy &TheMap = *LayoutInfo;
 313     for (LayoutInfoTy::iterator I = TheMap.begin(), E = TheMap.end();
 314          I != E; ) {
 315       if (I->first.first == this) {
 316         I->second->~StructLayout();
 317         free(I->second);
 318         TheMap.erase(I++);
 319       } else {
 320         ++I;
 321       }
 322     }
 323   }
 324 }
 325
 326 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
 327   LayoutInfoTy &TheMap = *LayoutInfo;
 328
 329   StructLayout *&SL = TheMap[LayoutKey(this, Ty)];
 330   if (SL) return SL;
 331
 332   // Otherwise, create the struct layout.  Because it is variable length, we
 333   // malloc it, then use placement new.
 334   unsigned NumElts = Ty->getNumElements();
 335   StructLayout *L =
 336     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1)*sizeof(uint64_t));
 337
 338   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 339   // entries to be added to TheMap, invalidating our reference.
 340   SL = L;
 341
 342   new (L) StructLayout(Ty, *this);
 343   return L;
 344 }
 345
 346 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
 347 /// objects.  If a TargetData object is alive when types are being refined and
 348 /// removed, this method must be called whenever a StructType is removed to
 349 /// avoid a dangling pointer in this cache.
 350 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
 351   if (!LayoutInfo.isConstructed()) return;  // No cache.
 352
 353   LayoutInfoTy::iterator I = LayoutInfo->find(LayoutKey(this, Ty));
 354   if (I != LayoutInfo->end()) {
 355     I->second->~StructLayout();
 356     free(I->second);
 357     LayoutInfo->erase(I);
 358   }
 359 }
 360
 361
 362 std::string TargetData::getStringRepresentation() const {
 363   std::string repr;
 364   repr.append(LittleEndian ? "e" : "E");
 365   repr.append("-p:").append(itostr((int64_t) (PointerMemSize * 8))).
 366       append(":").append(itostr((int64_t) (PointerABIAlign * 8))).
 367       append(":").append(itostr((int64_t) (PointerPrefAlign * 8)));
 368   for (align_const_iterator I = Alignments.begin();
 369        I != Alignments.end();
 370        ++I) {
 371     repr.append("-").append(1, (char) I->AlignType).
 372       append(utostr((int64_t) I->TypeBitWidth)).
 373       append(":").append(utostr((uint64_t) (I->ABIAlign * 8))).
 374       append(":").append(utostr((uint64_t) (I->PrefAlign * 8)));
 375   }
 376   return repr;
 377 }
 378
 379
 380 uint64_t TargetData::getTypeSize(const Type *Ty) const {
 381   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 382   switch (Ty->getTypeID()) {
 383   case Type::LabelTyID:
 384   case Type::PointerTyID:
 385     return getPointerSize();
 386   case Type::ArrayTyID: {
 387     const ArrayType *ATy = cast<ArrayType>(Ty);
 388     uint64_t Size;
 389     unsigned char Alignment;
 390     Size = getTypeSize(ATy->getElementType());
 391     Alignment = getABITypeAlignment(ATy->getElementType());
 392     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 393     return AlignedSize*ATy->getNumElements();
 394   }
 395   case Type::StructTyID: {
 396     // Get the layout annotation... which is lazily created on demand.
 397     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 398     return Layout->getSizeInBytes();
 399   }
 400   case Type::IntegerTyID: {
 401     unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
 402     if (BitWidth <= 8) {
 403       return 1;
 404     } else if (BitWidth <= 16) {
 405       return 2;
 406     } else if (BitWidth <= 32) {
 407       return 4;
 408     } else if (BitWidth <= 64) {
 409       return 8;
 410     } else
 411       assert(0 && "Integer types > 64 bits not supported.");
 412     break;
 413   }
 414   case Type::VoidTyID:
 415     return 1;
 416   case Type::FloatTyID:
 417     return 4;
 418   case Type::DoubleTyID:
 419     return 8;
 420   case Type::VectorTyID: {
 421     const VectorType *PTy = cast<VectorType>(Ty);
 422     return PTy->getBitWidth() / 8;
 423   }
 424   default:
 425     assert(0 && "TargetData::getTypeSize(): Unsupported type");
 426     break;
 427   }
 428   return 0;
 429 }
 430
 431 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
 432   if (Ty->isInteger())
 433     return cast<IntegerType>(Ty)->getBitWidth();
 434   else
 435     return getTypeSize(Ty) * 8;
 436 }
 437
 438
 439 /*!
 440   \param abi_or_pref Flag that determines which alignment is returned. true
 441   returns the ABI alignment, false returns the preferred alignment.
 442   \param Ty The underlying type for which alignment is determined.
 443
 444   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 445   == false) for the requested type \a Ty.
 446  */
 447 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
 448   int AlignType = -1;
 449
 450   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 451   switch (Ty->getTypeID()) {
 452   /* Early escape for the non-numeric types */
 453   case Type::LabelTyID:
 454   case Type::PointerTyID:
 455     return (abi_or_pref
 456             ? getPointerABIAlignment()
 457             : getPointerPrefAlignment());
 458   case Type::ArrayTyID:
 459     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 460
 461   case Type::StructTyID: {
 462     // Packed structure types always have an ABI alignment of one.
 463     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 464       return 1;
 465
 466     // Get the layout annotation... which is lazily created on demand.
 467     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 468     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref);
 469     return std::max(Align, (unsigned)Layout->getAlignment());
 470   }
 471   case Type::IntegerTyID:
 472   case Type::VoidTyID:
 473     AlignType = INTEGER_ALIGN;
 474     break;
 475   case Type::FloatTyID:
 476   case Type::DoubleTyID:
 477     AlignType = FLOAT_ALIGN;
 478     break;
 479   case Type::VectorTyID:
 480     AlignType = VECTOR_ALIGN;
 481     break;
 482   default:
 483     assert(0 && "Bad type for getAlignment!!!");
 484     break;
 485   }
 486
 487   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSize(Ty) * 8,
 488                           abi_or_pref);
 489 }
 490
 491 unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
 492   return getAlignment(Ty, true);
 493 }
 494
 495 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
 496   return getAlignment(Ty, false);
 497 }
 498
 499 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
 500   unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
 501   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 502   return Log2_32(Align);
 503 }
 504
 505 /// getIntPtrType - Return an unsigned integer type that is the same size or
 506 /// greater to the host pointer size.
 507 const Type *TargetData::getIntPtrType() const {
 508   switch (getPointerSize()) {
 509   default: assert(0 && "Unknown pointer size!");
 510   case 2: return Type::Int16Ty;
 511   case 4: return Type::Int32Ty;
 512   case 8: return Type::Int64Ty;
 513   }
 514 }
 515
 516
 517 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
 518                                       unsigned NumIndices) const {
 519   const Type *Ty = ptrTy;
 520   assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
 521   uint64_t Result = 0;
 522
 523   generic_gep_type_iterator<Value* const*>
 524     TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
 525   for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
 526     if (const StructType *STy = dyn_cast<StructType>(*TI)) {
 527       assert(Indices[CurIDX]->getType() == Type::Int32Ty &&"Illegal struct idx");
 528       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 529
 530       // Get structure layout information...
 531       const StructLayout *Layout = getStructLayout(STy);
 532
 533       // Add in the offset, as calculated by the structure layout info...
 534       Result += Layout->getElementOffset(FieldNo);
 535
 536       // Update Ty to refer to current element
 537       Ty = STy->getElementType(FieldNo);
 538     } else {
 539       // Update Ty to refer to current element
 540       Ty = cast<SequentialType>(Ty)->getElementType();
 541
 542       // Get the array index and the size of each array element.
 543       int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
 544       Result += arrayIdx * (int64_t)getTypeSize(Ty);
 545     }
 546   }
 547
 548   return Result;
 549 }
 550
 551 /// getPreferredAlignmentLog - Return the preferred alignment of the
 552 /// specified global, returned in log form.  This includes an explicitly
 553 /// requested alignment (if the global has one).
 554 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 555   const Type *ElemType = GV->getType()->getElementType();
 556   unsigned Alignment = getPreferredTypeAlignmentShift(ElemType);
 557   if (GV->getAlignment() > (1U << Alignment))
 558     Alignment = Log2_32(GV->getAlignment());
 559
 560   if (GV->hasInitializer()) {
 561     if (Alignment < 4) {
 562       // If the global is not external, see if it is large.  If so, give it a
 563       // larger alignment.
 564       if (getTypeSize(ElemType) > 128)
 565         Alignment = 4;    // 16-byte alignment.
 566     }
 567   }
 568   return Alignment;
 569 }