1 //===--- CGRecordLayoutBuilder.cpp - CGRecordLayout builder ----*- C++ -*-===// 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 // Builder implementation for CGRecordLayout objects. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "CGRecordLayout.h" 15 #include "CGCXXABI.h" 16 #include "CodeGenTypes.h" 17 #include "clang/AST/ASTContext.h" 18 #include "clang/AST/Attr.h" 19 #include "clang/AST/CXXInheritance.h" 20 #include "clang/AST/DeclCXX.h" 21 #include "clang/AST/Expr.h" 22 #include "clang/AST/RecordLayout.h" 23 #include "clang/Frontend/CodeGenOptions.h" 24 #include "llvm/IR/DataLayout.h" 25 #include "llvm/IR/DerivedTypes.h" 26 #include "llvm/IR/Type.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/MathExtras.h" 29 #include "llvm/Support/raw_ostream.h" 30 using namespace clang; 31 using namespace CodeGen; 32 33 namespace { 34 /// The CGRecordLowering is responsible for lowering an ASTRecordLayout to an 35 /// llvm::Type. Some of the lowering is straightforward, some is not. Here we 36 /// detail some of the complexities and weirdnesses here. 37 /// * LLVM does not have unions - Unions can, in theory be represented by any 38 /// llvm::Type with correct size. We choose a field via a specific heuristic 39 /// and add padding if necessary. 40 /// * LLVM does not have bitfields - Bitfields are collected into contiguous 41 /// runs and allocated as a single storage type for the run. ASTRecordLayout 42 /// contains enough information to determine where the runs break. Microsoft 43 /// and Itanium follow different rules and use different codepaths. 44 /// * It is desired that, when possible, bitfields use the appropriate iN type 45 /// when lowered to llvm types. For example unsigned x : 24 gets lowered to 46 /// i24. This isn't always possible because i24 has storage size of 32 bit 47 /// and if it is possible to use that extra byte of padding we must use 48 /// [i8 x 3] instead of i24. The function clipTailPadding does this. 49 /// C++ examples that require clipping: 50 /// struct { int a : 24; char b; }; // a must be clipped, b goes at offset 3 51 /// struct A { int a : 24; }; // a must be clipped because a struct like B 52 // could exist: struct B : A { char b; }; // b goes at offset 3 53 /// * Clang ignores 0 sized bitfields and 0 sized bases but *not* zero sized 54 /// fields. The existing asserts suggest that LLVM assumes that *every* field 55 /// has an underlying storage type. Therefore empty structures containing 56 /// zero sized subobjects such as empty records or zero sized arrays still get 57 /// a zero sized (empty struct) storage type. 58 /// * Clang reads the complete type rather than the base type when generating 59 /// code to access fields. Bitfields in tail position with tail padding may 60 /// be clipped in the base class but not the complete class (we may discover 61 /// that the tail padding is not used in the complete class.) However, 62 /// because LLVM reads from the complete type it can generate incorrect code 63 /// if we do not clip the tail padding off of the bitfield in the complete 64 /// layout. This introduces a somewhat awkward extra unnecessary clip stage. 65 /// The location of the clip is stored internally as a sentinal of type 66 /// SCISSOR. If LLVM were updated to read base types (which it probably 67 /// should because locations of things such as VBases are bogus in the llvm 68 /// type anyway) then we could eliminate the SCISSOR. 69 /// * Itanium allows nearly empty primary virtual bases. These bases don't get 70 /// get their own storage because they're laid out as part of another base 71 /// or at the beginning of the structure. Determining if a VBase actually 72 /// gets storage awkwardly involves a walk of all bases. 73 /// * VFPtrs and VBPtrs do *not* make a record NotZeroInitializable. 74 struct CGRecordLowering { 75 // MemberInfo is a helper structure that contains information about a record 76 // member. In additional to the standard member types, there exists a 77 // sentinal member type that ensures correct rounding. 78 struct MemberInfo { 79 CharUnits Offset; 80 enum InfoKind { VFPtr, VBPtr, Field, Base, VBase, Scissor } Kind; 81 llvm::Type *Data; 82 union { 83 const FieldDecl *FD; 84 const CXXRecordDecl *RD; 85 }; 86 MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data, 87 const FieldDecl *FD = nullptr) 88 : Offset(Offset), Kind(Kind), Data(Data), FD(FD) {} 89 MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data, 90 const CXXRecordDecl *RD) 91 : Offset(Offset), Kind(Kind), Data(Data), RD(RD) {} 92 // MemberInfos are sorted so we define a < operator. 93 bool operator <(const MemberInfo& a) const { return Offset < a.Offset; } 94 }; 95 // The constructor. 96 CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D, bool Packed); 97 // Short helper routines. 98 /// \brief Constructs a MemberInfo instance from an offset and llvm::Type *. 99 MemberInfo StorageInfo(CharUnits Offset, llvm::Type *Data) { 100 return MemberInfo(Offset, MemberInfo::Field, Data); 101 } 102 103 /// The Microsoft bitfield layout rule allocates discrete storage 104 /// units of the field's formal type and only combines adjacent 105 /// fields of the same formal type. We want to emit a layout with 106 /// these discrete storage units instead of combining them into a 107 /// continuous run. 108 bool isDiscreteBitFieldABI() { 109 return Context.getTargetInfo().getCXXABI().isMicrosoft() || 110 D->isMsStruct(Context); 111 } 112 113 /// The Itanium base layout rule allows virtual bases to overlap 114 /// other bases, which complicates layout in specific ways. 115 /// 116 /// Note specifically that the ms_struct attribute doesn't change this. 117 bool isOverlappingVBaseABI() { 118 return !Context.getTargetInfo().getCXXABI().isMicrosoft(); 119 } 120 121 /// \brief Wraps llvm::Type::getIntNTy with some implicit arguments. 122 llvm::Type *getIntNType(uint64_t NumBits) { 123 return llvm::Type::getIntNTy(Types.getLLVMContext(), 124 (unsigned)llvm::alignTo(NumBits, 8)); 125 } 126 /// \brief Gets an llvm type of size NumBytes and alignment 1. 127 llvm::Type *getByteArrayType(CharUnits NumBytes) { 128 assert(!NumBytes.isZero() && "Empty byte arrays aren't allowed."); 129 llvm::Type *Type = llvm::Type::getInt8Ty(Types.getLLVMContext()); 130 return NumBytes == CharUnits::One() ? Type : 131 (llvm::Type *)llvm::ArrayType::get(Type, NumBytes.getQuantity()); 132 } 133 /// \brief Gets the storage type for a field decl and handles storage 134 /// for itanium bitfields that are smaller than their declared type. 135 llvm::Type *getStorageType(const FieldDecl *FD) { 136 llvm::Type *Type = Types.ConvertTypeForMem(FD->getType()); 137 if (!FD->isBitField()) return Type; 138 if (isDiscreteBitFieldABI()) return Type; 139 return getIntNType(std::min(FD->getBitWidthValue(Context), 140 (unsigned)Context.toBits(getSize(Type)))); 141 } 142 /// \brief Gets the llvm Basesubobject type from a CXXRecordDecl. 143 llvm::Type *getStorageType(const CXXRecordDecl *RD) { 144 return Types.getCGRecordLayout(RD).getBaseSubobjectLLVMType(); 145 } 146 CharUnits bitsToCharUnits(uint64_t BitOffset) { 147 return Context.toCharUnitsFromBits(BitOffset); 148 } 149 CharUnits getSize(llvm::Type *Type) { 150 return CharUnits::fromQuantity(DataLayout.getTypeAllocSize(Type)); 151 } 152 CharUnits getAlignment(llvm::Type *Type) { 153 return CharUnits::fromQuantity(DataLayout.getABITypeAlignment(Type)); 154 } 155 bool isZeroInitializable(const FieldDecl *FD) { 156 return Types.isZeroInitializable(FD->getType()); 157 } 158 bool isZeroInitializable(const RecordDecl *RD) { 159 return Types.isZeroInitializable(RD); 160 } 161 void appendPaddingBytes(CharUnits Size) { 162 if (!Size.isZero()) 163 FieldTypes.push_back(getByteArrayType(Size)); 164 } 165 uint64_t getFieldBitOffset(const FieldDecl *FD) { 166 return Layout.getFieldOffset(FD->getFieldIndex()); 167 } 168 // Layout routines. 169 void setBitFieldInfo(const FieldDecl *FD, CharUnits StartOffset, 170 llvm::Type *StorageType); 171 /// \brief Lowers an ASTRecordLayout to a llvm type. 172 void lower(bool NonVirtualBaseType); 173 void lowerUnion(); 174 void accumulateFields(); 175 void accumulateBitFields(RecordDecl::field_iterator Field, 176 RecordDecl::field_iterator FieldEnd); 177 void accumulateBases(); 178 void accumulateVPtrs(); 179 void accumulateVBases(); 180 /// \brief Recursively searches all of the bases to find out if a vbase is 181 /// not the primary vbase of some base class. 182 bool hasOwnStorage(const CXXRecordDecl *Decl, const CXXRecordDecl *Query); 183 void calculateZeroInit(); 184 /// \brief Lowers bitfield storage types to I8 arrays for bitfields with tail 185 /// padding that is or can potentially be used. 186 void clipTailPadding(); 187 /// \brief Determines if we need a packed llvm struct. 188 void determinePacked(bool NVBaseType); 189 /// \brief Inserts padding everwhere it's needed. 190 void insertPadding(); 191 /// \brief Fills out the structures that are ultimately consumed. 192 void fillOutputFields(); 193 // Input memoization fields. 194 CodeGenTypes &Types; 195 const ASTContext &Context; 196 const RecordDecl *D; 197 const CXXRecordDecl *RD; 198 const ASTRecordLayout &Layout; 199 const llvm::DataLayout &DataLayout; 200 // Helpful intermediate data-structures. 201 std::vector<MemberInfo> Members; 202 // Output fields, consumed by CodeGenTypes::ComputeRecordLayout. 203 SmallVector<llvm::Type *, 16> FieldTypes; 204 llvm::DenseMap<const FieldDecl *, unsigned> Fields; 205 llvm::DenseMap<const FieldDecl *, CGBitFieldInfo> BitFields; 206 llvm::DenseMap<const CXXRecordDecl *, unsigned> NonVirtualBases; 207 llvm::DenseMap<const CXXRecordDecl *, unsigned> VirtualBases; 208 bool IsZeroInitializable : 1; 209 bool IsZeroInitializableAsBase : 1; 210 bool Packed : 1; 211 private: 212 CGRecordLowering(const CGRecordLowering &) = delete; 213 void operator =(const CGRecordLowering &) = delete; 214 }; 215 } // namespace { 216 217 CGRecordLowering::CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D, bool Packed) 218 : Types(Types), Context(Types.getContext()), D(D), 219 RD(dyn_cast<CXXRecordDecl>(D)), 220 Layout(Types.getContext().getASTRecordLayout(D)), 221 DataLayout(Types.getDataLayout()), IsZeroInitializable(true), 222 IsZeroInitializableAsBase(true), Packed(Packed) {} 223 224 void CGRecordLowering::setBitFieldInfo( 225 const FieldDecl *FD, CharUnits StartOffset, llvm::Type *StorageType) { 226 CGBitFieldInfo &Info = BitFields[FD->getCanonicalDecl()]; 227 Info.IsSigned = FD->getType()->isSignedIntegerOrEnumerationType(); 228 Info.Offset = (unsigned)(getFieldBitOffset(FD) - Context.toBits(StartOffset)); 229 Info.Size = FD->getBitWidthValue(Context); 230 Info.StorageSize = (unsigned)DataLayout.getTypeAllocSizeInBits(StorageType); 231 Info.StorageOffset = StartOffset; 232 if (Info.Size > Info.StorageSize) 233 Info.Size = Info.StorageSize; 234 // Reverse the bit offsets for big endian machines. Because we represent 235 // a bitfield as a single large integer load, we can imagine the bits 236 // counting from the most-significant-bit instead of the 237 // least-significant-bit. 238 if (DataLayout.isBigEndian()) 239 Info.Offset = Info.StorageSize - (Info.Offset + Info.Size); 240 } 241 242 void CGRecordLowering::lower(bool NVBaseType) { 243 // The lowering process implemented in this function takes a variety of 244 // carefully ordered phases. 245 // 1) Store all members (fields and bases) in a list and sort them by offset. 246 // 2) Add a 1-byte capstone member at the Size of the structure. 247 // 3) Clip bitfield storages members if their tail padding is or might be 248 // used by another field or base. The clipping process uses the capstone 249 // by treating it as another object that occurs after the record. 250 // 4) Determine if the llvm-struct requires packing. It's important that this 251 // phase occur after clipping, because clipping changes the llvm type. 252 // This phase reads the offset of the capstone when determining packedness 253 // and updates the alignment of the capstone to be equal of the alignment 254 // of the record after doing so. 255 // 5) Insert padding everywhere it is needed. This phase requires 'Packed' to 256 // have been computed and needs to know the alignment of the record in 257 // order to understand if explicit tail padding is needed. 258 // 6) Remove the capstone, we don't need it anymore. 259 // 7) Determine if this record can be zero-initialized. This phase could have 260 // been placed anywhere after phase 1. 261 // 8) Format the complete list of members in a way that can be consumed by 262 // CodeGenTypes::ComputeRecordLayout. 263 CharUnits Size = NVBaseType ? Layout.getNonVirtualSize() : Layout.getSize(); 264 if (D->isUnion()) 265 return lowerUnion(); 266 accumulateFields(); 267 // RD implies C++. 268 if (RD) { 269 accumulateVPtrs(); 270 accumulateBases(); 271 if (Members.empty()) 272 return appendPaddingBytes(Size); 273 if (!NVBaseType) 274 accumulateVBases(); 275 } 276 std::stable_sort(Members.begin(), Members.end()); 277 Members.push_back(StorageInfo(Size, getIntNType(8))); 278 clipTailPadding(); 279 determinePacked(NVBaseType); 280 insertPadding(); 281 Members.pop_back(); 282 calculateZeroInit(); 283 fillOutputFields(); 284 } 285 286 void CGRecordLowering::lowerUnion() { 287 CharUnits LayoutSize = Layout.getSize(); 288 llvm::Type *StorageType = nullptr; 289 bool SeenNamedMember = false; 290 // Iterate through the fields setting bitFieldInfo and the Fields array. Also 291 // locate the "most appropriate" storage type. The heuristic for finding the 292 // storage type isn't necessary, the first (non-0-length-bitfield) field's 293 // type would work fine and be simpler but would be different than what we've 294 // been doing and cause lit tests to change. 295 for (const auto *Field : D->fields()) { 296 if (Field->isBitField()) { 297 // Skip 0 sized bitfields. 298 if (Field->getBitWidthValue(Context) == 0) 299 continue; 300 llvm::Type *FieldType = getStorageType(Field); 301 if (LayoutSize < getSize(FieldType)) 302 FieldType = getByteArrayType(LayoutSize); 303 setBitFieldInfo(Field, CharUnits::Zero(), FieldType); 304 } 305 Fields[Field->getCanonicalDecl()] = 0; 306 llvm::Type *FieldType = getStorageType(Field); 307 // Compute zero-initializable status. 308 // This union might not be zero initialized: it may contain a pointer to 309 // data member which might have some exotic initialization sequence. 310 // If this is the case, then we aught not to try and come up with a "better" 311 // type, it might not be very easy to come up with a Constant which 312 // correctly initializes it. 313 if (!SeenNamedMember) { 314 SeenNamedMember = Field->getIdentifier(); 315 if (!SeenNamedMember) 316 if (const auto *FieldRD = 317 dyn_cast_or_null<RecordDecl>(Field->getType()->getAsTagDecl())) 318 SeenNamedMember = FieldRD->findFirstNamedDataMember(); 319 if (SeenNamedMember && !isZeroInitializable(Field)) { 320 IsZeroInitializable = IsZeroInitializableAsBase = false; 321 StorageType = FieldType; 322 } 323 } 324 // Because our union isn't zero initializable, we won't be getting a better 325 // storage type. 326 if (!IsZeroInitializable) 327 continue; 328 // Conditionally update our storage type if we've got a new "better" one. 329 if (!StorageType || 330 getAlignment(FieldType) > getAlignment(StorageType) || 331 (getAlignment(FieldType) == getAlignment(StorageType) && 332 getSize(FieldType) > getSize(StorageType))) 333 StorageType = FieldType; 334 } 335 // If we have no storage type just pad to the appropriate size and return. 336 if (!StorageType) 337 return appendPaddingBytes(LayoutSize); 338 // If our storage size was bigger than our required size (can happen in the 339 // case of packed bitfields on Itanium) then just use an I8 array. 340 if (LayoutSize < getSize(StorageType)) 341 StorageType = getByteArrayType(LayoutSize); 342 FieldTypes.push_back(StorageType); 343 appendPaddingBytes(LayoutSize - getSize(StorageType)); 344 // Set packed if we need it. 345 if (LayoutSize % getAlignment(StorageType)) 346 Packed = true; 347 } 348 349 void CGRecordLowering::accumulateFields() { 350 for (RecordDecl::field_iterator Field = D->field_begin(), 351 FieldEnd = D->field_end(); 352 Field != FieldEnd;) 353 if (Field->isBitField()) { 354 RecordDecl::field_iterator Start = Field; 355 // Iterate to gather the list of bitfields. 356 for (++Field; Field != FieldEnd && Field->isBitField(); ++Field); 357 accumulateBitFields(Start, Field); 358 } else { 359 Members.push_back(MemberInfo( 360 bitsToCharUnits(getFieldBitOffset(*Field)), MemberInfo::Field, 361 getStorageType(*Field), *Field)); 362 ++Field; 363 } 364 } 365 366 void 367 CGRecordLowering::accumulateBitFields(RecordDecl::field_iterator Field, 368 RecordDecl::field_iterator FieldEnd) { 369 // Run stores the first element of the current run of bitfields. FieldEnd is 370 // used as a special value to note that we don't have a current run. A 371 // bitfield run is a contiguous collection of bitfields that can be stored in 372 // the same storage block. Zero-sized bitfields and bitfields that would 373 // cross an alignment boundary break a run and start a new one. 374 RecordDecl::field_iterator Run = FieldEnd; 375 // Tail is the offset of the first bit off the end of the current run. It's 376 // used to determine if the ASTRecordLayout is treating these two bitfields as 377 // contiguous. StartBitOffset is offset of the beginning of the Run. 378 uint64_t StartBitOffset, Tail = 0; 379 if (isDiscreteBitFieldABI()) { 380 for (; Field != FieldEnd; ++Field) { 381 uint64_t BitOffset = getFieldBitOffset(*Field); 382 // Zero-width bitfields end runs. 383 if (Field->getBitWidthValue(Context) == 0) { 384 Run = FieldEnd; 385 continue; 386 } 387 llvm::Type *Type = Types.ConvertTypeForMem(Field->getType()); 388 // If we don't have a run yet, or don't live within the previous run's 389 // allocated storage then we allocate some storage and start a new run. 390 if (Run == FieldEnd || BitOffset >= Tail) { 391 Run = Field; 392 StartBitOffset = BitOffset; 393 Tail = StartBitOffset + DataLayout.getTypeAllocSizeInBits(Type); 394 // Add the storage member to the record. This must be added to the 395 // record before the bitfield members so that it gets laid out before 396 // the bitfields it contains get laid out. 397 Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type)); 398 } 399 // Bitfields get the offset of their storage but come afterward and remain 400 // there after a stable sort. 401 Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset), 402 MemberInfo::Field, nullptr, *Field)); 403 } 404 return; 405 } 406 for (;;) { 407 // Check to see if we need to start a new run. 408 if (Run == FieldEnd) { 409 // If we're out of fields, return. 410 if (Field == FieldEnd) 411 break; 412 // Any non-zero-length bitfield can start a new run. 413 if (Field->getBitWidthValue(Context) != 0) { 414 Run = Field; 415 StartBitOffset = getFieldBitOffset(*Field); 416 Tail = StartBitOffset + Field->getBitWidthValue(Context); 417 } 418 ++Field; 419 continue; 420 } 421 // Add bitfields to the run as long as they qualify. 422 if (Field != FieldEnd && Field->getBitWidthValue(Context) != 0 && 423 Tail == getFieldBitOffset(*Field)) { 424 Tail += Field->getBitWidthValue(Context); 425 ++Field; 426 continue; 427 } 428 // We've hit a break-point in the run and need to emit a storage field. 429 llvm::Type *Type = getIntNType(Tail - StartBitOffset); 430 // Add the storage member to the record and set the bitfield info for all of 431 // the bitfields in the run. Bitfields get the offset of their storage but 432 // come afterward and remain there after a stable sort. 433 Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type)); 434 for (; Run != Field; ++Run) 435 Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset), 436 MemberInfo::Field, nullptr, *Run)); 437 Run = FieldEnd; 438 } 439 } 440 441 void CGRecordLowering::accumulateBases() { 442 // If we've got a primary virtual base, we need to add it with the bases. 443 if (Layout.isPrimaryBaseVirtual()) { 444 const CXXRecordDecl *BaseDecl = Layout.getPrimaryBase(); 445 Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::Base, 446 getStorageType(BaseDecl), BaseDecl)); 447 } 448 // Accumulate the non-virtual bases. 449 for (const auto &Base : RD->bases()) { 450 if (Base.isVirtual()) 451 continue; 452 453 // Bases can be zero-sized even if not technically empty if they 454 // contain only a trailing array member. 455 const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl(); 456 if (!BaseDecl->isEmpty() && 457 !Context.getASTRecordLayout(BaseDecl).getNonVirtualSize().isZero()) 458 Members.push_back(MemberInfo(Layout.getBaseClassOffset(BaseDecl), 459 MemberInfo::Base, getStorageType(BaseDecl), BaseDecl)); 460 } 461 } 462 463 void CGRecordLowering::accumulateVPtrs() { 464 if (Layout.hasOwnVFPtr()) 465 Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::VFPtr, 466 llvm::FunctionType::get(getIntNType(32), /*isVarArg=*/true)-> 467 getPointerTo()->getPointerTo())); 468 if (Layout.hasOwnVBPtr()) 469 Members.push_back(MemberInfo(Layout.getVBPtrOffset(), MemberInfo::VBPtr, 470 llvm::Type::getInt32PtrTy(Types.getLLVMContext()))); 471 } 472 473 void CGRecordLowering::accumulateVBases() { 474 CharUnits ScissorOffset = Layout.getNonVirtualSize(); 475 // In the itanium ABI, it's possible to place a vbase at a dsize that is 476 // smaller than the nvsize. Here we check to see if such a base is placed 477 // before the nvsize and set the scissor offset to that, instead of the 478 // nvsize. 479 if (isOverlappingVBaseABI()) 480 for (const auto &Base : RD->vbases()) { 481 const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl(); 482 if (BaseDecl->isEmpty()) 483 continue; 484 // If the vbase is a primary virtual base of some base, then it doesn't 485 // get its own storage location but instead lives inside of that base. 486 if (Context.isNearlyEmpty(BaseDecl) && !hasOwnStorage(RD, BaseDecl)) 487 continue; 488 ScissorOffset = std::min(ScissorOffset, 489 Layout.getVBaseClassOffset(BaseDecl)); 490 } 491 Members.push_back(MemberInfo(ScissorOffset, MemberInfo::Scissor, nullptr, 492 RD)); 493 for (const auto &Base : RD->vbases()) { 494 const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl(); 495 if (BaseDecl->isEmpty()) 496 continue; 497 CharUnits Offset = Layout.getVBaseClassOffset(BaseDecl); 498 // If the vbase is a primary virtual base of some base, then it doesn't 499 // get its own storage location but instead lives inside of that base. 500 if (isOverlappingVBaseABI() && 501 Context.isNearlyEmpty(BaseDecl) && 502 !hasOwnStorage(RD, BaseDecl)) { 503 Members.push_back(MemberInfo(Offset, MemberInfo::VBase, nullptr, 504 BaseDecl)); 505 continue; 506 } 507 // If we've got a vtordisp, add it as a storage type. 508 if (Layout.getVBaseOffsetsMap().find(BaseDecl)->second.hasVtorDisp()) 509 Members.push_back(StorageInfo(Offset - CharUnits::fromQuantity(4), 510 getIntNType(32))); 511 Members.push_back(MemberInfo(Offset, MemberInfo::VBase, 512 getStorageType(BaseDecl), BaseDecl)); 513 } 514 } 515 516 bool CGRecordLowering::hasOwnStorage(const CXXRecordDecl *Decl, 517 const CXXRecordDecl *Query) { 518 const ASTRecordLayout &DeclLayout = Context.getASTRecordLayout(Decl); 519 if (DeclLayout.isPrimaryBaseVirtual() && DeclLayout.getPrimaryBase() == Query) 520 return false; 521 for (const auto &Base : Decl->bases()) 522 if (!hasOwnStorage(Base.getType()->getAsCXXRecordDecl(), Query)) 523 return false; 524 return true; 525 } 526 527 void CGRecordLowering::calculateZeroInit() { 528 for (std::vector<MemberInfo>::const_iterator Member = Members.begin(), 529 MemberEnd = Members.end(); 530 IsZeroInitializableAsBase && Member != MemberEnd; ++Member) { 531 if (Member->Kind == MemberInfo::Field) { 532 if (!Member->FD || isZeroInitializable(Member->FD)) 533 continue; 534 IsZeroInitializable = IsZeroInitializableAsBase = false; 535 } else if (Member->Kind == MemberInfo::Base || 536 Member->Kind == MemberInfo::VBase) { 537 if (isZeroInitializable(Member->RD)) 538 continue; 539 IsZeroInitializable = false; 540 if (Member->Kind == MemberInfo::Base) 541 IsZeroInitializableAsBase = false; 542 } 543 } 544 } 545 546 void CGRecordLowering::clipTailPadding() { 547 std::vector<MemberInfo>::iterator Prior = Members.begin(); 548 CharUnits Tail = getSize(Prior->Data); 549 for (std::vector<MemberInfo>::iterator Member = Prior + 1, 550 MemberEnd = Members.end(); 551 Member != MemberEnd; ++Member) { 552 // Only members with data and the scissor can cut into tail padding. 553 if (!Member->Data && Member->Kind != MemberInfo::Scissor) 554 continue; 555 if (Member->Offset < Tail) { 556 assert(Prior->Kind == MemberInfo::Field && !Prior->FD && 557 "Only storage fields have tail padding!"); 558 Prior->Data = getByteArrayType(bitsToCharUnits(llvm::alignTo( 559 cast<llvm::IntegerType>(Prior->Data)->getIntegerBitWidth(), 8))); 560 } 561 if (Member->Data) 562 Prior = Member; 563 Tail = Prior->Offset + getSize(Prior->Data); 564 } 565 } 566 567 void CGRecordLowering::determinePacked(bool NVBaseType) { 568 if (Packed) 569 return; 570 CharUnits Alignment = CharUnits::One(); 571 CharUnits NVAlignment = CharUnits::One(); 572 CharUnits NVSize = 573 !NVBaseType && RD ? Layout.getNonVirtualSize() : CharUnits::Zero(); 574 for (std::vector<MemberInfo>::const_iterator Member = Members.begin(), 575 MemberEnd = Members.end(); 576 Member != MemberEnd; ++Member) { 577 if (!Member->Data) 578 continue; 579 // If any member falls at an offset that it not a multiple of its alignment, 580 // then the entire record must be packed. 581 if (Member->Offset % getAlignment(Member->Data)) 582 Packed = true; 583 if (Member->Offset < NVSize) 584 NVAlignment = std::max(NVAlignment, getAlignment(Member->Data)); 585 Alignment = std::max(Alignment, getAlignment(Member->Data)); 586 } 587 // If the size of the record (the capstone's offset) is not a multiple of the 588 // record's alignment, it must be packed. 589 if (Members.back().Offset % Alignment) 590 Packed = true; 591 // If the non-virtual sub-object is not a multiple of the non-virtual 592 // sub-object's alignment, it must be packed. We cannot have a packed 593 // non-virtual sub-object and an unpacked complete object or vise versa. 594 if (NVSize % NVAlignment) 595 Packed = true; 596 // Update the alignment of the sentinal. 597 if (!Packed) 598 Members.back().Data = getIntNType(Context.toBits(Alignment)); 599 } 600 601 void CGRecordLowering::insertPadding() { 602 std::vector<std::pair<CharUnits, CharUnits> > Padding; 603 CharUnits Size = CharUnits::Zero(); 604 for (std::vector<MemberInfo>::const_iterator Member = Members.begin(), 605 MemberEnd = Members.end(); 606 Member != MemberEnd; ++Member) { 607 if (!Member->Data) 608 continue; 609 CharUnits Offset = Member->Offset; 610 assert(Offset >= Size); 611 // Insert padding if we need to. 612 if (Offset != 613 Size.alignTo(Packed ? CharUnits::One() : getAlignment(Member->Data))) 614 Padding.push_back(std::make_pair(Size, Offset - Size)); 615 Size = Offset + getSize(Member->Data); 616 } 617 if (Padding.empty()) 618 return; 619 // Add the padding to the Members list and sort it. 620 for (std::vector<std::pair<CharUnits, CharUnits> >::const_iterator 621 Pad = Padding.begin(), PadEnd = Padding.end(); 622 Pad != PadEnd; ++Pad) 623 Members.push_back(StorageInfo(Pad->first, getByteArrayType(Pad->second))); 624 std::stable_sort(Members.begin(), Members.end()); 625 } 626 627 void CGRecordLowering::fillOutputFields() { 628 for (std::vector<MemberInfo>::const_iterator Member = Members.begin(), 629 MemberEnd = Members.end(); 630 Member != MemberEnd; ++Member) { 631 if (Member->Data) 632 FieldTypes.push_back(Member->Data); 633 if (Member->Kind == MemberInfo::Field) { 634 if (Member->FD) 635 Fields[Member->FD->getCanonicalDecl()] = FieldTypes.size() - 1; 636 // A field without storage must be a bitfield. 637 if (!Member->Data) 638 setBitFieldInfo(Member->FD, Member->Offset, FieldTypes.back()); 639 } else if (Member->Kind == MemberInfo::Base) 640 NonVirtualBases[Member->RD] = FieldTypes.size() - 1; 641 else if (Member->Kind == MemberInfo::VBase) 642 VirtualBases[Member->RD] = FieldTypes.size() - 1; 643 } 644 } 645 646 CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types, 647 const FieldDecl *FD, 648 uint64_t Offset, uint64_t Size, 649 uint64_t StorageSize, 650 CharUnits StorageOffset) { 651 // This function is vestigial from CGRecordLayoutBuilder days but is still 652 // used in GCObjCRuntime.cpp. That usage has a "fixme" attached to it that 653 // when addressed will allow for the removal of this function. 654 llvm::Type *Ty = Types.ConvertTypeForMem(FD->getType()); 655 CharUnits TypeSizeInBytes = 656 CharUnits::fromQuantity(Types.getDataLayout().getTypeAllocSize(Ty)); 657 uint64_t TypeSizeInBits = Types.getContext().toBits(TypeSizeInBytes); 658 659 bool IsSigned = FD->getType()->isSignedIntegerOrEnumerationType(); 660 661 if (Size > TypeSizeInBits) { 662 // We have a wide bit-field. The extra bits are only used for padding, so 663 // if we have a bitfield of type T, with size N: 664 // 665 // T t : N; 666 // 667 // We can just assume that it's: 668 // 669 // T t : sizeof(T); 670 // 671 Size = TypeSizeInBits; 672 } 673 674 // Reverse the bit offsets for big endian machines. Because we represent 675 // a bitfield as a single large integer load, we can imagine the bits 676 // counting from the most-significant-bit instead of the 677 // least-significant-bit. 678 if (Types.getDataLayout().isBigEndian()) { 679 Offset = StorageSize - (Offset + Size); 680 } 681 682 return CGBitFieldInfo(Offset, Size, IsSigned, StorageSize, StorageOffset); 683 } 684 685 CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D, 686 llvm::StructType *Ty) { 687 CGRecordLowering Builder(*this, D, /*Packed=*/false); 688 689 Builder.lower(/*NonVirtualBaseType=*/false); 690 691 // If we're in C++, compute the base subobject type. 692 llvm::StructType *BaseTy = nullptr; 693 if (isa<CXXRecordDecl>(D) && !D->isUnion() && !D->hasAttr<FinalAttr>()) { 694 BaseTy = Ty; 695 if (Builder.Layout.getNonVirtualSize() != Builder.Layout.getSize()) { 696 CGRecordLowering BaseBuilder(*this, D, /*Packed=*/Builder.Packed); 697 BaseBuilder.lower(/*NonVirtualBaseType=*/true); 698 BaseTy = llvm::StructType::create( 699 getLLVMContext(), BaseBuilder.FieldTypes, "", BaseBuilder.Packed); 700 addRecordTypeName(D, BaseTy, ".base"); 701 // BaseTy and Ty must agree on their packedness for getLLVMFieldNo to work 702 // on both of them with the same index. 703 assert(Builder.Packed == BaseBuilder.Packed && 704 "Non-virtual and complete types must agree on packedness"); 705 } 706 } 707 708 // Fill in the struct *after* computing the base type. Filling in the body 709 // signifies that the type is no longer opaque and record layout is complete, 710 // but we may need to recursively layout D while laying D out as a base type. 711 Ty->setBody(Builder.FieldTypes, Builder.Packed); 712 713 CGRecordLayout *RL = 714 new CGRecordLayout(Ty, BaseTy, Builder.IsZeroInitializable, 715 Builder.IsZeroInitializableAsBase); 716 717 RL->NonVirtualBases.swap(Builder.NonVirtualBases); 718 RL->CompleteObjectVirtualBases.swap(Builder.VirtualBases); 719 720 // Add all the field numbers. 721 RL->FieldInfo.swap(Builder.Fields); 722 723 // Add bitfield info. 724 RL->BitFields.swap(Builder.BitFields); 725 726 // Dump the layout, if requested. 727 if (getContext().getLangOpts().DumpRecordLayouts) { 728 llvm::outs() << "\n*** Dumping IRgen Record Layout\n"; 729 llvm::outs() << "Record: "; 730 D->dump(llvm::outs()); 731 llvm::outs() << "\nLayout: "; 732 RL->print(llvm::outs()); 733 } 734 735 #ifndef NDEBUG 736 // Verify that the computed LLVM struct size matches the AST layout size. 737 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(D); 738 739 uint64_t TypeSizeInBits = getContext().toBits(Layout.getSize()); 740 assert(TypeSizeInBits == getDataLayout().getTypeAllocSizeInBits(Ty) && 741 "Type size mismatch!"); 742 743 if (BaseTy) { 744 CharUnits NonVirtualSize = Layout.getNonVirtualSize(); 745 746 uint64_t AlignedNonVirtualTypeSizeInBits = 747 getContext().toBits(NonVirtualSize); 748 749 assert(AlignedNonVirtualTypeSizeInBits == 750 getDataLayout().getTypeAllocSizeInBits(BaseTy) && 751 "Type size mismatch!"); 752 } 753 754 // Verify that the LLVM and AST field offsets agree. 755 llvm::StructType *ST = 756 dyn_cast<llvm::StructType>(RL->getLLVMType()); 757 const llvm::StructLayout *SL = getDataLayout().getStructLayout(ST); 758 759 const ASTRecordLayout &AST_RL = getContext().getASTRecordLayout(D); 760 RecordDecl::field_iterator it = D->field_begin(); 761 for (unsigned i = 0, e = AST_RL.getFieldCount(); i != e; ++i, ++it) { 762 const FieldDecl *FD = *it; 763 764 // For non-bit-fields, just check that the LLVM struct offset matches the 765 // AST offset. 766 if (!FD->isBitField()) { 767 unsigned FieldNo = RL->getLLVMFieldNo(FD); 768 assert(AST_RL.getFieldOffset(i) == SL->getElementOffsetInBits(FieldNo) && 769 "Invalid field offset!"); 770 continue; 771 } 772 773 // Ignore unnamed bit-fields. 774 if (!FD->getDeclName()) 775 continue; 776 777 // Don't inspect zero-length bitfields. 778 if (FD->getBitWidthValue(getContext()) == 0) 779 continue; 780 781 const CGBitFieldInfo &Info = RL->getBitFieldInfo(FD); 782 llvm::Type *ElementTy = ST->getTypeAtIndex(RL->getLLVMFieldNo(FD)); 783 784 // Unions have overlapping elements dictating their layout, but for 785 // non-unions we can verify that this section of the layout is the exact 786 // expected size. 787 if (D->isUnion()) { 788 // For unions we verify that the start is zero and the size 789 // is in-bounds. However, on BE systems, the offset may be non-zero, but 790 // the size + offset should match the storage size in that case as it 791 // "starts" at the back. 792 if (getDataLayout().isBigEndian()) 793 assert(static_cast<unsigned>(Info.Offset + Info.Size) == 794 Info.StorageSize && 795 "Big endian union bitfield does not end at the back"); 796 else 797 assert(Info.Offset == 0 && 798 "Little endian union bitfield with a non-zero offset"); 799 assert(Info.StorageSize <= SL->getSizeInBits() && 800 "Union not large enough for bitfield storage"); 801 } else { 802 assert(Info.StorageSize == 803 getDataLayout().getTypeAllocSizeInBits(ElementTy) && 804 "Storage size does not match the element type size"); 805 } 806 assert(Info.Size > 0 && "Empty bitfield!"); 807 assert(static_cast<unsigned>(Info.Offset) + Info.Size <= Info.StorageSize && 808 "Bitfield outside of its allocated storage"); 809 } 810 #endif 811 812 return RL; 813 } 814 815 void CGRecordLayout::print(raw_ostream &OS) const { 816 OS << "<CGRecordLayout\n"; 817 OS << " LLVMType:" << *CompleteObjectType << "\n"; 818 if (BaseSubobjectType) 819 OS << " NonVirtualBaseLLVMType:" << *BaseSubobjectType << "\n"; 820 OS << " IsZeroInitializable:" << IsZeroInitializable << "\n"; 821 OS << " BitFields:[\n"; 822 823 // Print bit-field infos in declaration order. 824 std::vector<std::pair<unsigned, const CGBitFieldInfo*> > BFIs; 825 for (llvm::DenseMap<const FieldDecl*, CGBitFieldInfo>::const_iterator 826 it = BitFields.begin(), ie = BitFields.end(); 827 it != ie; ++it) { 828 const RecordDecl *RD = it->first->getParent(); 829 unsigned Index = 0; 830 for (RecordDecl::field_iterator 831 it2 = RD->field_begin(); *it2 != it->first; ++it2) 832 ++Index; 833 BFIs.push_back(std::make_pair(Index, &it->second)); 834 } 835 llvm::array_pod_sort(BFIs.begin(), BFIs.end()); 836 for (unsigned i = 0, e = BFIs.size(); i != e; ++i) { 837 OS.indent(4); 838 BFIs[i].second->print(OS); 839 OS << "\n"; 840 } 841 842 OS << "]>\n"; 843 } 844 845 LLVM_DUMP_METHOD void CGRecordLayout::dump() const { 846 print(llvm::errs()); 847 } 848 849 void CGBitFieldInfo::print(raw_ostream &OS) const { 850 OS << "<CGBitFieldInfo" 851 << " Offset:" << Offset 852 << " Size:" << Size 853 << " IsSigned:" << IsSigned 854 << " StorageSize:" << StorageSize 855 << " StorageOffset:" << StorageOffset.getQuantity() << ">"; 856 } 857 858 LLVM_DUMP_METHOD void CGBitFieldInfo::dump() const { 859 print(llvm::errs()); 860 } 861