lib/Target/TargetData.cpp

//===-- TargetData.cpp - Data size & alignment routines --------------------==//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines target properties related to datatype size/offset/alignment
// information.
//
// This structure should be created once, filled in if the defaults are not
// correct and then passed around by const&.  None of the members functions
// require modification to the object.
//
//===----------------------------------------------------------------------===//

#include "llvm/Target/TargetData.h"
#include "llvm/Module.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Constants.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/StringExtras.h"
#include <algorithm>
#include <cstdlib>
#include <sstream>
using namespace llvm;

// Handle the Pass registration stuff necessary to use TargetData's.
namespace {
  // Register the default SparcV9 implementation...
  RegisterPass<TargetData> X("targetdata", "Target Data Layout");
}

static inline void getTypeInfoABI(const Type *Ty, const TargetData *TD,
                                  uint64_t &Size, unsigned char &Alignment);

static inline void getTypeInfoPref(const Type *Ty, const TargetData *TD,
                                   uint64_t &Size, unsigned char &Alignment);

//===----------------------------------------------------------------------===//
// Support for StructLayout
//===----------------------------------------------------------------------===//

StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
  StructAlignment = 0;
  StructSize = 0;
  NumElements = ST->getNumElements();

  // Loop over each of the elements, placing them in memory...
  for (unsigned i = 0, e = NumElements; i != e; ++i) {
    const Type *Ty = ST->getElementType(i);
    unsigned char A;
    unsigned TyAlign;
    uint64_t TySize;
    getTypeInfoABI(Ty, &TD, TySize, A);
    TyAlign = ST->isPacked() ? 1 : A;

    // Add padding if necessary to make the data element aligned properly...
    if (StructSize % TyAlign != 0)
      StructSize = (StructSize/TyAlign + 1) * TyAlign;   // Add padding...

    // Keep track of maximum alignment constraint
    StructAlignment = std::max(TyAlign, StructAlignment);

    MemberOffsets[i] = StructSize;
    StructSize += TySize;                 // Consume space for this data item
  }

  // Empty structures have alignment of 1 byte.
  if (StructAlignment == 0) StructAlignment = 1;

  // Add padding to the end of the struct so that it could be put in an array
  // and all array elements would be aligned correctly.
  if (StructSize % StructAlignment != 0)
    StructSize = (StructSize/StructAlignment + 1) * StructAlignment;
}


/// getElementContainingOffset - Given a valid offset into the structure,
/// return the structure index that contains it.
unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  const uint64_t *SI =
    std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  --SI;
  assert(*SI <= Offset && "upper_bound didn't work");
  assert((SI == &MemberOffsets[0] || *(SI-1) < Offset) &&
         (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
         "Upper bound didn't work!");
  return SI-&MemberOffsets[0];
}

//===----------------------------------------------------------------------===//
//                       TargetData Class Implementation
//===----------------------------------------------------------------------===//

