[COFF] Reduce the size of Chunk and SectionChunk, NFC

[rnk]

Summary

Reorder the fields in both to use padding more efficiently, and add more
comments on the purpose of the fields.

Replace std::vector<SectionChunk*> AssociativeChildren with a
singly-linked list. This avoids the separate vector allocation to list
associative children, and shrinks the 3 pointers used for the typically
empty vector down to 1.

In the end, this reduces the sum of heap allocations used to link
browser_tests.exe with NO PDB by 13.10%, going from 2,248,728 KB to
1,954,071 KB of heap. These numbers exclude memory mapped files, which
are of course a significant factor in LLD's memory usage.

[rnk]

• Fix -Wreorder

[ruiu]

lld/COFF/Chunks.cpp

47

This might be useful but at the same time it looks a bit overly cautious? Perhaps the symbol size is more important but we don't have something like this for them, for example.

[rnk]

lld/COFF/Chunks.cpp

47

Well, we don't have checks for symbol size yet. :)

Given that we don't have performance monitoring, I really want people to think hard before they casually add another field to SectionChunk. I wouldn't insist on it if we did, but these types of static_asserts have proven useful in LLVM for preventing size creep.

[ruiu]

lld/COFF/Chunks.cpp

47

Then maybe reiterating everything again, how about checking directly with a number like static_assert(sizeof(Chunk) == 48)? This should suffice to prevent making the struct larger by accident.

[rnk]

lld/COFF/Chunks.cpp

47

It would be wrong for 32-bit. Rather than trying to express it as math on sizeof(void*), I think the struct makes it clearer. And it helps document hidden members like vptr.

[aganea]

@rnk wrote:
This reduces the total size of all LLD heap allocations by 5.22%

What is the total heap size before/after? What percentage of that heap size is used by Chunks? How many of them do you have?

lld/COFF/Chunks.cpp

79

Is std::vector<SectionChunk *>'s implementation guaranteed to be 3 pointers? Wouldn't something like AlignedCharArrayUnion<std::vector<SectionChunk *>> be better? Just wondering.

lld/COFF/Chunks.h

127

64-bit for a value that's probably <10 most of the time, seems like an awful waste of space ;-)

If this takes so much memory, it'd be interesting to investigate (in terms of performance and dynamic value range) if some of the pointer members below could be converted to offset / bitfields.

[ruiu]

lld/COFF/Chunks.cpp

47

Yeah, but it still feels weird to me to repeat all the members again in a different file just for the purpose of assertion. For 32-bit, we can just set the upper bound like static_assert(sizeof(Chunk) <= 48) where 48 is the size of the struct in 64-bit.

[rnk]

In D59797#1442250, @aganea wrote:

@rnk wrote:
This reduces the total size of all LLD heap allocations by 5.22%

What is the total heap size before/after? What percentage of that heap size is used by Chunks? How many of them do you have?

I used the VS memory profiling tool and used the type view to see the most commonly allocated types. "void" just means allocations whose type wasn't determined, and a lot of it comes from vectors, specifically the new RelocTargets vector @mstorsjo added.

Before:
heap usage: 176,077 KB
type                                    count           size
lld-link.exe!lld::coff::SectionChunk    370,809         71,195,328
void                                    251,990         63,254,440
lld-link.exe!lld::coff::Symbol[]        444,020         24,865,120
lld-link.exe!lld::coff::DefinedRegular  379,729         18,226,992
char[]  249     1,233,585

After:
heap usage: 167,335 KB
type                                   |count          |byte size
---------------------------------------|---------------|-------------
void                                   |251,990        |63,254,440
lld-link.exe!lld::coff::SectionChunk   |370,809        |62,295,912
lld-link.exe!lld::coff::Symbol[]       |444,020        |24,865,120
lld-link.exe!lld::coff::DefinedRegular |379,729        |18,226,992
char[]                                 |249            |1,233,585

5.22% heap usage reduction

[mstorsjo]

In D59797#1442365, @rnk wrote:

I used the VS memory profiling tool and used the type view to see the most commonly allocated types. "void" just means allocations whose type wasn't determined, and a lot of it comes from vectors, specifically the new RelocTargets vector @mstorsjo added.

Since that vector isn't needed at all for x86, I guess it should be possible to skip it altogether there. It'll complicate the code a little bit, and the conditional might cost a little bit of runtime, but that'd give you back a lot as well.

