Garbage collect dllimported symbols.

[ruiu]

Summary

This is a different implementation than r303225 (which was reverted
in r303270, re-submitted in r303304 and then re-reverted in r303527).

In the previous patch, I tried to add Live bit to each dllimported
symbol. It turned out that it didn't work with "oldnames.lib" which
contains a lot of weak aliases to dllimported symbols.

The way we handle weak aliases is to check if undefined symbols
can be resolved using weak aliases, and if so, memcpy the Defined
symbols to weak Undefined symbols, so that any references to weak
aliases automatically see defined symbols instead of undefined ones.

This memcpy happens before MarkLive kicks in.

That means we may have multiple copies of dllimported symbols. So
turning on one instance's Live bit is not enough.

This patch moves the Live bit to dllimport file. Since multiple
copies of dllsymbols still point to the same file, we can use it as the
central repository to keep track of liveness.

[pcc]

Can you construct a test case that shows that we handle weak externals correctly?

lld/COFF/Writer.cpp

454

I guess this means that we are not gc'ing unused thunks any more. But I guess this isn't a regression, so it seems fine to me.

[ruiu]

• Added a test

[ruiu]

lld/COFF/Writer.cpp

454

Yes, that is correct. But in practice we are interested only in eliminating dependencies to DLL files and not to each symbol in a DLL, so it should be fine.

[pcc]

LGTM

lld/test/COFF/dllimport-gc.test

27

I think you can remove this line.

37

Can this just be NumberOfRelocations: 0?

lld/COFF/InputFiles.h

 //===- InputFiles.h ---------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_COFF_INPUT_FILES_H
 #define LLD_COFF_INPUT_FILES_H
 
+#include "Config.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/LTO/LTO.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Support/StringSaver.h"
 #include <memory>
private:
   std::vector<SymbolBody *> SparseSymbolBodies;
 };
 
 // This type represents import library members that contain DLL names
 // and symbols exported from the DLLs. See Microsoft PE/COFF spec. 7
 // for details about the format.
 class ImportFile : public InputFile {
 public:
-  explicit ImportFile(MemoryBufferRef M) : InputFile(ImportKind, M) {}
+  explicit ImportFile(MemoryBufferRef M)
+      : InputFile(ImportKind, M), Live(!Config->DoGC) {}
+
   static bool classof(const InputFile *F) { return F->kind() == ImportKind; }
 
   DefinedImportData *ImpSym = nullptr;
   DefinedImportData *ConstSym = nullptr;
   DefinedImportThunk *ThunkSym = nullptr;
   std::string DLLName;
 
 private:
   void parse() override;
 
 public:
   StringRef ExternalName;
   const coff_import_header *Hdr;
   Chunk *Location = nullptr;
+
+  // We want to eliminate dllimported symbols if no one actually refers them.
+  // This "Live" bit is used to keep track of which import library members
+  // are actually in use.
+  //
+  // If the Live bit is turned off by MarkLive, Writer will ignore dllimported
+  // symbols provided by this import library member.
+  bool Live;
 };
 
 // Used for LTO.
 class BitcodeFile : public InputFile {
 public:
   explicit BitcodeFile(MemoryBufferRef M) : InputFile(BitcodeKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == BitcodeKind; }
   std::vector<SymbolBody *> &getSymbols() { return SymbolBodies; }

lld/COFF/MarkLive.cpp

void markLive(const std::vector<Chunk *> &Chunks) {
 
   auto Enqueue = [&](SectionChunk *C) {
     if (C->isLive())
       return;
     C->markLive();
     Worklist.push_back(C);
   };
 
+  auto AddSym = [&](SymbolBody *B) {
+    if (auto *Sym = dyn_cast<DefinedRegular>(B))
+      Enqueue(Sym->getChunk());
+    else if (auto *Sym = dyn_cast<DefinedImportData>(B))
+      Sym->File->Live = true;
+    else if (auto *Sym = dyn_cast<DefinedImportThunk>(B))
+      Sym->WrappedSym->File->Live = true;
+  };
+
   // Add GC root chunks.
   for (SymbolBody *B : Config->GCRoot)
-    if (auto *D = dyn_cast<DefinedRegular>(B))
-      Enqueue(D->getChunk());
+    AddSym(B);
 
   while (!Worklist.empty()) {
     SectionChunk *SC = Worklist.pop_back_val();
     assert(SC->isLive() && "We mark as live when pushing onto the worklist!");
 
     // Mark all symbols listed in the relocation table for this section.
-    for (SymbolBody *S : SC->symbols())
-      if (auto *D = dyn_cast<DefinedRegular>(S))
-        Enqueue(D->getChunk());
+    for (SymbolBody *B : SC->symbols())
+      AddSym(B);
 
     // Mark associative sections if any.
     for (SectionChunk *C : SC->children())
       Enqueue(C);
   }
 }
 
 }
 }

