[WebAssembly] Don't duplicate functions in table output

[ncw]

Summary

Previously, we were ensuring that the "output index" for InputFunctions was unique across all symbols that referenced a function body, but allowing the same function body to have multiple table indexes.

Now, we use the same mechanism for table indexes as we already do for output indexes, ensuring that each InputFunction is only placed in the table once.

This makes the LLD output table denser and smaller, but with identical behaviour.

Note that we still need the Symbol::TableIndex member, to store the table index for function Symbols that don't have an InputFunction, ie for address-taken imports.

---

Split out from D41955. Please merge after D42096 and before D41955, otherwise you'll have to update the tests to merge in another order.

[sbc100]

Can you change the title something simpler like. e.g: "[WebAssembly] Don't duplicate functions in table output"?

[ncw]

No problem! I'd noticed your commit style was rather terser than mine, I'll adjust to it. I tend to err on the side of being rather verbose, to help distributed communication - apologies and thank you.

lld/trunk/test/wasm/weak-alias.ll

 ; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:   - Type:            FUNCTION
 ; CHECK-NEXT:     FunctionTypes:   [ 0, 0, 0, 0, 0, 0, 1 ]
 ; CHECK-NEXT:   - Type:            TABLE
 ; CHECK-NEXT:     Tables:
 ; CHECK-NEXT:       - ElemType:        ANYFUNC
 ; CHECK-NEXT:         Limits:
 ; CHECK-NEXT:           Flags:           [ HAS_MAX ]
-; CHECK-NEXT:           Initial:         0x00000003
-; CHECK-NEXT:           Maximum:         0x00000003
+; CHECK-NEXT:           Initial:         0x00000002
+; CHECK-NEXT:           Maximum:         0x00000002
 ; CHECK-NEXT:   - Type:            MEMORY
 ; CHECK-NEXT:     Memories:
 ; CHECK-NEXT:       - Initial:         0x00000002
 ; CHECK-NEXT:   - Type:            GLOBAL
 ; CHECK-NEXT:     Globals:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Type:            I32
 ; CHECK-NEXT:         Mutable:         true

 ; CHECK-NEXT:       - Name:            __heap_base
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:   - Type:            ELEM
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - Offset:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           1
-; CHECK-NEXT:         Functions:       [ 1, 1 ]
+; CHECK-NEXT:         Functions:       [ 1 ]
 ; CHECK-NEXT:   - Type:            CODE
 ; CHECK-NEXT:     Functions:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            1081808080000B
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            41000B
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            1081808080000B
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            1081808080000B
 ; CHECK-NEXT:       - Index:           4
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:           - Type:            I32
 ; CHECK-NEXT:             Count:           2
 ; CHECK-NEXT:         Body:            23808080800041106B220024808080800020004181808080003602081081808080002101200041106A24808080800020010B
 ; CHECK-NEXT:       - Index:           5
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:           - Type:            I32
 ; CHECK-NEXT:             Count:           2
-; CHECK-NEXT:         Body:            23808080800041106B220024808080800020004182808080003602081081808080002101200041106A24808080800020010B
+; CHECK-NEXT:         Body:            23808080800041106B220024808080800020004181808080003602081081808080002101200041106A24808080800020010B
 ; CHECK-NEXT:       - Index:           6
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            0B
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            linking
 ; CHECK-NEXT:     DataSize:        0
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name

 ; RELOC-NEXT:         GlobalMutable:   false
 ; RELOC-NEXT:   - Type:            FUNCTION
 ; RELOC-NEXT:     FunctionTypes:   [ 0, 0, 0, 0, 0, 0 ]
 ; RELOC-NEXT:   - Type:            TABLE
 ; RELOC-NEXT:     Tables:
 ; RELOC-NEXT:       - ElemType:        ANYFUNC
 ; RELOC-NEXT:         Limits:
 ; RELOC-NEXT:           Flags:           [ HAS_MAX ]
-; RELOC-NEXT:           Initial:         0x00000003
-; RELOC-NEXT:           Maximum:         0x00000003
+; RELOC-NEXT:           Initial:         0x00000002
+; RELOC-NEXT:           Maximum:         0x00000002
 ; RELOC-NEXT:   - Type:            MEMORY
 ; RELOC-NEXT:     Memories:
 ; RELOC-NEXT:       - Initial:         0x00000000
 ; RELOC-NEXT:   - Type:            EXPORT
 ; RELOC-NEXT:     Exports:
 ; RELOC-NEXT:       - Name:            _start
 ; RELOC-NEXT:         Kind:            FUNCTION
 ; RELOC-NEXT:         Index:           0

 ; RELOC-NEXT:       - Name:            call_direct_ptr
 ; RELOC-NEXT:         Kind:            FUNCTION
 ; RELOC-NEXT:         Index:           5
 ; RELOC-NEXT:   - Type:            ELEM
 ; RELOC-NEXT:     Segments:
 ; RELOC-NEXT:       - Offset:
 ; RELOC-NEXT:           Opcode:          I32_CONST
 ; RELOC-NEXT:           Value:           1