void TargetData::init(const std::string &TargetDescription) {
  std::string temp = TargetDescription;
  
  LittleEndian = false;
  PointerMemSize = 8;
  PointerABIAlignment   = 8;
  DoubleABIAlignment = 0;
  FloatABIAlignment = 4;
  LongABIAlignment   = 0;
  IntABIAlignment   = 4;
  ShortABIAlignment  = 2;
  ByteABIAlignment  = 1;
  BoolABIAlignment   = 1;
  BoolPrefAlignment = BoolABIAlignment;
  BytePrefAlignment = ByteABIAlignment;
  ShortPrefAlignment = ShortABIAlignment;
  IntPrefAlignment = IntABIAlignment;
  LongPrefAlignment = 8;
  FloatPrefAlignment = FloatABIAlignment;
  DoublePrefAlignment = 8;
  PointerPrefAlignment = PointerABIAlignment;
  AggMinPrefAlignment = 0;
  
  while (!temp.empty()) {
    std::string token = getToken(temp, "-");
    
    char signal = getToken(token, ":")[0];
    
    switch(signal) {
    case 'E':
      LittleEndian = false;
      break;
    case 'e':
      LittleEndian = true;
      break;
    case 'p':
      PointerMemSize = atoi(getToken(token,":").c_str()) / 8;
      PointerABIAlignment = atoi(getToken(token,":").c_str()) / 8;
      PointerPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (PointerPrefAlignment == 0)
        PointerPrefAlignment = PointerABIAlignment;
      break;
    case 'd':
      DoubleABIAlignment = atoi(getToken(token,":").c_str()) / 8;
      DoublePrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (DoublePrefAlignment == 0)
        DoublePrefAlignment = DoubleABIAlignment;
      break;
    case 'f':
      FloatABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
      FloatPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (FloatPrefAlignment == 0)
        FloatPrefAlignment = FloatABIAlignment;
      break;
    case 'l':
      LongABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
      LongPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (LongPrefAlignment == 0)
        LongPrefAlignment = LongABIAlignment;
      break;
    case 'i':
      IntABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
      IntPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (IntPrefAlignment == 0)
        IntPrefAlignment = IntABIAlignment;
      break;
    case 's':
      ShortABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
      ShortPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (ShortPrefAlignment == 0)
        ShortPrefAlignment = ShortABIAlignment;
      break;
    case 'b':
      ByteABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
      BytePrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (BytePrefAlignment == 0)
        BytePrefAlignment = ByteABIAlignment;
      break;
    case 'B':
      BoolABIAlignment = atoi(getToken(token, ":").c_str()) / 8;
      BoolPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      if (BoolPrefAlignment == 0)
        BoolPrefAlignment = BoolABIAlignment;
      break;
    case 'A':
      AggMinPrefAlignment = atoi(getToken(token,":").c_str()) / 8;
      break;
    default:
      break;
    }
  }

  // Unless explicitly specified, the alignments for longs and doubles is 
  // capped by pointer size.
  if (LongABIAlignment == 0)
	  LongABIAlignment = LongPrefAlignment = PointerMemSize;
  if (DoubleABIAlignment == 0)
    DoubleABIAlignment = DoublePrefAlignment = PointerMemSize;
}

TargetData::TargetData(const Module *M) {
  init(M->getDataLayout());
}

/// LayoutInfo - The lazy cache of structure layout information maintained by
/// TargetData.  Note that the struct types must have been free'd before
/// llvm_shutdown is called (and thus this is deallocated) because all the
/// targets with cached elements should have been destroyed.
///
typedef std::pair<const TargetData*,const StructType*> LayoutKey;

struct DenseMapLayoutKeyInfo {
  static inline LayoutKey getEmptyKey() { return LayoutKey(0, 0); }
  static inline LayoutKey getTombstoneKey() {
    return LayoutKey((TargetData*)(intptr_t)-1, 0);
  }
  static unsigned getHashValue(const LayoutKey &Val) {
    return DenseMapKeyInfo<void*>::getHashValue(Val.first) ^
           DenseMapKeyInfo<void*>::getHashValue(Val.second);
  }
  static bool isPod() { return true; }
};

typedef DenseMap<LayoutKey, StructLayout*, DenseMapLayoutKeyInfo> LayoutInfoTy;
static ManagedStatic<LayoutInfoTy> LayoutInfo;


TargetData::~TargetData() {
  if (LayoutInfo.isConstructed()) {
    // Remove any layouts for this TD.
    LayoutInfoTy &TheMap = *LayoutInfo;
    for (LayoutInfoTy::iterator I = TheMap.begin(), E = TheMap.end();
         I != E; ) {
      if (I->first.first == this) {
        I->second->~StructLayout();
        free(I->second);
        TheMap.erase(I++);
      } else {
        ++I;
      }
    }
  }
}

const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
  LayoutInfoTy &TheMap = *LayoutInfo;
  
  StructLayout *&SL = TheMap[LayoutKey(this, Ty)];
  if (SL) return SL;

  // Otherwise, create the struct layout.  Because it is variable length, we 
  // malloc it, then use placement new.
  unsigned NumElts = Ty->getNumElements();
  StructLayout *L =
    (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1)*sizeof(uint64_t));
  
  // Set SL before calling StructLayout's ctor.  The ctor could cause other
  // entries to be added to TheMap, invalidating our reference.
  SL = L;
  
  new (L) StructLayout(Ty, *this);
    
  return L;
}

/// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
/// objects.  If a TargetData object is alive when types are being refined and
/// removed, this method must be called whenever a StructType is removed to
/// avoid a dangling pointer in this cache.
void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
  if (!LayoutInfo.isConstructed()) return;  // No cache.
  
  LayoutInfoTy::iterator I = LayoutInfo->find(LayoutKey(this, Ty));
  if (I != LayoutInfo->end()) {
    I->second->~StructLayout();
    free(I->second);
    LayoutInfo->erase(I);
  }
}


