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