[WebAssembly] Write minimal types section

[sbc100]

Summary

Don't include type signatures that are not referenced by
some relocation.

We don't include this in the -gc-sections settings since
we are alwasy building the type section from scratch,
just like we do the table elements.

In the future we might want to unify the relocation
processing which is currently done once for gc-sections
and then again for building the sympathetic type and
table sections.

[ncw]

LGTM, can't see any potential problems (just endless merge conflicts coming up - I've just finished rebasing onto the GC changes...)

wasm/InputFiles.h

104

There is a class llvm::BitVector, but I don't know whether it's preferred over std::vector<bool> (presumably, or it wouldn't have been written?)

[ruiu]

wasm/InputFiles.h

104

I'm fine with this code. I prefer std containers over llvm's in this case because I don't think there's a large difference.

test/wasm/call-indirect.ll

 ; CHECK-NEXT:   Version:         0x00000001
 ; CHECK-NEXT: Sections:
 ; CHECK-NEXT:   - Type:            TYPE
 ; CHECK-NEXT:     Signatures:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         ReturnType:      I64
 ; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:       - Index:           1
-; CHECK-NEXT:         ReturnType:      NORESULT
+; CHECK-NEXT:         ReturnType:      I32
 ; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:       - Index:           2
-; CHECK-NEXT:         ReturnType:      I32
+; CHECK-NEXT:         ReturnType:      I64
 ; CHECK-NEXT:         ParamTypes:
+; CHECK-NEXT:           - I64
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         ReturnType:      NORESULT
 ; CHECK-NEXT:         ParamTypes:
-; CHECK-NEXT:           - I32
 ; CHECK-NEXT:       - Index:           4
-; CHECK-NEXT:         ReturnType:      I64
+; CHECK-NEXT:         ReturnType:      NORESULT
 ; CHECK-NEXT:         ParamTypes:
-; CHECK-NEXT:           - I64
+; CHECK-NEXT:           - I32
 ; CHECK-NEXT:   - Type:            FUNCTION
-; CHECK-NEXT:     FunctionTypes:   [ 0, 1, 2, 2, 3, 1 ]
+; CHECK-NEXT:     FunctionTypes:   [ 0, 3, 1, 1, 4, 3 ]
 ; 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:   - Type:            MEMORY

 ; CHECK-NEXT:     Functions:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            42010B
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:            - Type:            I32
 ; CHECK-NEXT:              Count:           1
-; CHECK-NEXT:          Body:            4100280284888080002100410028028088808000118080808000001A2000118280808000001A0B
+; CHECK-NEXT:          Body:            4100280284888080002100410028028088808000118080808000001A2000118180808000001A0B
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            41020B
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Locals:
-; CHECK-NEXT:         Body:            410028028888808000118280808000001A41000B
+; CHECK-NEXT:         Body:            410028028888808000118180808000001A41000B
 ; CHECK-NEXT:       - Index:           4
 ; CHECK-NEXT:         Locals:
-; CHECK-NEXT:         Body:            42012000118480808000001A0B
+; CHECK-NEXT:         Body:            42012000118280808000001A0B
 ; CHECK-NEXT:       - Index:           5
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            0B
 ; CHECK-NEXT:   - Type:            DATA
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - SectionOffset:    7
 ; CHECK-NEXT:         MemoryIndex:      0
 ; CHECK-NEXT:         Offset:

test/wasm/gc-sections.ll

 ; RUN: llc -filetype=obj %s -o %t.o
 ; RUN: lld -flavor wasm -print-gc-sections -o %t1.wasm %t.o | FileCheck %s -check-prefix=PRINT-GC
 ; PRINT-GC: removing unused section 'unused_function' in file '{{.*}}'
 ; PRINT-GC-NOT: removing unused section 'used_function' in file '{{.*}}'
 ; PRINT-GC: removing unused section '.data.unused_data' in file '{{.*}}'
 ; PRINT-GC-NOT: removing unused section '.data.used_data' in file '{{.*}}'
 
 target triple = "wasm32-unknown-unknown-wasm"
 
-@unused_data = hidden global i32 1, align 4
+@unused_data = hidden global i64 1, align 4
 @used_data = hidden global i32 2, align 4
 
-define hidden i32 @unused_function() {
-  %1 = load i32, i32* @unused_data, align 4
-  ret i32 %1
+define hidden i64 @unused_function() {
+  %1 = load i64, i64* @unused_data, align 4
+  ret i64 %1
 }
 
 define hidden i32 @used_function() {
   %1 = load i32, i32* @used_data, align 4
   ret i32 %1
 }
 
 define hidden void @_start() {
 entry:
   call i32 @used_function()
   ret void
 }
 
 ; RUN: obj2yaml %t1.wasm | FileCheck %s
+
+; CHECK:        - Type:            TYPE
+; CHECK-NEXT:     Signatures:      
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         ReturnType:      I32
+; CHECK-NEXT:         ParamTypes:      
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         ReturnType:      NORESULT
+; CHECK-NEXT:         ParamTypes:      
+; CHECK-NEXT:   - Type:            FUNCTION
+
 ; CHECK:        - 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:         '02000000'
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            linking
 ; CHECK-NEXT:     DataSize:        4
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name
 ; CHECK-NEXT:     FunctionNames:   
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            used_function
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Name:            _start
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Name:            __wasm_call_ctors
 ; CHECK-NEXT: ...
 
 ; RUN: lld -flavor wasm -print-gc-sections --no-gc-sections -o %t1.no-gc.wasm %t.o
 ; RUN: obj2yaml %t1.no-gc.wasm | FileCheck %s -check-prefix=NO-GC
+
+; NO-GC:        - Type:            TYPE
+; NO-GC-NEXT:     Signatures:      
+; NO-GC-NEXT:       - Index:           0
+; NO-GC-NEXT:         ReturnType:      I64
+; NO-GC-NEXT:         ParamTypes:      
+; NO-GC-NEXT:       - Index:           1
+; NO-GC-NEXT:         ReturnType:      I32
+; NO-GC-NEXT:         ParamTypes:      
+; NO-GC-NEXT:       - Index:           2
+; NO-GC-NEXT:         ReturnType:      NORESULT
+; NO-GC-NEXT:         ParamTypes:      
+; NO-GC-NEXT:   - Type:            FUNCTION
+
 ; NO-GC:        - Type:            DATA
 ; NO-GC-NEXT:     Segments:        
 ; NO-GC-NEXT:       - SectionOffset:   7
 ; NO-GC-NEXT:         MemoryIndex:     0
 ; NO-GC-NEXT:         Offset:          
 ; NO-GC-NEXT:           Opcode:          I32_CONST
 ; NO-GC-NEXT:           Value:           1024
-; NO-GC-NEXT:         Content:         '0100000002000000'
+; NO-GC-NEXT:         Content:         '010000000000000002000000'
 ; NO-GC-NEXT:   - Type:            CUSTOM
 ; NO-GC-NEXT:     Name:            linking
-; NO-GC-NEXT:     DataSize:        8
+; NO-GC-NEXT:     DataSize:        12
 ; NO-GC-NEXT:   - Type:            CUSTOM
 ; NO-GC-NEXT:     Name:            name
 ; NO-GC-NEXT:     FunctionNames:   
 ; NO-GC-NEXT:       - Index:           0
 ; NO-GC-NEXT:         Name:            unused_function
 ; NO-GC-NEXT:       - Index:           1
 ; NO-GC-NEXT:         Name:            used_function
 ; NO-GC-NEXT:       - Index:           2
 ; NO-GC-NEXT:         Name:            _start
 ; NO-GC-NEXT:       - Index:           3
 ; NO-GC-NEXT:         Name:            __wasm_call_ctors
 ; NO-GC-NEXT: ...
 
 ; RUN: not lld -flavor wasm --gc-sections --relocatable -o %t1.no-gc.wasm %t.o 2>&1 | FileCheck %s -check-prefix=CHECK-ERROR
 ; CHECK-ERROR: lld: error: -r and --gc-sections may not be used together

test/wasm/relocatable.ll

 ; CHECK-NEXT: FileHeader:
 ; CHECK-NEXT:   Version:         0x00000001
 ; CHECK-NEXT: Sections:
 ; CHECK-NEXT:   - Type:            TYPE
 ; CHECK-NEXT:     Signatures:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         ReturnType:      NORESULT
 ; CHECK-NEXT:         ParamTypes:
+; CHECK-NEXT:           - I32
 ; CHECK-NEXT:       - Index:           1
-; CHECK-NEXT:         ReturnType:      NORESULT
+; CHECK-NEXT:         ReturnType:      I32
 ; CHECK-NEXT:         ParamTypes:
-; CHECK-NEXT:           - I32
 ; CHECK-NEXT:       - Index:           2
-; CHECK-NEXT:         ReturnType:      I32
+; CHECK-NEXT:         ReturnType:      NORESULT
 ; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:   - Type:            IMPORT
 ; CHECK-NEXT:     Imports:
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           puts
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         SigIndex:        1
+; CHECK-NEXT:         SigIndex:        0
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           foo_import
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         SigIndex:        2
+; CHECK-NEXT:         SigIndex:        1
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           bar_import
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         SigIndex:        2
+; CHECK-NEXT:         SigIndex:        1
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           data_import
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         GlobalType:      I32
 ; CHECK-NEXT:         GlobalMutable:   false
 ; CHECK-NEXT:   - Type:            FUNCTION
-; CHECK-NEXT:     FunctionTypes:   [ 0, 2, 2 ]
+; CHECK-NEXT:     FunctionTypes:   [ 2, 1, 1 ]
 ; CHECK-NEXT:   - Type:            TABLE
 ; CHECK-NEXT:     Tables:
 ; CHECK-NEXT:       - ElemType:        ANYFUNC
 ; CHECK-NEXT:         Limits:
 ; CHECK-NEXT:           Flags:           [ HAS_MAX ]
 ; CHECK-NEXT:           Initial:         0x00000004
 ; CHECK-NEXT:           Maximum:         0x00000004
 ; CHECK-NEXT:   - Type:            MEMORY

wasm/InputChunks.h

public:
   ArrayRef<WasmRelocation> getRelocations() const { return Relocations; }
   StringRef getFileName() const { return File->getName(); }
 
   virtual StringRef getComdat() const = 0;
   virtual StringRef getName() const = 0;
 
   bool Discarded = false;
   std::vector<OutputRelocation> OutRelocations;
-  const ObjFile *File;
+  ObjFile *File;
 
   // The garbage collector sets sections' Live bits.
   // If GC is disabled, all sections are considered live by default.
   unsigned Live : 1;
 
 protected:
-  InputChunk(const ObjFile *F, Kind K)
+  InputChunk(ObjFile *F, Kind K)
       : File(F), Live(!Config->GcSections), SectionKind(K) {}
   virtual ~InputChunk() = default;
   void calcRelocations();
   virtual ArrayRef<uint8_t> data() const = 0;
   virtual uint32_t getInputSectionOffset() const = 0;
 
   std::vector<WasmRelocation> Relocations;
   int32_t OutputOffset = 0;
   Kind SectionKind;
 };
 
 // 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
 // memory that make on the data section. See:
 // https://webassembly.github.io/spec/syntax/modules.html#syntax-data
 //
 // For example, by default, clang will produce a separate data section for
 // each global variable.
 class InputSegment : public InputChunk {
 public:
-  InputSegment(const WasmSegment &Seg, const ObjFile *F)
+  InputSegment(const WasmSegment &Seg, ObjFile *F)
       : InputChunk(F, InputChunk::DataSegment), Segment(Seg) {}
 
   static bool classof(const InputChunk *C) { return C->kind() == DataSegment; }
 
   // Translate an offset in the input segment to an offset in the output
   // segment.
   uint32_t translateVA(uint32_t Address) const;
 
protected:
   const OutputSegment *OutputSeg = nullptr;
 };
 
 // Represents a single wasm function within and input file.  These are
 // combined to create the final output CODE section.
 class InputFunction : public InputChunk {
 public:
   InputFunction(const WasmSignature &S, const WasmFunction *Func,
-                const ObjFile *F)
+                ObjFile *F)
       : InputChunk(F, InputChunk::Function), Signature(S), Function(Func) {}
 
   static bool classof(const InputChunk *C) {
     return C->kind() == InputChunk::Function;
   }
 
   StringRef getName() const override { return Function->Name; }
   StringRef getComdat() const override { return Function->Comdat; }

wasm/InputFiles.h

public:
   uint32_t relocateFunctionIndex(uint32_t Original) const;
   uint32_t calcNewIndex(const WasmRelocation &Reloc) const;
   uint32_t calcNewValue(const WasmRelocation &Reloc) const;
 
   const WasmSection *CodeSection = nullptr;
   const WasmSection *DataSection = nullptr;
 
   std::vector<uint32_t> TypeMap;
+  std::vector<bool> TypeIsUsed;
   std::vector<InputSegment *> Segments;
   std::vector<InputFunction *> Functions;
 
   ArrayRef<Symbol *> getSymbols() const { return Symbols; }
 
   Symbol *getFunctionSymbol(uint32_t Index) const {
     return FunctionSymbols[Index];
   }

wasm/InputFiles.cpp

uint32_t ObjFile::relocateFunctionIndex(uint32_t Original) const {
   const Symbol *Sym = getFunctionSymbol(Original);
   uint32_t Index = Sym->getOutputIndex();
   DEBUG(dbgs() << "relocateFunctionIndex: " << toString(*Sym) << ": "
                << Original << " -> " << Index << "\n");
   return Index;
 }
 
 uint32_t ObjFile::relocateTypeIndex(uint32_t Original) const {
+  assert(TypeIsUsed[Original]);
   return TypeMap[Original];
 }
 
 uint32_t ObjFile::relocateTableIndex(uint32_t Original) const {
   const Symbol *Sym = getFunctionSymbol(Original);
   uint32_t Index = Sym->hasTableIndex() ? Sym->getTableIndex() : 0;
   DEBUG(dbgs() << "relocateTableIndex: " << toString(*Sym) << ": " << Original
                << " -> " << Index << "\n");
void ObjFile::parse() {
   for (const SectionRef &Sec : WasmObj->sections()) {
     const WasmSection &Section = WasmObj->getWasmSection(Sec);
     if (Section.Type == WASM_SEC_CODE)
       CodeSection = &Section;
     else if (Section.Type == WASM_SEC_DATA)
       DataSection = &Section;
   }
 
+  TypeMap.resize(getWasmObj()->types().size());
+  TypeIsUsed.resize(getWasmObj()->types().size(), false);
+
   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()) {

wasm/Writer.cpp

uint32_t Writer::registerType(const WasmSignature &Sig) {
   if (Pair.second) {
     DEBUG(dbgs() << "type " << toString(Sig) << "\n");
     Types.push_back(&Sig);
   }
   return Pair.first->second;
 }
 
 void Writer::calculateTypes() {
+  // The output type section is the union of the following sets:
+  // 1. Any signature used in the TYPE relocation
+  // 2. The signatures of all imported functions
+  // 3. The signatures of all defined functions
+
   for (ObjFile *File : Symtab->ObjectFiles) {
-    File->TypeMap.reserve(File->getWasmObj()->types().size());
-    for (const WasmSignature &Sig : File->getWasmObj()->types())
-      File->TypeMap.push_back(registerType(Sig));
+    ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
+    for (uint32_t I = 0; I < Types.size(); I++)
+      if (File->TypeIsUsed[I])
+        File->TypeMap[I] = registerType(Types[I]);
   }
 
-  for (Symbol *Sym : Symtab->getSymbols())
-    if (Sym->isFunction())
-      registerType(Sym->getFunctionType());
+  for (const Symbol *Sym : ImportedFunctions)
+
+  for (const InputFunction *F : DefinedFunctions)
+    registerType(F->Signature);
 }
 
 void Writer::assignIndexes() {
   uint32_t GlobalIndex = ImportedGlobals.size() + DefinedGlobals.size();
   uint32_t FunctionIndex = ImportedFunctions.size() + DefinedFunctions.size();
 
   if (Config->StackPointerSymbol) {
     DefinedGlobals.emplace_back(Config->StackPointerSymbol);
for (InputFunction *Func : File->Functions) {
       if (Func->Discarded || !Func->Live)
         continue;
       DefinedFunctions.emplace_back(Func);
       Func->setOutputIndex(FunctionIndex++);
     }
   }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
-    DEBUG(dbgs() << "Table Indexes: " << File->getName() << "\n");
-    auto HandleTableRelocs = [&](InputChunk *Chunk) {
+    DEBUG(dbgs() << "Handle relocs: " << File->getName() << "\n");
+    auto HandleRelocs = [&](InputChunk *Chunk) {
       if (Chunk->Discarded)
         return;
+      ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
       for (const WasmRelocation& Reloc : Chunk->getRelocations()) {
-        if (Reloc.Type != R_WEBASSEMBLY_TABLE_INDEX_I32 &&
-            Reloc.Type != R_WEBASSEMBLY_TABLE_INDEX_SLEB)
-          continue;
+        if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32 ||
+            Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB) {
           Symbol *Sym = File->getFunctionSymbol(Reloc.Index);
           if (Sym->hasTableIndex() || !Sym->hasOutputIndex())
             continue;
           Sym->setTableIndex(TableIndex++);
           IndirectFunctions.emplace_back(Sym);
+        } else if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB) {
+          Chunk->File->TypeMap[Reloc.Index] = registerType(Types[Reloc.Index]);
+          Chunk->File->TypeIsUsed[Reloc.Index] = true;
+        }
       }
     };
+
     for (InputFunction* Function : File->Functions)
-      HandleTableRelocs(Function);
+      HandleRelocs(Function);
     for (InputSegment* Segment : File->Segments)
-      HandleTableRelocs(Segment);
+      HandleRelocs(Segment);
   }
 }
 
 static StringRef getOutputDataSegmentName(StringRef Name) {
   if (Config->Relocatable)
     return Name;
 
   for (StringRef V :
void Writer::calculateInitFunctions() {
   // in the correct order.
   std::sort(InitFunctions.begin(), InitFunctions.end(),
             [](const WasmInitFunc &L, const WasmInitFunc &R) {
               return L.Priority < R.Priority;
             });
 }
 
 void Writer::run() {
-  log("-- calculateTypes");
-  calculateTypes();
   log("-- calculateImports");
   calculateImports();
   log("-- assignIndexes");
   assignIndexes();
   log("-- calculateExports");
   calculateExports();
   log("-- calculateInitFunctions");
   calculateInitFunctions();
   if (!Config->Relocatable)
     createCtorFunction();
+  log("-- calculateTypes");
+  calculateTypes();
 
   if (errorHandler().Verbose) {
     log("Defined Functions: " + Twine(DefinedFunctions.size()));
     log("Defined Globals  : " + Twine(DefinedGlobals.size()));
     log("Function Imports : " + Twine(ImportedFunctions.size()));
     log("Global Imports   : " + Twine(ImportedGlobals.size()));
     log("Total Imports    : " +
         Twine(ImportedFunctions.size() + ImportedGlobals.size()));