[riccibruno]

lld/COFF/Chunks.h

236

I think that llvm::SmallVector<Symbol *, 0> is one pointer smaller, with the drawback that it is limited to 2^32-1 elements.

[rnk]

• replace struct with current size

[rnk]

lld/COFF/Chunks.cpp

47

Fair enough. Honestly, writing down all the fields in one place helped me identify the profitable reorderings, but we don't need to commit it.

lld/COFF/Chunks.h

232

I'm not sure we need to store this, actually, it's pretty easy to recompute on demand. At the very least, we could shorten the size to 32-bits. I think ~4 billion is a reasonable implementation limit on relocations.

236

My plan is to see if I can eliminate it completely, but I wanted to treat it separately once I established that the size of this was important and put a cap on it.

259

This, for example, is typically 2-3 elements long: each comdat .text section will have a an assoc pdata and xdata. A singly linked list could suffice instead.

[pcc]

lld/COFF/Chunks.cpp

47

I found D59044 (and, to a lesser extent, D59269) by staring at the output of clang with -Xclang -fdump-record-layouts. Maybe it would be worth adding this trick to the documentation somewhere?

[smeenai]

lld/COFF/Chunks.cpp

47

The clang static analyzer has a padding checker (https://clang.llvm.org/docs/analyzer/checkers.html#optin-performance-padding), and clang-tools-extra has clang-reorder-fields to automatically reorder fields according to the padding checker's findings. I haven't used those myself, but a coworker had success with them in the past.

[rnk]

• Replace std::vector<> with singly linked list

[rnk]

I added one last size optimization, replacing a std::vector with a forward linked list and a custom iterator for it. PTAL

[rnk]

I think I've addressed all the comments, and I know that @ruiu is currently travelling or recovering from travel to Japan, so I'll go ahead and land this. Feel free to provide post-commit feedback.

[rnk]

• last update

[MaskRay]

this reduces the sum of heap allocations ... These numbers exclude memory mapped files

May I ask how you counted the memory usage minus memory mapped files?

[rnk]

In D59797#1452440, @MaskRay wrote:

this reduces the sum of heap allocations ... These numbers exclude memory mapped files

May I ask how you counted the memory usage minus memory mapped files?

I'm using the Visual Studio memory profiler tool, which I believe just tracks heap allocations. It doesn't look at virtual memory or file mappings at all, it just sums the total size of all active heap allocations. So, it's not a complete picture of memory usage, but it represents the memory that we have the most control over.

clang/include/clang/Basic/Attr.td

def MSNoVTable : InheritableAttr, TargetSpecificAttr<TargetMicrosoftCXXABI> {
   let Subjects = SubjectList<[CXXRecord]>;
   let Documentation = [MSNoVTableDocs];
 }
 
 def : IgnoredAttr {
   let Spellings = [Declspec<"property">];
 }
 
+def MSAllocator : InheritableAttr {
+  let Spellings = [Declspec<"allocator">];
+  let Subjects = SubjectList<[Function]>;
+  let Documentation = [MSAllocatorDocs];
+}
+
 def MSStruct : InheritableAttr {
   let Spellings = [GCC<"ms_struct">];
   let Subjects = SubjectList<[Record]>;
   let Documentation = [Undocumented];
 }
 
 def DLLExport : InheritableAttr, TargetSpecificAttr<TargetWindows> {
   let Spellings = [Declspec<"dllexport">, GCC<"dllexport">];

clang/include/clang/Basic/AttrDocs.td

 added to arbitrary functions that need to follow the same convention - for
 example, a user can add them to auxiliary functions called by the server routine
 that have their return value of type ``kern_return_t`` unconditionally returned
 from the routine. The attribute can be applied to C++ methods, and in this case
 it will be automatically applied to overrides if the method is virtual. The
 attribute can also be written using C++11 syntax: ``[[mig::server_routine]]``.
 }];
 }
+
+def MSAllocatorDocs : Documentation {
+  let Category = DocCatType;
+  let Content = [{
+The ``__declspec(allocator)`` attribute is applied to functions that allocate
+memory, such as operator new in C++. When CodeView debug information is emitted
+(enabled by ``clang -gcodeview`` or ``clang-cl /Z7``), Clang will attempt to
+record the code offset of heap allocation call sites in the debug info. It will
+also record the type being allocated using some local heuristics. The Visual
+Studio debugger uses this information to `profile memory usage`_.
+
+.. _profile memory usage: https://docs.microsoft.com/en-us/visualstudio/profiling/memory-usage
+
+This attribute does not affect optimizations in any way, unlike GCC's
+``__attribute__((malloc))``.
+}];
+}