-; RELOC-NEXT:         Functions:       [ 1, 1 ]
+; RELOC-NEXT:         Functions:       [ 1 ]
 ; RELOC-NEXT:   - Type:            CODE
 ; RELOC-NEXT:     Relocations:
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
 ; RELOC-NEXT:         Index:           1
 ; RELOC-NEXT:         Offset:          0x00000004
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
 ; RELOC-NEXT:         Index:           1
 ; RELOC-NEXT:         Offset:          0x00000012

 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:           - Type:            I32
 ; RELOC-NEXT:             Count:           2
 ; RELOC-NEXT:         Body:            23808080800041106B220024808080800020004181808080003602081081808080002101200041106A24808080800020010B
 ; RELOC-NEXT:       - Index:           5
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:           - Type:            I32
 ; RELOC-NEXT:             Count:           2
-; RELOC-NEXT:         Body:            23808080800041106B220024808080800020004182808080003602081081808080002101200041106A24808080800020010B
+; RELOC-NEXT:         Body:            23808080800041106B220024808080800020004181808080003602081081808080002101200041106A24808080800020010B
 ; RELOC-NEXT:   - Type:            CUSTOM
 ; RELOC-NEXT:     Name:            linking
 ; RELOC-NEXT:     DataSize:        0
 ; RELOC-NEXT:     SymbolInfo:
 ; RELOC-NEXT:       - Name:            alias_fn
 ; RELOC-NEXT:         Flags:           [ BINDING_WEAK ]
 ; RELOC-NEXT:   - Type:            CUSTOM
 ; RELOC-NEXT:     Name:            name

lld/trunk/wasm/InputChunks.h

InputFunction(const WasmSignature &S, const WasmFunction *Func,
                 const ObjFile *F)
       : InputChunk(F), Signature(S), Function(Func) {}
 
   virtual StringRef getName() const { return Function->Name; }
   StringRef getComdat() const override { return Function->Comdat; }
   uint32_t getOutputIndex() const { return OutputIndex.getValue(); }
   bool hasOutputIndex() const { return OutputIndex.hasValue(); }
   void setOutputIndex(uint32_t Index);
+  uint32_t getTableIndex() const { return TableIndex.getValue(); }
+  bool hasTableIndex() const { return TableIndex.hasValue(); }
+  void setTableIndex(uint32_t Index);
 
   const WasmSignature &Signature;
 
 protected:
   ArrayRef<uint8_t> data() const override {
     return File->CodeSection->Content.slice(getInputSectionOffset(),
                                             Function->Size);
   }
   uint32_t getInputSectionOffset() const override {
     return Function->CodeSectionOffset;
   }
 
   const WasmFunction *Function;
   llvm::Optional<uint32_t> OutputIndex;
+  llvm::Optional<uint32_t> TableIndex;
 };
 
 class SyntheticFunction : public InputFunction {
 public:
   SyntheticFunction(const WasmSignature &S, ArrayRef<uint8_t> Body,
                     StringRef Name)
       : InputFunction(S, nullptr, nullptr), Name(Name), Body(Body) {}
 

lld/trunk/wasm/InputChunks.cpp

void InputChunk::calcRelocations() {
   }
 }
 
 void InputFunction::setOutputIndex(uint32_t Index) {
   DEBUG(dbgs() << "InputFunction::setOutputIndex: " << Index << "\n");
   assert(!hasOutputIndex());
   OutputIndex = Index;
 }
+
+void InputFunction::setTableIndex(uint32_t Index) {
+  DEBUG(dbgs() << "InputFunction::setTableIndex " << Index << "\n");
+  assert(!hasTableIndex());
+  TableIndex = Index;
+}

lld/trunk/wasm/Symbols.h

public:
 
   // Returns true if an output index has been set for this symbol
   bool hasOutputIndex() const;
 
   // Set the output index of the symbol (in the function or global index
   // space of the output object.
   void setOutputIndex(uint32_t Index);
 
-  uint32_t getTableIndex() const { return TableIndex.getValue(); }
+  uint32_t getTableIndex() const;
 
   // Returns true if a table index has been set for this symbol
-  bool hasTableIndex() const { return TableIndex.hasValue(); }
+  bool hasTableIndex() const;
 
   // Set the table index of the symbol
   void setTableIndex(uint32_t Index);
 
   // Returns the virtual address of a defined global.
   // Only works for globals, not functions.
   uint32_t getVirtualAddress() const;
 

lld/trunk/wasm/Symbols.cpp

 
 void Symbol::setOutputIndex(uint32_t Index) {
   DEBUG(dbgs() << "setOutputIndex " << Name << " -> " << Index << "\n");
   assert(!Function);
   assert(!OutputIndex.hasValue());
   OutputIndex = Index;
 }
 
+uint32_t Symbol::getTableIndex() const {
+  if (Function)
+    return Function->getTableIndex();
+  return TableIndex.getValue();
+}
+
+bool Symbol::hasTableIndex() const {
+  if (Function)
+    return Function->hasTableIndex();
+  return TableIndex.hasValue();
+}
+
 void Symbol::setTableIndex(uint32_t Index) {
+  // For imports, we set the table index here on the Symbol; for defined
+  // functions we set the index on the InputFunction so that we don't export
+  // the same thing twice (keeps the table size down).
+  if (Function) {
+    Function->setTableIndex(Index);
+    return;
+  }
   DEBUG(dbgs() << "setTableIndex " << Name << " -> " << Index << "\n");
   assert(!TableIndex.hasValue());
   TableIndex = Index;
 }
 
 void Symbol::update(Kind K, InputFile *F, uint32_t Flags_,
                     const InputSegment *Seg, InputFunction *Func,
                     uint32_t Address) {