[WebAssembly] LLD: Don't write out discarded function symbols

[ncw]

Summary

This is small change, on the principle, "let's keep the commits small and take little baby steps in each commit".

APPLIES AFTER:

• D40845 (LLD Comdat support)

This beefs up Sam's change with a few lines of code taken from ELF-LLD, which has the notion of "discarded" input sections. We now have "discarded" InputSegments/InputFunctions.

As proof of concept, I've implemented discarding duplicate weak symbols. If two files both define the same function weakly, then the second copy shouldn't be written out, since all calls to it will go via relocations, and no relocations can touch the function if it's not reachable via any Symbols. Hence if every translation unit provides a function like "std::string::whatever" it will only be written out once.

The behaviour is covered by existing tests, which exercise the weak symbols code, and assert on the output.

[ncw]

Updated to make the diff a bit shorter/tidier.

(I've rolled in a few "cosmetic" changes like removing an unused variable SymbolTable::SyntheticSymbols - I hope that's OK, it didn't seem worth a review on its own.)

[sbc100]

Cool. Didn't expect that to be so simple :)

I'll submit the cosmetic changes separately.

wasm/InputFiles.cpp

214

How about just:

if (S->getFile() != this)  {
    // This symbol was already defined in another file.
    Functions[WasmSym.ElementIndex - NumFunctionImports] = &InputFunction::Discarded;
}

And can we do the same for globals?

wasm/InputFunction.cpp

18 ↗

(On Diff #127539)

Seems a shame to add a new source file just for this.

I've not looked at how the other linker do this, but could we not just have a "Discarded" flag on these objects instead of the these magic statics?

[ncw]

wasm/InputFiles.cpp

214

Sadly that won't work, the extra layer of redirection with ReachedFunctions is definitely necessary. The way you wrote it was my first attempt!

Here's the problematic C code:

void defaultImpl(void) { ... }
void aliasedCall(void) __attribute__((weak,alias("defaultImpl")));

static void consumingFunction() {
  aliasedCall();
  defaultImpl();
}

Here, you can see the symbol "aliasedCall" is a function export - so the function body for "defaultImpl" is exported with two different names in the exports section, "defaultImpl" and "aliasedCall".

Now imagine that another translation unit defines the symbol "aliasedCall" (either strongly or just gets in first). In this case, we'll get S->getFile() != this for the Function when we process the "aliasedCall" export. Yet, the Function is reachable through two different Symbols, and "defaultCall()" should still reach the function in this translation unit.

Short answer: if one Symbol points to another file, that's not enough reason to prune that Symbol's InputFunction. We need every Symbol that points to the Function to be redirected in order to safely prune it.

Luckily we have a test for it already. One of the aliased symbol tests caught this bug.

---

Secondly, globals. Hmm, it's trickier. In general, no, since an InputSegment can contain multiple globals? We could put in some code to count how many globals refer to each InputSegment, and if it's a segment with a solitary global we could prune it... Would be interesting to see how much the filesize goes down.

My expectation is that almost all the "weak" symbols that are used in the wild are C++ inlines. Even low-level systems code typically only uses weak symbols in a small number of files.

Thus, optimising the case of weak symbols is not a priority. Comdat handling will prune the duplicate InputSegments that actually occur in the wild, and we don't really need to handle the non-Comdat case.

wasm/InputFunction.cpp

18 ↗

(On Diff #127539)

The file is doing no harm. We might need the file anyway eventually. Let's not let the length of the file affect any other decisions.

Good question about Discarded, I was initially surprised too.

The "Discarded" implementation I'm using comes directly from the ELF linker, to keep Rui happy. It's actually quite sensible: if you have a flag, there are two problems. a) you have to check the flag everywhere, and b) you have to keep on checking it forever whenever someone adds new code, ie it's a pain for ever.

Redirecting to a dummy Function like "Discarded" is much safer. Since all the fields in Discarded are null, there's no chance at all that you'll use it by mistake. You only need to check against Discarded in a couple of places, everywhere else can reference the InputFuction/InputSegment without worrying - you'll pass on its nullness if you reference the members.

Keeping it similar to ELF-LLD is probably a good enough reason to use the idiom for now, in any case.

[sbc100]

Cool. Didn't expect that to be so simple :)

I'll submit the cosmetic changes separately.

wasm/InputFunction.cpp

18 ↗

(On Diff #127539)

I don't think we should aim for complete parity with ELF. For example there is no ::Discarded thing in the COFF version. Not to say that we shouldn't go this route but I think we need more of a reason.

ELF seems to use both Discarded.. the the Live flag. I don't see why we could just mark this section as Live = false, it would need to be checked in exactly the same number of places. I also think Sec->isLive() is much more readable than Sec != &InputSection::Discarded). But obviously ELF chose to have both these method so maybe we will run into the same reason they did.

wasm/InputSegment.h

66 ↗

(On Diff #127539)

We don't need this if we are not going to do the same for globals, right?

[ncw]

Sorry also for the lengthy responses!

It would be nice to merge as much as possible before the holidays, or there'll be lots of rebasing pain when we come back from holidays and find patches that are weeks out of date.

Having said it's not important, I might have time today to add some detection for discarding the segment containing a weak global.

wasm/InputFunction.cpp

18 ↗

(On Diff #127539)

I think COFF and ELF use isLive for GC - so we shouldn't use that here for something else. In LLD I think "discarded" means "we've thrown it away, we'll never use it", and sections are initially not discarded, but can be discarded, and that's a definitive decision for the section. "Live" means the section is reachable, and it's initially false and set to true as reachability is calculated during the GC phase.

I could change it to setDiscarded/isDiscarded, if you'd prefer that, I don't particularly mind. Rui did request we keep variable naming and idioms consistent between the different backends.

wasm/InputSegment.h

66 ↗

(On Diff #127539)

We will be doing the same for globals in the Comdat review D40845 (which stacks on top of this one). I haven't implemented segment discarding based on weak globals (as I have for functions), but I have implemented segment discarding based on Comdats.

This will be used in future.

[ncw]

Updated:

• Rebased to be on top of Sam's D41419
• Added handling of global symbols, allowing InputSegments to be discarded as well if the InputSegment contains nothing else apart from the discarded Global

All these refactoring patches are going to be a big pain if they can't be merged quickly...

[ncw]

Rebased as requested. Tests pass.

[sbc100]

wasm/InputChunks.cpp

26

This size of a global symbol isn't represented this way. In fact we don't represent the size at all currently.

[ncw]

Updated to be on top of D40845, and removed non-quite-correct handling of globals/segments.

[ncw]

I'm abandoning this!

The changes are too small and not worth doing really, if we plan to merge Comdat support without having general weak-symbol discarding.

Presumably this case will be eventually covered by a GC implementation.

wasm/InputChunks.cpp

26

It took me a moment to see what you mean - the type doesn't tell you the size! For a struct, it seems like the type is 'i32', although the size will be typically much larger than 4.

OK, this doesn't work. We can't exclude Segments based on whether all the data in them is part of a global - maybe we can assume though that each global "owns" the segment that contains it?

Doesn't really matter, I'll abandon this revision.

[sbc100]

Actually I did an experiment with ELF and it looks like unused weak symbols are not stripped by default. i.e. you need to use --gc-sections to achieve this. So I think it makes sense for us to do the same (and --gc-sections will be the default for us).

test/wasm/weak-symbols.ll

 ; CHECK-NEXT:   Version:         0x00000001
 ; CHECK-NEXT: Sections:
 ; CHECK-NEXT:   - Type:            TYPE
 ; CHECK-NEXT:     Signatures:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         ReturnType:      I32
 ; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:   - Type:            FUNCTION
-; CHECK-NEXT:     FunctionTypes:   [ 0, 0, 0, 0, 0 ]
+; CHECK-NEXT:     FunctionTypes:   [ 0, 0, 0, 0 ]
 ; CHECK-NEXT:   - Type:            TABLE
 ; CHECK-NEXT:     Tables:
 ; CHECK-NEXT:       - ElemType:        ANYFUNC
 ; CHECK-NEXT:         Limits:
 ; CHECK-NEXT:           Flags:           [ HAS_MAX ]
 ; CHECK-NEXT:           Initial:         0x00000002
 ; CHECK-NEXT:           Maximum:         0x00000002
 ; CHECK-NEXT:   - Type:            MEMORY

 ; CHECK-NEXT:       - Name:            weakFn
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            exportWeak1
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:       - Name:            exportWeak2
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         Index:           4
+; CHECK-NEXT:         Index:           3
 ; CHECK-NEXT:   - Type:            ELEM
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - Offset:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           1
 ; CHECK-NEXT:         Functions:       [ 1 ]
 ; CHECK-NEXT:   - Type:            CODE
 ; CHECK-NEXT:     Functions:
 ; CHECK-NEXT:       - Locals:
 ; CHECK-NEXT:         Body:            1081808080001A4100280280888080000B
 ; CHECK-NEXT:       - Locals:
 ; CHECK-NEXT:         Body:            41010B
 ; CHECK-NEXT:       - Locals:
 ; CHECK-NEXT:         Body:            4181808080000B
 ; CHECK-NEXT:       - Locals:
-; CHECK-NEXT:         Body:            41020B
-; CHECK-NEXT:       - Locals:
 ; CHECK-NEXT:         Body:            4181808080000B
 ; CHECK-NEXT:   - Type:            DATA
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - SectionOffset:   7
 ; CHECK-NEXT:         MemoryIndex:     0
 ; CHECK-NEXT:         Offset:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           1024
-; CHECK-NEXT:         Content:         '0100000002000000'
+; CHECK-NEXT:         Content:         '01000000'
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            linking
-; CHECK-NEXT:     DataSize:        8
+; CHECK-NEXT:     DataSize:        4
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name
 ; CHECK-NEXT:     FunctionNames:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            _start
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Name:            exportWeak1
-; CHECK-NEXT:       - Index:           4
+; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Name:            exportWeak2
 ; CHECK-NEXT: ...

wasm/InputChunks.h

 
 #include "InputFiles.h"
 #include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Object/Wasm.h"
 
 using llvm::object::WasmSegment;
 using llvm::wasm::WasmFunction;
+using llvm::wasm::WasmGlobal;
 using llvm::wasm::WasmRelocation;
 using llvm::wasm::WasmSignature;
 using llvm::object::WasmSection;
 
 namespace lld {
 namespace wasm {
 
 class ObjFile;
 class OutputSegment;
 
 class InputChunk {
 public:
   InputChunk(const ObjFile &F) : File(F) {}
   virtual ~InputChunk() = default;
   void copyRelocations(const WasmSection &Section);
 
   virtual const uint8_t *getData() const = 0;
   virtual uint32_t getSize() const = 0;
   virtual uint32_t getInputSectionOffset() const = 0;
 
   int32_t OutputOffset = 0;
   int32_t InputOffset = 0;
+  bool Discarded = false;
   std::vector<WasmRelocation> Relocations;
   std::vector<OutputRelocation> OutRelocations;
   const ObjFile &File;
 };
 
 // Represents a WebAssembly data segment which can be included as part of
 // an output data segments.  Note that in WebAssembly, unlike ELF and other
 // formats, used the term "data segment" to refer to the continous regions of
public:
   uint32_t getInputSectionOffset() const override {
     return Segment.SectionOffset;
   }
   uint32_t getAlignment() const { return Segment.Data.Alignment; }
   uint32_t startVA() const { return Segment.Data.Offset.Value.Int32; }
   uint32_t endVA() const { return startVA() + getSize(); }
   StringRef getName() const { return Segment.Data.Name; }
 
+  // Returns whether the InputSegment contains any data other than that
+  // referenced by the given global symbol.  An InputSegment can contain (in
+  // theory) a mixture of static data and globals, although the frontend
+  // currently emits a single segment for each global.
+  bool isCoveredByGlobal(const WasmGlobal& Global) const;
+
 protected:
   const WasmSegment &Segment;
   const OutputSegment *OutputSeg = nullptr;
 };
 
 class InputFunction : public InputChunk {
 public:
   InputFunction(const WasmSignature &S, const WasmFunction &Func,

wasm/InputChunks.cpp

-//===- InputSegment.cpp ---------------------------------------------------===//
+//===- InputChunks.cpp ----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputChunks.h"
 #include "OutputSegment.h"
 #include "lld/Common/LLVM.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace lld::wasm;
+using llvm::wasm::ValType;
+
+static uint32_t getValueTypeBytes(int32_t Type) {
+  switch (static_cast<wasm::ValType>(Type)) {
+  case ValType::I32: case ValType::F32: return 4;
+  case ValType::I64: case ValType::F64: return 8;
+  default: llvm_unreachable("unexpected type");
+  }
+}
 
 uint32_t InputSegment::translateVA(uint32_t Address) const {
   assert(Address >= startVA() && Address < endVA());
   int32_t Delta = OutputSeg->StartVA + OutputOffset - startVA();
   DEBUG(dbgs() << "translateVA: " << getName() << " Delta=" << Delta
                << " Address=" << Address << "\n");
   return Address + Delta;
 }
 
+bool InputSegment::isCoveredByGlobal(const WasmGlobal& Global) const {
+  uint32_t GlobalAddr = Global.InitExpr.Value.Int32;
+  uint32_t GlobalSize = getValueTypeBytes(Global.Type);
+  return GlobalAddr == startVA() && GlobalAddr + GlobalSize == endVA();
+}
+
 void InputChunk::copyRelocations(const WasmSection &Section) {
   size_t Start = getInputSectionOffset();
   size_t Size = getSize();
   for (const WasmRelocation &R : Section.Relocations)
     if (R.Offset >= Start && R.Offset < Start + Size)
       Relocations.push_back(R);
 }

wasm/InputFiles.h

 private:
   Symbol *createDefined(const WasmSymbol &Sym,
                         const InputSegment *Segment = nullptr,
                         InputFunction *Function = nullptr);
   Symbol *createUndefined(const WasmSymbol &Sym,
                           const WasmSignature *Signature = nullptr);
   void initializeSymbols();
   InputSegment *getSegment(const WasmSymbol &WasmSym) const;
+  InputSegment *getSegment(uint32_t Address) const;
   const WasmSignature *getFunctionSig(const WasmSymbol &Sym) const;
   InputFunction *getFunction(const WasmSymbol &Sym) const;
 
   // List of all symbols referenced or defined by this file.
   std::vector<Symbol *> Symbols;
 
   // List of all function symbols indexed by the function index space
   std::vector<Symbol *> FunctionSymbols;

wasm/InputFiles.cpp

 //===- InputFiles.cpp -----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
 
 #include "Config.h"
 #include "InputChunks.h"
 #include "SymbolTable.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Object/Binary.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace lld;
 using namespace lld::wasm;
void ObjFile::parse() {
   }
 
   initializeSymbols();
 }
 
 // Return the InputSegment in which a given symbol is defined.
 InputSegment *ObjFile::getSegment(const WasmSymbol &WasmSym) const {
   uint32_t Address = WasmObj->getWasmSymbolValue(WasmSym);
-  for (InputSegment *Segment : Segments) {
-    if (Address >= Segment->startVA() && Address < Segment->endVA()) {
-      DEBUG(dbgs() << "Found symbol in segment: " << WasmSym.Name << " -> "
-                   << Segment->getName() << "\n");
-
-      return Segment;
-    }
+  InputSegment *Segment = getSegment(Address);
+  if (!Segment)
+    fatal("symbol not found in any segment: " + WasmSym.Name);
+
+InputSegment *ObjFile::getSegment(uint32_t Address) const {
+  for (InputSegment *Segment : Segments) {
+    if (Address >= Segment->startVA() && Address < Segment->endVA())
+      return Segment;
   }
-  error("symbol not found in any segment: " + WasmSym.Name);
   return nullptr;
 }
 
 // Get the signature for a given function symbol, either by looking
 // it up in function sections (for defined functions), of the imports section
 // (for imported functions).
 const WasmSignature *ObjFile::getFunctionSig(const WasmSymbol &Sym) const {
   DEBUG(dbgs() << "getFunctionSig: " << Sym.Name << "\n");
case WASM_EXTERNAL_FUNCTION:
       ++NumFunctionImports;
       break;
     case WASM_EXTERNAL_GLOBAL:
       ++NumGlobalImports;
       break;
     }
   }
 
-  FunctionSymbols.resize(NumFunctionImports + WasmObj->functions().size());
-  GlobalSymbols.resize(NumGlobalImports + WasmObj->globals().size());
+  ArrayRef<WasmFunction> Funcs = WasmObj->functions();
+  ArrayRef<uint32_t> FuncTypes = WasmObj->functionTypes();
+  ArrayRef<WasmSignature> Types = WasmObj->types();
+  ArrayRef<WasmGlobal> Globals = WasmObj->globals();
+
+  FunctionSymbols.resize(NumFunctionImports + Funcs.size());
+  GlobalSymbols.resize(NumGlobalImports + Globals.size());
 
   for (const WasmSegment &S : WasmObj->dataSegments()) {
     InputSegment *Seg = make<InputSegment>(S, *this);
     Seg->copyRelocations(*DataSection);
     Segments.emplace_back(Seg);
   }
 
-  ArrayRef<WasmFunction> Funcs = WasmObj->functions();
-  ArrayRef<uint32_t> FuncTypes = WasmObj->functionTypes();
-  ArrayRef<WasmSignature> Types = WasmObj->types();
   for (size_t I = 0; I < Funcs.size(); ++I) {
     const WasmFunction &Func = Funcs[I];
     const WasmSignature &Sig = Types[FuncTypes[I]];
     InputFunction *F = make<InputFunction>(Sig, Func, *this);
     F->copyRelocations(*CodeSection);
     Functions.emplace_back(F);
   }
 
   // Populate `FunctionSymbols` and `GlobalSymbols` based on the WasmSymbols
   // in the object
+  SmallBitVector ReachedFunctions(Funcs.size(), false);
+  SmallBitVector ReachedGlobals(Globals.size(), false);
   for (const SymbolRef &Sym : WasmObj->symbols()) {
     const WasmSymbol &WasmSym = WasmObj->getWasmSymbol(Sym.getRawDataRefImpl());
     Symbol *S;
     switch (WasmSym.Type) {
     case WasmSymbol::SymbolType::FUNCTION_IMPORT:
       S = createUndefined(WasmSym, getFunctionSig(WasmSym));
       break;
     case WasmSymbol::SymbolType::GLOBAL_IMPORT:
       S = createUndefined(WasmSym);
       break;
     case WasmSymbol::SymbolType::GLOBAL_EXPORT:
       S = createDefined(WasmSym, getSegment(WasmSym), nullptr);
+      if (S->getFile() == this)
+        ReachedGlobals[WasmSym.ElementIndex - NumGlobalImports] = true;
       break;
     case WasmSymbol::SymbolType::FUNCTION_EXPORT:
       S = createDefined(WasmSym, nullptr, getFunction(WasmSym));
+      if (S->getFile() == this)
+        ReachedFunctions[WasmSym.ElementIndex - NumFunctionImports] = true;
       break;
     case WasmSymbol::SymbolType::DEBUG_FUNCTION_NAME:
       // These are for debugging only, no need to create linker symbols for them
       continue;
     }
 
     Symbols.push_back(S);
     if (WasmSym.isFunction()) {
       DEBUG(dbgs() << "Function: " << WasmSym.ElementIndex << " -> "
                    << toString(*S) << "\n");
       FunctionSymbols[WasmSym.ElementIndex] = S;
     } else {
       DEBUG(dbgs() << "Global: " << WasmSym.ElementIndex << " -> "
                    << toString(*S) << "\n");
       GlobalSymbols[WasmSym.ElementIndex] = S;
     }
   }
 
+  // This is a crude precursor to garbage collection, but it works really nicely
+  // for discarding multiple copies of inline (=Comdat/weak) symbols.  If the
+  // function isn't reachable by any Symbol (because another file has defined
+  // the weak symbol), then it's discardable.  We aren't considering here
+  // whether the Symbol is actually ever called.
+  for (uint32_t I = 0; I < Funcs.size(); ++I) {
+    if (!ReachedFunctions[I])
+      Functions[I]->Discarded = true;
+  }
+  for (uint32_t I = 0; I < Globals.size(); ++I) {
+    // TODO It's crazy that we have to do a linear search through the segments
+    // for each global! We should *somehow* associate each global with its
+    // segment (and maybe each segment with its globals).  NB. Using the
+    // GlobalSym wouldn't work, we want the segment from *this file* not the
+    // one stored on the Symbol, which could come from another file.
+    InputSegment *Seg = getSegment(Globals[I].InitExpr.Value.Int32);
+    if (!ReachedGlobals[I] && Seg->isCoveredByGlobal(Globals[I]))
+      Seg->Discarded = true;
+  }
+
   // Populate `TableSymbols` with all symbols that are called indirectly
   uint32_t SegmentCount = WasmObj->elements().size();
   if (SegmentCount) {
     if (SegmentCount > 1)
       fatal(getName() + ": contains more than one element segment");
     const WasmElemSegment &Segment = WasmObj->elements()[0];
     if (Segment.Offset.Opcode != WASM_OPCODE_I32_CONST)
       fatal(getName() + ": unsupported element segment");

wasm/Writer.cpp

for (Symbol *Sym : File->getSymbols()) {
         continue;
 
       DefinedGlobals.emplace_back(Sym);
       Sym->setOutputIndex(GlobalIndex++);
     }
 
     DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
     for (InputFunction *Func : File->Functions) {
+      if (Func->Discarded)
+        continue;
       DefinedFunctions.emplace_back(Func);
       Func->setOutputIndex(FunctionIndex++);
     }
 
     DEBUG(dbgs() << "Table Indexes: " << File->getName() << "\n");
     for (Symbol *Sym : File->getTableSymbols()) {
       if (!Sym->hasTableIndex()) {
         Sym->setTableIndex(TableIndex++);
static StringRef getOutputDataSegmentName(StringRef Name) {
   }
 
   return Name;
 }
 
 void Writer::createOutputSegments() {
   for (ObjFile *File : Symtab->ObjectFiles) {
     for (InputSegment *Segment : File->Segments) {
+      if (Segment->Discarded)
+        continue;
       StringRef Name = getOutputDataSegmentName(Segment->getName());
       OutputSegment *&S = SegmentMap[Name];
       if (S == nullptr) {
         DEBUG(dbgs() << "new segment: " << Name << "\n");
         S = make<OutputSegment>(Name);
         Segments.push_back(S);
       }
       S->addInputSegment(Segment);