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 static inline void getTypeInfoABI(const Type *Ty, const TargetData *TD,
  40                                   uint64_t &Size, unsigned char &Alignment);
  41
  42 static inline void getTypeInfoPref(const Type *Ty, const TargetData *TD,
  43                                    uint64_t &Size, unsigned char &Alignment);
  44
  45 //===----------------------------------------------------------------------===//
  46 // Support for StructLayout
  47 //===----------------------------------------------------------------------===//
  48
  49 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
  50   StructAlignment = 0;
  51   StructSize = 0;
  52   NumElements = ST->getNumElements();
  53
  54   // Loop over each of the elements, placing them in memory...
  55   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  56     const Type *Ty = ST->getElementType(i);
  57     unsigned char A;
  58     unsigned TyAlign;
  59     uint64_t TySize;
  60     getTypeInfoABI(Ty, &TD, TySize, A);
  61     TyAlign = ST->isPacked() ? 1 : A;
  62
  63     // Add padding if necessary to make the data element aligned properly...
  64     if (StructSize % TyAlign != 0)
  65       StructSize = (StructSize/TyAlign + 1) * TyAlign;   // Add padding...
  66
  67     // Keep track of maximum alignment constraint
  68     StructAlignment = std::max(TyAlign, StructAlignment);
  69
  70     MemberOffsets[i] = StructSize;
  71     StructSize += TySize;                 // Consume space for this data item
  72   }
  73
  74   // Empty structures have alignment of 1 byte.
  75   if (StructAlignment == 0) StructAlignment = 1;
  76
  77   // Add padding to the end of the struct so that it could be put in an array
  78   // and all array elements would be aligned correctly.
  79   if (StructSize % StructAlignment != 0)
  80     StructSize = (StructSize/StructAlignment + 1) * StructAlignment;
  81 }
  82
  83
  84 /// getElementContainingOffset - Given a valid offset into the structure,
  85 /// return the structure index that contains it.
  86 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  87   const uint64_t *SI =
  88     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  89   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  90   --SI;
  91   assert(*SI <= Offset && "upper_bound didn't work");
  92   assert((SI == &MemberOffsets[0] || *(SI-1) < Offset) &&
  93          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  94          "Upper bound didn't work!");
  95   return SI-&MemberOffsets[0];
  96 }
  97
  98 //===----------------------------------------------------------------------===//
  99 //                       TargetData Class Implementation
 100 //===----------------------------------------------------------------------===//
 101
 102 void TargetData::init(const std::string &TargetDescription) {
 103   std::string temp = TargetDescription;
 104
 105   LittleEndian = false;
 106   PointerMemSize = 8;
 107   PointerABIAlignment   = 8;
 108   DoubleABIAlignment = 0;
 109   FloatABIAlignment = 4;
 110   LongABIAlignment   = 0;
 111   IntABIAlignment   = 4;
 112   ShortABIAlignment  = 2;
 113   ByteABIAlignment  = 1;
 114   BoolABIAlignment   = 1;
 115   BoolPrefAlignment = BoolABIAlignment;
 116   BytePrefAlignment = ByteABIAlignment;
 117   ShortPrefAlignment = ShortABIAlignment;
 118   IntPrefAlignment = IntABIAlignment;
 119   LongPrefAlignment = 8;
 120   FloatPrefAlignment = FloatABIAlignment;
 121   DoublePrefAlignment = 8;
 122   PointerPrefAlignment = PointerABIAlignment;
 123   AggMinPrefAlignment = 0;
 124
 125   while (!temp.empty()) {
 126     std::string token = getToken(temp, "-");
 127
 128     char signal = getToken(token, ":")[0];
 129
 130     switch(signal) {
 131     case 'E':
 132       LittleEndian = false;
 133       break;
 134     case 'e':
 135       LittleEndian = true;
 136       break;
 137     case 'p':
 138       PointerMemSize = atoi(getToken(token,":").c_str()) / 8;
 139       PointerABIAlignment = atoi(getToken(token,":").c_str()) / 8;
 140       PointerPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 141       if (PointerPrefAlignment == 0)
 142         PointerPrefAlignment = PointerABIAlignment;
 143       break;
 144     case 'd':
 145       DoubleABIAlignment = atoi(getToken(token,":").c_str()) / 8;
 146       DoublePrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 147       if (DoublePrefAlignment == 0)
 148         DoublePrefAlignment = DoubleABIAlignment;
 149       break;
 150     case 'f':
 151       FloatABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
 152       FloatPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 153       if (FloatPrefAlignment == 0)
 154         FloatPrefAlignment = FloatABIAlignment;
 155       break;
 156     case 'l':
 157       LongABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
 158       LongPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 159       if (LongPrefAlignment == 0)
 160         LongPrefAlignment = LongABIAlignment;
 161       break;
 162     case 'i':
 163       IntABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
 164       IntPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 165       if (IntPrefAlignment == 0)
 166         IntPrefAlignment = IntABIAlignment;
 167       break;
 168     case 's':
 169       ShortABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
 170       ShortPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 171       if (ShortPrefAlignment == 0)
 172         ShortPrefAlignment = ShortABIAlignment;
 173       break;
 174     case 'b':
 175       ByteABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
 176       BytePrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 177       if (BytePrefAlignment == 0)
 178         BytePrefAlignment = ByteABIAlignment;
 179       break;
 180     case 'B':
 181       BoolABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
 182       BoolPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 183       if (BoolPrefAlignment == 0)
 184         BoolPrefAlignment = BoolABIAlignment;
 185       break;
 186     case 'A':
 187       AggMinPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
 188       break;
 189     default:
 190       break;
 191     }
 192   }
 193
 194   // Unless explicitly specified, the alignments for longs and doubles is
 195   // capped by pointer size.
 196   if (LongABIAlignment == 0)
 197           LongABIAlignment = LongPrefAlignment = PointerMemSize;
 198   if (DoubleABIAlignment == 0)
 199     DoubleABIAlignment = DoublePrefAlignment = PointerMemSize;
 200 }
 201
 202 TargetData::TargetData(const Module *M) {
 203   init(M->getDataLayout());
 204 }
 205
 206 /// LayoutInfo - The lazy cache of structure layout information maintained by
 207 /// TargetData.  Note that the struct types must have been free'd before
 208 /// llvm_shutdown is called (and thus this is deallocated) because all the
 209 /// targets with cached elements should have been destroyed.
 210 ///
 211 typedef std::pair<const TargetData*,const StructType*> LayoutKey;
 212
 213 struct DenseMapLayoutKeyInfo {
 214   static inline LayoutKey getEmptyKey() { return LayoutKey(0, 0); }
 215   static inline LayoutKey getTombstoneKey() {
 216     return LayoutKey((TargetData*)(intptr_t)-1, 0);
 217   }
 218   static unsigned getHashValue(const LayoutKey &Val) {
 219     return DenseMapKeyInfo<void*>::getHashValue(Val.first) ^
 220            DenseMapKeyInfo<void*>::getHashValue(Val.second);
 221   }
 222   static bool isPod() { return true; }
 223 };
 224
 225 typedef DenseMap<LayoutKey, StructLayout*, DenseMapLayoutKeyInfo> LayoutInfoTy;
 226 static ManagedStatic<LayoutInfoTy> LayoutInfo;
 227
 228
 229 TargetData::~TargetData() {
 230   if (LayoutInfo.isConstructed()) {
 231     // Remove any layouts for this TD.
 232     LayoutInfoTy &TheMap = *LayoutInfo;
 233     for (LayoutInfoTy::iterator I = TheMap.begin(), E = TheMap.end();
 234          I != E; ) {
 235       if (I->first.first == this) {
 236         I->second->~StructLayout();
 237         free(I->second);
 238         TheMap.erase(I++);
 239       } else {
 240         ++I;
 241       }
 242     }
 243   }
 244 }
 245
 246 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
 247   LayoutInfoTy &TheMap = *LayoutInfo;
 248
 249   StructLayout *&SL = TheMap[LayoutKey(this, Ty)];
 250   if (SL) return SL;
 251
 252   // Otherwise, create the struct layout.  Because it is variable length, we
 253   // malloc it, then use placement new.
 254   unsigned NumElts = Ty->getNumElements();
 255   StructLayout *L =
 256     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1)*sizeof(uint64_t));
 257
 258   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 259   // entries to be added to TheMap, invalidating our reference.
 260   SL = L;
 261
 262   new (L) StructLayout(Ty, *this);
 263
 264   return L;
 265 }
 266
 267 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
 268 /// objects.  If a TargetData object is alive when types are being refined and
 269 /// removed, this method must be called whenever a StructType is removed to
 270 /// avoid a dangling pointer in this cache.
 271 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
 272   if (!LayoutInfo.isConstructed()) return;  // No cache.
 273
 274   LayoutInfoTy::iterator I = LayoutInfo->find(LayoutKey(this, Ty));
 275   if (I != LayoutInfo->end()) {
 276     I->second->~StructLayout();
 277     free(I->second);
 278     LayoutInfo->erase(I);
 279   }
 280 }
 281
 282
 283 std::string TargetData::getStringRepresentation() const {
 284   std::stringstream repr;
 285
 286   if (LittleEndian)
 287     repr << "e";
 288   else
 289     repr << "E";
 290
 291   repr << "-p:" << (PointerMemSize * 8) << ":" << (PointerABIAlignment * 8);
 292   repr << "-d:" << (DoubleABIAlignment * 8) << ":"
 293        << (DoublePrefAlignment * 8);
 294   repr << "-f:" << (FloatABIAlignment * 8) << ":"
 295        << (FloatPrefAlignment * 8);
 296   repr << "-l:" << (LongABIAlignment * 8) << ":"
 297        << (LongPrefAlignment * 8);
 298   repr << "-i:" << (IntABIAlignment * 8) << ":"
 299        << (IntPrefAlignment * 8);
 300   repr << "-s:" << (ShortABIAlignment * 8) << ":"
 301        << (ShortPrefAlignment * 8);
 302   repr << "-b:" << (ByteABIAlignment * 8) << ":"
 303        << (BytePrefAlignment * 8);
 304   repr << "-B:" << (BoolABIAlignment * 8) << ":"
 305        << (BoolPrefAlignment * 8);
 306   repr << "-A:" << (AggMinPrefAlignment * 8);
 307
 308   return repr.str();
 309 }
 310
 311
 312 static inline void getTypeInfoABI(const Type *Ty, const TargetData *TD,
 313                                   uint64_t &Size, unsigned char &Alignment) {
 314   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 315   switch (Ty->getTypeID()) {
 316   case Type::IntegerTyID: {
 317     unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
 318     if (BitWidth <= 8) {
 319       Size = 1; Alignment = TD->getByteABIAlignment();
 320     } else if (BitWidth <= 16) {
 321       Size = 2; Alignment = TD->getShortABIAlignment();
 322     } else if (BitWidth <= 32) {
 323       Size = 4; Alignment = TD->getIntABIAlignment();
 324     } else if (BitWidth <= 64) {
 325       Size = 8; Alignment = TD->getLongABIAlignment();
 326     } else {
 327       Size = ((BitWidth + 7) / 8) & ~1;
 328       Alignment = TD->getLongABIAlignment();
 329     }
 330     return;
 331   }
 332   case Type::VoidTyID:   Size = 1; Alignment = TD->getByteABIAlignment(); return;
 333   case Type::FloatTyID:  Size = 4; Alignment = TD->getFloatABIAlignment(); return;
 334   case Type::DoubleTyID: Size = 8; Alignment = TD->getDoubleABIAlignment(); return;
 335   case Type::LabelTyID:
 336   case Type::PointerTyID:
 337     Size = TD->getPointerSize(); Alignment = TD->getPointerABIAlignment();
 338     return;
 339   case Type::ArrayTyID: {
 340     const ArrayType *ATy = cast<ArrayType>(Ty);
 341     getTypeInfoABI(ATy->getElementType(), TD, Size, Alignment);
 342     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 343     Size = AlignedSize*ATy->getNumElements();
 344     return;
 345   }
 346   case Type::PackedTyID: {
 347     const PackedType *PTy = cast<PackedType>(Ty);
 348     getTypeInfoABI(PTy->getElementType(), TD, Size, Alignment);
 349     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 350     Size = AlignedSize*PTy->getNumElements();
 351     // FIXME: The alignments of specific packed types are target dependent.
 352     // For now, just set it to be equal to Size.
 353     Alignment = Size;
 354     return;
 355   }
 356   case Type::StructTyID: {
 357     // Get the layout annotation... which is lazily created on demand.
 358     const StructLayout *Layout = TD->getStructLayout(cast<StructType>(Ty));
 359     Size = Layout->getSizeInBytes(); Alignment = Layout->getAlignment();
 360     return;
 361   }
 362
 363   default:
 364     assert(0 && "Bad type for getTypeInfo!!!");
 365     return;
 366   }
 367 }
 368
 369 static inline void getTypeInfoPref(const Type *Ty, const TargetData *TD,
 370                                    uint64_t &Size, unsigned char &Alignment) {
 371   assert(Ty->isSized() && "Cannot getTypeInfoPref() on a type that is unsized!");
 372   switch (Ty->getTypeID()) {
 373   case Type::IntegerTyID: {
 374     unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
 375     if (BitWidth <= 8) {
 376       Size = 1; Alignment = TD->getBytePrefAlignment();
 377     } else if (BitWidth <= 16) {
 378       Size = 2; Alignment = TD->getShortPrefAlignment();
 379     } else if (BitWidth <= 32) {
 380       Size = 4; Alignment = TD->getIntPrefAlignment();
 381     } else if (BitWidth <= 64) {
 382       Size = 8; Alignment = TD->getLongPrefAlignment();
 383     } else
 384       assert(0 && "Integer types > 64 bits not supported.");
 385     return;
 386   }
 387   case Type::VoidTyID:
 388     Size = 1; Alignment = TD->getBytePrefAlignment();
 389     return;
 390   case Type::FloatTyID:
 391     Size = 4; Alignment = TD->getFloatPrefAlignment();
 392     return;
 393   case Type::DoubleTyID:
 394     Size = 8; Alignment = TD->getDoublePrefAlignment();
 395     return;
 396   case Type::LabelTyID:
 397   case Type::PointerTyID:
 398     Size = TD->getPointerSize(); Alignment = TD->getPointerPrefAlignment();
 399     return;
 400   case Type::ArrayTyID: {
 401     const ArrayType *ATy = cast<ArrayType>(Ty);
 402     getTypeInfoPref(ATy->getElementType(), TD, Size, Alignment);
 403     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 404     Size = AlignedSize*ATy->getNumElements();
 405     return;
 406   }
 407   case Type::PackedTyID: {
 408     const PackedType *PTy = cast<PackedType>(Ty);
 409     getTypeInfoPref(PTy->getElementType(), TD, Size, Alignment);
 410     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 411     Size = AlignedSize*PTy->getNumElements();
 412     // FIXME: The alignments of specific packed types are target dependent.
 413     // For now, just set it to be equal to Size.
 414     Alignment = Size;
 415     return;
 416   }
 417   case Type::StructTyID: {
 418     // Get the layout annotation... which is lazily created on demand;
 419     // enforce minimum aggregate alignment.
 420     const StructLayout *Layout = TD->getStructLayout(cast<StructType>(Ty));
 421     Size = Layout->getSizeInBytes();
 422     Alignment = std::max(Layout->getAlignment(),
 423                          (const unsigned int)TD->getAggMinPrefAlignment());
 424     return;
 425   }
 426
 427   default:
 428     assert(0 && "Bad type for getTypeInfoPref!!!");
 429     return;
 430   }
 431 }
 432
 433
 434 uint64_t TargetData::getTypeSize(const Type *Ty) const {
 435   uint64_t Size;
 436   unsigned char Align;
 437   getTypeInfoABI(Ty, this, Size, Align);
 438   return Size;
 439 }
 440
 441 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
 442   if (Ty->isInteger())
 443     return cast<IntegerType>(Ty)->getBitWidth();
 444
 445   uint64_t Size;
 446   unsigned char Align;
 447   getTypeInfoABI(Ty, this, Size, Align);
 448   return Size * 8;
 449 }
 450
 451 unsigned char TargetData::getTypeAlignmentABI(const Type *Ty) const {
 452   uint64_t Size;
 453   unsigned char Align;
 454   getTypeInfoABI(Ty, this, Size, Align);
 455   return Align;
 456 }
 457
 458 unsigned char TargetData::getTypeAlignmentPref(const Type *Ty) const {
 459   uint64_t Size;
 460   unsigned char Align;
 461   getTypeInfoPref(Ty, this, Size, Align);
 462   return Align;
 463 }
 464
 465 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
 466   unsigned Align = getTypeAlignmentPref(Ty);
 467   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 468   return Log2_32(Align);
 469 }
 470
 471 /// getIntPtrType - Return an unsigned integer type that is the same size or
 472 /// greater to the host pointer size.
 473 const Type *TargetData::getIntPtrType() const {
 474   switch (getPointerSize()) {
 475   default: assert(0 && "Unknown pointer size!");
 476   case 2: return Type::Int16Ty;
 477   case 4: return Type::Int32Ty;
 478   case 8: return Type::Int64Ty;
 479   }
 480 }
 481
 482
 483 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
 484                                       unsigned NumIndices) const {
 485   const Type *Ty = ptrTy;
 486   assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
 487   uint64_t Result = 0;
 488
 489   generic_gep_type_iterator<Value* const*>
 490     TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
 491   for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
 492     if (const StructType *STy = dyn_cast<StructType>(*TI)) {
 493       assert(Indices[CurIDX]->getType() == Type::Int32Ty &&"Illegal struct idx");
 494       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 495
 496       // Get structure layout information...
 497       const StructLayout *Layout = getStructLayout(STy);
 498
 499       // Add in the offset, as calculated by the structure layout info...
 500       Result += Layout->getElementOffset(FieldNo);
 501
 502       // Update Ty to refer to current element
 503       Ty = STy->getElementType(FieldNo);
 504     } else {
 505       // Update Ty to refer to current element
 506       Ty = cast<SequentialType>(Ty)->getElementType();
 507
 508       // Get the array index and the size of each array element.
 509       int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
 510       Result += arrayIdx * (int64_t)getTypeSize(Ty);
 511     }
 512   }
 513
 514   return Result;
 515 }
 516
 517 /// getPreferredAlignmentLog - Return the preferred alignment of the
 518 /// specified global, returned in log form.  This includes an explicitly
 519 /// requested alignment (if the global has one).
 520 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 521   const Type *ElemType = GV->getType()->getElementType();
 522   unsigned Alignment = getPreferredTypeAlignmentShift(ElemType);
 523   if (GV->getAlignment() > (1U << Alignment))
 524     Alignment = Log2_32(GV->getAlignment());
 525
 526   if (GV->hasInitializer()) {
 527     if (Alignment < 4) {
 528       // If the global is not external, see if it is large.  If so, give it a
 529       // larger alignment.
 530       if (getTypeSize(ElemType) > 128)
 531         Alignment = 4;    // 16-byte alignment.
 532     }
 533   }
 534   return Alignment;
 535 }
 536