[COFF] Replace OutputSection* with uint16_t index in Chunk

[rnk]

Summary

Shaves another 8 bytes off of SectionChunk, the most commonly allocated
type in LLD.

These indices are only valid after we've assigned chunks to output
sections and removed empty sections, so do that in a new pass.

[ruiu]

LGTM

[aganea]

Great stuff, thanks for doing this Reid! :) Inherently, this should make things a bit faster, it will also reduce cache misses.
We use a neat tool called Crunchersharp to have a broader overview:

[aganea]

lld/test/COFF/strtab-size.s

16 ↗

(On Diff #201098)

Could you please explain why this changed? Just curious.

[rnk]

In D62356#1516109, @aganea wrote:

Great stuff, thanks for doing this Reid! :) Inherently, this should make things a bit faster, it will also reduce cache misses.

Yep, that's the hope. :) I really should go back to PDB memory usage optimization, though, it is the 80% of the 80/20 portion.

We use a neat tool called Crunchersharp to have a broader overview:

Thanks, I built it, but when I try to use it to load lld.pdb, it raises a "class not registered" exception, despite the fact that I followed the README.md instructions and registered msdia120.dll. DIA registration seems to be a continuing pain point in the Windows development world. :( I'll mess around with it.

lld/test/COFF/strtab-size.s

16 ↗

(On Diff #201098)

When I dumped the symbols, .data and .bss no longer showed up. Now that we assign output sections to chunks after removing zero-size output sections, these symbols from the input objects no longer show up in the symbol table. llvm-mc always creates zero-size .data and .bss, although perhaps it shouldn't.

[aganea]

Thanks, I built it, but when I try to use it to load lld.pdb, it raises a "class not registered" exception, despite the fact that I followed the README.md instructions and registered msdia120.dll. DIA registration seems to be a continuing pain point in the Windows development world. :( I'll mess around with it.

I do this:

@echo off

@REM AUTO-ELEVATE the batch file to admin if needed!
net file 1>nul 2>nul && goto :run || powershell -ex unrestricted -Command "Start-Process -Wait -Verb RunAs -FilePath '%comspec%' -ArgumentList '/c \"%~fnx0\" %*'"
goto :eof
:run

regsvr32.exe "C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\DIA SDK\bin\msdia140.dll"
regsvr32.exe "C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\DIA SDK\bin\amd64\msdia140.dll"

[rnk]

In D62356#1516490, @aganea wrote:

regsvr32.exe "C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\DIA SDK\bin\msdia140.dll"
regsvr32.exe "C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\DIA SDK\bin\amd64\msdia140.dll"

I ran an elevated cmd prompt, and ran both the above regsvr32 commands, but I still get:

System.Runtime.InteropServices.COMException (0x80040154): Retrieving the COM class factory for component with CLSID {3BFCEA48-620F-4B6B-81F7-B9AF75454C7D} failed due to the following error: 80040154 Class not registered (Exception from HRESULT: 0x80040154 (REGDB_E_CLASSNOTREG)).

[aganea]

The Interop.Dia2Lib.dll and the msdiaXXX.dll have to match. Try regsvr32.exe "C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\Packages\Debugger\msdia120.dll" (or look for msdia120.dll on your PC).

COFF/Chunks.h

public:
   // Returns the section name if this is a section chunk.
   // It is illegal to call this function on non-section chunks.
   virtual StringRef getSectionName() const {
     llvm_unreachable("unimplemented getSectionName");
   }
 
   // An output section has pointers to chunks in the section, and each
   // chunk has a back pointer to an output section.
-  void setOutputSection(OutputSection *O) { Out = O; }
-  OutputSection *getOutputSection() const { return Out; }
+  void setOutputSectionIdx(uint16_t O) { OSIdx = O; }
+  uint16_t getOutputSectionIdx() const { return OSIdx; }
+  OutputSection *getOutputSection() const;
 
   // Windows-specific.
   // Collect all locations that contain absolute addresses for base relocations.
   virtual void getBaserels(std::vector<Baserel> *Res) {}
 
   // Returns a human-readable name of this chunk. Chunks are unnamed chunks of
   // bytes, so this is used only for logging or debugging.
   virtual StringRef getDebugName() { return ""; }
 
   virtual bool isHotPatchable() const { return false; }
 
 protected:
   Chunk(Kind K = OtherKind) : ChunkKind(K) {}
 
   const Kind ChunkKind;
 
   // The alignment of this chunk, stored in log2 form. The writer uses the
   // value.
   uint8_t P2Align = 0;
 
+  // The output section index for this chunk. The first valid section number is
+  // one.
+  uint16_t OSIdx = 0;
+
   // The RVA of this chunk in the output. The writer sets a value.
   uint32_t RVA = 0;
-
-  // The output section for this chunk.
-  OutputSection *Out = nullptr;
 };
 
 // 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:

COFF/Chunks.cpp

SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
   // 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. As of this writing, the number
 // below is the size of this class on x64 platforms.
-static_assert(sizeof(SectionChunk) <= 104, "SectionChunk grew unexpectedly");
+static_assert(sizeof(SectionChunk) <= 96, "SectionChunk grew unexpectedly");
 
 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
 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
uint8_t Baserel::getDefaultType() {
   default:
     llvm_unreachable("unknown machine type");
   }
 }
 
 MergeChunk *MergeChunk::Instances[Log2MaxSectionAlignment + 1] = {};
 
 MergeChunk::MergeChunk(uint32_t Alignment)
-    : Builder(StringTableBuilder::RAW, Alignment) {
+    : Chunk(OtherKind), Builder(StringTableBuilder::RAW, Alignment) {
   setAlignment(Alignment);
 }
 
 void MergeChunk::addSection(SectionChunk *C) {
   assert(isPowerOf2_32(C->getAlignment()));
   uint8_t P2Align = llvm::Log2_32(C->getAlignment());
   assert(P2Align >= 0 && P2Align < array_lengthof(Instances));
   auto *&MC = Instances[P2Align];
void MergeChunk::finalizeContents() {
   Finalized = true;
 }
 
 void MergeChunk::assignSubsectionRVAs() {
   for (SectionChunk *C : Sections) {
     if (!C->Live)
       continue;
     size_t Off = Builder.getOffset(toStringRef(C->getContents()));
-    C->setOutputSection(Out);
     C->setRVA(RVA + Off);
   }
 }
 
 uint32_t MergeChunk::getOutputCharacteristics() const {
   return IMAGE_SCN_MEM_READ | IMAGE_SCN_CNT_INITIALIZED_DATA;
 }
 

COFF/PDB.cpp

void PDBLinker::mergeSymbolRecords(ObjFile *File, const CVIndexMap &IndexMap,
   // Add any remaining symbols we've accumulated.
   File->ModuleDBI->addSymbolsInBulk(BulkSymbols);
 }
 
 // Allocate memory for a .debug$S / .debug$F section and relocate it.
 static ArrayRef<uint8_t> relocateDebugChunk(BumpPtrAllocator &Alloc,
                                             SectionChunk &DebugChunk) {
   uint8_t *Buffer = Alloc.Allocate<uint8_t>(DebugChunk.getSize());
-  assert(DebugChunk.getOutputSection() == nullptr &&
+  assert(DebugChunk.getOutputSectionIdx() == 0 &&
          "debug sections should not be in output sections");
   DebugChunk.writeTo(Buffer);
   return makeArrayRef(Buffer, DebugChunk.getSize());
 }
 
 static pdb::SectionContrib createSectionContrib(const Chunk *C, uint32_t Modi) {
   OutputSection *OS = C ? C->getOutputSection() : nullptr;
   pdb::SectionContrib SC;

COFF/Writer.cpp

 static_assert(sizeof(DOSProgram) % 8 == 0,
               "DOSProgram size must be multiple of 8");
 
 static const int DOSStubSize = sizeof(dos_header) + sizeof(DOSProgram);
 static_assert(DOSStubSize % 8 == 0, "DOSStub size must be multiple of 8");
 
 static const int NumberOfDataDirectory = 16;
 
+// Global vector of all output sections. After output sections are finalized,
+// this can be indexed by Chunk::getOutputSection.
+static std::vector<OutputSection *> OutputSections;
+
+OutputSection *Chunk::getOutputSection() const {
+  return OSIdx == 0 ? nullptr : OutputSections[OSIdx - 1];
+}
+
 namespace {
 
 class DebugDirectoryChunk : public Chunk {
 public:
   DebugDirectoryChunk(const std::vector<Chunk *> &R, bool WriteRepro)
       : Records(R), WriteRepro(WriteRepro) {}
 
   size_t getSize() const override {
private:
   void appendImportThunks();
   void locateImportTables();
   void createExportTable();
   void mergeSections();
   void removeUnusedSections();
   void assignAddresses();
   void finalizeAddresses();
   void removeEmptySections();
+  void assignOutputSectionIndices();
   void createSymbolAndStringTable();
   void openFile(StringRef OutputPath);
   template <typename PEHeaderTy> void writeHeader();
   void createSEHTable();
   void createRuntimePseudoRelocs();
   void insertCtorDtorSymbols();
   void createGuardCFTables();
   void markSymbolsForRVATable(ObjFile *File,
private:
   OutputSection *findSection(StringRef Name);
   void addBaserels();
   void addBaserelBlocks(std::vector<Baserel> &V);
 
   uint32_t getSizeOfInitializedData();
 
   std::unique_ptr<FileOutputBuffer> &Buffer;
   std::map<PartialSectionKey, PartialSection *> PartialSections;
-  std::vector<OutputSection *> OutputSections;
   std::vector<char> Strtab;
   std::vector<llvm::object::coff_symbol16> OutputSymtab;
   IdataContents Idata;
   Chunk *ImportTableStart = nullptr;
   uint64_t ImportTableSize = 0;
   Chunk *IATStart = nullptr;
   uint64_t IATSize = 0;
   DelayLoadContents DelayIdata;

 
 static Timer CodeLayoutTimer("Code Layout", Timer::root());
 static Timer DiskCommitTimer("Commit Output File", Timer::root());
 
 void writeResult() { Writer().run(); }
 
 void OutputSection::addChunk(Chunk *C) {
   Chunks.push_back(C);
-  C->setOutputSection(this);
 }
 
 void OutputSection::insertChunkAtStart(Chunk *C) {
   Chunks.insert(Chunks.begin(), C);
-  C->setOutputSection(this);
 }
 
 void OutputSection::setPermissions(uint32_t C) {
   Header.Characteristics &= ~PermMask;
   Header.Characteristics |= C;
 }
 
 void OutputSection::merge(OutputSection *Other) {
-  for (Chunk *C : Other->Chunks)
-    C->setOutputSection(this);
   Chunks.insert(Chunks.end(), Other->Chunks.begin(), Other->Chunks.end());
   Other->Chunks.clear();
   ContribSections.insert(ContribSections.end(), Other->ContribSections.begin(),
                          Other->ContribSections.end());
   Other->ContribSections.clear();
 }
 
 // Write the section header to a given buffer.
for (size_t J = 0, E = OriginalRelocs.size(); J < E; ++J) {
       // thunk.
       Defined *Thunk;
       bool WasNew;
       std::tie(Thunk, WasNew) = getThunk(LastThunks, Sym, P, Rel.Type, Margin);
       if (WasNew) {
         Chunk *ThunkChunk = Thunk->getChunk();
         ThunkChunk->setRVA(
             ThunkInsertionRVA); // Estimate of where it will be located.
-        ThunkChunk->setOutputSection(OS);
         OS->Chunks.insert(OS->Chunks.begin() + ThunkInsertionSpot, ThunkChunk);
         ThunkInsertionSpot++;
         ThunksSize += ThunkChunk->getSize();
         ThunkInsertionRVA += ThunkChunk->getSize();
         AddressesChanged = true;
       }
 
       // To redirect the relocation, add a symbol to the parent object file's
void Writer::run() {
   createSections();
   createMiscChunks();
   appendImportThunks();
   createExportTable();
   mergeSections();
   removeUnusedSections();
   finalizeAddresses();
   removeEmptySections();
+  assignOutputSectionIndices();
   setSectionPermissions();
   createSymbolAndStringTable();
 
   if (FileSize > UINT32_MAX)
     fatal("image size (" + Twine(FileSize) + ") " +
         "exceeds maximum allowable size (" + Twine(UINT32_MAX) + ")");
 
   openFile(Config->OutputFile);

 
 // The Windows loader doesn't seem to like empty sections,
 // so we remove them if any.
 void Writer::removeEmptySections() {
   auto IsEmpty = [](OutputSection *S) { return S->getVirtualSize() == 0; };
   OutputSections.erase(
       std::remove_if(OutputSections.begin(), OutputSections.end(), IsEmpty),
       OutputSections.end());
+}
+
+void Writer::assignOutputSectionIndices() {
+  // Assign final output section indices, and assign each chunk to its output
+  // section.
   uint32_t Idx = 1;
-  for (OutputSection *Sec : OutputSections)
-    Sec->SectionIndex = Idx++;
+  for (OutputSection *OS : OutputSections) {
+    OS->SectionIndex = Idx;
+    for (Chunk *C : OS->Chunks)
+      C->setOutputSectionIdx(Idx);
+    ++Idx;
+  }
+
+  // Merge chunks are containers of chunks, so assign those an output section
+  // too.
+  for (MergeChunk *MC : MergeChunk::Instances)
+    if (MC)
+      for (SectionChunk *SC : MC->Sections)
+        if (SC && SC->Live)
+          SC->setOutputSectionIdx(MC->getOutputSectionIdx());
 }
 
 size_t Writer::addEntryToStringTable(StringRef Str) {
   assert(Str.size() > COFF::NameSize);
   size_t OffsetOfEntry = Strtab.size() + 4; // +4 for the size field
   Strtab.insert(Strtab.end(), Str.begin(), Str.end());
   Strtab.push_back('\0');
   return OffsetOfEntry;
case Symbol::DefinedImportThunkKind:
     break;
 
   case Symbol::DefinedRegularKind: {
     // This is a regular, defined, symbol from a COFF file. Mark the symbol as
     // address taken if the symbol type is function and it's in an executable
     // section.
     auto *D = cast<DefinedRegular>(S);
     if (D->getCOFFSymbol().getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION) {
-      Chunk *RefChunk = D->getChunk();
-      OutputSection *OS = RefChunk ? RefChunk->getOutputSection() : nullptr;
-      if (OS && OS->Header.Characteristics & IMAGE_SCN_MEM_EXECUTE)
+      SectionChunk *SC = dyn_cast<SectionChunk>(D->getChunk());
+      if (SC && SC->Live &&
+          SC->getOutputCharacteristics() & IMAGE_SCN_MEM_EXECUTE)
         addSymbolToRVASet(AddressTakenSyms, D);
     }
     break;
   }
   }
 }
 
 // Visit all relocations from all section contributions of this object file and

 }
 
 // Sort .pdata section contents according to PE/COFF spec 5.5.
 void Writer::sortExceptionTable() {
   if (!FirstPdata)
     return;
   // We assume .pdata contains function table entries only.
   auto BufAddr = [&](Chunk *C) {
-    return Buffer->getBufferStart() + C->getOutputSection()->getFileOff() +
-           C->getRVA() - C->getOutputSection()->getRVA();
+    OutputSection *OS = C->getOutputSection();
+    return Buffer->getBufferStart() + OS->getFileOff() + C->getRVA() -
+           OS->getRVA();
   };
   uint8_t *Begin = BufAddr(FirstPdata);
   uint8_t *End = BufAddr(LastPdata) + LastPdata->getSize();
   if (Config->Machine == AMD64) {
     struct Entry { ulittle32_t Begin, End, Unwind; };
     parallelSort(
         MutableArrayRef<Entry>((Entry *)Begin, (Entry *)End),
         [](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });

test/COFF/strtab-size.s

 # REQUIRES: x86
 
 # Test that the strtab size is included in the allocation even if the
 # strtab itself is empty. To achieve this, we need a number of symbols N
 # where alignTo(N*18, 512) < alignTo(N*18 + 4, 512), where the first
 # positive N fulfilling that is 199.
 
 # RUN: llvm-mc -triple=x86_64-windows-msvc %s -filetype=obj -o %t.obj
 # RUN: lld-link -out:%t.exe -entry:main %t.obj -debug:dwarf
 
 # If the size of the strtab isn't allocated for, llvm-readobj would
 # output SymbolCount: 0 (and dumpbin.exe would error out with "invalid file
 # or disk full, cannot seek to 0x1602").
 
 # RUN: llvm-readobj --file-headers %t.exe | FileCheck %s
-# CHECK: SymbolCount: 199
+# CHECK: SymbolCount: 197
 
 .global main
 .text
 main:
 sym0:
 sym1:
 sym2:
 sym3: