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 = ST->isPacked() ? 1 : 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 void TargetData::init(const std::string &TargetDescription) {
  99   std::string temp = TargetDescription;
 100
 101   LittleEndian = false;
 102   PointerSize = 8;
 103   PointerAlignment   = 8;
 104   DoubleAlignment = 8;
 105   FloatAlignment = 4;
 106   LongAlignment   = 8;
 107   IntAlignment   = 4;
 108   ShortAlignment  = 2;
 109   ByteAlignment  = 1;
 110   BoolAlignment   = 1;
 111
 112   while (!temp.empty()) {
 113     std::string token = getToken(temp, "-");
 114
 115     char signal = getToken(token, ":")[0];
 116
 117     switch(signal) {
 118     case 'E':
 119       LittleEndian = false;
 120       break;
 121     case 'e':
 122       LittleEndian = true;
 123       break;
 124     case 'p':
 125       PointerSize = atoi(getToken(token,":").c_str()) / 8;
 126       PointerAlignment = atoi(getToken(token,":").c_str()) / 8;
 127       break;
 128     case 'd':
 129       DoubleAlignment = atoi(getToken(token,":").c_str()) / 8;
 130       break;
 131     case 'f':
 132       FloatAlignment = atoi(getToken(token, ":").c_str()) / 8;
 133       break;
 134     case 'l':
 135       LongAlignment = atoi(getToken(token, ":").c_str()) / 8;
 136       break;
 137     case 'i':
 138       IntAlignment = atoi(getToken(token, ":").c_str()) / 8;
 139       break;
 140     case 's':
 141       ShortAlignment = atoi(getToken(token, ":").c_str()) / 8;
 142       break;
 143     case 'b':
 144       ByteAlignment = atoi(getToken(token, ":").c_str()) / 8;
 145       break;
 146     case 'B':
 147       BoolAlignment = atoi(getToken(token, ":").c_str()) / 8;
 148       break;
 149     default:
 150       break;
 151     }
 152   }
 153 }
 154
 155 TargetData::TargetData(const Module *M) {
 156   LittleEndian     = M->getEndianness() != Module::BigEndian;
 157   PointerSize      = M->getPointerSize() != Module::Pointer64 ? 4 : 8;
 158   PointerAlignment = PointerSize;
 159   DoubleAlignment  = PointerSize;
 160   FloatAlignment   = 4;
 161   LongAlignment    = PointerSize;
 162   IntAlignment     = 4;
 163   ShortAlignment   = 2;
 164   ByteAlignment    = 1;
 165   BoolAlignment    = 1;
 166 }
 167
 168 /// Layouts - The lazy cache of structure layout information maintained by
 169 /// TargetData.
 170 ///
 171 static std::map<std::pair<const TargetData*,const StructType*>,
 172                 StructLayout> *Layouts = 0;
 173
 174
 175 TargetData::~TargetData() {
 176   if (Layouts) {
 177     // Remove any layouts for this TD.
 178     std::map<std::pair<const TargetData*,
 179       const StructType*>, StructLayout>::iterator
 180       I = Layouts->lower_bound(std::make_pair(this, (const StructType*)0));
 181     while (I != Layouts->end() && I->first.first == this)
 182       Layouts->erase(I++);
 183     if (Layouts->empty()) {
 184       delete Layouts;
 185       Layouts = 0;
 186     }
 187   }
 188 }
 189
 190 std::string TargetData::getStringRepresentation() const {
 191   std::stringstream repr;
 192
 193   if (LittleEndian)
 194     repr << "e";
 195   else
 196     repr << "E";
 197
 198   repr << "-p:" << (PointerSize * 8) << ":" << (PointerAlignment * 8);
 199   repr << "-d:64:" << (DoubleAlignment * 8);
 200   repr << "-f:32:" << (FloatAlignment * 8);
 201   repr << "-l:64:" << (LongAlignment * 8);
 202   repr << "-i:32:" << (IntAlignment * 8);
 203   repr << "-s:16:" << (ShortAlignment * 8);
 204   repr << "-b:8:" << (ByteAlignment * 8);
 205   repr << "-B:8:" << (BoolAlignment * 8);
 206
 207   return repr.str();
 208 }
 209
 210 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
 211   if (Layouts == 0)
 212     Layouts = new std::map<std::pair<const TargetData*,const StructType*>,
 213                            StructLayout>();
 214   std::map<std::pair<const TargetData*,const StructType*>,
 215                      StructLayout>::iterator
 216     I = Layouts->lower_bound(std::make_pair(this, Ty));
 217   if (I != Layouts->end() && I->first.first == this && I->first.second == Ty)
 218     return &I->second;
 219   else {
 220     return &Layouts->insert(I, std::make_pair(std::make_pair(this, Ty),
 221                                               StructLayout(Ty, *this)))->second;
 222   }
 223 }
 224
 225 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
 226 /// objects.  If a TargetData object is alive when types are being refined and
 227 /// removed, this method must be called whenever a StructType is removed to
 228 /// avoid a dangling pointer in this cache.
 229 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
 230   if (!Layouts) return;  // No cache.
 231
 232   std::map<std::pair<const TargetData*,const StructType*>,
 233            StructLayout>::iterator I = Layouts->find(std::make_pair(this, Ty));
 234   if (I != Layouts->end())
 235     Layouts->erase(I);
 236 }
 237
 238
 239
 240 static inline void getTypeInfo(const Type *Ty, const TargetData *TD,
 241                                uint64_t &Size, unsigned char &Alignment) {
 242   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 243   switch (Ty->getTypeID()) {
 244   case Type::Int1TyID:   Size = 1; Alignment = TD->getBoolAlignment(); return;
 245   case Type::VoidTyID:
 246   case Type::Int8TyID:   Size = 1; Alignment = TD->getByteAlignment(); return;
 247   case Type::Int16TyID:  Size = 2; Alignment = TD->getShortAlignment(); return;
 248   case Type::Int32TyID:  Size = 4; Alignment = TD->getIntAlignment(); return;
 249   case Type::Int64TyID:  Size = 8; Alignment = TD->getLongAlignment(); return;
 250   case Type::FloatTyID:  Size = 4; Alignment = TD->getFloatAlignment(); return;
 251   case Type::DoubleTyID: Size = 8; Alignment = TD->getDoubleAlignment(); return;
 252   case Type::LabelTyID:
 253   case Type::PointerTyID:
 254     Size = TD->getPointerSize(); Alignment = TD->getPointerAlignment();
 255     return;
 256   case Type::ArrayTyID: {
 257     const ArrayType *ATy = cast<ArrayType>(Ty);
 258     getTypeInfo(ATy->getElementType(), TD, Size, Alignment);
 259     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 260     Size = AlignedSize*ATy->getNumElements();
 261     return;
 262   }
 263   case Type::PackedTyID: {
 264     const PackedType *PTy = cast<PackedType>(Ty);
 265     getTypeInfo(PTy->getElementType(), TD, Size, Alignment);
 266     unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 267     Size = AlignedSize*PTy->getNumElements();
 268     // FIXME: The alignments of specific packed types are target dependent.
 269     // For now, just set it to be equal to Size.
 270     Alignment = Size;
 271     return;
 272   }
 273   case Type::StructTyID: {
 274     // Get the layout annotation... which is lazily created on demand.
 275     const StructLayout *Layout = TD->getStructLayout(cast<StructType>(Ty));
 276     Size = Layout->StructSize; Alignment = Layout->StructAlignment;
 277     return;
 278   }
 279
 280   default:
 281     assert(0 && "Bad type for getTypeInfo!!!");
 282     return;
 283   }
 284 }
 285
 286 uint64_t TargetData::getTypeSize(const Type *Ty) const {
 287   uint64_t Size;
 288   unsigned char Align;
 289   getTypeInfo(Ty, this, Size, Align);
 290   return Size;
 291 }
 292
 293 unsigned char TargetData::getTypeAlignment(const Type *Ty) const {
 294   uint64_t Size;
 295   unsigned char Align;
 296   getTypeInfo(Ty, this, Size, Align);
 297   return Align;
 298 }
 299
 300 unsigned char TargetData::getTypeAlignmentShift(const Type *Ty) const {
 301   unsigned Align = getTypeAlignment(Ty);
 302   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 303   return Log2_32(Align);
 304 }
 305
 306 /// getIntPtrType - Return an unsigned integer type that is the same size or
 307 /// greater to the host pointer size.
 308 const Type *TargetData::getIntPtrType() const {
 309   switch (getPointerSize()) {
 310   default: assert(0 && "Unknown pointer size!");
 311   case 2: return Type::Int16Ty;
 312   case 4: return Type::Int32Ty;
 313   case 8: return Type::Int64Ty;
 314   }
 315 }
 316
 317
 318 uint64_t TargetData::getIndexedOffset(const Type *ptrTy,
 319                                       const std::vector<Value*> &Idx) const {
 320   const Type *Ty = ptrTy;
 321   assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
 322   uint64_t Result = 0;
 323
 324   generic_gep_type_iterator<std::vector<Value*>::const_iterator>
 325     TI = gep_type_begin(ptrTy, Idx.begin(), Idx.end());
 326   for (unsigned CurIDX = 0; CurIDX != Idx.size(); ++CurIDX, ++TI) {
 327     if (const StructType *STy = dyn_cast<StructType>(*TI)) {
 328       assert(Idx[CurIDX]->getType() == Type::Int32Ty && "Illegal struct idx");
 329       unsigned FieldNo = cast<ConstantInt>(Idx[CurIDX])->getZExtValue();
 330
 331       // Get structure layout information...
 332       const StructLayout *Layout = getStructLayout(STy);
 333
 334       // Add in the offset, as calculated by the structure layout info...
 335       assert(FieldNo < Layout->MemberOffsets.size() &&"FieldNo out of range!");
 336       Result += Layout->MemberOffsets[FieldNo];
 337
 338       // Update Ty to refer to current element
 339       Ty = STy->getElementType(FieldNo);
 340     } else {
 341       // Update Ty to refer to current element
 342       Ty = cast<SequentialType>(Ty)->getElementType();
 343
 344       // Get the array index and the size of each array element.
 345       int64_t arrayIdx = cast<ConstantInt>(Idx[CurIDX])->getSExtValue();
 346       Result += arrayIdx * (int64_t)getTypeSize(Ty);
 347     }
 348   }
 349
 350   return Result;
 351 }
 352
 353 /// getPreferredAlignmentLog - Return the preferred alignment of the
 354 /// specified global, returned in log form.  This includes an explicitly
 355 /// requested alignment (if the global has one).
 356 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 357   const Type *ElemType = GV->getType()->getElementType();
 358   unsigned Alignment = getTypeAlignmentShift(ElemType);
 359   if (GV->getAlignment() > (1U << Alignment))
 360     Alignment = Log2_32(GV->getAlignment());
 361
 362   if (GV->hasInitializer()) {
 363     // Always round up alignment of global doubles to 8 bytes.
 364     if (GV->getType()->getElementType() == Type::DoubleTy && Alignment < 3)
 365       Alignment = 3;
 366     if (Alignment < 4) {
 367       // If the global is not external, see if it is large.  If so, give it a
 368       // larger alignment.
 369       if (getTypeSize(ElemType) > 128)
 370         Alignment = 4;    // 16-byte alignment.
 371     }
 372   }
 373   return Alignment;
 374 }
 375