clang/include/clang/Basic/DiagnosticSemaKinds.td

def warn_objc_precise_lifetime_meaningless : Error<
   "%select{__unsafe_unretained|__autoreleasing}0 objects">;
 def err_invalid_pcs : Error<"invalid PCS type">;
 def warn_attribute_not_on_decl : Warning<
   "%0 attribute ignored when parsing type">, InGroup<IgnoredAttributes>;
 def err_base_specifier_attribute : Error<
   "%0 attribute cannot be applied to a base specifier">;
 def err_invalid_attribute_on_virtual_function : Error<
   "%0 attribute cannot be applied to virtual functions">;
+def warn_declspec_allocator_nonpointer : Warning<
+  "ignoring __declspec(allocator) because the function return type %0 is not "
+  "a pointer or reference type">, InGroup<IgnoredAttributes>;
 
 def ext_cannot_use_trivial_abi : ExtWarn<
   "'trivial_abi' cannot be applied to %0">, InGroup<IgnoredAttributes>;
 
 // Availability attribute
 def warn_availability_unknown_platform : Warning<
   "unknown platform %0 in availability macro">, InGroup<Availability>;
 def warn_availability_version_ordering : Warning<

clang/lib/Sema/SemaDeclAttr.cpp

if (!IsKernReturnT || T.getCanonicalType() != S.getASTContext().IntTy) {
              diag::warn_mig_server_routine_does_not_return_kern_return_t);
       return;
     }
   }
 
   handleSimpleAttribute<MIGServerRoutineAttr>(S, D, AL);
 }
 
