//===--- CGRecordLayoutBuilder.cpp - CGRecordLayout builder ----*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Builder implementation for CGRecordLayout objects. // //===----------------------------------------------------------------------===// #include "ABIInfoImpl.h" #include "CGCXXABI.h" #include "CGRecordLayout.h" #include "CodeGenTypes.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Attr.h" #include "clang/AST/CXXInheritance.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/Expr.h" #include "clang/AST/RecordLayout.h" #include "clang/Basic/CodeGenOptions.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Type.h" #include "llvm/Support/Debug.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" using namespace clang; using namespace CodeGen; namespace { /// The CGRecordLowering is responsible for lowering an ASTRecordLayout to an /// llvm::Type. Some of the lowering is straightforward, some is not. Here we /// detail some of the complexities and weirdnesses here. /// * LLVM does not have unions - Unions can, in theory be represented by any /// llvm::Type with correct size. We choose a field via a specific heuristic /// and add padding if necessary. /// * LLVM does not have bitfields - Bitfields are collected into contiguous /// runs and allocated as a single storage type for the run. ASTRecordLayout /// contains enough information to determine where the runs break. Microsoft /// and Itanium follow different rules and use different codepaths. /// * It is desired that, when possible, bitfields use the appropriate iN type /// when lowered to llvm types. For example unsigned x : 24 gets lowered to /// i24. This isn't always possible because i24 has storage size of 32 bit /// and if it is possible to use that extra byte of padding we must use [i8 x /// 3] instead of i24. This is computed when accumulating bitfields in /// accumulateBitfields. /// C++ examples that require clipping: /// struct { int a : 24; char b; }; // a must be clipped, b goes at offset 3 /// struct A { int a : 24; ~A(); }; // a must be clipped because: /// struct B : A { char b; }; // b goes at offset 3 /// * The allocation of bitfield access units is described in more detail in /// CGRecordLowering::accumulateBitFields. /// * Clang ignores 0 sized bitfields and 0 sized bases but *not* zero sized /// fields. The existing asserts suggest that LLVM assumes that *every* field /// has an underlying storage type. Therefore empty structures containing /// zero sized subobjects such as empty records or zero sized arrays still get /// a zero sized (empty struct) storage type. /// * Clang reads the complete type rather than the base type when generating /// code to access fields. Bitfields in tail position with tail padding may /// be clipped in the base class but not the complete class (we may discover /// that the tail padding is not used in the complete class.) However, /// because LLVM reads from the complete type it can generate incorrect code /// if we do not clip the tail padding off of the bitfield in the complete /// layout. /// * Itanium allows nearly empty primary virtual bases. These bases don't get /// get their own storage because they're laid out as part of another base /// or at the beginning of the structure. Determining if a VBase actually /// gets storage awkwardly involves a walk of all bases. /// * VFPtrs and VBPtrs do *not* make a record NotZeroInitializable. struct CGRecordLowering { // MemberInfo is a helper structure that contains information about a record // member. In additional to the standard member types, there exists a // sentinel member type that ensures correct rounding. struct MemberInfo { CharUnits Offset; enum InfoKind { VFPtr, VBPtr, Field, Base, VBase } Kind; llvm::Type *Data; union { const FieldDecl *FD; const CXXRecordDecl *RD; }; MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data, const FieldDecl *FD = nullptr) : Offset(Offset), Kind(Kind), Data(Data), FD(FD) {} MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data, const CXXRecordDecl *RD) : Offset(Offset), Kind(Kind), Data(Data), RD(RD) {} // MemberInfos are sorted so we define a < operator. bool operator <(const MemberInfo& a) const { return Offset < a.Offset; } }; // The constructor. CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D, bool Packed); // Short helper routines. /// Constructs a MemberInfo instance from an offset and llvm::Type *. static MemberInfo StorageInfo(CharUnits Offset, llvm::Type *Data) { return MemberInfo(Offset, MemberInfo::Field, Data); } /// The Microsoft bitfield layout rule allocates discrete storage /// units of the field's formal type and only combines adjacent /// fields of the same formal type. We want to emit a layout with /// these discrete storage units instead of combining them into a /// continuous run. bool isDiscreteBitFieldABI() const { return Context.getTargetInfo().getCXXABI().isMicrosoft() || D->isMsStruct(Context); } /// Helper function to check if we are targeting AAPCS. bool isAAPCS() const { return Context.getTargetInfo().getABI().starts_with("aapcs"); } /// Helper function to check if the target machine is BigEndian. bool isBE() const { return Context.getTargetInfo().isBigEndian(); } /// The Itanium base layout rule allows virtual bases to overlap /// other bases, which complicates layout in specific ways. /// /// Note specifically that the ms_struct attribute doesn't change this. bool isOverlappingVBaseABI() const { return !Context.getTargetInfo().getCXXABI().isMicrosoft(); } /// Wraps llvm::Type::getIntNTy with some implicit arguments. llvm::Type *getIntNType(uint64_t NumBits) const { unsigned AlignedBits = llvm::alignTo(NumBits, Context.getCharWidth()); return llvm::Type::getIntNTy(Types.getLLVMContext(), AlignedBits); } /// Get the LLVM type sized as one character unit. llvm::Type *getCharType() const { return llvm::Type::getIntNTy(Types.getLLVMContext(), Context.getCharWidth()); } /// Gets an llvm type of size NumChars and alignment 1. llvm::Type *getByteArrayType(CharUnits NumChars) const { assert(!NumChars.isZero() && "Empty byte arrays aren't allowed."); llvm::Type *Type = getCharType(); return NumChars == CharUnits::One() ? Type : (llvm::Type *)llvm::ArrayType::get(Type, NumChars.getQuantity()); } /// Gets the storage type for a field decl and handles storage /// for itanium bitfields that are smaller than their declared type. llvm::Type *getStorageType(const FieldDecl *FD) const { llvm::Type *Type = Types.ConvertTypeForMem(FD->getType()); if (!FD->isBitField()) return Type; if (isDiscreteBitFieldABI()) return Type; return getIntNType(std::min(FD->getBitWidthValue(Context), (unsigned)Context.toBits(getSize(Type)))); } /// Gets the llvm Basesubobject type from a CXXRecordDecl. llvm::Type *getStorageType(const CXXRecordDecl *RD) const { return Types.getCGRecordLayout(RD).getBaseSubobjectLLVMType(); } CharUnits bitsToCharUnits(uint64_t BitOffset) const { return Context.toCharUnitsFromBits(BitOffset); } CharUnits getSize(llvm::Type *Type) const { return CharUnits::fromQuantity(DataLayout.getTypeAllocSize(Type)); } CharUnits getAlignment(llvm::Type *Type) const { return CharUnits::fromQuantity(DataLayout.getABITypeAlign(Type)); } bool isZeroInitializable(const FieldDecl *FD) const { return Types.isZeroInitializable(FD->getType()); } bool isZeroInitializable(const RecordDecl *RD) const { return Types.isZeroInitializable(RD); } void appendPaddingBytes(CharUnits Size) { if (!Size.isZero()) FieldTypes.push_back(getByteArrayType(Size)); } uint64_t getFieldBitOffset(const FieldDecl *FD) const { return Layout.getFieldOffset(FD->getFieldIndex()); } // Layout routines. void setBitFieldInfo(const FieldDecl *FD, CharUnits StartOffset, llvm::Type *StorageType); /// Lowers an ASTRecordLayout to a llvm type. void lower(bool NonVirtualBaseType); void lowerUnion(bool isNoUniqueAddress); void accumulateFields(bool isNonVirtualBaseType); RecordDecl::field_iterator accumulateBitFields(bool isNonVirtualBaseType, RecordDecl::field_iterator Field, RecordDecl::field_iterator FieldEnd); void computeVolatileBitfields(); void accumulateBases(); void accumulateVPtrs(); void accumulateVBases(); /// Recursively searches all of the bases to find out if a vbase is /// not the primary vbase of some base class. bool hasOwnStorage(const CXXRecordDecl *Decl, const CXXRecordDecl *Query) const; void calculateZeroInit(); CharUnits calculateTailClippingOffset(bool isNonVirtualBaseType) const; void checkBitfieldClipping(bool isNonVirtualBaseType) const; /// Determines if we need a packed llvm struct. void determinePacked(bool NVBaseType); /// Inserts padding everywhere it's needed. void insertPadding(); /// Fills out the structures that are ultimately consumed. void fillOutputFields(); // Input memoization fields. CodeGenTypes &Types; const ASTContext &Context; const RecordDecl *D; const CXXRecordDecl *RD; const ASTRecordLayout &Layout; const llvm::DataLayout &DataLayout; // Helpful intermediate data-structures. std::vector Members; // Output fields, consumed by CodeGenTypes::ComputeRecordLayout. SmallVector FieldTypes; llvm::DenseMap Fields; llvm::DenseMap BitFields; llvm::DenseMap NonVirtualBases; llvm::DenseMap VirtualBases; bool IsZeroInitializable : 1; bool IsZeroInitializableAsBase : 1; bool Packed : 1; private: CGRecordLowering(const CGRecordLowering &) = delete; void operator =(const CGRecordLowering &) = delete; }; } // namespace { CGRecordLowering::CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D, bool Packed) : Types(Types), Context(Types.getContext()), D(D), RD(dyn_cast(D)), Layout(Types.getContext().getASTRecordLayout(D)), DataLayout(Types.getDataLayout()), IsZeroInitializable(true), IsZeroInitializableAsBase(true), Packed(Packed) {} void CGRecordLowering::setBitFieldInfo( const FieldDecl *FD, CharUnits StartOffset, llvm::Type *StorageType) { CGBitFieldInfo &Info = BitFields[FD->getCanonicalDecl()]; Info.IsSigned = FD->getType()->isSignedIntegerOrEnumerationType(); Info.Offset = (unsigned)(getFieldBitOffset(FD) - Context.toBits(StartOffset)); Info.Size = FD->getBitWidthValue(Context); Info.StorageSize = (unsigned)DataLayout.getTypeAllocSizeInBits(StorageType); Info.StorageOffset = StartOffset; if (Info.Size > Info.StorageSize) Info.Size = Info.StorageSize; // Reverse the bit offsets for big endian machines. Because we represent // a bitfield as a single large integer load, we can imagine the bits // counting from the most-significant-bit instead of the // least-significant-bit. if (DataLayout.isBigEndian()) Info.Offset = Info.StorageSize - (Info.Offset + Info.Size); Info.VolatileStorageSize = 0; Info.VolatileOffset = 0; Info.VolatileStorageOffset = CharUnits::Zero(); } void CGRecordLowering::lower(bool NVBaseType) { // The lowering process implemented in this function takes a variety of // carefully ordered phases. // 1) Store all members (fields and bases) in a list and sort them by offset. // 2) Add a 1-byte capstone member at the Size of the structure. // 3) Clip bitfield storages members if their tail padding is or might be // used by another field or base. The clipping process uses the capstone // by treating it as another object that occurs after the record. // 4) Determine if the llvm-struct requires packing. It's important that this // phase occur after clipping, because clipping changes the llvm type. // This phase reads the offset of the capstone when determining packedness // and updates the alignment of the capstone to be equal of the alignment // of the record after doing so. // 5) Insert padding everywhere it is needed. This phase requires 'Packed' to // have been computed and needs to know the alignment of the record in // order to understand if explicit tail padding is needed. // 6) Remove the capstone, we don't need it anymore. // 7) Determine if this record can be zero-initialized. This phase could have // been placed anywhere after phase 1. // 8) Format the complete list of members in a way that can be consumed by // CodeGenTypes::ComputeRecordLayout. CharUnits Size = NVBaseType ? Layout.getNonVirtualSize() : Layout.getSize(); if (D->isUnion()) { lowerUnion(NVBaseType); computeVolatileBitfields(); return; } accumulateFields(NVBaseType); // RD implies C++. if (RD) { accumulateVPtrs(); accumulateBases(); if (Members.empty()) { appendPaddingBytes(Size); computeVolatileBitfields(); return; } if (!NVBaseType) accumulateVBases(); } llvm::stable_sort(Members); checkBitfieldClipping(NVBaseType); Members.push_back(StorageInfo(Size, getIntNType(8))); determinePacked(NVBaseType); insertPadding(); Members.pop_back(); calculateZeroInit(); fillOutputFields(); computeVolatileBitfields(); } void CGRecordLowering::lowerUnion(bool isNoUniqueAddress) { CharUnits LayoutSize = isNoUniqueAddress ? Layout.getDataSize() : Layout.getSize(); llvm::Type *StorageType = nullptr; bool SeenNamedMember = false; // Iterate through the fields setting bitFieldInfo and the Fields array. Also // locate the "most appropriate" storage type. The heuristic for finding the // storage type isn't necessary, the first (non-0-length-bitfield) field's // type would work fine and be simpler but would be different than what we've // been doing and cause lit tests to change. for (const auto *Field : D->fields()) { if (Field->isBitField()) { if (Field->isZeroLengthBitField(Context)) continue; llvm::Type *FieldType = getStorageType(Field); if (LayoutSize < getSize(FieldType)) FieldType = getByteArrayType(LayoutSize); setBitFieldInfo(Field, CharUnits::Zero(), FieldType); } Fields[Field->getCanonicalDecl()] = 0; llvm::Type *FieldType = getStorageType(Field); // Compute zero-initializable status. // This union might not be zero initialized: it may contain a pointer to // data member which might have some exotic initialization sequence. // If this is the case, then we aught not to try and come up with a "better" // type, it might not be very easy to come up with a Constant which // correctly initializes it. if (!SeenNamedMember) { SeenNamedMember = Field->getIdentifier(); if (!SeenNamedMember) if (const auto *FieldRD = Field->getType()->getAsRecordDecl()) SeenNamedMember = FieldRD->findFirstNamedDataMember(); if (SeenNamedMember && !isZeroInitializable(Field)) { IsZeroInitializable = IsZeroInitializableAsBase = false; StorageType = FieldType; } } // Because our union isn't zero initializable, we won't be getting a better // storage type. if (!IsZeroInitializable) continue; // Conditionally update our storage type if we've got a new "better" one. if (!StorageType || getAlignment(FieldType) > getAlignment(StorageType) || (getAlignment(FieldType) == getAlignment(StorageType) && getSize(FieldType) > getSize(StorageType))) StorageType = FieldType; } // If we have no storage type just pad to the appropriate size and return. if (!StorageType) return appendPaddingBytes(LayoutSize); // If our storage size was bigger than our required size (can happen in the // case of packed bitfields on Itanium) then just use an I8 array. if (LayoutSize < getSize(StorageType)) StorageType = getByteArrayType(LayoutSize); FieldTypes.push_back(StorageType); appendPaddingBytes(LayoutSize - getSize(StorageType)); // Set packed if we need it. const auto StorageAlignment = getAlignment(StorageType); assert((Layout.getSize() % StorageAlignment == 0 || Layout.getDataSize() % StorageAlignment) && "Union's standard layout and no_unique_address layout must agree on " "packedness"); if (Layout.getDataSize() % StorageAlignment) Packed = true; } void CGRecordLowering::accumulateFields(bool isNonVirtualBaseType) { for (RecordDecl::field_iterator Field = D->field_begin(), FieldEnd = D->field_end(); Field != FieldEnd;) { if (Field->isBitField()) { Field = accumulateBitFields(isNonVirtualBaseType, Field, FieldEnd); assert((Field == FieldEnd || !Field->isBitField()) && "Failed to accumulate all the bitfields"); } else if (isEmptyFieldForLayout(Context, *Field)) { // Empty fields have no storage. ++Field; } else { // Use base subobject layout for the potentially-overlapping field, // as it is done in RecordLayoutBuilder Members.push_back(MemberInfo( bitsToCharUnits(getFieldBitOffset(*Field)), MemberInfo::Field, Field->isPotentiallyOverlapping() ? getStorageType(Field->getType()->getAsCXXRecordDecl()) : getStorageType(*Field), *Field)); ++Field; } } } // Create members for bitfields. Field is a bitfield, and FieldEnd is the end // iterator of the record. Return the first non-bitfield encountered. We need // to know whether this is the base or complete layout, as virtual bases could // affect the upper bound of bitfield access unit allocation. RecordDecl::field_iterator CGRecordLowering::accumulateBitFields(bool isNonVirtualBaseType, RecordDecl::field_iterator Field, RecordDecl::field_iterator FieldEnd) { if (isDiscreteBitFieldABI()) { // Run stores the first element of the current run of bitfields. FieldEnd is // used as a special value to note that we don't have a current run. A // bitfield run is a contiguous collection of bitfields that can be stored // in the same storage block. Zero-sized bitfields and bitfields that would // cross an alignment boundary break a run and start a new one. RecordDecl::field_iterator Run = FieldEnd; // Tail is the offset of the first bit off the end of the current run. It's // used to determine if the ASTRecordLayout is treating these two bitfields // as contiguous. StartBitOffset is offset of the beginning of the Run. uint64_t StartBitOffset, Tail = 0; for (; Field != FieldEnd && Field->isBitField(); ++Field) { // Zero-width bitfields end runs. if (Field->isZeroLengthBitField(Context)) { Run = FieldEnd; continue; } uint64_t BitOffset = getFieldBitOffset(*Field); llvm::Type *Type = Types.ConvertTypeForMem(Field->getType()); // If we don't have a run yet, or don't live within the previous run's // allocated storage then we allocate some storage and start a new run. if (Run == FieldEnd || BitOffset >= Tail) { Run = Field; StartBitOffset = BitOffset; Tail = StartBitOffset + DataLayout.getTypeAllocSizeInBits(Type); // Add the storage member to the record. This must be added to the // record before the bitfield members so that it gets laid out before // the bitfields it contains get laid out. Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type)); } // Bitfields get the offset of their storage but come afterward and remain // there after a stable sort. Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset), MemberInfo::Field, nullptr, *Field)); } return Field; } // The SysV ABI can overlap bitfield storage units with both other bitfield // storage units /and/ other non-bitfield data members. Accessing a sequence // of bitfields mustn't interfere with adjacent non-bitfields -- they're // permitted to be accessed in separate threads for instance. // We split runs of bit-fields into a sequence of "access units". When we emit // a load or store of a bit-field, we'll load/store the entire containing // access unit. As mentioned, the standard requires that these loads and // stores must not interfere with accesses to other memory locations, and it // defines the bit-field's memory location as the current run of // non-zero-width bit-fields. So an access unit must never overlap with // non-bit-field storage or cross a zero-width bit-field. Otherwise, we're // free to draw the lines as we see fit. // Drawing these lines well can be complicated. LLVM generally can't modify a // program to access memory that it didn't before, so using very narrow access // units can prevent the compiler from using optimal access patterns. For // example, suppose a run of bit-fields occupies four bytes in a struct. If we // split that into four 1-byte access units, then a sequence of assignments // that doesn't touch all four bytes may have to be emitted with multiple // 8-bit stores instead of a single 32-bit store. On the other hand, if we use // very wide access units, we may find ourselves emitting accesses to // bit-fields we didn't really need to touch, just because LLVM was unable to // clean up after us. // It is desirable to have access units be aligned powers of 2 no larger than // a register. (On non-strict alignment ISAs, the alignment requirement can be // dropped.) A three byte access unit will be accessed using 2-byte and 1-byte // accesses and bit manipulation. If no bitfield straddles across the two // separate accesses, it is better to have separate 2-byte and 1-byte access // units, as then LLVM will not generate unnecessary memory accesses, or bit // manipulation. Similarly, on a strict-alignment architecture, it is better // to keep access-units naturally aligned, to avoid similar bit // manipulation synthesizing larger unaligned accesses. // Bitfields that share parts of a single byte are, of necessity, placed in // the same access unit. That unit will encompass a consecutive run where // adjacent bitfields share parts of a byte. (The first bitfield of such an // access unit will start at the beginning of a byte.) // We then try and accumulate adjacent access units when the combined unit is // naturally sized, no larger than a register, and (on a strict alignment // ISA), naturally aligned. Note that this requires lookahead to one or more // subsequent access units. For instance, consider a 2-byte access-unit // followed by 2 1-byte units. We can merge that into a 4-byte access-unit, // but we would not want to merge a 2-byte followed by a single 1-byte (and no // available tail padding). We keep track of the best access unit seen so far, // and use that when we determine we cannot accumulate any more. Then we start // again at the bitfield following that best one. // The accumulation is also prevented when: // *) it would cross a character-aigned zero-width bitfield, or // *) fine-grained bitfield access option is in effect. CharUnits RegSize = bitsToCharUnits(Context.getTargetInfo().getRegisterWidth()); unsigned CharBits = Context.getCharWidth(); // Limit of useable tail padding at end of the record. Computed lazily and // cached here. CharUnits ScissorOffset = CharUnits::Zero(); // Data about the start of the span we're accumulating to create an access // unit from. Begin is the first bitfield of the span. If Begin is FieldEnd, // we've not got a current span. The span starts at the BeginOffset character // boundary. BitSizeSinceBegin is the size (in bits) of the span -- this might // include padding when we've advanced to a subsequent bitfield run. RecordDecl::field_iterator Begin = FieldEnd; CharUnits BeginOffset; uint64_t BitSizeSinceBegin; // The (non-inclusive) end of the largest acceptable access unit we've found // since Begin. If this is Begin, we're gathering the initial set of bitfields // of a new span. BestEndOffset is the end of that acceptable access unit -- // it might extend beyond the last character of the bitfield run, using // available padding characters. RecordDecl::field_iterator BestEnd = Begin; CharUnits BestEndOffset; bool BestClipped; // Whether the representation must be in a byte array. for (;;) { // AtAlignedBoundary is true iff Field is the (potential) start of a new // span (or the end of the bitfields). When true, LimitOffset is the // character offset of that span and Barrier indicates whether the new // span cannot be merged into the current one. bool AtAlignedBoundary = false; bool Barrier = false; if (Field != FieldEnd && Field->isBitField()) { uint64_t BitOffset = getFieldBitOffset(*Field); if (Begin == FieldEnd) { // Beginning a new span. Begin = Field; BestEnd = Begin; assert((BitOffset % CharBits) == 0 && "Not at start of char"); BeginOffset = bitsToCharUnits(BitOffset); BitSizeSinceBegin = 0; } else if ((BitOffset % CharBits) != 0) { // Bitfield occupies the same character as previous bitfield, it must be // part of the same span. This can include zero-length bitfields, should // the target not align them to character boundaries. Such non-alignment // is at variance with the standards, which require zero-length // bitfields be a barrier between access units. But of course we can't // achieve that in the middle of a character. assert(BitOffset == Context.toBits(BeginOffset) + BitSizeSinceBegin && "Concatenating non-contiguous bitfields"); } else { // Bitfield potentially begins a new span. This includes zero-length // bitfields on non-aligning targets that lie at character boundaries // (those are barriers to merging). if (Field->isZeroLengthBitField(Context)) Barrier = true; AtAlignedBoundary = true; } } else { // We've reached the end of the bitfield run. Either we're done, or this // is a barrier for the current span. if (Begin == FieldEnd) break; Barrier = true; AtAlignedBoundary = true; } // InstallBest indicates whether we should create an access unit for the // current best span: fields [Begin, BestEnd) occupying characters // [BeginOffset, BestEndOffset). bool InstallBest = false; if (AtAlignedBoundary) { // Field is the start of a new span or the end of the bitfields. The // just-seen span now extends to BitSizeSinceBegin. // Determine if we can accumulate that just-seen span into the current // accumulation. CharUnits AccessSize = bitsToCharUnits(BitSizeSinceBegin + CharBits - 1); if (BestEnd == Begin) { // This is the initial run at the start of a new span. By definition, // this is the best seen so far. BestEnd = Field; BestEndOffset = BeginOffset + AccessSize; // Assume clipped until proven not below. BestClipped = true; if (!BitSizeSinceBegin) // A zero-sized initial span -- this will install nothing and reset // for another. InstallBest = true; } else if (AccessSize > RegSize) // Accumulating the just-seen span would create a multi-register access // unit, which would increase register pressure. InstallBest = true; if (!InstallBest) { // Determine if accumulating the just-seen span will create an expensive // access unit or not. llvm::Type *Type = getIntNType(Context.toBits(AccessSize)); if (!Context.getTargetInfo().hasCheapUnalignedBitFieldAccess()) { // Unaligned accesses are expensive. Only accumulate if the new unit // is naturally aligned. Otherwise install the best we have, which is // either the initial access unit (can't do better), or a naturally // aligned accumulation (since we would have already installed it if // it wasn't naturally aligned). CharUnits Align = getAlignment(Type); if (Align > Layout.getAlignment()) // The alignment required is greater than the containing structure // itself. InstallBest = true; else if (!BeginOffset.isMultipleOf(Align)) // The access unit is not at a naturally aligned offset within the // structure. InstallBest = true; if (InstallBest && BestEnd == Field) // We're installing the first span, whose clipping was presumed // above. Compute it correctly. if (getSize(Type) == AccessSize) BestClipped = false; } if (!InstallBest) { // Find the next used storage offset to determine what the limit of // the current span is. That's either the offset of the next field // with storage (which might be Field itself) or the end of the // non-reusable tail padding. CharUnits LimitOffset; for (auto Probe = Field; Probe != FieldEnd; ++Probe) if (!isEmptyFieldForLayout(Context, *Probe)) { // A member with storage sets the limit. assert((getFieldBitOffset(*Probe) % CharBits) == 0 && "Next storage is not byte-aligned"); LimitOffset = bitsToCharUnits(getFieldBitOffset(*Probe)); goto FoundLimit; } // We reached the end of the fields, determine the bounds of useable // tail padding. As this can be complex for C++, we cache the result. if (ScissorOffset.isZero()) { ScissorOffset = calculateTailClippingOffset(isNonVirtualBaseType); assert(!ScissorOffset.isZero() && "Tail clipping at zero"); } LimitOffset = ScissorOffset; FoundLimit:; CharUnits TypeSize = getSize(Type); if (BeginOffset + TypeSize <= LimitOffset) { // There is space before LimitOffset to create a naturally-sized // access unit. BestEndOffset = BeginOffset + TypeSize; BestEnd = Field; BestClipped = false; } if (Barrier) // The next field is a barrier that we cannot merge across. InstallBest = true; else if (Types.getCodeGenOpts().FineGrainedBitfieldAccesses) // Fine-grained access, so no merging of spans. InstallBest = true; else // Otherwise, we're not installing. Update the bit size // of the current span to go all the way to LimitOffset, which is // the (aligned) offset of next bitfield to consider. BitSizeSinceBegin = Context.toBits(LimitOffset - BeginOffset); } } } if (InstallBest) { assert((Field == FieldEnd || !Field->isBitField() || (getFieldBitOffset(*Field) % CharBits) == 0) && "Installing but not at an aligned bitfield or limit"); CharUnits AccessSize = BestEndOffset - BeginOffset; if (!AccessSize.isZero()) { // Add the storage member for the access unit to the record. The // bitfields get the offset of their storage but come afterward and // remain there after a stable sort. llvm::Type *Type; if (BestClipped) { assert(getSize(getIntNType(Context.toBits(AccessSize))) > AccessSize && "Clipped access need not be clipped"); Type = getByteArrayType(AccessSize); } else { Type = getIntNType(Context.toBits(AccessSize)); assert(getSize(Type) == AccessSize && "Unclipped access must be clipped"); } Members.push_back(StorageInfo(BeginOffset, Type)); for (; Begin != BestEnd; ++Begin) if (!Begin->isZeroLengthBitField(Context)) Members.push_back( MemberInfo(BeginOffset, MemberInfo::Field, nullptr, *Begin)); } // Reset to start a new span. Field = BestEnd; Begin = FieldEnd; } else { assert(Field != FieldEnd && Field->isBitField() && "Accumulating past end of bitfields"); assert(!Barrier && "Accumulating across barrier"); // Accumulate this bitfield into the current (potential) span. BitSizeSinceBegin += Field->getBitWidthValue(Context); ++Field; } } return Field; } void CGRecordLowering::accumulateBases() { // If we've got a primary virtual base, we need to add it with the bases. if (Layout.isPrimaryBaseVirtual()) { const CXXRecordDecl *BaseDecl = Layout.getPrimaryBase(); Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::Base, getStorageType(BaseDecl), BaseDecl)); } // Accumulate the non-virtual bases. for (const auto &Base : RD->bases()) { if (Base.isVirtual()) continue; // Bases can be zero-sized even if not technically empty if they // contain only a trailing array member. const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl(); if (!isEmptyRecordForLayout(Context, Base.getType()) && !Context.getASTRecordLayout(BaseDecl).getNonVirtualSize().isZero()) Members.push_back(MemberInfo(Layout.getBaseClassOffset(BaseDecl), MemberInfo::Base, getStorageType(BaseDecl), BaseDecl)); } } /// The AAPCS that defines that, when possible, bit-fields should /// be accessed using containers of the declared type width: /// When a volatile bit-field is read, and its container does not overlap with /// any non-bit-field member or any zero length bit-field member, its container /// must be read exactly once using the access width appropriate to the type of /// the container. When a volatile bit-field is written, and its container does /// not overlap with any non-bit-field member or any zero-length bit-field /// member, its container must be read exactly once and written exactly once /// using the access width appropriate to the type of the container. The two /// accesses are not atomic. /// /// Enforcing the width restriction can be disabled using /// -fno-aapcs-bitfield-width. void CGRecordLowering::computeVolatileBitfields() { if (!isAAPCS() || !Types.getCodeGenOpts().AAPCSBitfieldWidth) return; for (auto &I : BitFields) { const FieldDecl *Field = I.first; CGBitFieldInfo &Info = I.second; llvm::Type *ResLTy = Types.ConvertTypeForMem(Field->getType()); // If the record alignment is less than the type width, we can't enforce a // aligned load, bail out. if ((uint64_t)(Context.toBits(Layout.getAlignment())) < ResLTy->getPrimitiveSizeInBits()) continue; // CGRecordLowering::setBitFieldInfo() pre-adjusts the bit-field offsets // for big-endian targets, but it assumes a container of width // Info.StorageSize. Since AAPCS uses a different container size (width // of the type), we first undo that calculation here and redo it once // the bit-field offset within the new container is calculated. const unsigned OldOffset = isBE() ? Info.StorageSize - (Info.Offset + Info.Size) : Info.Offset; // Offset to the bit-field from the beginning of the struct. const unsigned AbsoluteOffset = Context.toBits(Info.StorageOffset) + OldOffset; // Container size is the width of the bit-field type. const unsigned StorageSize = ResLTy->getPrimitiveSizeInBits(); // Nothing to do if the access uses the desired // container width and is naturally aligned. if (Info.StorageSize == StorageSize && (OldOffset % StorageSize == 0)) continue; // Offset within the container. unsigned Offset = AbsoluteOffset & (StorageSize - 1); // Bail out if an aligned load of the container cannot cover the entire // bit-field. This can happen for example, if the bit-field is part of a // packed struct. AAPCS does not define access rules for such cases, we let // clang to follow its own rules. if (Offset + Info.Size > StorageSize) continue; // Re-adjust offsets for big-endian targets. if (isBE()) Offset = StorageSize - (Offset + Info.Size); const CharUnits StorageOffset = Context.toCharUnitsFromBits(AbsoluteOffset & ~(StorageSize - 1)); const CharUnits End = StorageOffset + Context.toCharUnitsFromBits(StorageSize) - CharUnits::One(); const ASTRecordLayout &Layout = Context.getASTRecordLayout(Field->getParent()); // If we access outside memory outside the record, than bail out. const CharUnits RecordSize = Layout.getSize(); if (End >= RecordSize) continue; // Bail out if performing this load would access non-bit-fields members. bool Conflict = false; for (const auto *F : D->fields()) { // Allow sized bit-fields overlaps. if (F->isBitField() && !F->isZeroLengthBitField(Context)) continue; const CharUnits FOffset = Context.toCharUnitsFromBits( Layout.getFieldOffset(F->getFieldIndex())); // As C11 defines, a zero sized bit-field defines a barrier, so // fields after and before it should be race condition free. // The AAPCS acknowledges it and imposes no restritions when the // natural container overlaps a zero-length bit-field. if (F->isZeroLengthBitField(Context)) { if (End > FOffset && StorageOffset < FOffset) { Conflict = true; break; } } const CharUnits FEnd = FOffset + Context.toCharUnitsFromBits( Types.ConvertTypeForMem(F->getType())->getPrimitiveSizeInBits()) - CharUnits::One(); // If no overlap, continue. if (End < FOffset || FEnd < StorageOffset) continue; // The desired load overlaps a non-bit-field member, bail out. Conflict = true; break; } if (Conflict) continue; // Write the new bit-field access parameters. // As the storage offset now is defined as the number of elements from the // start of the structure, we should divide the Offset by the element size. Info.VolatileStorageOffset = StorageOffset / Context.toCharUnitsFromBits(StorageSize).getQuantity(); Info.VolatileStorageSize = StorageSize; Info.VolatileOffset = Offset; } } void CGRecordLowering::accumulateVPtrs() { if (Layout.hasOwnVFPtr()) Members.push_back( MemberInfo(CharUnits::Zero(), MemberInfo::VFPtr, llvm::PointerType::getUnqual(Types.getLLVMContext()))); if (Layout.hasOwnVBPtr()) Members.push_back( MemberInfo(Layout.getVBPtrOffset(), MemberInfo::VBPtr, llvm::PointerType::getUnqual(Types.getLLVMContext()))); } CharUnits CGRecordLowering::calculateTailClippingOffset(bool isNonVirtualBaseType) const { if (!RD) return Layout.getDataSize(); CharUnits ScissorOffset = Layout.getNonVirtualSize(); // In the itanium ABI, it's possible to place a vbase at a dsize that is // smaller than the nvsize. Here we check to see if such a base is placed // before the nvsize and set the scissor offset to that, instead of the // nvsize. if (!isNonVirtualBaseType && isOverlappingVBaseABI()) for (const auto &Base : RD->vbases()) { const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl(); if (isEmptyRecordForLayout(Context, Base.getType())) continue; // If the vbase is a primary virtual base of some base, then it doesn't // get its own storage location but instead lives inside of that base. if (Context.isNearlyEmpty(BaseDecl) && !hasOwnStorage(RD, BaseDecl)) continue; ScissorOffset = std::min(ScissorOffset, Layout.getVBaseClassOffset(BaseDecl)); } return ScissorOffset; } void CGRecordLowering::accumulateVBases() { for (const auto &Base : RD->vbases()) { const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl(); if (isEmptyRecordForLayout(Context, Base.getType())) continue; CharUnits Offset = Layout.getVBaseClassOffset(BaseDecl); // If the vbase is a primary virtual base of some base, then it doesn't // get its own storage location but instead lives inside of that base. if (isOverlappingVBaseABI() && Context.isNearlyEmpty(BaseDecl) && !hasOwnStorage(RD, BaseDecl)) { Members.push_back(MemberInfo(Offset, MemberInfo::VBase, nullptr, BaseDecl)); continue; } // If we've got a vtordisp, add it as a storage type. if (Layout.getVBaseOffsetsMap().find(BaseDecl)->second.hasVtorDisp()) Members.push_back(StorageInfo(Offset - CharUnits::fromQuantity(4), getIntNType(32))); Members.push_back(MemberInfo(Offset, MemberInfo::VBase, getStorageType(BaseDecl), BaseDecl)); } } bool CGRecordLowering::hasOwnStorage(const CXXRecordDecl *Decl, const CXXRecordDecl *Query) const { const ASTRecordLayout &DeclLayout = Context.getASTRecordLayout(Decl); if (DeclLayout.isPrimaryBaseVirtual() && DeclLayout.getPrimaryBase() == Query) return false; for (const auto &Base : Decl->bases()) if (!hasOwnStorage(Base.getType()->getAsCXXRecordDecl(), Query)) return false; return true; } void CGRecordLowering::calculateZeroInit() { for (std::vector::const_iterator Member = Members.begin(), MemberEnd = Members.end(); IsZeroInitializableAsBase && Member != MemberEnd; ++Member) { if (Member->Kind == MemberInfo::Field) { if (!Member->FD || isZeroInitializable(Member->FD)) continue; IsZeroInitializable = IsZeroInitializableAsBase = false; } else if (Member->Kind == MemberInfo::Base || Member->Kind == MemberInfo::VBase) { if (isZeroInitializable(Member->RD)) continue; IsZeroInitializable = false; if (Member->Kind == MemberInfo::Base) IsZeroInitializableAsBase = false; } } } // Verify accumulateBitfields computed the correct storage representations. void CGRecordLowering::checkBitfieldClipping(bool IsNonVirtualBaseType) const { #ifndef NDEBUG auto ScissorOffset = calculateTailClippingOffset(IsNonVirtualBaseType); auto Tail = CharUnits::Zero(); for (const auto &M : Members) { // Only members with data could possibly overlap. if (!M.Data) continue; assert(M.Offset >= Tail && "Bitfield access unit is not clipped"); Tail = M.Offset + getSize(M.Data); assert((Tail <= ScissorOffset || M.Offset >= ScissorOffset) && "Bitfield straddles scissor offset"); } #endif } void CGRecordLowering::determinePacked(bool NVBaseType) { if (Packed) return; CharUnits Alignment = CharUnits::One(); CharUnits NVAlignment = CharUnits::One(); CharUnits NVSize = !NVBaseType && RD ? Layout.getNonVirtualSize() : CharUnits::Zero(); for (std::vector::const_iterator Member = Members.begin(), MemberEnd = Members.end(); Member != MemberEnd; ++Member) { if (!Member->Data) continue; // If any member falls at an offset that it not a multiple of its alignment, // then the entire record must be packed. if (Member->Offset % getAlignment(Member->Data)) Packed = true; if (Member->Offset < NVSize) NVAlignment = std::max(NVAlignment, getAlignment(Member->Data)); Alignment = std::max(Alignment, getAlignment(Member->Data)); } // If the size of the record (the capstone's offset) is not a multiple of the // record's alignment, it must be packed. if (Members.back().Offset % Alignment) Packed = true; // If the non-virtual sub-object is not a multiple of the non-virtual // sub-object's alignment, it must be packed. We cannot have a packed // non-virtual sub-object and an unpacked complete object or vise versa. if (NVSize % NVAlignment) Packed = true; // Update the alignment of the sentinel. if (!Packed) Members.back().Data = getIntNType(Context.toBits(Alignment)); } void CGRecordLowering::insertPadding() { std::vector > Padding; CharUnits Size = CharUnits::Zero(); for (std::vector::const_iterator Member = Members.begin(), MemberEnd = Members.end(); Member != MemberEnd; ++Member) { if (!Member->Data) continue; CharUnits Offset = Member->Offset; assert(Offset >= Size); // Insert padding if we need to. if (Offset != Size.alignTo(Packed ? CharUnits::One() : getAlignment(Member->Data))) Padding.push_back(std::make_pair(Size, Offset - Size)); Size = Offset + getSize(Member->Data); } if (Padding.empty()) return; // Add the padding to the Members list and sort it. for (std::vector >::const_iterator Pad = Padding.begin(), PadEnd = Padding.end(); Pad != PadEnd; ++Pad) Members.push_back(StorageInfo(Pad->first, getByteArrayType(Pad->second))); llvm::stable_sort(Members); } void CGRecordLowering::fillOutputFields() { for (std::vector::const_iterator Member = Members.begin(), MemberEnd = Members.end(); Member != MemberEnd; ++Member) { if (Member->Data) FieldTypes.push_back(Member->Data); if (Member->Kind == MemberInfo::Field) { if (Member->FD) Fields[Member->FD->getCanonicalDecl()] = FieldTypes.size() - 1; // A field without storage must be a bitfield. if (!Member->Data) setBitFieldInfo(Member->FD, Member->Offset, FieldTypes.back()); } else if (Member->Kind == MemberInfo::Base) NonVirtualBases[Member->RD] = FieldTypes.size() - 1; else if (Member->Kind == MemberInfo::VBase) VirtualBases[Member->RD] = FieldTypes.size() - 1; } } CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types, const FieldDecl *FD, uint64_t Offset, uint64_t Size, uint64_t StorageSize, CharUnits StorageOffset) { // This function is vestigial from CGRecordLayoutBuilder days but is still // used in GCObjCRuntime.cpp. That usage has a "fixme" attached to it that // when addressed will allow for the removal of this function. llvm::Type *Ty = Types.ConvertTypeForMem(FD->getType()); CharUnits TypeSizeInBytes = CharUnits::fromQuantity(Types.getDataLayout().getTypeAllocSize(Ty)); uint64_t TypeSizeInBits = Types.getContext().toBits(TypeSizeInBytes); bool IsSigned = FD->getType()->isSignedIntegerOrEnumerationType(); if (Size > TypeSizeInBits) { // We have a wide bit-field. The extra bits are only used for padding, so // if we have a bitfield of type T, with size N: // // T t : N; // // We can just assume that it's: // // T t : sizeof(T); // Size = TypeSizeInBits; } // Reverse the bit offsets for big endian machines. Because we represent // a bitfield as a single large integer load, we can imagine the bits // counting from the most-significant-bit instead of the // least-significant-bit. if (Types.getDataLayout().isBigEndian()) { Offset = StorageSize - (Offset + Size); } return CGBitFieldInfo(Offset, Size, IsSigned, StorageSize, StorageOffset); } std::unique_ptr CodeGenTypes::ComputeRecordLayout(const RecordDecl *D, llvm::StructType *Ty) { CGRecordLowering Builder(*this, D, /*Packed=*/false); Builder.lower(/*NonVirtualBaseType=*/false); // If we're in C++, compute the base subobject type. llvm::StructType *BaseTy = nullptr; if (isa(D)) { BaseTy = Ty; if (Builder.Layout.getNonVirtualSize() != Builder.Layout.getSize()) { CGRecordLowering BaseBuilder(*this, D, /*Packed=*/Builder.Packed); BaseBuilder.lower(/*NonVirtualBaseType=*/true); BaseTy = llvm::StructType::create( getLLVMContext(), BaseBuilder.FieldTypes, "", BaseBuilder.Packed); addRecordTypeName(D, BaseTy, ".base"); // BaseTy and Ty must agree on their packedness for getLLVMFieldNo to work // on both of them with the same index. assert(Builder.Packed == BaseBuilder.Packed && "Non-virtual and complete types must agree on packedness"); } } // Fill in the struct *after* computing the base type. Filling in the body // signifies that the type is no longer opaque and record layout is complete, // but we may need to recursively layout D while laying D out as a base type. Ty->setBody(Builder.FieldTypes, Builder.Packed); auto RL = std::make_unique( Ty, BaseTy, (bool)Builder.IsZeroInitializable, (bool)Builder.IsZeroInitializableAsBase); RL->NonVirtualBases.swap(Builder.NonVirtualBases); RL->CompleteObjectVirtualBases.swap(Builder.VirtualBases); // Add all the field numbers. RL->FieldInfo.swap(Builder.Fields); // Add bitfield info. RL->BitFields.swap(Builder.BitFields); // Dump the layout, if requested. if (getContext().getLangOpts().DumpRecordLayouts) { llvm::outs() << "\n*** Dumping IRgen Record Layout\n"; llvm::outs() << "Record: "; D->dump(llvm::outs()); llvm::outs() << "\nLayout: "; RL->print(llvm::outs()); } #ifndef NDEBUG // Verify that the computed LLVM struct size matches the AST layout size. const ASTRecordLayout &Layout = getContext().getASTRecordLayout(D); uint64_t TypeSizeInBits = getContext().toBits(Layout.getSize()); assert(TypeSizeInBits == getDataLayout().getTypeAllocSizeInBits(Ty) && "Type size mismatch!"); if (BaseTy) { CharUnits NonVirtualSize = Layout.getNonVirtualSize(); uint64_t AlignedNonVirtualTypeSizeInBits = getContext().toBits(NonVirtualSize); assert(AlignedNonVirtualTypeSizeInBits == getDataLayout().getTypeAllocSizeInBits(BaseTy) && "Type size mismatch!"); } // Verify that the LLVM and AST field offsets agree. llvm::StructType *ST = RL->getLLVMType(); const llvm::StructLayout *SL = getDataLayout().getStructLayout(ST); const ASTRecordLayout &AST_RL = getContext().getASTRecordLayout(D); RecordDecl::field_iterator it = D->field_begin(); for (unsigned i = 0, e = AST_RL.getFieldCount(); i != e; ++i, ++it) { const FieldDecl *FD = *it; // Ignore zero-sized fields. if (isEmptyFieldForLayout(getContext(), FD)) continue; // For non-bit-fields, just check that the LLVM struct offset matches the // AST offset. if (!FD->isBitField()) { unsigned FieldNo = RL->getLLVMFieldNo(FD); assert(AST_RL.getFieldOffset(i) == SL->getElementOffsetInBits(FieldNo) && "Invalid field offset!"); continue; } // Ignore unnamed bit-fields. if (!FD->getDeclName()) continue; const CGBitFieldInfo &Info = RL->getBitFieldInfo(FD); llvm::Type *ElementTy = ST->getTypeAtIndex(RL->getLLVMFieldNo(FD)); // Unions have overlapping elements dictating their layout, but for // non-unions we can verify that this section of the layout is the exact // expected size. if (D->isUnion()) { // For unions we verify that the start is zero and the size // is in-bounds. However, on BE systems, the offset may be non-zero, but // the size + offset should match the storage size in that case as it // "starts" at the back. if (getDataLayout().isBigEndian()) assert(static_cast(Info.Offset + Info.Size) == Info.StorageSize && "Big endian union bitfield does not end at the back"); else assert(Info.Offset == 0 && "Little endian union bitfield with a non-zero offset"); assert(Info.StorageSize <= SL->getSizeInBits() && "Union not large enough for bitfield storage"); } else { assert((Info.StorageSize == getDataLayout().getTypeAllocSizeInBits(ElementTy) || Info.VolatileStorageSize == getDataLayout().getTypeAllocSizeInBits(ElementTy)) && "Storage size does not match the element type size"); } assert(Info.Size > 0 && "Empty bitfield!"); assert(static_cast(Info.Offset) + Info.Size <= Info.StorageSize && "Bitfield outside of its allocated storage"); } #endif return RL; } void CGRecordLayout::print(raw_ostream &OS) const { OS << " > BFIs; for (llvm::DenseMap::const_iterator it = BitFields.begin(), ie = BitFields.end(); it != ie; ++it) { const RecordDecl *RD = it->first->getParent(); unsigned Index = 0; for (RecordDecl::field_iterator it2 = RD->field_begin(); *it2 != it->first; ++it2) ++Index; BFIs.push_back(std::make_pair(Index, &it->second)); } llvm::array_pod_sort(BFIs.begin(), BFIs.end()); for (unsigned i = 0, e = BFIs.size(); i != e; ++i) { OS.indent(4); BFIs[i].second->print(OS); OS << "\n"; } OS << "]>\n"; } LLVM_DUMP_METHOD void CGRecordLayout::dump() const { print(llvm::errs()); } void CGBitFieldInfo::print(raw_ostream &OS) const { OS << ""; } LLVM_DUMP_METHOD void CGBitFieldInfo::dump() const { print(llvm::errs()); }