std::string TargetData::getStringRepresentation() const {
  std::stringstream repr;
  
  if (LittleEndian)
    repr << "e";
  else
    repr << "E";
  
  repr << "-p:" << (PointerMemSize * 8) << ":" << (PointerABIAlignment * 8);
  repr << "-d:" << (DoubleABIAlignment * 8) << ":"
       << (DoublePrefAlignment * 8);
  repr << "-f:" << (FloatABIAlignment * 8) << ":"
       << (FloatPrefAlignment * 8);
  repr << "-l:" << (LongABIAlignment * 8) << ":"
       << (LongPrefAlignment * 8);
  repr << "-i:" << (IntABIAlignment * 8) << ":"
       << (IntPrefAlignment * 8);
  repr << "-s:" << (ShortABIAlignment * 8) << ":"
       << (ShortPrefAlignment * 8);
  repr << "-b:" << (ByteABIAlignment * 8) << ":"
       << (BytePrefAlignment * 8);
  repr << "-B:" << (BoolABIAlignment * 8) << ":"
       << (BoolPrefAlignment * 8);
  repr << "-A:" << (AggMinPrefAlignment * 8);
  
  return repr.str();
}


static inline void getTypeInfoABI(const Type *Ty, const TargetData *TD,
                                  uint64_t &Size, unsigned char &Alignment) {
  assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
  switch (Ty->getTypeID()) {
  case Type::IntegerTyID: {
    unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
    if (BitWidth <= 8) {
      Size = 1; Alignment = TD->getByteABIAlignment();
    } else if (BitWidth <= 16) {
      Size = 2; Alignment = TD->getShortABIAlignment();
    } else if (BitWidth <= 32) {
      Size = 4; Alignment = TD->getIntABIAlignment();
    } else if (BitWidth <= 64) {
      Size = 8; Alignment = TD->getLongABIAlignment();
    } else {
      Size = ((BitWidth + 7) / 8) & ~1;
      Alignment = TD->getLongABIAlignment();
    }
    return;
  }
  case Type::VoidTyID:   Size = 1; Alignment = TD->getByteABIAlignment(); return;
  case Type::FloatTyID:  Size = 4; Alignment = TD->getFloatABIAlignment(); return;
  case Type::DoubleTyID: Size = 8; Alignment = TD->getDoubleABIAlignment(); return;
  case Type::LabelTyID:
  case Type::PointerTyID:
    Size = TD->getPointerSize(); Alignment = TD->getPointerABIAlignment();
    return;
  case Type::ArrayTyID: {
    const ArrayType *ATy = cast<ArrayType>(Ty);
    getTypeInfoABI(ATy->getElementType(), TD, Size, Alignment);
    unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
    Size = AlignedSize*ATy->getNumElements();
    return;
  }
  case Type::PackedTyID: {
    const PackedType *PTy = cast<PackedType>(Ty);
    getTypeInfoABI(PTy->getElementType(), TD, Size, Alignment);
    unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
    Size = AlignedSize*PTy->getNumElements();
    // FIXME: The alignments of specific packed types are target dependent.
    // For now, just set it to be equal to Size.
    Alignment = Size;
    return;
  }
  case Type::StructTyID: {
    // Get the layout annotation... which is lazily created on demand.
    const StructLayout *Layout = TD->getStructLayout(cast<StructType>(Ty));
    Size = Layout->getSizeInBytes(); Alignment = Layout->getAlignment();
    return;
  }

  default:
    assert(0 && "Bad type for getTypeInfo!!!");
    return;
  }
}

