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 getTypeInfo(const Type *Ty, const TargetData *TD,
  38                                uint64_t &Size, unsigned char &Alignment);
  39
  40 //===----------------------------------------------------------------------===//
  41 // Support for StructLayout
  42 //===----------------------------------------------------------------------===//
  43
  44 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
  45   StructAlignment = 0;
  46   StructSize = 0;
  47
  48   // Loop over each of the elements, placing them in memory...
  49   for (StructType::element_iterator TI = ST->element_begin(),
  50          TE = ST->element_end(); TI != TE; ++TI) {
  51     const Type *Ty = *TI;
  52     unsigned char A;
  53     unsigned TyAlign;
  54     uint64_t TySize;
  55     getTypeInfo(Ty, &TD, TySize, A);
  56     TyAlign = A;
  57
  58     // Add padding if necessary to make the data element aligned properly...
  59     if (StructSize % TyAlign != 0)
  60       StructSize = (StructSize/TyAlign + 1) * TyAlign;   // Add padding...
  61
  62     // Keep track of maximum alignment constraint
  63     StructAlignment = std::max(TyAlign, StructAlignment);
  64
  65     MemberOffsets.push_back(StructSize);
  66     StructSize += TySize;                 // Consume space for this data item
  67   }
  68
  69   // Empty structures have alignment of 1 byte.
  70   if (StructAlignment == 0) StructAlignment = 1;
  71
  72   // Add padding to the end of the struct so that it could be put in an array
  73   // and all array elements would be aligned correctly.
  74   if (StructSize % StructAlignment != 0)
  75     StructSize = (StructSize/StructAlignment + 1) * StructAlignment;
  76 }
  77
  78
  79 /// getElementContainingOffset - Given a valid offset into the structure,
  80 /// return the structure index that contains it.
  81 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  82   std::vector<uint64_t>::const_iterator SI =
  83     std::upper_bound(MemberOffsets.begin(), MemberOffsets.end(),
  84                      Offset);
  85   assert(SI != MemberOffsets.begin() && "Offset not in structure type!");
  86   --SI;
  87   assert(*SI <= Offset && "upper_bound didn't work");
  88   assert((SI == MemberOffsets.begin() || *(SI-1) < Offset) &&
  89          (SI+1 == MemberOffsets.end() || *(SI+1) > Offset) &&
  90          "Upper bound didn't work!");
  91   return SI-MemberOffsets.begin();
  92 }
  93
  94 //===----------------------------------------------------------------------===//
  95 //                       TargetData Class Implementation
  96 //===----------------------------------------------------------------------===//
  97
  98 TargetData::TargetData(const std::string &TargetName,
  99                        bool isLittleEndian, unsigned char PtrSize,
 100                        unsigned char PtrAl, unsigned char DoubleAl,
 101                        unsigned char FloatAl, unsigned char LongAl,
 102                        unsigned char IntAl, unsigned char ShortAl,
 103                        unsigned char ByteAl, unsigned char BoolAl) {
 104
 105   // If this assert triggers, a pass "required" TargetData information, but the
 106   // top level tool did not provide one for it.  We do not want to default
 107   // construct, or else we might end up using a bad endianness or pointer size!
 108   //
 109   assert(!TargetName.empty() &&
 110          "ERROR: Tool did not specify a target data to use!");
 111
 112   LittleEndian     = isLittleEndian;
 113   PointerSize      = PtrSize;
 114   PointerAlignment = PtrAl;
 115   DoubleAlignment  = DoubleAl;
 116   FloatAlignment   = FloatAl;
 117   LongAlignment    = LongAl;
 118   IntAlignment     = IntAl;
 119   ShortAlignment   = ShortAl;
 120   ByteAlignment    = ByteAl;
 121   BoolAlignment    = BoolAl;
 122 }
 123
 124 TargetData::TargetData(const std::string &TargetName,
 125                        const std::string &TargetDescription) {
 126   std::string temp = TargetDescription;
 127
 128   LittleEndian = false;
 129   PointerSize = 8;
 130   PointerAlignment   = 8;
 131   DoubleAlignment = 8;
 132   FloatAlignment = 4;
 133   LongAlignment   = 8;
 134   IntAlignment   = 4;
 135   ShortAlignment  = 2;
 136   ByteAlignment  = 1;
 137   BoolAlignment   = 1;
 138
 139   while (temp.length() > 0) {
 140     std::string token = getToken(temp, "-");
 141
 142     char signal = getToken(token, ":")[0];
 143
 144     switch(signal) {
 145     case 'E':
 146       LittleEndian = false;
 147       break;
 148     case 'e':
 149       LittleEndian = true;
 150       break;
 151     case 'p':
 152       PointerSize = atoi(getToken(token,":").c_str()) / 8;
 153       PointerAlignment = atoi(getToken(token,":").c_str()) / 8;
 154       break;
 155     case 'd':
 156       token = getToken(token,":"); //Ignore the size
 157       DoubleAlignment = atoi(getToken(token,":").c_str()) / 8;
 158       break;
 159     case 'f':
 160       token = getToken(token, ":"); //Ignore the size
 161       FloatAlignment = atoi(getToken(token, ":").c_str()) / 8;
 162       break;
 163     case 'l':
 164       token = getToken(token, ":"); //Ignore the size
 165       LongAlignment = atoi(getToken(token, ":").c_str()) / 8;
 166       break;
 167     case 'i':
 168       token = getToken(token, ":"); //Ignore the size
 169       IntAlignment = atoi(getToken(token, ":").c_str()) / 8;
 170       break;
 171     case 's':
 172       token = getToken(token, ":"); //Ignore the size
 173       ShortAlignment = atoi(getToken(token, ":").c_str()) / 8;
 174       break;
 175     case 'b':
 176       token = getToken(token, ":"); //Ignore the size
 177       ByteAlignment = atoi(getToken(token, ":").c_str()) / 8;
 178       break;
 179     case 'B':
 180       token = getToken(token, ":"); //Ignore the size
 181       BoolAlignment = atoi(getToken(token, ":").c_str()) / 8;
 182       break;
 183     default:
 184       break;
 185     }
 186   }
 187 }
 188
 189 TargetData::TargetData(const std::string &ToolName, const Module *M) {
 190   LittleEndian     = M->getEndianness() != Module::BigEndian;
 191   PointerSize      = M->getPointerSize() != Module::Pointer64 ? 4 : 8;
 192   PointerAlignment = PointerSize;
 193   DoubleAlignment  = PointerSize;
 194   FloatAlignment   = 4;
 195   LongAlignment    = PointerSize;
 196   IntAlignment     = 4;
 197   ShortAlignment   = 2;
 198   ByteAlignment    = 1;
 199   BoolAlignment    = 1;
 200 }
 201
 202 /// Layouts - The lazy cache of structure layout information maintained by
 203 /// TargetData.
 204 ///
 205 static std::map<std::pair<const TargetData*,const StructType*>,
 206                 StructLayout> *Layouts = 0;
 207
 208
 209 TargetData::~TargetData() {
 210   if (Layouts) {
 211     // Remove any layouts for this TD.
 212     std::map<std::pair<const TargetData*,
 213       const StructType*>, StructLayout>::iterator
 214       I = Layouts->lower_bound(std::make_pair(this, (const StructType*)0));
 215     while (I != Layouts->end() && I->first.first == this)
 216       Layouts->erase(I++);
 217     if (Layouts->empty()) {
 218       delete Layouts;
 219       Layouts = 0;
 220     }
 221   }
 222 }
 223
 224 std::string TargetData::getStringRepresentation() const {
 225   std::stringstream repr;
 226
 227   if (LittleEndian)
 228     repr << "e";
 229   else
 230     repr << "E";
 231
 232   repr << "-p:" << (PointerSize * 8) << ":" << (PointerAlignment * 8);
 233   repr << "-d:64:" << (DoubleAlignment * 8);
 234   repr << "-f:32:" << (FloatAlignment * 8);
 235   repr << "-l:64:" << (LongAlignment * 8);
 236   repr << "-i:32:" << (IntAlignment * 8);
 237   repr << "-s:16:" << (ShortAlignment * 8);
 238   repr << "-b:8:" << (ByteAlignment * 8);
 239   repr << "-B:8:" << (BoolAlignment * 8);
 240
 241   return repr.str();
 242 }
 243
 244 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
 245   if (Layouts == 0)
 246     Layouts = new std::map<std::pair<const TargetData*,const StructType*>,
 247                            StructLayout>();
 248   std::map<std::pair<const TargetData*,const StructType*>,
 249                      StructLayout>::iterator
 250     I = Layouts->lower_bound(std::make_pair(this, Ty));
 251   if (I != Layouts->end() && I->first.first == this && I->first.second == Ty)
 252     return &I->second;
 253   else {
 254     return &Layouts->insert(I, std::make_pair(std::make_pair(this, Ty),
 255                                               StructLayout(Ty, *this)))->second;
 256   }
 257 }
 258
 259 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
 260 /// objects.  If a TargetData object is alive when types are being refined and
 261 /// removed, this method must be called whenever a StructType is removed to
 262 /// avoid a dangling pointer in this cache.
 263 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
 264   if (!Layouts) return;  // No cache.
 265
 266   std::map<std::pair<const TargetData*,const StructType*>,
 267            StructLayout>::iterator I = Layouts->find(std::make_pair(this, Ty));
 268   if (I != Layouts->end())
 269     Layouts->erase(I);
 270 }
 271
 272
 273
 274 static inline void getTypeInfo(const Type *Ty, const TargetData *TD,
 275                                uint64_t &Size, unsigned char &Alignment) {
 276   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 277   switch (Ty->getTypeID()) {
 278   case Type::BoolTyID:   Size = 1; Alignment = TD->getBoolAlignment(); return;
 279   case Type::VoidTyID:
 280   case Type::UByteTyID:
 281   case Type::SByteTyID:  Size = 1; Alignment = TD->getByteAlignment(); return;
 282   case Type::UShortTyID:
 283   case Type::ShortTyID:  Size = 2; Alignment = TD->getShortAlignment(); return;
 284   case Type::UIntTyID:
 285   case Type::IntTyID:    Size = 4; Alignment = TD->getIntAlignment(); return;
 286   case Type::ULongTyID:
 287   case Type::LongTyID:   Size = 8; Alignment = TD->getLongAlignment(); return;
 288   case Type::FloatTyID:  Size = 4; Alignment = TD->getFloatAlignment(); return;
 289   case Type::DoubleTyID: Size = 8; Alignment = TD->getDoubleAlignment(); return;
 290   case Type::LabelTyID:
 291   case Type::PointerTyID:
 292     Size = TD->getPointerSize(); Alignment = TD->getPointerAlignment();
 293     return;
 294   case Type::ArrayTyID: {
 295     const ArrayType *ATy = cast<ArrayType>(Ty);
 296     getTypeInfo(ATy->getElementType(), TD, Size, Alignment);
 297     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 298     Size = AlignedSize*ATy->getNumElements();
 299     return;
 300   }
 301   case Type::PackedTyID: {
 302     const PackedType *PTy = cast<PackedType>(Ty);
 303     getTypeInfo(PTy->getElementType(), TD, Size, Alignment);
 304     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 305     Size = AlignedSize*PTy->getNumElements();
 306     // FIXME: The alignments of specific packed types are target dependent.
 307     // For now, just set it to be equal to Size.
 308     Alignment = Size;
 309     return;
 310   }
 311   case Type::StructTyID: {
 312     // Get the layout annotation... which is lazily created on demand.
 313     const StructLayout *Layout = TD->getStructLayout(cast<StructType>(Ty));
 314     Size = Layout->StructSize; Alignment = Layout->StructAlignment;
 315     return;
 316   }
 317
 318   default:
 319     assert(0 && "Bad type for getTypeInfo!!!");
 320     return;
 321   }
 322 }
 323
 324 uint64_t TargetData::getTypeSize(const Type *Ty) const {
 325   uint64_t Size;
 326   unsigned char Align;
 327   getTypeInfo(Ty, this, Size, Align);
 328   return Size;
 329 }
 330
 331 unsigned char TargetData::getTypeAlignment(const Type *Ty) const {
 332   uint64_t Size;
 333   unsigned char Align;
 334   getTypeInfo(Ty, this, Size, Align);
 335   return Align;
 336 }
 337
 338 unsigned char TargetData::getTypeAlignmentShift(const Type *Ty) const {
 339   unsigned Align = getTypeAlignment(Ty);
 340   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 341   return Log2_32(Align);
 342 }
 343
 344 /// getIntPtrType - Return an unsigned integer type that is the same size or
 345 /// greater to the host pointer size.
 346 const Type *TargetData::getIntPtrType() const {
 347   switch (getPointerSize()) {
 348   default: assert(0 && "Unknown pointer size!");
 349   case 2: return Type::UShortTy;
 350   case 4: return Type::UIntTy;
 351   case 8: return Type::ULongTy;
 352   }
 353 }
 354
 355
 356 uint64_t TargetData::getIndexedOffset(const Type *ptrTy,
 357                                       const std::vector<Value*> &Idx) const {
 358   const Type *Ty = ptrTy;
 359   assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
 360   uint64_t Result = 0;
 361
 362   generic_gep_type_iterator<std::vector<Value*>::const_iterator>
 363     TI = gep_type_begin(ptrTy, Idx.begin(), Idx.end());
 364   for (unsigned CurIDX = 0; CurIDX != Idx.size(); ++CurIDX, ++TI) {
 365     if (const StructType *STy = dyn_cast<StructType>(*TI)) {
 366       assert(Idx[CurIDX]->getType() == Type::UIntTy && "Illegal struct idx");
 367       unsigned FieldNo = cast<ConstantUInt>(Idx[CurIDX])->getValue();
 368
 369       // Get structure layout information...
 370       const StructLayout *Layout = getStructLayout(STy);
 371
 372       // Add in the offset, as calculated by the structure layout info...
 373       assert(FieldNo < Layout->MemberOffsets.size() &&"FieldNo out of range!");
 374       Result += Layout->MemberOffsets[FieldNo];
 375
 376       // Update Ty to refer to current element
 377       Ty = STy->getElementType(FieldNo);
 378     } else {
 379       // Update Ty to refer to current element
 380       Ty = cast<SequentialType>(Ty)->getElementType();
 381
 382       // Get the array index and the size of each array element.
 383       int64_t arrayIdx = cast<ConstantInt>(Idx[CurIDX])->getRawValue();
 384       Result += arrayIdx * (int64_t)getTypeSize(Ty);
 385     }
 386   }
 387
 388   return Result;
 389 }
 390