+static void handleMSAllocatorAttr(Sema &S, Decl *D, const ParsedAttr &AL) {
+  // Warn if the return type is not a pointer or reference type.
+  if (auto *FD = dyn_cast<FunctionDecl>(D)) {
+    QualType RetTy = FD->getReturnType();
+    if (!RetTy->isPointerType() && !RetTy->isReferenceType()) {
+      S.Diag(AL.getLoc(), diag::warn_declspec_allocator_nonpointer)
+          << AL.getRange() << RetTy;
+      return;
+    }
+  }
+
+  handleSimpleAttribute<MSAllocatorAttr>(S, D, AL);
+}
+
 //===----------------------------------------------------------------------===//
 // Top Level Sema Entry Points
 //===----------------------------------------------------------------------===//
 
 /// ProcessDeclAttribute - Apply the specific attribute to the specified decl if
 /// the attribute applies to decls.  If the attribute is a type attribute, just
 /// silently ignore it if a GNU attribute.
 static void ProcessDeclAttribute(Sema &S, Scope *scope, Decl *D,
static void ProcessDeclAttribute(Sema &S, Scope *scope, Decl *D,
 
   case ParsedAttr::AT_ObjCExternallyRetained:
     handleObjCExternallyRetainedAttr(S, D, AL);
     break;
 
   case ParsedAttr::AT_MIGServerRoutine:
     handleMIGServerRoutineAttr(S, D, AL);
     break;
+
+  case ParsedAttr::AT_MSAllocator:
+    handleMSAllocatorAttr(S, D, AL);
+    break;
   }
 }
 
 /// ProcessDeclAttributeList - Apply all the decl attributes in the specified
 /// attribute list to the specified decl, ignoring any type attributes.
 void Sema::ProcessDeclAttributeList(Scope *S, Decl *D,
                                     const ParsedAttributesView &AttrList,
                                     bool IncludeCXX11Attributes) {

clang/test/SemaCXX/declspec-allocator.cpp

+// RUN: %clang_cc1 -fms-compatibility -triple x86_64-windows-msvc -std=c++14 -fms-extensions -fms-compatibility-version=19.00 -verify %s
+
+__declspec(allocator) int err_on_data; // expected-warning {{'allocator' attribute only applies to functions}}
+__declspec(allocator) struct ErrOnStruct1; // expected-warning {{place it after "struct" to apply attribute}}
+struct __declspec(allocator) ErrOnStruct2 {}; // expected-warning {{'allocator' attribute only applies to functions}}
+__declspec(allocator) void err_on_ret_void(); // expected-warning {{not a pointer or reference type}}
+__declspec(allocator) int err_on_ret_int(); // expected-warning {{not a pointer or reference type}}
+__declspec(allocator) void *accept_on_ptr1();
+__declspec(allocator) void *accept_on_ptr2(size_t);
+void * __declspec(allocator) accept_on_ptr3(size_t); // expected-error {{expected unqualified-id}}
+
+struct Foo { int x; };
+__declspec(allocator) Foo *accept_nonvoid_ptr(size_t);

lld/COFF/Chunks.h

 const uint32_t TypeMask = 0x000000E0;
 
 // A Chunk represents a chunk of data that will occupy space in the
 // output (if the resolver chose that). It may or may not be backed by
 // a section of an input file. It could be linker-created data, or
 // doesn't even have actual data (if common or bss).
 class Chunk {
 public:
-  enum Kind { SectionKind, OtherKind };
+  enum Kind : uint8_t { SectionKind, OtherKind };
   Kind kind() const { return ChunkKind; }
   virtual ~Chunk() = default;
 
   // Returns the size of this chunk (even if this is a common or BSS.)
   virtual size_t getSize() const = 0;
 
   // Write this chunk to a mmap'ed file, assuming Buf is pointing to
   // beginning of the file. Because this function may use RVA values
public:
   uint32_t Alignment = 1;
 
   virtual bool isHotPatchable() const { return false; }
 
 protected:
   Chunk(Kind K = OtherKind) : ChunkKind(K) {}
   const Kind ChunkKind;
 
+public:
+  // Whether this section needs to be kept distinct from other sections during
+  // ICF. This is set by the driver using address-significance tables.
+  bool KeepUnique = false;
+
+protected:
   // The RVA of this chunk in the output. The writer sets a value.
   uint64_t RVA = 0;
 
   // The output section for this chunk.
   OutputSection *Out = nullptr;
 
 public:
   // The offset from beginning of the output section. The writer sets a value.
   uint64_t OutputSectionOff = 0;
-
-  // Whether this section needs to be kept distinct from other sections during
-  // ICF. This is set by the driver using address-significance tables.
-  bool KeepUnique = false;
 };
 
 // A chunk corresponding a section of an input file.
 class SectionChunk final : public Chunk {
   // Identical COMDAT Folding feature accesses section internal data.
   friend class ICF;
 
 public:
public:
   static ArrayRef<uint8_t> consumeDebugMagic(ArrayRef<uint8_t> Data,
                                              StringRef SectionName);
 
   static SectionChunk *findByName(ArrayRef<SectionChunk *> Sections,
                                   StringRef Name);
 
   bool isHotPatchable() const override { return File->HotPatchable; }
 
-  // A pointer pointing to a replacement for this chunk.
-  // Initially it points to "this" object. If this chunk is merged
-  // with other chunk by ICF, it points to another chunk,
-  // and this chunk is considered as dead.
-  SectionChunk *Repl;
-
-  // The CRC of the contents as described in the COFF spec 4.5.5.
-  // Auxiliary Format 5: Section Definitions. Used for ICF.
-  uint32_t Checksum = 0;
-
-  const coff_section *Header;
-
   // The file that this chunk was created from.
   ObjFile *File;
 
+  // Pointer to the COFF section header in the input file.
+  const coff_section *Header;
+
   // The COMDAT leader symbol if this is a COMDAT chunk.
   DefinedRegular *Sym = nullptr;
 
-  // The COMDAT selection if this is a COMDAT chunk.
-  llvm::COFF::COMDATType Selection = (llvm::COFF::COMDATType)0;
-
+  // Relocations for this section.
   ArrayRef<coff_relocation> Relocs;
 
-  // Used by the garbage collector.
-  bool Live;
-
   // When inserting a thunk, we need to adjust a relocation to point to
   // the thunk instead of the actual original target Symbol.
   std::vector<Symbol *> RelocTargets;
 
+  // The CRC of the contents as described in the COFF spec 4.5.5.
+  // Auxiliary Format 5: Section Definitions. Used for ICF.
+  uint32_t Checksum = 0;
+
+  // Indicates whether the section should be included in the output file.
+  // Sections may become dead if the garbage collector discards them, if ICF
+  // replaces them, or if they are associated with a non-prevailing comdat
+  // section.
+  bool Live;
+
+  // The COMDAT selection if this is a COMDAT chunk.
+  llvm::COFF::COMDATType Selection = (llvm::COFF::COMDATType)0;
+
+  // A pointer pointing to a replacement for this chunk.
+  // Initially it points to "this" object. If this chunk is merged
+  // with other chunk by ICF, it points to another chunk,
+  // and this chunk is considered as dead.
+  SectionChunk *Repl;
+
 private:
   StringRef SectionName;
   std::vector<SectionChunk *> AssocChildren;
 
   // Used for ICF (Identical COMDAT Folding)
   void replace(SectionChunk *Other);
   uint32_t Class[2] = {0, 0};
 };
 
 // This class is used to implement an lld-specific feature (not implemented in
 // MSVC) that minimizes the output size by finding string literals sharing tail

lld/COFF/Chunks.cpp

 using namespace llvm::support::endian;
 using namespace llvm::COFF;
 using llvm::support::ulittle32_t;
 
 namespace lld {
 namespace coff {
 
 SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
-    : Chunk(SectionKind), Repl(this), Header(H), File(F),
-      Relocs(File->getCOFFObj()->getRelocations(Header)) {
+    : Chunk(SectionKind), File(F), Header(H),
+      Relocs(File->getCOFFObj()->getRelocations(Header)), Repl(this) {
   // Initialize SectionName.
   File->getCOFFObj()->getSectionName(Header, SectionName);
 
   Alignment = Header->getAlignment();
 
   // If linker GC is disabled, every chunk starts out alive.  If linker GC is
   // enabled, treat non-comdat sections as roots. Generally optimized object
   // files will be built with -ffunction-sections or /Gy, so most things worth
   // stripping will be in a comdat.
   Live = !Config->DoGC || !isCOMDAT();
 }
 
+// SectionChunk is one of the most frequently allocated classes, so it is
+// important to keep it as compact as possible. 168 happens to be the size of
+// the class on x64 as of this writing.
+static_assert(sizeof(SectionChunk) <= 168, "SectionChunk grew unexpectedly");
+
 // Initialize the RelocTargets vector, to allow redirecting certain relocations
 // to a thunk instead of the actual symbol the relocation's symbol table index
 // indicates.
 void SectionChunk::readRelocTargets() {
   assert(RelocTargets.empty());
   RelocTargets.reserve(Relocs.size());
   for (const coff_relocation &Rel : Relocs)
     RelocTargets.push_back(File->getSymbol(Rel.SymbolTableIndex));

 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
 static void or32(uint8_t *P, uint32_t V) { write32le(P, read32le(P) | V); }
 
 // Verify that given sections are appropriate targets for SECREL
 // relocations. This check is relaxed because unfortunately debug
 // sections have section-relative relocations against absolute symbols.
 static bool checkSecRel(const SectionChunk *Sec, OutputSection *OS) {
   if (OS)
     return true;
   if (Sec->isCodeView())
     return false;
   error("SECREL relocation cannot be applied to absolute symbols");
   return false;
 }
 
 static void applySecRel(const SectionChunk *Sec, uint8_t *Off,
                         OutputSection *OS, uint64_t S) {

llvm/include/llvm/BinaryFormat/COFF.h

enum RelocationTypesARM64 : unsigned {
   IMAGE_REL_ARM64_TOKEN = 0x000C,
   IMAGE_REL_ARM64_SECTION = 0x000D,
   IMAGE_REL_ARM64_ADDR64 = 0x000E,
   IMAGE_REL_ARM64_BRANCH19 = 0x000F,
   IMAGE_REL_ARM64_BRANCH14 = 0x0010,
   IMAGE_REL_ARM64_REL32 = 0x0011,
 };
 
-enum COMDATType : unsigned {
+enum COMDATType : uint8_t {
   IMAGE_COMDAT_SELECT_NODUPLICATES = 1,
   IMAGE_COMDAT_SELECT_ANY,
   IMAGE_COMDAT_SELECT_SAME_SIZE,
   IMAGE_COMDAT_SELECT_EXACT_MATCH,
   IMAGE_COMDAT_SELECT_ASSOCIATIVE,
   IMAGE_COMDAT_SELECT_LARGEST,
   IMAGE_COMDAT_SELECT_NEWEST
 };