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