1249259Sdim//===-- DataLayout.cpp - Data size & alignment routines --------------------==// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file defines layout properties related to datatype size/offset/alignment 11249259Sdim// information. 12249259Sdim// 13249259Sdim// This structure should be created once, filled in if the defaults are not 14249259Sdim// correct and then passed around by const&. None of the members functions 15249259Sdim// require modification to the object. 16249259Sdim// 17249259Sdim//===----------------------------------------------------------------------===// 18249259Sdim 19249259Sdim#include "llvm/IR/DataLayout.h" 20249259Sdim#include "llvm/ADT/DenseMap.h" 21276479Sdim#include "llvm/ADT/STLExtras.h" 22276479Sdim#include "llvm/ADT/Triple.h" 23249259Sdim#include "llvm/IR/Constants.h" 24249259Sdim#include "llvm/IR/DerivedTypes.h" 25276479Sdim#include "llvm/IR/GetElementPtrTypeIterator.h" 26249259Sdim#include "llvm/IR/Module.h" 27249259Sdim#include "llvm/Support/ErrorHandling.h" 28249259Sdim#include "llvm/Support/ManagedStatic.h" 29249259Sdim#include "llvm/Support/MathExtras.h" 30249259Sdim#include "llvm/Support/Mutex.h" 31249259Sdim#include "llvm/Support/raw_ostream.h" 32249259Sdim#include <algorithm> 33249259Sdim#include <cstdlib> 34249259Sdimusing namespace llvm; 35249259Sdim 36249259Sdim//===----------------------------------------------------------------------===// 37249259Sdim// Support for StructLayout 38249259Sdim//===----------------------------------------------------------------------===// 39249259Sdim 40251662SdimStructLayout::StructLayout(StructType *ST, const DataLayout &DL) { 41249259Sdim assert(!ST->isOpaque() && "Cannot get layout of opaque structs"); 42249259Sdim StructAlignment = 0; 43249259Sdim StructSize = 0; 44296417Sdim IsPadded = false; 45249259Sdim NumElements = ST->getNumElements(); 46249259Sdim 47249259Sdim // Loop over each of the elements, placing them in memory. 48249259Sdim for (unsigned i = 0, e = NumElements; i != e; ++i) { 49249259Sdim Type *Ty = ST->getElementType(i); 50251662Sdim unsigned TyAlign = ST->isPacked() ? 1 : DL.getABITypeAlignment(Ty); 51249259Sdim 52249259Sdim // Add padding if necessary to align the data element properly. 53296417Sdim if ((StructSize & (TyAlign-1)) != 0) { 54296417Sdim IsPadded = true; 55280031Sdim StructSize = RoundUpToAlignment(StructSize, TyAlign); 56296417Sdim } 57249259Sdim 58249259Sdim // Keep track of maximum alignment constraint. 59249259Sdim StructAlignment = std::max(TyAlign, StructAlignment); 60249259Sdim 61249259Sdim MemberOffsets[i] = StructSize; 62251662Sdim StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item 63249259Sdim } 64249259Sdim 65249259Sdim // Empty structures have alignment of 1 byte. 66249259Sdim if (StructAlignment == 0) StructAlignment = 1; 67249259Sdim 68249259Sdim // Add padding to the end of the struct so that it could be put in an array 69249259Sdim // and all array elements would be aligned correctly. 70296417Sdim if ((StructSize & (StructAlignment-1)) != 0) { 71296417Sdim IsPadded = true; 72280031Sdim StructSize = RoundUpToAlignment(StructSize, StructAlignment); 73296417Sdim } 74249259Sdim} 75249259Sdim 76249259Sdim 77249259Sdim/// getElementContainingOffset - Given a valid offset into the structure, 78249259Sdim/// return the structure index that contains it. 79249259Sdimunsigned StructLayout::getElementContainingOffset(uint64_t Offset) const { 80249259Sdim const uint64_t *SI = 81249259Sdim std::upper_bound(&MemberOffsets[0], &MemberOffsets[NumElements], Offset); 82249259Sdim assert(SI != &MemberOffsets[0] && "Offset not in structure type!"); 83249259Sdim --SI; 84249259Sdim assert(*SI <= Offset && "upper_bound didn't work"); 85249259Sdim assert((SI == &MemberOffsets[0] || *(SI-1) <= Offset) && 86249259Sdim (SI+1 == &MemberOffsets[NumElements] || *(SI+1) > Offset) && 87249259Sdim "Upper bound didn't work!"); 88249259Sdim 89249259Sdim // Multiple fields can have the same offset if any of them are zero sized. 90249259Sdim // For example, in { i32, [0 x i32], i32 }, searching for offset 4 will stop 91249259Sdim // at the i32 element, because it is the last element at that offset. This is 92249259Sdim // the right one to return, because anything after it will have a higher 93249259Sdim // offset, implying that this element is non-empty. 94249259Sdim return SI-&MemberOffsets[0]; 95249259Sdim} 96249259Sdim 97249259Sdim//===----------------------------------------------------------------------===// 98249259Sdim// LayoutAlignElem, LayoutAlign support 99249259Sdim//===----------------------------------------------------------------------===// 100249259Sdim 101249259SdimLayoutAlignElem 102249259SdimLayoutAlignElem::get(AlignTypeEnum align_type, unsigned abi_align, 103249259Sdim unsigned pref_align, uint32_t bit_width) { 104249259Sdim assert(abi_align <= pref_align && "Preferred alignment worse than ABI!"); 105249259Sdim LayoutAlignElem retval; 106249259Sdim retval.AlignType = align_type; 107249259Sdim retval.ABIAlign = abi_align; 108249259Sdim retval.PrefAlign = pref_align; 109249259Sdim retval.TypeBitWidth = bit_width; 110249259Sdim return retval; 111249259Sdim} 112249259Sdim 113249259Sdimbool 114249259SdimLayoutAlignElem::operator==(const LayoutAlignElem &rhs) const { 115249259Sdim return (AlignType == rhs.AlignType 116249259Sdim && ABIAlign == rhs.ABIAlign 117249259Sdim && PrefAlign == rhs.PrefAlign 118249259Sdim && TypeBitWidth == rhs.TypeBitWidth); 119249259Sdim} 120249259Sdim 121249259Sdimconst LayoutAlignElem 122276479SdimDataLayout::InvalidAlignmentElem = { INVALID_ALIGN, 0, 0, 0 }; 123249259Sdim 124249259Sdim//===----------------------------------------------------------------------===// 125249259Sdim// PointerAlignElem, PointerAlign support 126249259Sdim//===----------------------------------------------------------------------===// 127249259Sdim 128249259SdimPointerAlignElem 129276479SdimPointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign, 130276479Sdim unsigned PrefAlign, uint32_t TypeByteWidth) { 131276479Sdim assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!"); 132249259Sdim PointerAlignElem retval; 133276479Sdim retval.AddressSpace = AddressSpace; 134276479Sdim retval.ABIAlign = ABIAlign; 135276479Sdim retval.PrefAlign = PrefAlign; 136276479Sdim retval.TypeByteWidth = TypeByteWidth; 137249259Sdim return retval; 138249259Sdim} 139249259Sdim 140249259Sdimbool 141249259SdimPointerAlignElem::operator==(const PointerAlignElem &rhs) const { 142249259Sdim return (ABIAlign == rhs.ABIAlign 143249259Sdim && AddressSpace == rhs.AddressSpace 144249259Sdim && PrefAlign == rhs.PrefAlign 145276479Sdim && TypeByteWidth == rhs.TypeByteWidth); 146249259Sdim} 147249259Sdim 148249259Sdimconst PointerAlignElem 149276479SdimDataLayout::InvalidPointerElem = { 0U, 0U, 0U, ~0U }; 150249259Sdim 151249259Sdim//===----------------------------------------------------------------------===// 152249259Sdim// DataLayout Class Implementation 153249259Sdim//===----------------------------------------------------------------------===// 154249259Sdim 155276479Sdimconst char *DataLayout::getManglingComponent(const Triple &T) { 156276479Sdim if (T.isOSBinFormatMachO()) 157276479Sdim return "-m:o"; 158288943Sdim if (T.isOSWindows() && T.isOSBinFormatCOFF()) 159288943Sdim return T.getArch() == Triple::x86 ? "-m:x" : "-m:w"; 160276479Sdim return "-m:e"; 161276479Sdim} 162249259Sdim 163276479Sdimstatic const LayoutAlignElem DefaultAlignments[] = { 164276479Sdim { INTEGER_ALIGN, 1, 1, 1 }, // i1 165276479Sdim { INTEGER_ALIGN, 8, 1, 1 }, // i8 166276479Sdim { INTEGER_ALIGN, 16, 2, 2 }, // i16 167276479Sdim { INTEGER_ALIGN, 32, 4, 4 }, // i32 168276479Sdim { INTEGER_ALIGN, 64, 4, 8 }, // i64 169276479Sdim { FLOAT_ALIGN, 16, 2, 2 }, // half 170276479Sdim { FLOAT_ALIGN, 32, 4, 4 }, // float 171276479Sdim { FLOAT_ALIGN, 64, 8, 8 }, // double 172276479Sdim { FLOAT_ALIGN, 128, 16, 16 }, // ppcf128, quad, ... 173276479Sdim { VECTOR_ALIGN, 64, 8, 8 }, // v2i32, v1i64, ... 174276479Sdim { VECTOR_ALIGN, 128, 16, 16 }, // v16i8, v8i16, v4i32, ... 175276479Sdim { AGGREGATE_ALIGN, 0, 0, 8 } // struct 176276479Sdim}; 177276479Sdim 178276479Sdimvoid DataLayout::reset(StringRef Desc) { 179276479Sdim clear(); 180276479Sdim 181276479Sdim LayoutMap = nullptr; 182280031Sdim BigEndian = false; 183249259Sdim StackNaturalAlign = 0; 184276479Sdim ManglingMode = MM_None; 185249259Sdim 186249259Sdim // Default alignments 187276479Sdim for (const LayoutAlignElem &E : DefaultAlignments) { 188276479Sdim setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign, 189276479Sdim E.TypeBitWidth); 190276479Sdim } 191249259Sdim setPointerAlignment(0, 8, 8, 8); 192249259Sdim 193249259Sdim parseSpecifier(Desc); 194249259Sdim} 195249259Sdim 196249259Sdim/// Checked version of split, to ensure mandatory subparts. 197249259Sdimstatic std::pair<StringRef, StringRef> split(StringRef Str, char Separator) { 198249259Sdim assert(!Str.empty() && "parse error, string can't be empty here"); 199249259Sdim std::pair<StringRef, StringRef> Split = Str.split(Separator); 200280031Sdim if (Split.second.empty() && Split.first != Str) 201280031Sdim report_fatal_error("Trailing separator in datalayout string"); 202280031Sdim if (!Split.second.empty() && Split.first.empty()) 203280031Sdim report_fatal_error("Expected token before separator in datalayout string"); 204249259Sdim return Split; 205249259Sdim} 206249259Sdim 207276479Sdim/// Get an unsigned integer, including error checks. 208249259Sdimstatic unsigned getInt(StringRef R) { 209249259Sdim unsigned Result; 210249259Sdim bool error = R.getAsInteger(10, Result); (void)error; 211276479Sdim if (error) 212276479Sdim report_fatal_error("not a number, or does not fit in an unsigned int"); 213249259Sdim return Result; 214249259Sdim} 215249259Sdim 216249259Sdim/// Convert bits into bytes. Assert if not a byte width multiple. 217249259Sdimstatic unsigned inBytes(unsigned Bits) { 218280031Sdim if (Bits % 8) 219280031Sdim report_fatal_error("number of bits must be a byte width multiple"); 220249259Sdim return Bits / 8; 221249259Sdim} 222249259Sdim 223249259Sdimvoid DataLayout::parseSpecifier(StringRef Desc) { 224288943Sdim StringRepresentation = Desc; 225249259Sdim while (!Desc.empty()) { 226249259Sdim // Split at '-'. 227249259Sdim std::pair<StringRef, StringRef> Split = split(Desc, '-'); 228249259Sdim Desc = Split.second; 229249259Sdim 230249259Sdim // Split at ':'. 231249259Sdim Split = split(Split.first, ':'); 232249259Sdim 233249259Sdim // Aliases used below. 234249259Sdim StringRef &Tok = Split.first; // Current token. 235249259Sdim StringRef &Rest = Split.second; // The rest of the string. 236249259Sdim 237249259Sdim char Specifier = Tok.front(); 238249259Sdim Tok = Tok.substr(1); 239249259Sdim 240249259Sdim switch (Specifier) { 241276479Sdim case 's': 242276479Sdim // Ignored for backward compatibility. 243276479Sdim // FIXME: remove this on LLVM 4.0. 244276479Sdim break; 245249259Sdim case 'E': 246280031Sdim BigEndian = true; 247249259Sdim break; 248249259Sdim case 'e': 249280031Sdim BigEndian = false; 250249259Sdim break; 251249259Sdim case 'p': { 252249259Sdim // Address space. 253249259Sdim unsigned AddrSpace = Tok.empty() ? 0 : getInt(Tok); 254280031Sdim if (!isUInt<24>(AddrSpace)) 255280031Sdim report_fatal_error("Invalid address space, must be a 24bit integer"); 256249259Sdim 257249259Sdim // Size. 258280031Sdim if (Rest.empty()) 259280031Sdim report_fatal_error( 260280031Sdim "Missing size specification for pointer in datalayout string"); 261249259Sdim Split = split(Rest, ':'); 262249259Sdim unsigned PointerMemSize = inBytes(getInt(Tok)); 263288943Sdim if (!PointerMemSize) 264288943Sdim report_fatal_error("Invalid pointer size of 0 bytes"); 265249259Sdim 266249259Sdim // ABI alignment. 267280031Sdim if (Rest.empty()) 268280031Sdim report_fatal_error( 269280031Sdim "Missing alignment specification for pointer in datalayout string"); 270249259Sdim Split = split(Rest, ':'); 271249259Sdim unsigned PointerABIAlign = inBytes(getInt(Tok)); 272288943Sdim if (!isPowerOf2_64(PointerABIAlign)) 273288943Sdim report_fatal_error( 274288943Sdim "Pointer ABI alignment must be a power of 2"); 275249259Sdim 276249259Sdim // Preferred alignment. 277249259Sdim unsigned PointerPrefAlign = PointerABIAlign; 278249259Sdim if (!Rest.empty()) { 279249259Sdim Split = split(Rest, ':'); 280249259Sdim PointerPrefAlign = inBytes(getInt(Tok)); 281288943Sdim if (!isPowerOf2_64(PointerPrefAlign)) 282288943Sdim report_fatal_error( 283288943Sdim "Pointer preferred alignment must be a power of 2"); 284249259Sdim } 285249259Sdim 286249259Sdim setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign, 287249259Sdim PointerMemSize); 288249259Sdim break; 289249259Sdim } 290249259Sdim case 'i': 291249259Sdim case 'v': 292249259Sdim case 'f': 293276479Sdim case 'a': { 294249259Sdim AlignTypeEnum AlignType; 295249259Sdim switch (Specifier) { 296249259Sdim default: 297249259Sdim case 'i': AlignType = INTEGER_ALIGN; break; 298249259Sdim case 'v': AlignType = VECTOR_ALIGN; break; 299249259Sdim case 'f': AlignType = FLOAT_ALIGN; break; 300249259Sdim case 'a': AlignType = AGGREGATE_ALIGN; break; 301249259Sdim } 302249259Sdim 303249259Sdim // Bit size. 304249259Sdim unsigned Size = Tok.empty() ? 0 : getInt(Tok); 305249259Sdim 306280031Sdim if (AlignType == AGGREGATE_ALIGN && Size != 0) 307280031Sdim report_fatal_error( 308280031Sdim "Sized aggregate specification in datalayout string"); 309276479Sdim 310249259Sdim // ABI alignment. 311280031Sdim if (Rest.empty()) 312280031Sdim report_fatal_error( 313280031Sdim "Missing alignment specification in datalayout string"); 314249259Sdim Split = split(Rest, ':'); 315249259Sdim unsigned ABIAlign = inBytes(getInt(Tok)); 316288943Sdim if (AlignType != AGGREGATE_ALIGN && !ABIAlign) 317288943Sdim report_fatal_error( 318288943Sdim "ABI alignment specification must be >0 for non-aggregate types"); 319249259Sdim 320249259Sdim // Preferred alignment. 321249259Sdim unsigned PrefAlign = ABIAlign; 322249259Sdim if (!Rest.empty()) { 323249259Sdim Split = split(Rest, ':'); 324249259Sdim PrefAlign = inBytes(getInt(Tok)); 325249259Sdim } 326249259Sdim 327249259Sdim setAlignment(AlignType, ABIAlign, PrefAlign, Size); 328249259Sdim 329249259Sdim break; 330249259Sdim } 331249259Sdim case 'n': // Native integer types. 332249259Sdim for (;;) { 333249259Sdim unsigned Width = getInt(Tok); 334280031Sdim if (Width == 0) 335280031Sdim report_fatal_error( 336280031Sdim "Zero width native integer type in datalayout string"); 337249259Sdim LegalIntWidths.push_back(Width); 338249259Sdim if (Rest.empty()) 339249259Sdim break; 340249259Sdim Split = split(Rest, ':'); 341249259Sdim } 342249259Sdim break; 343249259Sdim case 'S': { // Stack natural alignment. 344249259Sdim StackNaturalAlign = inBytes(getInt(Tok)); 345249259Sdim break; 346249259Sdim } 347276479Sdim case 'm': 348280031Sdim if (!Tok.empty()) 349280031Sdim report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string"); 350280031Sdim if (Rest.empty()) 351280031Sdim report_fatal_error("Expected mangling specifier in datalayout string"); 352280031Sdim if (Rest.size() > 1) 353280031Sdim report_fatal_error("Unknown mangling specifier in datalayout string"); 354276479Sdim switch(Rest[0]) { 355276479Sdim default: 356280031Sdim report_fatal_error("Unknown mangling in datalayout string"); 357276479Sdim case 'e': 358276479Sdim ManglingMode = MM_ELF; 359276479Sdim break; 360276479Sdim case 'o': 361276479Sdim ManglingMode = MM_MachO; 362276479Sdim break; 363276479Sdim case 'm': 364276479Sdim ManglingMode = MM_Mips; 365276479Sdim break; 366276479Sdim case 'w': 367288943Sdim ManglingMode = MM_WinCOFF; 368276479Sdim break; 369288943Sdim case 'x': 370288943Sdim ManglingMode = MM_WinCOFFX86; 371288943Sdim break; 372276479Sdim } 373276479Sdim break; 374249259Sdim default: 375280031Sdim report_fatal_error("Unknown specifier in datalayout string"); 376249259Sdim break; 377249259Sdim } 378249259Sdim } 379249259Sdim} 380249259Sdim 381276479SdimDataLayout::DataLayout(const Module *M) : LayoutMap(nullptr) { 382280031Sdim init(M); 383280031Sdim} 384280031Sdim 385288943Sdimvoid DataLayout::init(const Module *M) { *this = M->getDataLayout(); } 386249259Sdim 387276479Sdimbool DataLayout::operator==(const DataLayout &Other) const { 388280031Sdim bool Ret = BigEndian == Other.BigEndian && 389276479Sdim StackNaturalAlign == Other.StackNaturalAlign && 390276479Sdim ManglingMode == Other.ManglingMode && 391276479Sdim LegalIntWidths == Other.LegalIntWidths && 392276479Sdim Alignments == Other.Alignments && Pointers == Other.Pointers; 393288943Sdim // Note: getStringRepresentation() might differs, it is not canonicalized 394276479Sdim return Ret; 395249259Sdim} 396249259Sdim 397249259Sdimvoid 398249259SdimDataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align, 399249259Sdim unsigned pref_align, uint32_t bit_width) { 400288943Sdim if (!isUInt<24>(bit_width)) 401288943Sdim report_fatal_error("Invalid bit width, must be a 24bit integer"); 402288943Sdim if (!isUInt<16>(abi_align)) 403288943Sdim report_fatal_error("Invalid ABI alignment, must be a 16bit integer"); 404288943Sdim if (!isUInt<16>(pref_align)) 405288943Sdim report_fatal_error("Invalid preferred alignment, must be a 16bit integer"); 406288943Sdim if (abi_align != 0 && !isPowerOf2_64(abi_align)) 407288943Sdim report_fatal_error("Invalid ABI alignment, must be a power of 2"); 408288943Sdim if (pref_align != 0 && !isPowerOf2_64(pref_align)) 409288943Sdim report_fatal_error("Invalid preferred alignment, must be a power of 2"); 410288943Sdim 411288943Sdim if (pref_align < abi_align) 412288943Sdim report_fatal_error( 413288943Sdim "Preferred alignment cannot be less than the ABI alignment"); 414288943Sdim 415276479Sdim for (LayoutAlignElem &Elem : Alignments) { 416276479Sdim if (Elem.AlignType == (unsigned)align_type && 417276479Sdim Elem.TypeBitWidth == bit_width) { 418249259Sdim // Update the abi, preferred alignments. 419276479Sdim Elem.ABIAlign = abi_align; 420276479Sdim Elem.PrefAlign = pref_align; 421249259Sdim return; 422249259Sdim } 423249259Sdim } 424249259Sdim 425249259Sdim Alignments.push_back(LayoutAlignElem::get(align_type, abi_align, 426249259Sdim pref_align, bit_width)); 427249259Sdim} 428249259Sdim 429276479SdimDataLayout::PointersTy::iterator 430276479SdimDataLayout::findPointerLowerBound(uint32_t AddressSpace) { 431276479Sdim return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace, 432276479Sdim [](const PointerAlignElem &A, uint32_t AddressSpace) { 433276479Sdim return A.AddressSpace < AddressSpace; 434276479Sdim }); 435276479Sdim} 436276479Sdim 437276479Sdimvoid DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign, 438276479Sdim unsigned PrefAlign, 439276479Sdim uint32_t TypeByteWidth) { 440288943Sdim if (PrefAlign < ABIAlign) 441288943Sdim report_fatal_error( 442288943Sdim "Preferred alignment cannot be less than the ABI alignment"); 443288943Sdim 444276479Sdim PointersTy::iterator I = findPointerLowerBound(AddrSpace); 445276479Sdim if (I == Pointers.end() || I->AddressSpace != AddrSpace) { 446276479Sdim Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, 447276479Sdim TypeByteWidth)); 448249259Sdim } else { 449276479Sdim I->ABIAlign = ABIAlign; 450276479Sdim I->PrefAlign = PrefAlign; 451276479Sdim I->TypeByteWidth = TypeByteWidth; 452249259Sdim } 453249259Sdim} 454249259Sdim 455249259Sdim/// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or 456249259Sdim/// preferred if ABIInfo = false) the layout wants for the specified datatype. 457249259Sdimunsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType, 458249259Sdim uint32_t BitWidth, bool ABIInfo, 459249259Sdim Type *Ty) const { 460249259Sdim // Check to see if we have an exact match and remember the best match we see. 461249259Sdim int BestMatchIdx = -1; 462249259Sdim int LargestInt = -1; 463249259Sdim for (unsigned i = 0, e = Alignments.size(); i != e; ++i) { 464249259Sdim if (Alignments[i].AlignType == (unsigned)AlignType && 465249259Sdim Alignments[i].TypeBitWidth == BitWidth) 466249259Sdim return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign; 467249259Sdim 468249259Sdim // The best match so far depends on what we're looking for. 469296417Sdim if (AlignType == INTEGER_ALIGN && 470296417Sdim Alignments[i].AlignType == INTEGER_ALIGN) { 471249259Sdim // The "best match" for integers is the smallest size that is larger than 472249259Sdim // the BitWidth requested. 473249259Sdim if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 || 474249259Sdim Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth)) 475249259Sdim BestMatchIdx = i; 476249259Sdim // However, if there isn't one that's larger, then we must use the 477249259Sdim // largest one we have (see below) 478249259Sdim if (LargestInt == -1 || 479249259Sdim Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth) 480249259Sdim LargestInt = i; 481249259Sdim } 482249259Sdim } 483249259Sdim 484249259Sdim // Okay, we didn't find an exact solution. Fall back here depending on what 485249259Sdim // is being looked for. 486249259Sdim if (BestMatchIdx == -1) { 487249259Sdim // If we didn't find an integer alignment, fall back on most conservative. 488249259Sdim if (AlignType == INTEGER_ALIGN) { 489249259Sdim BestMatchIdx = LargestInt; 490288943Sdim } else if (AlignType == VECTOR_ALIGN) { 491249259Sdim // By default, use natural alignment for vector types. This is consistent 492249259Sdim // with what clang and llvm-gcc do. 493249259Sdim unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType()); 494249259Sdim Align *= cast<VectorType>(Ty)->getNumElements(); 495249259Sdim // If the alignment is not a power of 2, round up to the next power of 2. 496249259Sdim // This happens for non-power-of-2 length vectors. 497249259Sdim if (Align & (Align-1)) 498249259Sdim Align = NextPowerOf2(Align); 499249259Sdim return Align; 500249259Sdim } 501249259Sdim } 502249259Sdim 503288943Sdim // If we still couldn't find a reasonable default alignment, fall back 504288943Sdim // to a simple heuristic that the alignment is the first power of two 505288943Sdim // greater-or-equal to the store size of the type. This is a reasonable 506288943Sdim // approximation of reality, and if the user wanted something less 507288943Sdim // less conservative, they should have specified it explicitly in the data 508288943Sdim // layout. 509288943Sdim if (BestMatchIdx == -1) { 510288943Sdim unsigned Align = getTypeStoreSize(Ty); 511288943Sdim if (Align & (Align-1)) 512288943Sdim Align = NextPowerOf2(Align); 513288943Sdim return Align; 514288943Sdim } 515288943Sdim 516249259Sdim // Since we got a "best match" index, just return it. 517249259Sdim return ABIInfo ? Alignments[BestMatchIdx].ABIAlign 518249259Sdim : Alignments[BestMatchIdx].PrefAlign; 519249259Sdim} 520249259Sdim 521249259Sdimnamespace { 522249259Sdim 523249259Sdimclass StructLayoutMap { 524249259Sdim typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy; 525249259Sdim LayoutInfoTy LayoutInfo; 526249259Sdim 527249259Sdimpublic: 528276479Sdim ~StructLayoutMap() { 529249259Sdim // Remove any layouts. 530276479Sdim for (const auto &I : LayoutInfo) { 531276479Sdim StructLayout *Value = I.second; 532249259Sdim Value->~StructLayout(); 533249259Sdim free(Value); 534249259Sdim } 535249259Sdim } 536249259Sdim 537249259Sdim StructLayout *&operator[](StructType *STy) { 538249259Sdim return LayoutInfo[STy]; 539249259Sdim } 540249259Sdim}; 541249259Sdim 542249259Sdim} // end anonymous namespace 543249259Sdim 544276479Sdimvoid DataLayout::clear() { 545276479Sdim LegalIntWidths.clear(); 546276479Sdim Alignments.clear(); 547276479Sdim Pointers.clear(); 548276479Sdim delete static_cast<StructLayoutMap *>(LayoutMap); 549276479Sdim LayoutMap = nullptr; 550249259Sdim} 551249259Sdim 552276479SdimDataLayout::~DataLayout() { 553276479Sdim clear(); 554249259Sdim} 555249259Sdim 556249259Sdimconst StructLayout *DataLayout::getStructLayout(StructType *Ty) const { 557249259Sdim if (!LayoutMap) 558249259Sdim LayoutMap = new StructLayoutMap(); 559249259Sdim 560249259Sdim StructLayoutMap *STM = static_cast<StructLayoutMap*>(LayoutMap); 561249259Sdim StructLayout *&SL = (*STM)[Ty]; 562249259Sdim if (SL) return SL; 563249259Sdim 564249259Sdim // Otherwise, create the struct layout. Because it is variable length, we 565249259Sdim // malloc it, then use placement new. 566249259Sdim int NumElts = Ty->getNumElements(); 567249259Sdim StructLayout *L = 568249259Sdim (StructLayout *)malloc(sizeof(StructLayout)+(NumElts-1) * sizeof(uint64_t)); 569249259Sdim 570249259Sdim // Set SL before calling StructLayout's ctor. The ctor could cause other 571249259Sdim // entries to be added to TheMap, invalidating our reference. 572249259Sdim SL = L; 573249259Sdim 574249259Sdim new (L) StructLayout(Ty, *this); 575249259Sdim 576249259Sdim return L; 577249259Sdim} 578249259Sdim 579249259Sdim 580276479Sdimunsigned DataLayout::getPointerABIAlignment(unsigned AS) const { 581276479Sdim PointersTy::const_iterator I = findPointerLowerBound(AS); 582276479Sdim if (I == Pointers.end() || I->AddressSpace != AS) { 583276479Sdim I = findPointerLowerBound(0); 584276479Sdim assert(I->AddressSpace == 0); 585276479Sdim } 586276479Sdim return I->ABIAlign; 587276479Sdim} 588276479Sdim 589276479Sdimunsigned DataLayout::getPointerPrefAlignment(unsigned AS) const { 590276479Sdim PointersTy::const_iterator I = findPointerLowerBound(AS); 591276479Sdim if (I == Pointers.end() || I->AddressSpace != AS) { 592276479Sdim I = findPointerLowerBound(0); 593276479Sdim assert(I->AddressSpace == 0); 594276479Sdim } 595276479Sdim return I->PrefAlign; 596276479Sdim} 597276479Sdim 598276479Sdimunsigned DataLayout::getPointerSize(unsigned AS) const { 599276479Sdim PointersTy::const_iterator I = findPointerLowerBound(AS); 600276479Sdim if (I == Pointers.end() || I->AddressSpace != AS) { 601276479Sdim I = findPointerLowerBound(0); 602276479Sdim assert(I->AddressSpace == 0); 603276479Sdim } 604276479Sdim return I->TypeByteWidth; 605276479Sdim} 606276479Sdim 607261991Sdimunsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const { 608261991Sdim assert(Ty->isPtrOrPtrVectorTy() && 609261991Sdim "This should only be called with a pointer or pointer vector type"); 610249259Sdim 611261991Sdim if (Ty->isPointerTy()) 612261991Sdim return getTypeSizeInBits(Ty); 613261991Sdim 614261991Sdim return getTypeSizeInBits(Ty->getScalarType()); 615261991Sdim} 616261991Sdim 617249259Sdim/*! 618249259Sdim \param abi_or_pref Flag that determines which alignment is returned. true 619249259Sdim returns the ABI alignment, false returns the preferred alignment. 620249259Sdim \param Ty The underlying type for which alignment is determined. 621249259Sdim 622249259Sdim Get the ABI (\a abi_or_pref == true) or preferred alignment (\a abi_or_pref 623249259Sdim == false) for the requested type \a Ty. 624249259Sdim */ 625249259Sdimunsigned DataLayout::getAlignment(Type *Ty, bool abi_or_pref) const { 626249259Sdim int AlignType = -1; 627249259Sdim 628249259Sdim assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!"); 629249259Sdim switch (Ty->getTypeID()) { 630249259Sdim // Early escape for the non-numeric types. 631249259Sdim case Type::LabelTyID: 632249259Sdim return (abi_or_pref 633249259Sdim ? getPointerABIAlignment(0) 634249259Sdim : getPointerPrefAlignment(0)); 635249259Sdim case Type::PointerTyID: { 636280031Sdim unsigned AS = cast<PointerType>(Ty)->getAddressSpace(); 637249259Sdim return (abi_or_pref 638249259Sdim ? getPointerABIAlignment(AS) 639249259Sdim : getPointerPrefAlignment(AS)); 640249259Sdim } 641249259Sdim case Type::ArrayTyID: 642249259Sdim return getAlignment(cast<ArrayType>(Ty)->getElementType(), abi_or_pref); 643249259Sdim 644249259Sdim case Type::StructTyID: { 645249259Sdim // Packed structure types always have an ABI alignment of one. 646249259Sdim if (cast<StructType>(Ty)->isPacked() && abi_or_pref) 647249259Sdim return 1; 648249259Sdim 649249259Sdim // Get the layout annotation... which is lazily created on demand. 650249259Sdim const StructLayout *Layout = getStructLayout(cast<StructType>(Ty)); 651249259Sdim unsigned Align = getAlignmentInfo(AGGREGATE_ALIGN, 0, abi_or_pref, Ty); 652249259Sdim return std::max(Align, Layout->getAlignment()); 653249259Sdim } 654249259Sdim case Type::IntegerTyID: 655249259Sdim AlignType = INTEGER_ALIGN; 656249259Sdim break; 657249259Sdim case Type::HalfTyID: 658249259Sdim case Type::FloatTyID: 659249259Sdim case Type::DoubleTyID: 660249259Sdim // PPC_FP128TyID and FP128TyID have different data contents, but the 661249259Sdim // same size and alignment, so they look the same here. 662249259Sdim case Type::PPC_FP128TyID: 663249259Sdim case Type::FP128TyID: 664249259Sdim case Type::X86_FP80TyID: 665249259Sdim AlignType = FLOAT_ALIGN; 666249259Sdim break; 667249259Sdim case Type::X86_MMXTyID: 668249259Sdim case Type::VectorTyID: 669249259Sdim AlignType = VECTOR_ALIGN; 670249259Sdim break; 671249259Sdim default: 672249259Sdim llvm_unreachable("Bad type for getAlignment!!!"); 673249259Sdim } 674249259Sdim 675249259Sdim return getAlignmentInfo((AlignTypeEnum)AlignType, getTypeSizeInBits(Ty), 676249259Sdim abi_or_pref, Ty); 677249259Sdim} 678249259Sdim 679249259Sdimunsigned DataLayout::getABITypeAlignment(Type *Ty) const { 680249259Sdim return getAlignment(Ty, true); 681249259Sdim} 682249259Sdim 683249259Sdim/// getABIIntegerTypeAlignment - Return the minimum ABI-required alignment for 684249259Sdim/// an integer type of the specified bitwidth. 685249259Sdimunsigned DataLayout::getABIIntegerTypeAlignment(unsigned BitWidth) const { 686276479Sdim return getAlignmentInfo(INTEGER_ALIGN, BitWidth, true, nullptr); 687249259Sdim} 688249259Sdim 689249259Sdimunsigned DataLayout::getPrefTypeAlignment(Type *Ty) const { 690249259Sdim return getAlignment(Ty, false); 691249259Sdim} 692249259Sdim 693249259Sdimunsigned DataLayout::getPreferredTypeAlignmentShift(Type *Ty) const { 694249259Sdim unsigned Align = getPrefTypeAlignment(Ty); 695249259Sdim assert(!(Align & (Align-1)) && "Alignment is not a power of two!"); 696249259Sdim return Log2_32(Align); 697249259Sdim} 698249259Sdim 699249259SdimIntegerType *DataLayout::getIntPtrType(LLVMContext &C, 700249259Sdim unsigned AddressSpace) const { 701249259Sdim return IntegerType::get(C, getPointerSizeInBits(AddressSpace)); 702249259Sdim} 703249259Sdim 704249259SdimType *DataLayout::getIntPtrType(Type *Ty) const { 705249259Sdim assert(Ty->isPtrOrPtrVectorTy() && 706249259Sdim "Expected a pointer or pointer vector type."); 707276479Sdim unsigned NumBits = getPointerTypeSizeInBits(Ty); 708249259Sdim IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits); 709249259Sdim if (VectorType *VecTy = dyn_cast<VectorType>(Ty)) 710249259Sdim return VectorType::get(IntTy, VecTy->getNumElements()); 711249259Sdim return IntTy; 712249259Sdim} 713249259Sdim 714249259SdimType *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const { 715276479Sdim for (unsigned LegalIntWidth : LegalIntWidths) 716276479Sdim if (Width <= LegalIntWidth) 717276479Sdim return Type::getIntNTy(C, LegalIntWidth); 718276479Sdim return nullptr; 719249259Sdim} 720249259Sdim 721261991Sdimunsigned DataLayout::getLargestLegalIntTypeSize() const { 722276479Sdim auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end()); 723276479Sdim return Max != LegalIntWidths.end() ? *Max : 0; 724261991Sdim} 725261991Sdim 726249259Sdimuint64_t DataLayout::getIndexedOffset(Type *ptrTy, 727249259Sdim ArrayRef<Value *> Indices) const { 728249259Sdim Type *Ty = ptrTy; 729249259Sdim assert(Ty->isPointerTy() && "Illegal argument for getIndexedOffset()"); 730249259Sdim uint64_t Result = 0; 731249259Sdim 732249259Sdim generic_gep_type_iterator<Value* const*> 733249259Sdim TI = gep_type_begin(ptrTy, Indices); 734249259Sdim for (unsigned CurIDX = 0, EndIDX = Indices.size(); CurIDX != EndIDX; 735249259Sdim ++CurIDX, ++TI) { 736249259Sdim if (StructType *STy = dyn_cast<StructType>(*TI)) { 737249259Sdim assert(Indices[CurIDX]->getType() == 738249259Sdim Type::getInt32Ty(ptrTy->getContext()) && 739249259Sdim "Illegal struct idx"); 740249259Sdim unsigned FieldNo = cast<ConstantInt>(Indices[CurIDX])->getZExtValue(); 741249259Sdim 742249259Sdim // Get structure layout information... 743249259Sdim const StructLayout *Layout = getStructLayout(STy); 744249259Sdim 745249259Sdim // Add in the offset, as calculated by the structure layout info... 746249259Sdim Result += Layout->getElementOffset(FieldNo); 747249259Sdim 748249259Sdim // Update Ty to refer to current element 749249259Sdim Ty = STy->getElementType(FieldNo); 750249259Sdim } else { 751249259Sdim // Update Ty to refer to current element 752249259Sdim Ty = cast<SequentialType>(Ty)->getElementType(); 753249259Sdim 754249259Sdim // Get the array index and the size of each array element. 755249259Sdim if (int64_t arrayIdx = cast<ConstantInt>(Indices[CurIDX])->getSExtValue()) 756249259Sdim Result += (uint64_t)arrayIdx * getTypeAllocSize(Ty); 757249259Sdim } 758249259Sdim } 759249259Sdim 760249259Sdim return Result; 761249259Sdim} 762249259Sdim 763249259Sdim/// getPreferredAlignment - Return the preferred alignment of the specified 764249259Sdim/// global. This includes an explicitly requested alignment (if the global 765249259Sdim/// has one). 766249259Sdimunsigned DataLayout::getPreferredAlignment(const GlobalVariable *GV) const { 767249259Sdim Type *ElemType = GV->getType()->getElementType(); 768249259Sdim unsigned Alignment = getPrefTypeAlignment(ElemType); 769249259Sdim unsigned GVAlignment = GV->getAlignment(); 770249259Sdim if (GVAlignment >= Alignment) { 771249259Sdim Alignment = GVAlignment; 772249259Sdim } else if (GVAlignment != 0) { 773249259Sdim Alignment = std::max(GVAlignment, getABITypeAlignment(ElemType)); 774249259Sdim } 775249259Sdim 776249259Sdim if (GV->hasInitializer() && GVAlignment == 0) { 777249259Sdim if (Alignment < 16) { 778249259Sdim // If the global is not external, see if it is large. If so, give it a 779249259Sdim // larger alignment. 780249259Sdim if (getTypeSizeInBits(ElemType) > 128) 781249259Sdim Alignment = 16; // 16-byte alignment. 782249259Sdim } 783249259Sdim } 784249259Sdim return Alignment; 785249259Sdim} 786249259Sdim 787249259Sdim/// getPreferredAlignmentLog - Return the preferred alignment of the 788249259Sdim/// specified global, returned in log form. This includes an explicitly 789249259Sdim/// requested alignment (if the global has one). 790249259Sdimunsigned DataLayout::getPreferredAlignmentLog(const GlobalVariable *GV) const { 791249259Sdim return Log2_32(getPreferredAlignment(GV)); 792249259Sdim} 793276479Sdim 794