lld/COFF/Symbols.h

public:
   }
 
   uint64_t getRVA() { return File->Location->getRVA(); }
   StringRef getDLLName() { return File->DLLName; }
   StringRef getExternalName() { return File->ExternalName; }
   void setLocation(Chunk *AddressTable) { File->Location = AddressTable; }
   uint16_t getOrdinal() { return File->Hdr->OrdinalHint; }
 
-private:
   ImportFile *File;
 };
 
 // This class represents a symbol for a jump table entry which jumps
 // to a function in a DLL. Linker are supposed to create such symbols
 // without "__imp_" prefix for all function symbols exported from
 // DLLs, so that you can call DLL functions as regular functions with
 // a regular name. A function pointer is given as a DefinedImportData.
 class DefinedImportThunk : public Defined {
 public:
   DefinedImportThunk(StringRef Name, DefinedImportData *S, uint16_t Machine);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedImportThunkKind;
   }
 
   uint64_t getRVA() { return Data->getRVA(); }
   Chunk *getChunk() { return Data; }
 
+  DefinedImportData *WrappedSym;
+
 private:
   Chunk *Data;
 };
 
 // If you have a symbol "__imp_foo" in your object file, a symbol name
 // "foo" becomes automatically available as a pointer to "__imp_foo".
 // This class is for such automatically-created symbols.
 // Yes, this is an odd feature. We didn't intend to implement that.

lld/COFF/Symbols.cpp

static Chunk *makeImportThunk(DefinedImportData *S, uint16_t Machine) {
   if (Machine == I386)
     return make<ImportThunkChunkX86>(S);
   assert(Machine == ARMNT);
   return make<ImportThunkChunkARM>(S);
 }
 
 DefinedImportThunk::DefinedImportThunk(StringRef Name, DefinedImportData *S,
                                        uint16_t Machine)
-    : Defined(DefinedImportThunkKind, Name),
+    : Defined(DefinedImportThunkKind, Name), WrappedSym(S),
       Data(makeImportThunk(S, Machine)) {}
 
 Defined *Undefined::getWeakAlias() {
   // A weak alias may be a weak alias to another symbol, so check recursively.
   for (SymbolBody *A = WeakAlias; A; A = cast<Undefined>(A)->WeakAlias)
     if (auto *D = dyn_cast<Defined>(A))
       return D;
   return nullptr;
 }
 } // namespace coff
 } // namespace lld

