lib/Target/TargetData.cpp

   1 //===-- TargetData.cpp - Data size & alignment routines --------------------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/Constants.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Module.h"
  23 #include "llvm/Support/GetElementPtrTypeIterator.h"
  24 #include "llvm/Support/MathExtras.h"
  25 #include "llvm/Support/ManagedStatic.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include "llvm/System/Mutex.h"
  29 #include "llvm/ADT/DenseMap.h"
  30 #include <algorithm>
  31 #include <cstdlib>
  32 using namespace llvm;
  33
  34 // Handle the Pass registration stuff necessary to use TargetData's.
  35
  36 // Register the default SparcV9 implementation...
  37 static RegisterPass<TargetData> X("targetdata", "Target Data Layout", false,
  38                                   true);
  39 char TargetData::ID = 0;
  40
  41 //===----------------------------------------------------------------------===//
  42 // Support for StructLayout
  43 //===----------------------------------------------------------------------===//
  44
  45 StructLayout::StructLayout(const StructType *ST, const TargetData &TD) {
  46   StructAlignment = 0;
  47   StructSize = 0;
  48   NumElements = ST->getNumElements();
  49
  50   // Loop over each of the elements, placing them in memory.
  51   for (unsigned i = 0, e = NumElements; i != e; ++i) {
  52     const Type *Ty = ST->getElementType(i);
  53     unsigned TyAlign = ST->isPacked() ? 1 : TD.getABITypeAlignment(Ty);
  54
  55     // Add padding if necessary to align the data element properly.
  56     if ((StructSize & (TyAlign-1)) != 0)
  57       StructSize = TargetData::RoundUpAlignment(StructSize, TyAlign);
  58
  59     // Keep track of maximum alignment constraint.
  60     StructAlignment = std::max(TyAlign, StructAlignment);
  61
  62     MemberOffsets[i] = StructSize;
  63     StructSize += TD.getTypeAllocSize(Ty); // Consume space for this data item
  64   }
  65
  66   // Empty structures have alignment of 1 byte.
  67   if (StructAlignment == 0) StructAlignment = 1;
  68
  69   // Add padding to the end of the struct so that it could be put in an array
  70   // and all array elements would be aligned correctly.
  71   if ((StructSize & (StructAlignment-1)) != 0)
  72     StructSize = TargetData::RoundUpAlignment(StructSize, StructAlignment);
  73 }
  74
  75
  76 /// getElementContainingOffset - Given a valid offset into the structure,
  77 /// return the structure index that contains it.
  78 unsigned StructLayout::getElementContainingOffset(uint64_t Offset) const {
  79   const uint64_t *SI =
  80     std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset);
  81   assert(SI != &MemberOffsets[0] && "Offset not in structure type!");
  82   --SI;
  83   assert(*SI <= Offset && "upper_bound didn't work");
  84   assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) &&
  85          (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) &&
  86          "Upper bound didn't work!");
  87
  88   // Multiple fields can have the same offset if any of them are zero sized.
  89   // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop
  90   // at the i32 element, because it is the last element at that offset.  This is
  91   // the right one to return, because anything after it will have a higher
  92   // offset, implying that this element is non-empty.
  93   return SI-&MemberOffsets[0];
  94 }
  95
  96 //===----------------------------------------------------------------------===//
  97 // TargetAlignElem, TargetAlign support
  98 //===----------------------------------------------------------------------===//
  99
 100 TargetAlignElem
 101 TargetAlignElem::get(AlignTypeEnum align_type, unsigned char abi_align,
 102                      unsigned char pref_align, uint32_t bit_width) {
 103   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 104   TargetAlignElem retval;
 105   retval.AlignType = align_type;
 106   retval.ABIAlign = abi_align;
 107   retval.PrefAlign = pref_align;
 108   retval.TypeBitWidth = bit_width;
 109   return retval;
 110 }
 111
 112 bool
 113 TargetAlignElem::operator==(const TargetAlignElem &rhs) const {
 114   return (AlignType == rhs.AlignType
 115           && ABIAlign == rhs.ABIAlign
 116           && PrefAlign == rhs.PrefAlign
 117           && TypeBitWidth == rhs.TypeBitWidth);
 118 }
 119
 120 const TargetAlignElem TargetData::InvalidAlignmentElem =
 121                 TargetAlignElem::get((AlignTypeEnum) -1, 0, 0, 0);
 122
 123 //===----------------------------------------------------------------------===//
 124 //                       TargetData Class Implementation
 125 //===----------------------------------------------------------------------===//
 126
 127 /// getInt - Get an integer ignoring errors.
 128 static unsigned getInt(StringRef R) {
 129   unsigned Result = 0;
 130   R.getAsInteger(10, Result);
 131   return Result;
 132 }
 133
 134 void TargetData::init(StringRef Desc) {
 135   LayoutMap = 0;
 136   LittleEndian = false;
 137   PointerMemSize = 8;
 138   PointerABIAlign = 8;
 139   PointerPrefAlign = PointerABIAlign;
 140
 141   // Default alignments
 142   setAlignment(INTEGER_ALIGN,   1,  1, 1);   // i1
 143   setAlignment(INTEGER_ALIGN,   1,  1, 8);   // i8
 144   setAlignment(INTEGER_ALIGN,   2,  2, 16);  // i16
 145   setAlignment(INTEGER_ALIGN,   4,  4, 32);  // i32
 146   setAlignment(INTEGER_ALIGN,   4,  8, 64);  // i64
 147   setAlignment(FLOAT_ALIGN,     4,  4, 32);  // float
 148   setAlignment(FLOAT_ALIGN,     8,  8, 64);  // double
 149   setAlignment(VECTOR_ALIGN,    8,  8, 64);  // v2i32, v1i64, ...
 150   setAlignment(VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
 151   setAlignment(AGGREGATE_ALIGN, 0,  8,  0);  // struct
 152
 153   while (!Desc.empty()) {
 154     std::pair<StringRef, StringRef> Split = Desc.split('-');
 155     StringRef Token = Split.first;
 156     Desc = Split.second;
 157
 158     if (Token.empty())
 159       continue;
 160
 161     Split = Token.split(':');
 162     StringRef Specifier = Split.first;
 163     Token = Split.second;
 164
 165     assert(!Specifier.empty() && "Can't be empty here");
 166
 167     switch (Specifier[0]) {
 168     case 'E':
 169       LittleEndian = false;
 170       break;
 171     case 'e':
 172       LittleEndian = true;
 173       break;
 174     case 'p':
 175       Split = Token.split(':');
 176       PointerMemSize = getInt(Split.first) / 8;
 177       Split = Split.second.split(':');
 178       PointerABIAlign = getInt(Split.first) / 8;
 179       Split = Split.second.split(':');
 180       PointerPrefAlign = getInt(Split.first) / 8;
 181       if (PointerPrefAlign == 0)
 182         PointerPrefAlign = PointerABIAlign;
 183       break;
 184     case 'i':
 185     case 'v':
 186     case 'f':
 187     case 'a':
 188     case 's': {
 189       AlignTypeEnum AlignType;
 190       switch (Specifier[0]) {
 191       default:
 192       case 'i': AlignType = INTEGER_ALIGN; break;
 193       case 'v': AlignType = VECTOR_ALIGN; break;
 194       case 'f': AlignType = FLOAT_ALIGN; break;
 195       case 'a': AlignType = AGGREGATE_ALIGN; break;
 196       case 's': AlignType = STACK_ALIGN; break;
 197       }
 198       unsigned Size = getInt(Specifier.substr(1));
 199       Split = Token.split(':');
 200       unsigned char ABIAlign = getInt(Split.first) / 8;
 201
 202       Split = Split.second.split(':');
 203       unsigned char PrefAlign = getInt(Split.first) / 8;
 204       if (PrefAlign == 0)
 205         PrefAlign = ABIAlign;
 206       setAlignment(AlignType, ABIAlign, PrefAlign, Size);
 207       break;
 208     }
 209     case 'n':  // Native integer types.
 210       Specifier = Specifier.substr(1);
 211       do {
 212         if (unsigned Width = getInt(Specifier))
 213           LegalIntWidths.push_back(Width);
 214         Split = Token.split(':');
 215         Specifier = Split.first;
 216         Token = Split.second;
 217       } while (!Specifier.empty() || !Token.empty());
 218       break;
 219
 220     default:
 221       break;
 222     }
 223   }
 224 }
 225
 226 /// Default ctor.
 227 ///
 228 /// @note This has to exist, because this is a pass, but it should never be
 229 /// used.
 230 TargetData::TargetData() : ImmutablePass(&ID) {
 231   report_fatal_error("Bad TargetData ctor used.  "
 232                     "Tool did not specify a TargetData to use?");
 233 }
 234
 235 TargetData::TargetData(const Module *M)
 236   : ImmutablePass(&ID) {
 237   init(M->getDataLayout());
 238 }
 239
 240 void
 241 TargetData::setAlignment(AlignTypeEnum align_type, unsigned char abi_align,
 242                          unsigned char pref_align, uint32_t bit_width) {
 243   assert(abi_align <= pref_align && "Preferred alignment worse than ABI!");
 244   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 245     if (Alignments[i].AlignType == align_type &&
 246         Alignments[i].TypeBitWidth == bit_width) {
 247       // Update the abi, preferred alignments.
 248       Alignments[i].ABIAlign = abi_align;
 249       Alignments[i].PrefAlign = pref_align;
 250       return;
 251     }
 252   }
 253
 254   Alignments.push_back(TargetAlignElem::get(align_type, abi_align,
 255                                             pref_align, bit_width));
 256 }
 257
 258 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 259 /// preferred if ABIInfo = false) the target wants for the specified datatype.
 260 unsigned TargetData::getAlignmentInfo(AlignTypeEnum AlignType,
 261                                       uint32_t BitWidth, bool ABIInfo,
 262                                       const Type *Ty) 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 == INTEGER_ALIGN &&
 273          Alignments[i].AlignType == INTEGER_ALIGN) {
 274       // The "best match" for integers is the smallest size that is larger than
 275       // the BitWidth requested.
 276       if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
 277            Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
 278         BestMatchIdx = i;
 279       // However, if there isn't one that's larger, then we must use the
 280       // largest one we have (see below)
 281       if (LargestInt == -1 ||
 282           Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
 283         LargestInt = i;
 284     }
 285   }
 286
 287   // Okay, we didn't find an exact solution.  Fall back here depending on what
 288   // is being looked for.
 289   if (BestMatchIdx == -1) {
 290     // If we didn't find an integer alignment, fall back on most conservative.
 291     if (AlignType == INTEGER_ALIGN) {
 292       BestMatchIdx = LargestInt;
 293     } else {
 294       assert(AlignType == VECTOR_ALIGN && "Unknown alignment type!");
 295
 296       // By default, use natural alignment for vector types. This is consistent
 297       // with what clang and llvm-gcc do.
 298       unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
 299       Align *= cast<VectorType>(Ty)->getNumElements();
 300       // If the alignment is not a power of 2, round up to the next power of 2.
 301       // This happens for non-power-of-2 length vectors.
 302       if (Align & (Align-1))
 303         Align = llvm::NextPowerOf2(Align);
 304       return Align;
 305     }
 306   }
 307
 308   // Since we got a "best match" index, just return it.
 309   return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
 310                  : Alignments[BestMatchIdx].PrefAlign;
 311 }
 312
 313 namespace {
 314
 315 class StructLayoutMap : public AbstractTypeUser {
 316   typedef DenseMap<const StructType*, StructLayout*> LayoutInfoTy;
 317   LayoutInfoTy LayoutInfo;
 318
 319   void RemoveEntry(LayoutInfoTy::iterator I, bool WasAbstract) {
 320     I->second->~StructLayout();
 321     free(I->second);
 322     if (WasAbstract)
 323       I->first->removeAbstractTypeUser(this);
 324     LayoutInfo.erase(I);
 325   }
 326
 327
 328   /// refineAbstractType - The callback method invoked when an abstract type is
 329   /// resolved to another type.  An object must override this method to update
 330   /// its internal state to reference NewType instead of OldType.
 331   ///
 332   virtual void refineAbstractType(const DerivedType *OldTy,
 333                                   const Type *) {
 334     LayoutInfoTy::iterator I = LayoutInfo.find(cast<const StructType>(OldTy));
 335     assert(I != LayoutInfo.end() && "Using type but not in map?");
 336     RemoveEntry(I, true);
 337   }
 338
 339   /// typeBecameConcrete - The other case which AbstractTypeUsers must be aware
 340   /// of is when a type makes the transition from being abstract (where it has
 341   /// clients on its AbstractTypeUsers list) to concrete (where it does not).
 342   /// This method notifies ATU's when this occurs for a type.
 343   ///
 344   virtual void typeBecameConcrete(const DerivedType *AbsTy) {
 345     LayoutInfoTy::iterator I = LayoutInfo.find(cast<const StructType>(AbsTy));
 346     assert(I != LayoutInfo.end() && "Using type but not in map?");
 347     RemoveEntry(I, true);
 348   }
 349
 350 public:
 351   virtual ~StructLayoutMap() {
 352     // Remove any layouts.
 353     for (LayoutInfoTy::iterator
 354            I = LayoutInfo.begin(), E = LayoutInfo.end(); I != E; ++I) {
 355       const Type *Key = I->first;
 356       StructLayout *Value = I->second;
 357
 358       if (Key->isAbstract())
 359         Key->removeAbstractTypeUser(this);
 360
 361       Value->~StructLayout();
 362       free(Value);
 363     }
 364   }
 365
 366   void InvalidateEntry(const StructType *Ty) {
 367     LayoutInfoTy::iterator I = LayoutInfo.find(Ty);
 368     if (I == LayoutInfo.end()) return;
 369     RemoveEntry(I, Ty->isAbstract());
 370   }
 371
 372   StructLayout *&operator[](const StructType *STy) {
 373     return LayoutInfo[STy];
 374   }
 375
 376   // for debugging...
 377   virtual void dump() const {}
 378 };
 379
 380 } // end anonymous namespace
 381
 382 TargetData::~TargetData() {
 383   delete static_cast<StructLayoutMap*>(LayoutMap);
 384 }
 385
 386 const StructLayout *TargetData::getStructLayout(const StructType *Ty) const {
 387   if (!LayoutMap)
 388     LayoutMap = new StructLayoutMap();
 389
 390   StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap);
 391   StructLayout *&SL = (*STM)[Ty];
 392   if (SL) return SL;
 393
 394   // Otherwise, create the struct layout.  Because it is variable length, we
 395   // malloc it, then use placement new.
 396   int NumElts = Ty->getNumElements();
 397   StructLayout *L =
 398     (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t));
 399
 400   // Set SL before calling StructLayout's ctor.  The ctor could cause other
 401   // entries to be added to TheMap, invalidating our reference.
 402   SL = L;
 403
 404   new (L) StructLayout(Ty, *this);
 405
 406   if (Ty->isAbstract())
 407     Ty->addAbstractTypeUser(STM);
 408
 409   return L;
 410 }
 411
 412 /// InvalidateStructLayoutInfo - TargetData speculatively caches StructLayout
 413 /// objects.  If a TargetData object is alive when types are being refined and
 414 /// removed, this method must be called whenever a StructType is removed to
 415 /// avoid a dangling pointer in this cache.
 416 void TargetData::InvalidateStructLayoutInfo(const StructType *Ty) const {
 417   if (!LayoutMap) return;  // No cache.
 418
 419   static_cast<StructLayoutMap*>(LayoutMap)->InvalidateEntry(Ty);
 420 }
 421
 422 std::string TargetData::getStringRepresentation() const {
 423   std::string Result;
 424   raw_string_ostream OS(Result);
 425
 426   OS << (LittleEndian ? "e" : "E")
 427      << "-p:" << PointerMemSize*8 << ':' << PointerABIAlign*8
 428      << ':' << PointerPrefAlign*8;
 429   for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
 430     const TargetAlignElem &AI = Alignments[i];
 431     OS << '-' << (char)AI.AlignType << AI.TypeBitWidth << ':'
 432        << AI.ABIAlign*8 << ':' << AI.PrefAlign*8;
 433   }
 434
 435   if (!LegalIntWidths.empty()) {
 436     OS << "-n" << (unsigned)LegalIntWidths[0];
 437
 438     for (unsigned i = 1, e = LegalIntWidths.size(); i != e; ++i)
 439       OS << ':' << (unsigned)LegalIntWidths[i];
 440   }
 441   return OS.str();
 442 }
 443
 444
 445 uint64_t TargetData::getTypeSizeInBits(const Type *Ty) const {
 446   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 447   switch (Ty->getTypeID()) {
 448   case Type::LabelTyID:
 449   case Type::PointerTyID:
 450     return getPointerSizeInBits();
 451   case Type::ArrayTyID: {
 452     const ArrayType *ATy = cast<ArrayType>(Ty);
 453     return getTypeAllocSizeInBits(ATy->getElementType())*ATy->getNumElements();
 454   }
 455   case Type::StructTyID:
 456     // Get the layout annotation... which is lazily created on demand.
 457     return getStructLayout(cast<StructType>(Ty))->getSizeInBits();
 458   case Type::UnionTyID: {
 459     const UnionType *UnTy = cast<UnionType>(Ty);
 460     uint64_t Size = 0;
 461     for (UnionType::element_iterator i = UnTy->element_begin(),
 462              e = UnTy->element_end(); i != e; ++i) {
 463       Size = std::max(Size, getTypeSizeInBits(*i));
 464     }
 465     return Size;
 466   }
 467   case Type::IntegerTyID:
 468     return cast<IntegerType>(Ty)->getBitWidth();
 469   case Type::VoidTyID:
 470     return 8;
 471   case Type::FloatTyID:
 472     return 32;
 473   case Type::DoubleTyID:
 474     return 64;
 475   case Type::PPC_FP128TyID:
 476   case Type::FP128TyID:
 477     return 128;
 478   // In memory objects this is always aligned to a higher boundary, but
 479   // only 80 bits contain information.
 480   case Type::X86_FP80TyID:
 481     return 80;
 482   case Type::VectorTyID:
 483     return cast<VectorType>(Ty)->getBitWidth();
 484   default:
 485     llvm_unreachable("TargetData::getTypeSizeInBits(): Unsupported type");
 486     break;
 487   }
 488   return 0;
 489 }
 490
 491 /*!
 492   \param abi_or_pref Flag that determines which alignment is returned. true
 493   returns the ABI alignment, false returns the preferred alignment.
 494   \param Ty The underlying type for which alignment is determined.
 495
 496   Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref
 497   == false) for the requested type \a Ty.
 498  */
 499 unsigned char TargetData::getAlignment(const Type *Ty, bool abi_or_pref) const {
 500   int AlignType = -1;
 501
 502   assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!");
 503   switch (Ty->getTypeID()) {
 504   // Early escape for the non-numeric types.
 505   case Type::LabelTyID:
 506   case Type::PointerTyID:
 507     return (abi_or_pref
 508             ? getPointerABIAlignment()
 509             : getPointerPrefAlignment());
 510   case Type::ArrayTyID:
 511     return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref);
 512
 513   case Type::StructTyID: {
 514     // Packed structure types always have an ABI alignment of one.
 515     if (cast<StructType>(Ty)->isPacked() && abi_or_pref)
 516       return 1;
 517
 518     // Get the layout annotation... which is lazily created on demand.
 519     const StructLayout *Layout = getStructLayout(cast<StructType>(Ty));
 520     unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty);
 521     return std::max(Align, (unsigned)Layout->getAlignment());
 522   }
 523   case Type::UnionTyID: {
 524     const UnionType *UnTy = cast<UnionType>(Ty);
 525     unsigned Align = 1;
 526
 527     // Unions need the maximum alignment of all their entries
 528     for (UnionType::element_iterator i = UnTy->element_begin(),
 529              e = UnTy->element_end(); i != e; ++i) {
 530       Align = std::max(Align, (unsigned)getAlignment(*i, abi_or_pref));
 531     }
 532     return Align;
 533   }
 534   case Type::IntegerTyID:
 535   case Type::VoidTyID:
 536     AlignType = INTEGER_ALIGN;
 537     break;
 538   case Type::FloatTyID:
 539   case Type::DoubleTyID:
 540   // PPC_FP128TyID and FP128TyID have different data contents, but the
 541   // same size and alignment, so they look the same here.
 542   case Type::PPC_FP128TyID:
 543   case Type::FP128TyID:
 544   case Type::X86_FP80TyID:
 545     AlignType = FLOAT_ALIGN;
 546     break;
 547   case Type::VectorTyID:
 548     AlignType = VECTOR_ALIGN;
 549     break;
 550   default:
 551     llvm_unreachable("Bad type for getAlignment!!!");
 552     break;
 553   }
 554
 555   return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty),
 556                           abi_or_pref, Ty);
 557 }
 558
 559 unsigned char TargetData::getABITypeAlignment(const Type *Ty) const {
 560   return getAlignment(Ty, true);
 561 }
 562
 563 /// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for
 564 /// an integer type of the specified bitwidth.
 565 unsigned char TargetData::getABIIntegerTypeAlignment(unsigned BitWidth) const {
 566   return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, 0);
 567 }
 568
 569
 570 unsigned char TargetData::getCallFrameTypeAlignment(const Type *Ty) const {
 571   for (unsigned i = 0, e = Alignments.size(); i != e; ++i)
 572     if (Alignments[i].AlignType == STACK_ALIGN)
 573       return Alignments[i].ABIAlign;
 574
 575   return getABITypeAlignment(Ty);
 576 }
 577
 578 unsigned char TargetData::getPrefTypeAlignment(const Type *Ty) const {
 579   return getAlignment(Ty, false);
 580 }
 581
 582 unsigned char TargetData::getPreferredTypeAlignmentShift(const Type *Ty) const {
 583   unsigned Align = (unsigned) getPrefTypeAlignment(Ty);
 584   assert(!(Align & (Align-1)) && "Alignment is not a power of two!");
 585   return Log2_32(Align);
 586 }
 587
 588 /// getIntPtrType - Return an unsigned integer type that is the same size or
 589 /// greater to the host pointer size.
 590 const IntegerType *TargetData::getIntPtrType(LLVMContext &C) const {
 591   return IntegerType::get(C, getPointerSizeInBits());
 592 }
 593
 594
 595 uint64_t TargetData::getIndexedOffset(const Type *ptrTy, Value* const* Indices,
 596                                       unsigned NumIndices) const {
 597   const Type *Ty = ptrTy;
 598   assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()");
 599   uint64_t Result = 0;
 600
 601   generic_gep_type_iterator<Value* const*>
 602     TI = gep_type_begin(ptrTy, Indices, Indices+NumIndices);
 603   for (unsigned CurIDX = 0; CurIDX != NumIndices; ++CurIDX, ++TI) {
 604     if (const StructType *STy = dyn_cast<StructType>(*TI)) {
 605       assert(Indices[CurIDX]->getType() ==
 606              Type::getInt32Ty(ptrTy->getContext()) &&
 607              "Illegal struct idx");
 608       unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 609
 610       // Get structure layout information...
 611       const StructLayout *Layout = getStructLayout(STy);
 612
 613       // Add in the offset, as calculated by the structure layout info...
 614       Result += Layout->getElementOffset(FieldNo);
 615
 616       // Update Ty to refer to current element
 617       Ty = STy->getElementType(FieldNo);
 618     } else if (const UnionType *UnTy = dyn_cast<UnionType>(*TI)) {
 619         unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue();
 620
 621         // Offset into union is canonically 0, but type changes
 622         Ty = UnTy->getElementType(FieldNo);
 623     } else {
 624       // Update Ty to refer to current element
 625       Ty = cast<SequentialType>(Ty)->getElementType();
 626
 627       // Get the array index and the size of each array element.
 628       if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue())
 629         Result += arrayIdx * (int64_t)getTypeAllocSize(Ty);
 630     }
 631   }
 632
 633   return Result;
 634 }
 635
 636 /// getPreferredAlignment - Return the preferred alignment of the specified
 637 /// global.  This includes an explicitly requested alignment (if the global
 638 /// has one).
 639 unsigned TargetData::getPreferredAlignment(const GlobalVariable *GV) const {
 640   const Type *ElemType = GV->getType()->getElementType();
 641   unsigned Alignment = getPrefTypeAlignment(ElemType);
 642   if (GV->getAlignment() > Alignment)
 643     Alignment = GV->getAlignment();
 644
 645   if (GV->hasInitializer()) {
 646     if (Alignment < 16) {
 647       // If the global is not external, see if it is large.  If so, give it a
 648       // larger alignment.
 649       if (getTypeSizeInBits(ElemType) > 128)
 650         Alignment = 16;    // 16-byte alignment.
 651     }
 652   }
 653   return Alignment;
 654 }
 655
 656 /// getPreferredAlignmentLog - Return the preferred alignment of the
 657 /// specified global, returned in log form.  This includes an explicitly
 658 /// requested alignment (if the global has one).
 659 unsigned TargetData::getPreferredAlignmentLog(const GlobalVariable *GV) const {
 660   return Log2_32(getPreferredAlignment(GV));
 661 }