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/DenseMap.h"
  27 #include "llvm/ADT/StringExtras.h"
  28 #include <algorithm>
  29 #include <cstdlib>
  30 #include <sstream>
  31 using namespace llvm;
  32
  33 // Handle the Pass registration stuff necessary to use TargetData's.
  34 namespace {
  35   // Register the default SparcV9 implementation...
  36   RegisterPass<TargetData> X("targetdata", "Target Data Layout");
  37 }
  38 char TargetData::ID = 0;
  39
  40 //===----------------------------------------------------------------------===//
  41 // Support for StructLayout
  42 //===----------------------------------------------------------------------===//
  43
  44 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
  45   StructAlignment = 0;
  46   StructSize = 0;
  47   NumElements = ST->getNumElements();
  48
  49   // Loop over each of the elements, placing them in memory...
  50   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  51     const Type *Ty = ST->getElementType(i);
  52     unsigned TyAlign;
  53     uint64_t TySize;
  54     TyAlign = (ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty));
  55     TySize = TD.getTypeSize(Ty);
  56
  57     // Add padding if necessary to make the data element aligned properly...
  58     if (StructSize % TyAlign != 0)
  59       StructSize = (StructSize/TyAlign + 1) * TyAlign;   // Add padding...
  60
  61     // Keep track of maximum alignment constraint
  62     StructAlignment = std::max(TyAlign, StructAlignment);
  63
  64     MemberOffsets[i] = StructSize;
  65     StructSize += TySize;                 // Consume space for this data item
  66   }
  67
  68   // Empty structures have alignment of 1 byte.
  69   if (StructAlignment == 0) StructAlignment = 1;
  70
  71   // Add padding to the end of the struct so that it could be put in an array
  72   // and all array elements would be aligned correctly.
  73   if (StructSize % StructAlignment != 0)
  74     StructSize = (StructSize/StructAlignment + 1) * StructAlignment;
  75 }
  76
  77
  78 /// getElementContainingOffset - Given a valid offset into the structure,
  79 /// return the structure index that contains it.
  80 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  81   const uint64_t *SI =
  82     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  83   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  84   --SI;
  85   assert(*SI <= Offset && "upper_bound didn't work");
  86   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  87          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  88          "Upper bound didn't work!");
  89
  90   // Multiple fields can have the same offset if any of them are zero sized.
  91   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  92   // at the i32 element, because it is the last element at that offset.  This is
  93   // the right one to return, because anything after it will have a higher
  94   // offset, implying that this element is non-empty.
  95   return SI-&MemberOffsets[0];
  96 }
  97
  98 //===----------------------------------------------------------------------===//
  99 // TargetAlignElem, TargetAlign support
 100 //===----------------------------------------------------------------------===//
 101
 102 TargetAlignElem
 103 TargetAlignElem::get(AlignTypeEnum align_type, unsigned char abi_align,
 104                      unsigned char pref_align, uint32_t bit_width) {
 105   TargetAlignElem retval;
 106   retval.AlignType = align_type;
 107   retval.ABIAlign = abi_align;
 108   retval.PrefAlign = pref_align;
 109   retval.TypeBitWidth = bit_width;
 110   return retval;
 111 }
 112
 113 bool
 114 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
 115   return (AlignType == rhs.AlignType
 116           && ABIAlign == rhs.ABIAlign
 117           && PrefAlign == rhs.PrefAlign
 118           && TypeBitWidth == rhs.TypeBitWidth);
 119 }
 120
 121 std::ostream &
 122 TargetAlignElem::dump(std::ostream &os) const {
 123   return os << AlignType
 124             << TypeBitWidth
 125             << ":" << (int) (ABIAlign * 8)
 126             << ":" << (int) (PrefAlign * 8);
 127 }
 128
 129 const TargetAlignElem TargetData::InvalidAlignmentElem =
 130                 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
 131
 132 //===----------------------------------------------------------------------===//
 133 //                       TargetData Class Implementation
 134 //===----------------------------------------------------------------------===//
 135
 136 /*!
 137  A TargetDescription string consists of a sequence of hyphen-delimited
 138  specifiers for target endianness, pointer size and alignments, and various
 139  primitive type sizes and alignments. A typical string looks something like:
 140  <br><br>
 141  "E-p:32:32:32-i1:8:8-i8:8:8-i32:32:32-i64:32:64-f32:32:32-f64:32:64"
 142  <br><br>
 143  (note: this string is not fully specified and is only an example.)
 144  \p
 145  Alignments come in two flavors: ABI and preferred. ABI alignment (abi_align,
 146  below) dictates how a type will be aligned within an aggregate and when used
 147  as an argument.  Preferred alignment (pref_align, below) determines a type's
 148  alignment when emitted as a global.
 149  \p
 150  Specifier string details:
 151  <br><br>
 152  <i>[E|e]</i>: Endianness. "E" specifies a big-endian target data model, "e"
 153  specifies a little-endian target data model.
 154  <br><br>
 155  <i>p:@verbatim<size>:<abi_align>:<pref_align>@endverbatim</i>: Pointer size,
 156  ABI and preferred alignment.
 157  <br><br>
 158  <i>@verbatim<type><size>:<abi_align>:<pref_align>@endverbatim</i>: Numeric type alignment. Type is
 159  one of <i>i|f|v|a</i>, corresponding to integer, floating point, vector (aka
 160  packed) or aggregate.  Size indicates the size, e.g., 32 or 64 bits.
 161  \p
 162  The default string, fully specified is:
 163  <br><br>
 164  "E-p:64:64:64-a0:0:0-f32:32:32-f64:0:64"
 165  "-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:0:64"
 166  "-v64:64:64-v128:128:128"
 167  <br><br>
 168  Note that in the case of aggregates, 0 is the default ABI and preferred
 169  alignment. This is a special case, where the aggregate's computed worst-case
 170  alignment will be used.
 171  */
 172 void TargetData::init(const std::string &TargetDescription) {
 173   std::string temp = TargetDescription;
 174
 175   LittleEndian = false;
 176   PointerMemSize = 8;
 177   PointerABIAlign   = 8;
 178   PointerPrefAlign = PointerABIAlign;
 179
 180   // Default alignments
 181   setAlignment(INTEGER_ALIGN,   1,  1, 1);   // Bool
 182   setAlignment(INTEGER_ALIGN,   1,  1, 8);   // Byte
 183   setAlignment(INTEGER_ALIGN,   2,  2, 16);  // short
 184   setAlignment(INTEGER_ALIGN,   4,  4, 32);  // int
 185   setAlignment(INTEGER_ALIGN,   4,  8, 64);  // long
 186   setAlignment(FLOAT_ALIGN,     4,  4, 32);  // float
 187   setAlignment(FLOAT_ALIGN,     8,  8, 64);  // double
 188   setAlignment(VECTOR_ALIGN,    8,  8, 64);  // v2i32
 189   setAlignment(VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
 190   setAlignment(AGGREGATE_ALIGN, 0,  8,  0);  // struct, union, class, ...
 191
 192   while (!temp.empty()) {
 193     std::string token = getToken(temp, "-");
 194     std::string arg0 = getToken(token, ":");
 195     const char *p = arg0.c_str();
 196     switch(*p) {
 197     case 'E':
 198       LittleEndian = false;
 199       break;
 200     case 'e':
 201       LittleEndian = true;
 202       break;
 203     case 'p':
 204       PointerMemSize = atoi(getToken(token,":").c_str()) / 8;
 205       PointerABIAlign = atoi(getToken(token,":").c_str()) / 8;
 206       PointerPrefAlign = atoi(getToken(token,":").c_str()) / 8;
 207       if (PointerPrefAlign == 0)
 208         PointerPrefAlign = PointerABIAlign;
 209       break;
 210     case 'i':
 211     case 'v':
 212     case 'f':
 213     case 'a':
 214     case 's': {
 215       AlignTypeEnum align_type;
 216       switch(*p) {
 217         case 'i': align_type = INTEGER_ALIGN; break;
 218         case 'v': align_type = VECTOR_ALIGN; break;
 219         case 'f': align_type = FLOAT_ALIGN; break;
 220         case 'a': align_type = AGGREGATE_ALIGN; break;
 221         case 's': align_type = STACK_ALIGN; break;
 222       }
 223       uint32_t size = (uint32_t) atoi(++p);
 224       unsigned char abi_align = atoi(getToken(token, ":").c_str()) / 8;
 225       unsigned char pref_align = atoi(getToken(token, ":").c_str()) / 8;
 226       if (pref_align == 0)
 227         pref_align = abi_align;
 228       setAlignment(align_type, abi_align, pref_align, size);
 229       break;
 230     }
 231     default:
 232       break;
 233     }
 234   }
 235 }
 236
 237 TargetData::TargetData(const Module *M)
 238   : ImmutablePass((intptr_t)&ID) {
 239   init(M->getDataLayout());
 240 }
 241
 242 void
 243 TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
 244                          unsigned char pref_align, uint32_t bit_width) {
 245   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 246     if (Alignments[i].AlignType == align_type &&
 247         Alignments[i].TypeBitWidth == bit_width) {
 248       // Update the abi, preferred alignments.
 249       Alignments[i].ABIAlign = abi_align;
 250       Alignments[i].PrefAlign = pref_align;
 251       return;
 252     }
 253   }
 254
 255   Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
 256                                             pref_align, bit_width));
 257 }
 258
 259 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 260 /// preferred if ABIInfo = false) the target wants for the specified datatype.
 261 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
 262                                       uint32_t BitWidth, bool ABIInfo) const {
 263   // Check to see if we have an exact match and remember the best match we see.
 264   int BestMatchIdx = -1;
 265   int LargestInt = -1;
 266   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 267     if (Alignments[i].AlignType == AlignType &&
 268         Alignments[i].TypeBitWidth == BitWidth)
 269       return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
 270
 271     // The best match so far depends on what we're looking for.
 272     if (AlignType == VECTOR_ALIGN) {
 273       // If this is a specification for a smaller vector type, we will fall back
 274       // to it.  This happens because <128 x double> can be implemented in terms
 275       // of 64 <2 x double>.
 276       if (Alignments[i].AlignType == VECTOR_ALIGN &&
 277           Alignments[i].TypeBitWidth < BitWidth) {
 278         // Verify that we pick the biggest of the fallbacks.
 279         if (BestMatchIdx == -1 ||
 280             Alignments[BestMatchIdx].TypeBitWidth < BitWidth)
 281           BestMatchIdx = i;
 282       }
 283     } else if (AlignType == INTEGER_ALIGN &&
 284                Alignments[i].AlignType == INTEGER_ALIGN) {
 285       // The "best match" for integers is the smallest size that is larger than
 286       // the BitWidth requested.
 287       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 288            Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 289         BestMatchIdx = i;
 290       // However, if there isn't one that's larger, then we must use the
 291       // largest one we have (see below)
 292       if (LargestInt == -1 ||
 293           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 294         LargestInt = i;
 295     }
 296   }
 297
 298   // For integers, if we didn't find a best match, use the largest one found.
 299   if (BestMatchIdx == -1)
 300     BestMatchIdx = LargestInt;
 301
 302   // Okay, we didn't find an exact solution.  Fall back here depending on what
 303   // is being looked for.
 304   assert(BestMatchIdx != -1 && "Didn't find alignment info for this datatype!");
 305
 306   // Since we got a "best match" index, just return it.
 307   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 308                  : Alignments[BestMatchIdx].PrefAlign;
 309 }
 310
 311 /// LayoutInfo - The lazy cache of structure layout information maintained by
 312 /// TargetData.  Note that the struct types must have been free'd before
 313 /// llvm_shutdown is called (and thus this is deallocated) because all the
 314 /// targets with cached elements should have been destroyed.
 315 ///
 316 typedef std::pair<const TargetData*,const StructType*> LayoutKey;
 317
 318 struct DenseMapLayoutKeyInfo {
 319   static inline LayoutKey getEmptyKey() { return LayoutKey(0, 0); }
 320   static inline LayoutKey getTombstoneKey() {
 321     return LayoutKey((TargetData*)(intptr_t)-1, 0);
 322   }
 323   static unsigned getHashValue(const LayoutKey &Val) {
 324     return DenseMapInfo<void*>::getHashValue(Val.first) ^
 325            DenseMapInfo<void*>::getHashValue(Val.second);
 326   }
 327   static bool isEqual(const LayoutKey &LHS, const LayoutKey &RHS) {
 328     return LHS == RHS;
 329   }
 330
 331   static bool isPod() { return true; }
 332 };
 333
 334 typedef DenseMap<LayoutKey, StructLayout*, DenseMapLayoutKeyInfo> LayoutInfoTy;
 335 static ManagedStatic<LayoutInfoTy> LayoutInfo;
 336
 337
 338 TargetData::~TargetData() {
 339   if (LayoutInfo.isConstructed()) {
 340     // Remove any layouts for this TD.
 341     LayoutInfoTy &TheMap = *LayoutInfo;
 342     for (LayoutInfoTy::iterator I = TheMap.begin(), E = TheMap.end();
 343          I != E; ) {
 344       if (I->first.first == this) {
 345         I->second->~StructLayout();
 346         free(I->second);
 347         TheMap.erase(I++);
 348       } else {
 349         ++I;
 350       }
 351     }
 352   }
 353 }
 354
 355 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
 356   LayoutInfoTy &TheMap = *LayoutInfo;
 357
 358   StructLayout *&SL = TheMap[LayoutKey(this, Ty)];
 359   if (SL) return SL;
 360
 361   // Otherwise, create the struct layout.  Because it is variable length, we
 362   // malloc it, then use placement new.
 363   int NumElts = Ty->getNumElements();
 364   StructLayout *L =
 365     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1)*sizeof(uint64_t));
 366
 367   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 368   // entries to be added to TheMap, invalidating our reference.
 369   SL = L;
 370
 371   new (L) StructLayout(Ty, *this);
 372   return L;
 373 }
 374
 375 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
 376 /// objects.  If a TargetData object is alive when types are being refined and
 377 /// removed, this method must be called whenever a StructType is removed to
 378 /// avoid a dangling pointer in this cache.
 379 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
 380   if (!LayoutInfo.isConstructed()) return;  // No cache.
 381
 382   LayoutInfoTy::iterator I = LayoutInfo->find(LayoutKey(this, Ty));
 383   if (I != LayoutInfo->end()) {
 384     I->second->~StructLayout();
 385     free(I->second);
 386     LayoutInfo->erase(I);
 387   }
 388 }
 389
 390
 391 std::string TargetData::getStringRepresentation() const {
 392   std::string repr;
 393   repr.append(LittleEndian ? "e" : "E");
 394   repr.append("-p:").append(itostr((int64_t) (PointerMemSize * 8))).
 395       append(":").append(itostr((int64_t) (PointerABIAlign * 8))).
 396       append(":").append(itostr((int64_t) (PointerPrefAlign * 8)));
 397   for (align_const_iterator I = Alignments.begin();
 398        I != Alignments.end();
 399        ++I) {
 400     repr.append("-").append(1, (char) I->AlignType).
 401       append(utostr((int64_t) I->TypeBitWidth)).
 402       append(":").append(utostr((uint64_t) (I->ABIAlign * 8))).
 403       append(":").append(utostr((uint64_t) (I->PrefAlign * 8)));
 404   }
 405   return repr;
 406 }
 407
 408
 409 uint64_t TargetData::getTypeSize(const Type *Ty) const {
 410   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 411   switch (Ty->getTypeID()) {
 412   case Type::LabelTyID:
 413   case Type::PointerTyID:
 414     return getPointerSize();
 415   case Type::ArrayTyID: {
 416     const ArrayType *ATy = cast<ArrayType>(Ty);
 417     uint64_t Size;
 418     unsigned char Alignment;
 419     Size = getTypeSize(ATy->getElementType());
 420     Alignment = getABITypeAlignment(ATy->getElementType());
 421     uint64_t AlignedSize = (Size + Alignment - 1)/Alignment*Alignment;
 422     return AlignedSize*ATy->getNumElements();
 423   }
 424   case Type::StructTyID: {
 425     // Get the layout annotation... which is lazily created on demand.
 426     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 427     return Layout->getSizeInBytes();
 428   }
 429   case Type::IntegerTyID: {
 430     unsigned BitWidth = cast<IntegerType>(Ty)->getBitWidth();
 431     if (BitWidth <= 8) {
 432       return 1;
 433     } else if (BitWidth <= 16) {
 434       return 2;
 435     } else if (BitWidth <= 32) {
 436       return 4;
 437     } else if (BitWidth <= 64) {
 438       return 8;
 439     } else {
 440       // The size of this > 64 bit type is chosen as a multiple of the
 441       // preferred alignment of the largest "native" size the target supports.
 442       // We first obtain the the alignment info for this type and then compute
 443       // the next largest multiple of that size.
 444       uint64_t size = getAlignmentInfo(INTEGER_ALIGN, BitWidth, false) * 8;
 445       return (((BitWidth / (size)) + (BitWidth % size != 0)) * size) / 8;
 446     }
 447     break;
 448   }
 449   case Type::VoidTyID:
 450     return 1;
 451   case Type::FloatTyID:
 452     return 4;
 453   case Type::DoubleTyID:
 454     return 8;
 455   case Type::PPC_FP128TyID:
 456   case Type::FP128TyID:
 457     return 16;
 458   // In memory objects this is always aligned to a higher boundary, but
 459   // only 10 bytes contain information.
 460   case Type::X86_FP80TyID:
 461     return 10;
 462   case Type::VectorTyID: {
 463     const VectorType *PTy = cast<VectorType>(Ty);
 464     return PTy->getBitWidth() / 8;
 465   }
 466   default:
 467     assert(0 && "TargetData::getTypeSize(): Unsupported type");
 468     break;
 469   }
 470   return 0;
 471 }
 472
 473 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
 474   if (Ty->isInteger())
 475     return cast<IntegerType>(Ty)->getBitWidth();
 476   else
 477     return getTypeSize(Ty) * 8;
 478 }
 479
 480 uint64_t TargetData::getABITypeSizeInBits(const Type *Ty) const {
 481   if (Ty->isInteger())
 482     return cast<IntegerType>(Ty)->getBitWidth();
 483   else
 484     return getABITypeSize(Ty) * 8;
 485 }
 486 /*!
 487   \param abi_or_pref Flag that determines which alignment is returned. true
 488   returns the ABI alignment, false returns the preferred alignment.
 489   \param Ty The underlying type for which alignment is determined.
 490
 491   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 492   == false) for the requested type \a Ty.
 493  */
 494 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
 495   int AlignType = -1;
 496
 497   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 498   switch (Ty->getTypeID()) {
 499   /* Early escape for the non-numeric types */
 500   case Type::LabelTyID:
 501   case Type::PointerTyID:
 502     return (abi_or_pref
 503             ? getPointerABIAlignment()
 504             : getPointerPrefAlignment());
 505   case Type::ArrayTyID:
 506     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 507
 508   case Type::StructTyID: {
 509     // Packed structure types always have an ABI alignment of one.
 510     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 511       return 1;
 512
 513     // Get the layout annotation... which is lazily created on demand.
 514     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 515     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref);
 516     return std::max(Align, (unsigned)Layout->getAlignment());
 517   }
 518   case Type::IntegerTyID:
 519   case Type::VoidTyID:
 520     AlignType = INTEGER_ALIGN;
 521     break;
 522   case Type::FloatTyID:
 523   case Type::DoubleTyID:
 524   // PPC_FP128TyID and FP128TyID have different data contents, but the
 525   // same size and alignment, so they look the same here.
 526   case Type::PPC_FP128TyID:
 527   case Type::FP128TyID:
 528   case Type::X86_FP80TyID:
 529     AlignType = FLOAT_ALIGN;
 530     break;
 531   case Type::VectorTyID: {
 532     const VectorType *VTy = cast<VectorType>(Ty);
 533     // Degenerate vectors are assumed to be scalar-ized
 534     if (VTy->getNumElements() == 1)
 535       return getAlignment(VTy->getElementType(), abi_or_pref);
 536     else
 537       AlignType = VECTOR_ALIGN;
 538     break;
 539   }
 540   default:
 541     assert(0 && "Bad type for getAlignment!!!");
 542     break;
 543   }
 544
 545   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSize(Ty) * 8,
 546                           abi_or_pref);
 547 }
 548
 549 unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
 550   return getAlignment(Ty, true);
 551 }
 552
 553 unsigned char TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
 554   for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
 555     if (Alignments[i].AlignType == STACK_ALIGN)
 556       return Alignments[i].ABIAlign;
 557
 558   return getABITypeAlignment(Ty);
 559 }
 560
 561 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
 562   return getAlignment(Ty, false);
 563 }
 564
 565 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
 566   unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
 567   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 568   return Log2_32(Align);
 569 }
 570
 571 /// getIntPtrType - Return an unsigned integer type that is the same size or
 572 /// greater to the host pointer size.
 573 const Type *TargetData::getIntPtrType() const {
 574   return IntegerType::get(getPointerSizeInBits());
 575 }
 576
 577
 578 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
 579                                       unsigned NumIndices) const {
 580   const Type *Ty = ptrTy;
 581   assert(isa<PointerType>(Ty) && "Illegal argument for getIndexedOffset()");
 582   uint64_t Result = 0;
 583
 584   generic_gep_type_iterator<Value* const*>
 585     TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
 586   for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
 587     if (const StructType *STy = dyn_cast<StructType>(*TI)) {
 588       assert(Indices[CurIDX]->getType() == Type::Int32Ty &&
 589              "Illegal struct idx");
 590       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 591
 592       // Get structure layout information...
 593       const StructLayout *Layout = getStructLayout(STy);
 594
 595       // Add in the offset, as calculated by the structure layout info...
 596       Result += Layout->getElementOffset(FieldNo);
 597
 598       // Update Ty to refer to current element
 599       Ty = STy->getElementType(FieldNo);
 600     } else {
 601       // Update Ty to refer to current element
 602       Ty = cast<SequentialType>(Ty)->getElementType();
 603
 604       // Get the array index and the size of each array element.
 605       int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue();
 606       Result += arrayIdx * (int64_t)getTypeSize(Ty);
 607     }
 608   }
 609
 610   return Result;
 611 }
 612
 613 /// getPreferredAlignmentLog - Return the preferred alignment of the
 614 /// specified global, returned in log form.  This includes an explicitly
 615 /// requested alignment (if the global has one).
 616 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 617   const Type *ElemType = GV->getType()->getElementType();
 618   unsigned Alignment = getPreferredTypeAlignmentShift(ElemType);
 619   if (GV->getAlignment() > (1U << Alignment))
 620     Alignment = Log2_32(GV->getAlignment());
 621
 622   if (GV->hasInitializer()) {
 623     if (Alignment < 4) {
 624       // If the global is not external, see if it is large.  If so, give it a
 625       // larger alignment.
 626       if (getTypeSize(ElemType) > 128)
 627         Alignment = 4;    // 16-byte alignment.
 628     }
 629   }
 630   return Alignment;
 631 }