lld/COFF/Writer.cpp

 void Writer::createImportTables() {
   if (Symtab->ImportFiles.empty())
     return;
 
   // Initialize DLLOrder so that import entries are ordered in
   // the same order as in the command line. (That affects DLL
   // initialization order, and this ordering is MSVC-compatible.)
   for (ImportFile *File : Symtab->ImportFiles) {
+    if (!File->Live)
+      continue;
+
     std::string DLL = StringRef(File->DLLName).lower();
     if (Config->DLLOrder.count(DLL) == 0)
       Config->DLLOrder[DLL] = Config->DLLOrder.size();
   }
 
   OutputSection *Text = createSection(".text");
   for (ImportFile *File : Symtab->ImportFiles) {
+    if (!File->Live)
+      continue;
+
     if (DefinedImportThunk *Thunk = File->ThunkSym)
       Text->addChunk(Thunk->getChunk());
+
     if (Config->DelayLoads.count(StringRef(File->DLLName).lower())) {
       DelayIdata.add(File->ImpSym);
     } else {
       Idata.add(File->ImpSym);
     }
   }
+
   if (!Idata.empty()) {
     OutputSection *Sec = createSection(".idata");
     for (Chunk *C : Idata.getChunks())
       Sec->addChunk(C);
   }
+
   if (!DelayIdata.empty()) {
     Defined *Helper = cast<Defined>(Config->DelayLoadHelper);
     DelayIdata.create(Helper);
     OutputSection *Sec = createSection(".didat");
     for (Chunk *C : DelayIdata.getChunks())
       Sec->addChunk(C);
     Sec = createSection(".data");
     for (Chunk *C : DelayIdata.getDataChunks())
Optional<coff_symbol16> Writer::createSymbol(Defined *Def) {
   // Relative symbols are unrepresentable in a COFF symbol table.
   if (isa<DefinedRelative>(Def))
     return None;
 
   if (auto *D = dyn_cast<DefinedRegular>(Def))
     if (!D->getChunk()->isLive())
       return None;
 
+  if (auto *Sym = dyn_cast<DefinedImportData>(Def))
+    if (!Sym->File->Live)
+      return None;
+
+  if (auto *Sym = dyn_cast<DefinedImportThunk>(Def))
+    if (!Sym->WrappedSym->File->Live)
+      return None;
+
   coff_symbol16 Sym;
   StringRef Name = Def->getName();
   if (Name.size() > COFF::NameSize) {
     Sym.Name.Offset.Zeroes = 0;
     Sym.Name.Offset.Offset = addEntryToStringTable(Name);
   } else {
     memset(Sym.Name.ShortName, 0, COFF::NameSize);
     memcpy(Sym.Name.ShortName, Name.data(), Name.size());

lld/test/COFF/Inputs/import.yaml

 --- !COFF
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: []
 sections:
   - Name:            .text
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
     Alignment:       4
     SectionData:     0000000000000000
+    Relocations:
+      - VirtualAddress:  0
+        SymbolName:      exportfn1
+        Type:            IMAGE_REL_AMD64_ADDR32NB
+      - VirtualAddress:  4
+        SymbolName:      exportfn2
+        Type:            IMAGE_REL_AMD64_ADDR32NB
 symbols:
   - Name:            .text
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_STATIC
     SectionDefinition:
       Length:          8
-      NumberOfRelocations: 0
+      NumberOfRelocations: 2
       NumberOfLinenumbers: 0
       CheckSum:        0
       Number:          0
   - Name:            main
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_FUNCTION

lld/test/COFF/Inputs/oldname.yaml

+--- !COFF
+header:
+  Machine:         IMAGE_FILE_MACHINE_UNKNOWN
+  Characteristics: [  ]
+sections:
+  - Name:            .drectve
+    Characteristics: [ IMAGE_SCN_LNK_INFO, IMAGE_SCN_LNK_REMOVE ]
+    Alignment:       1
+    SectionData:     ''
+symbols:
+  - Name:            exportfn1
+    Value:           0
+    SectionNumber:   0
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+  - Name:            exportfn1_alias
+    Value:           0
+    SectionNumber:   0
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_WEAK_EXTERNAL
+    WeakExternal:
+      TagIndex:        0
+      Characteristics: IMAGE_WEAK_EXTERN_SEARCH_ALIAS
+...

lld/test/COFF/dllimport-gc.test

+# REQUIRES: winres
+
+# RUN: yaml2obj < %p/Inputs/export.yaml > %t-lib.obj
+# RUN: lld-link /out:%t.dll /dll %t-lib.obj /implib:%t.lib /export:exportfn1
+
+# RUN: yaml2obj < %p/Inputs/oldname.yaml > %t-oldname.obj
+
+# RUN: yaml2obj < %s > %t.obj
+
+# RUN: lld-link /out:%t1.exe /entry:main %t.obj %t-oldname.obj %t.lib
+# RUN: llvm-readobj -coff-imports %t1.exe | FileCheck -check-prefix=REF %s
+# REF-NOT: Symbol: exportfn1
+
+# RUN: lld-link /out:%t2.exe /entry:main %t.obj %t-oldname.obj %t.lib /opt:noref
+# RUN: llvm-readobj -coff-imports %t2.exe | FileCheck -check-prefix=NOREF %s
+# NOREF: Symbol: exportfn1
+
 --- !COFF
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: []
 sections:
   - Name:            .text
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
     Alignment:       4
     SectionData:     0000000000000000
+    Relocations:
 symbols:
   - Name:            .text
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_STATIC
     SectionDefinition:
       Length:          8
-      NumberOfRelocations: 0
+      NumberOfRelocations: 2
       NumberOfLinenumbers: 0
       CheckSum:        0
       Number:          0
   - Name:            main
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
     StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
   - Name:            exportfn1
     Value:           0
     SectionNumber:   0
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
-  - Name:            exportfn2
+  - Name:            exportfn1_alias
     Value:           0
     SectionNumber:   0
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
 ...