[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

233

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

233

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 ↗

(On Diff #129266)

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 ↗

(On Diff #129266)

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:       - Index:           0
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            1081808080001A4100280280888080000B
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            41010B
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            4181808080000B
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Locals:
-; CHECK-NEXT:         Body:            41020B
-; CHECK-NEXT:       - Index:           4
-; 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:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            linking
 ; CHECK-NEXT:     DataSize:        8
 ; 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/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;
for (size_t I = 0; I < Funcs.size(); ++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);
   for (const SymbolRef &Sym : WasmObj->symbols()) {
     const WasmSymbol &WasmSym = WasmObj->getWasmSymbol(Sym.getRawDataRefImpl());
     Symbol *S;
     switch (WasmSym.Type) {
     case WasmSymbol::SymbolType::FUNCTION_EXPORT: {
       InputFunction *Function = getFunction(WasmSym);
       if (!isExcludedByComdat(Function)) {
         S = createDefined(WasmSym, Symbol::Kind::DefinedFunctionKind, nullptr,
                           Function);
+        if (S->getFile() == this)
+          ReachedFunctions[WasmSym.ElementIndex - NumFunctionImports] = true;
         break;
       } else {
         Function->Discarded = true;
         // fall through:
       }
     }
     case WasmSymbol::SymbolType::FUNCTION_IMPORT:
       S = createUndefined(WasmSym, Symbol::Kind::UndefinedFunctionKind,
                           getFunctionSig(WasmSym));
       break;
     case WasmSymbol::SymbolType::GLOBAL_EXPORT: {
       InputSegment *Segment = getSegment(WasmSym);
       if (!isExcludedByComdat(Segment)) {
         S = createDefined(WasmSym, Symbol::Kind::DefinedGlobalKind,
                           Segment, nullptr, getGlobalValue(WasmSym));
         break;
       } else {
         Segment->Discarded = true;
         // fall through:
       }
     }
     case WasmSymbol::SymbolType::GLOBAL_IMPORT:
       S = createUndefined(WasmSym, Symbol::Kind::UndefinedGlobalKind);
       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");
for (const SymbolRef &Sym : WasmObj->symbols()) {
     }
   }
 
   DEBUG(for (size_t I = 0; I < FunctionSymbols.size(); ++I)
             assert(FunctionSymbols[I] != nullptr);
         for (size_t I = 0; I < GlobalSymbols.size(); ++I)
             assert(GlobalSymbols[I] != nullptr););
 
+  // This is a crude precursor to garbage collection, but it works really nicely
+  // for discarding multiple copies of 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;
+  }
+
   // 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");