static inline void getTypeInfoPref(const Type *Ty, const TargetData *TD,
                                   uint64_t &Size, unsigned char &Alignment) {
  assert(Ty->isSized() && "Cannot getTypeInfoPref() on a type that is unsized!");
  switch (Ty->getTypeID()) {
  case Type::IntegerTyID: {
    unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
    if (BitWidth <= 8) {
      Size = 1; Alignment = TD->getBytePrefAlignment();
    } else if (BitWidth <= 16) {
      Size = 2; Alignment = TD->getShortPrefAlignment();
    } else if (BitWidth <= 32) {
      Size = 4; Alignment = TD->getIntPrefAlignment();
    } else if (BitWidth <= 64) {
      Size = 8; Alignment = TD->getLongPrefAlignment();
    } else
      assert(0 && "Integer types > 64 bits not supported.");
    return;
  }
  case Type::VoidTyID:
    Size = 1; Alignment = TD->getBytePrefAlignment();
    return;
  case Type::FloatTyID:
    Size = 4; Alignment = TD->getFloatPrefAlignment();
    return;
  case Type::DoubleTyID:
    Size = 8; Alignment = TD->getDoublePrefAlignment();
    return;
  case Type::LabelTyID:
  case Type::PointerTyID:
    Size = TD->getPointerSize(); Alignment = TD->getPointerPrefAlignment();
    return;
  case Type::ArrayTyID: {
    const ArrayType *ATy = cast<ArrayType>(Ty);
    getTypeInfoPref(ATy->getElementType(), TD, Size, Alignment);
    unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
    Size = AlignedSize*ATy->getNumElements();
    return;
  }
  case Type::PackedTyID: {
    const PackedType *PTy = cast<PackedType>(Ty);
    getTypeInfoPref(PTy->getElementType(), TD, Size, Alignment);
    unsigned AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
    Size = AlignedSize*PTy->getNumElements();
    // FIXME: The alignments of specific packed types are target dependent.
    // For now, just set it to be equal to Size.
    Alignment = Size;
    return;
  }
  case Type::StructTyID: {
    // Get the layout annotation... which is lazily created on demand;
    // enforce minimum aggregate alignment.
    const StructLayout *Layout = TD->getStructLayout(cast<StructType>(Ty));
    Size = Layout->getSizeInBytes();
    Alignment = std::max(Layout->getAlignment(),
                         (const unsigned int)TD->getAggMinPrefAlignment());
    return;
  }

  default:
    assert(0 && "Bad type for getTypeInfoPref!!!");
    return;
  }
}


uint64_t TargetData::getTypeSize(const Type *Ty) const {
  uint64_t Size;
  unsigned char Align;
  getTypeInfoABI(Ty, this, Size, Align);
  return Size;
}

uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
  if (Ty->isInteger())
    return cast<IntegerType>(Ty)->getBitWidth();

  uint64_t Size;
  unsigned char Align;
  getTypeInfoABI(Ty, this, Size, Align);
  return Size * 8;
}

unsigned char TargetData::getTypeAlignmentABI(const Type *Ty) const {
  uint64_t Size;
  unsigned char Align;
  getTypeInfoABI(Ty, this, Size, Align);
  return Align;
}

unsigned char TargetData::getTypeAlignmentPref(const Type *Ty) const {
  uint64_t Size;
  unsigned char Align;
  getTypeInfoPref(Ty, this, Size, Align);
  return Align;
}

unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
  unsigned Align = getTypeAlignmentPref(Ty);
  assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
  return Log2_32(Align);
}

/// getIntPtrType - Return an unsigned integer type that is the same size or
/// greater to the host pointer size.
const Type *TargetData::getIntPtrType() const {
  switch (getPointerSize()) {
  default: assert(0 && "Unknown pointer size!");
  case 2: return Type::Int16Ty;
  case 4: return Type::Int32Ty;
  case 8: return Type::Int64Ty;
  }
}


uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
                                      unsigned NumIndices) const {
  const Type *Ty = ptrTy;
  assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
  uint64_t Result = 0;

  generic_gep_type_iterator<Value* const*>
    TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
  for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
    if (const StructType *STy = dyn_cast<StructType>(*TI)) {
      assert(Indices[CurIDX]->getType() == Type::Int32Ty &&"Illegal struct idx");
      unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();

      // Get structure layout information...
      const StructLayout *Layout = getStructLayout(STy);

      // Add in the offset, as calculated by the structure layout info...
      Result += Layout->getElementOffset(FieldNo);

      // Update Ty to refer to current element
      Ty = STy->getElementType(FieldNo);
    } else {
      // Update Ty to refer to current element
      Ty = cast<SequentialType>(Ty)->getElementType();

      // Get the array index and the size of each array element.
      int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
      Result += arrayIdx * (int64_t)getTypeSize(Ty);
    }
  }

  return Result;
}

/// getPreferredAlignmentLog - Return the preferred alignment of the
/// specified global, returned in log form.  This includes an explicitly
/// requested alignment (if the global has one).
unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
  const Type *ElemType = GV->getType()->getElementType();
  unsigned Alignment = getPreferredTypeAlignmentShift(ElemType);
  if (GV->getAlignment() > (1U << Alignment))
    Alignment = Log2_32(GV->getAlignment());
  
  if (GV->hasInitializer()) {
    if (Alignment < 4) {
      // If the global is not external, see if it is large.  If so, give it a
      // larger alignment.
      if (getTypeSize(ElemType) > 128)
        Alignment = 4;    // 16-byte alignment.
    }
  }
  return Alignment;
}