[WebAssembly] Add first claass symbol table to wasm objects

This is combination of two patches by Nicholas Wilson:
  1. https://reviews.llvm.org/D41954
  2. https://reviews.llvm.org/D42495

Along with a few local modifications:
- One change I made was to add the UNDEFINED bit to the binary format
  to avoid the extra byte used when writing data symbols.  Although this
  bit is redundant for other symbols types (i.e. undefined can be
  implied if a function or global is a wasm import)
- I prefer to be explicit and consistent and not have derived flags.
- Some field renaming.
- Some reverting of unrelated minor changes.
- No test output differences.

Differential Revision: https://reviews.llvm.org/D43147

llvm-svn: 325860

1 files changed, 169 insertions, 135 deletions

diff --git a/llvm/lib/Object/WasmObjectFile.cpp b/llvm/lib/Object/WasmObjectFile.cpp
index 82adc35076d..4483dae809d 100644
--- a/llvm/lib/Object/WasmObjectFile.cpp
+++ b/llvm/lib/Object/WasmObjectFile.cpp
@@ -317,69 +317,6 @@ Error WasmObjectFile::parseNameSection(const uint8_t *Ptr, const uint8_t *End) {
   return Error::success();
 }
 
-void WasmObjectFile::populateSymbolTable() {
-  // Add imports to symbol table
-  size_t GlobalIndex = 0;
-  size_t FunctionIndex = 0;
-  for (const wasm::WasmImport& Import : Imports) {
-    switch (Import.Kind) {
-    case wasm::WASM_EXTERNAL_GLOBAL:
-      assert(Import.Global.Type == wasm::WASM_TYPE_I32);
-      SymbolMap.try_emplace(Import.Field, Symbols.size());
-      Symbols.emplace_back(Import.Field, WasmSymbol::SymbolType::GLOBAL_IMPORT,
-                           GlobalIndex++);
-      DEBUG(dbgs() << "Adding import: " << Symbols.back()
-                   << " sym index:" << Symbols.size() << "\n");
-      break;
-    case wasm::WASM_EXTERNAL_FUNCTION:
-      SymbolMap.try_emplace(Import.Field, Symbols.size());
-      Symbols.emplace_back(Import.Field,
-                           WasmSymbol::SymbolType::FUNCTION_IMPORT,
-                           FunctionIndex++, Import.SigIndex);
-      DEBUG(dbgs() << "Adding import: " << Symbols.back()
-                   << " sym index:" << Symbols.size() << "\n");
-      break;
-    default:
-      break;
-    }
-  }
-
-  // Add exports to symbol table
-  for (const wasm::WasmExport& Export : Exports) {
-    if (Export.Kind == wasm::WASM_EXTERNAL_FUNCTION ||
-        Export.Kind == wasm::WASM_EXTERNAL_GLOBAL) {
-      WasmSymbol::SymbolType ExportType =
-          Export.Kind == wasm::WASM_EXTERNAL_FUNCTION
-              ? WasmSymbol::SymbolType::FUNCTION_EXPORT
-              : WasmSymbol::SymbolType::GLOBAL_EXPORT;
-      auto Pair = SymbolMap.try_emplace(Export.Name, Symbols.size());
-      if (Pair.second) {
-        Symbols.emplace_back(Export.Name, ExportType, Export.Index);
-        DEBUG(dbgs() << "Adding export: " << Symbols.back()
-                     << " sym index:" << Symbols.size() << "\n");
-      } else {
-        uint32_t SymIndex = Pair.first->second;
-        const WasmSymbol &OldSym = Symbols[SymIndex];
-        WasmSymbol NewSym(Export.Name, ExportType, Export.Index);
-        NewSym.setAltIndex(OldSym.ElementIndex);
-        Symbols[SymIndex] = NewSym;
-
-        DEBUG(dbgs() << "Replacing existing symbol:  " << NewSym
-                     << " sym index:" << SymIndex << "\n");
-      }
-    }
-    if (Export.Kind == wasm::WASM_EXTERNAL_FUNCTION &&
-        isDefinedFunctionIndex(Export.Index)) {
-      auto &Function = getDefinedFunction(Export.Index);
-      if (Function.Name.empty()) {
-        // Use the export's name to set a name for the Function, but only if one
-        // hasn't already been set.
-        Function.Name = Export.Name;
-      }
-    }
-  }
-}
-
 Error WasmObjectFile::parseLinkingSection(const uint8_t *Ptr,
                                           const uint8_t *End) {
   HasLinkingSection = true;
@@ -388,37 +325,15 @@ Error WasmObjectFile::parseLinkingSection(const uint8_t *Ptr,
         "Linking data must come after code section", object_error::parse_failed);
   }
 
-  // Only populate the symbol table with imports and exports if the object
-  // has a linking section (i.e. its a relocatable object file). Otherwise
-  // the global might not represent symbols at all.
-  populateSymbolTable();
-
   while (Ptr < End) {
     uint8_t Type = readVarint7(Ptr);
     uint32_t Size = readVaruint32(Ptr);
     const uint8_t *SubSectionEnd = Ptr + Size;
     switch (Type) {
-    case wasm::WASM_SYMBOL_INFO: {
-      uint32_t Count = readVaruint32(Ptr);
-      while (Count--) {
-        StringRef Symbol = readString(Ptr);
-        uint32_t Flags = readVaruint32(Ptr);
-        auto iter = SymbolMap.find(Symbol);
-        if (iter == SymbolMap.end()) {
-          return make_error<GenericBinaryError>(
-              "Invalid symbol name in linking section: " + Symbol,
-              object_error::parse_failed);
-        }
-        uint32_t SymIndex = iter->second;
-        assert(SymIndex < Symbols.size());
-        Symbols[SymIndex].Flags = Flags;
-        DEBUG(dbgs() << "Set symbol flags index:"
-                     << SymIndex << " name:"
-                     << Symbols[SymIndex].Name << " expected:"
-                     << Symbol << " flags: " << Flags << "\n");
-      }
+    case wasm::WASM_SYMBOL_TABLE:
+      if (Error Err = parseLinkingSectionSymtab(Ptr, SubSectionEnd))
+        return Err;
       break;
-    }
     case wasm::WASM_DATA_SIZE:
       LinkingData.DataSize = readVaruint32(Ptr);
       break;
@@ -440,10 +355,10 @@ Error WasmObjectFile::parseLinkingSection(const uint8_t *Ptr,
       for (uint32_t i = 0; i < Count; i++) {
         wasm::WasmInitFunc Init;
         Init.Priority = readVaruint32(Ptr);
-        Init.FunctionIndex = readVaruint32(Ptr);
-        if (!isValidFunctionIndex(Init.FunctionIndex))
-          return make_error<GenericBinaryError>("Invalid function index: " +
-                                                    Twine(Init.FunctionIndex),
+        Init.Symbol = readVaruint32(Ptr);
+        if (!isValidFunctionSymbolIndex(Init.Symbol))
+          return make_error<GenericBinaryError>("Invalid function symbol: " +
+                                                    Twine(Init.Symbol),
                                                 object_error::parse_failed);
         LinkingData.InitFunctions.emplace_back(Init);
       }
@@ -467,6 +382,110 @@ Error WasmObjectFile::parseLinkingSection(const uint8_t *Ptr,
   return Error::success();
 }
 
+Error WasmObjectFile::parseLinkingSectionSymtab(const uint8_t *&Ptr,
+                                                const uint8_t *End) {
+  uint32_t Count = readVaruint32(Ptr);
+  LinkingData.SymbolTable.reserve(Count);
+  Symbols.reserve(Count);
+  StringSet<> SymbolNames;
+
+  std::vector<wasm::WasmImport *> ImportedGlobals;
+  std::vector<wasm::WasmImport *> ImportedFunctions;
+  ImportedGlobals.reserve(Imports.size());
+  ImportedFunctions.reserve(Imports.size());
+  for (auto &I : Imports) {
+    if (I.Kind == wasm::WASM_EXTERNAL_FUNCTION)
+      ImportedFunctions.emplace_back(&I);
+    else if (I.Kind == wasm::WASM_EXTERNAL_GLOBAL)
+      ImportedGlobals.emplace_back(&I);
+  }
+
+  while (Count--) {
+    wasm::WasmSymbolInfo Info;
+    const wasm::WasmSignature *FunctionType = nullptr;
+    const wasm::WasmGlobalType *GlobalType = nullptr;
+
+    Info.Kind = readUint8(Ptr);
+    Info.Flags = readVaruint32(Ptr);
+    bool IsDefined = (Info.Flags & wasm::WASM_SYMBOL_UNDEFINED) == 0;
+
+    switch (Info.Kind) {
+    case wasm::WASM_SYMBOL_TYPE_FUNCTION:
+      Info.ElementIndex = readVaruint32(Ptr);
+      if (!isValidFunctionIndex(Info.ElementIndex) ||
+          IsDefined != isDefinedFunctionIndex(Info.ElementIndex))
+        return make_error<GenericBinaryError>("invalid function symbol index",
+                                              object_error::parse_failed);
+      if (IsDefined) {
+        Info.Name = readString(Ptr);
+        unsigned FuncIndex = Info.ElementIndex - NumImportedFunctions;
+        FunctionType = &Signatures[FunctionTypes[FuncIndex]];
+        auto &Function = Functions[FuncIndex];
+        if (Function.Name.empty()) {
+          // Use the symbol's name to set a name for the Function, but only if
+          // one hasn't already been set.
+          Function.Name = Info.Name;
+        }
+      } else {
+        wasm::WasmImport &Import = *ImportedFunctions[Info.ElementIndex];
+        FunctionType = &Signatures[Import.SigIndex];
+        Info.Name = Import.Field;
+      }
+      break;
+
+    case wasm::WASM_SYMBOL_TYPE_GLOBAL:
+      Info.ElementIndex = readVaruint32(Ptr);
+      if (!isValidGlobalIndex(Info.ElementIndex) ||
+          IsDefined != isDefinedGlobalIndex(Info.ElementIndex))
+        return make_error<GenericBinaryError>("invalid global symbol index",
+                                              object_error::parse_failed);
+      if (IsDefined) {
+        Info.Name = readString(Ptr);
+        unsigned GlobalIndex = Info.ElementIndex - NumImportedGlobals;
+        GlobalType = &Globals[GlobalIndex].Type;
+      } else {
+        wasm::WasmImport &Import = *ImportedGlobals[Info.ElementIndex];
+        Info.Name = Import.Field;
+        GlobalType = &Import.Global;
+      }
+      break;
+
+    case wasm::WASM_SYMBOL_TYPE_DATA:
+      Info.Name = readString(Ptr);
+      if (IsDefined) {
+        uint32_t Index = readVaruint32(Ptr);
+        if (Index >= DataSegments.size())
+          return make_error<GenericBinaryError>("invalid data symbol index",
+                                                object_error::parse_failed);
+        uint32_t Offset = readVaruint32(Ptr);
+        uint32_t Size = readVaruint32(Ptr);
+        if (Offset + Size > DataSegments[Index].Data.Content.size())
+          return make_error<GenericBinaryError>("invalid data symbol index",
+                                                object_error::parse_failed);
+        Info.DataRef = wasm::WasmDataReference{Index, Offset, Size};
+      }
+      break;
+
+    default:
+      return make_error<GenericBinaryError>("Invalid symbol type",
+                                            object_error::parse_failed);
+    }
+
+    if ((Info.Flags & wasm::WASM_SYMBOL_BINDING_MASK) !=
+            wasm::WASM_SYMBOL_BINDING_LOCAL &&
+        !SymbolNames.insert(Info.Name).second)
+      return make_error<GenericBinaryError>("Duplicate symbol name " +
+                                                Twine(Info.Name),
+                                            object_error::parse_failed);
+    LinkingData.SymbolTable.emplace_back(Info);
+    Symbols.emplace_back(LinkingData.SymbolTable.back(), FunctionType,
+                         GlobalType);
+    DEBUG(dbgs() << "Adding symbol: " << Symbols.back() << "\n");
+  }
+
+  return Error::success();
+}
+
 Error WasmObjectFile::parseLinkingSectionComdat(const uint8_t *&Ptr,
                                                 const uint8_t *End)
 {
@@ -706,6 +725,7 @@ Error WasmObjectFile::parseMemorySection(const uint8_t *Ptr, const uint8_t *End)
 }
 
 Error WasmObjectFile::parseGlobalSection(const uint8_t *Ptr, const uint8_t *End) {
+  GlobalSection = Sections.size();
   uint32_t Count = readVaruint32(Ptr);
   Globals.reserve(Count);
   while (Count--) {
@@ -737,12 +757,11 @@ Error WasmObjectFile::parseExportSection(const uint8_t *Ptr, const uint8_t *End)
         return make_error<GenericBinaryError>("Invalid function export",
                                               object_error::parse_failed);
       break;
-    case wasm::WASM_EXTERNAL_GLOBAL: {
-      if (Ex.Index >= Globals.size() + NumImportedGlobals)
+    case wasm::WASM_EXTERNAL_GLOBAL:
+      if (!isValidGlobalIndex(Ex.Index))
         return make_error<GenericBinaryError>("Invalid global export",
                                               object_error::parse_failed);
       break;
-    }
     case wasm::WASM_EXTERNAL_MEMORY:
     case wasm::WASM_EXTERNAL_TABLE:
       break;
@@ -759,18 +778,35 @@ Error WasmObjectFile::parseExportSection(const uint8_t *Ptr, const uint8_t *End)
 }
 
 bool WasmObjectFile::isValidFunctionIndex(uint32_t Index) const {
-  return Index < FunctionTypes.size() + NumImportedFunctions;
+  return Index < NumImportedFunctions + FunctionTypes.size();
 }
 
 bool WasmObjectFile::isDefinedFunctionIndex(uint32_t Index) const {
   return Index >= NumImportedFunctions && isValidFunctionIndex(Index);
 }
 
-wasm::WasmFunction& WasmObjectFile::getDefinedFunction(uint32_t Index) {
+bool WasmObjectFile::isValidGlobalIndex(uint32_t Index) const {
+  return Index < NumImportedGlobals + Globals.size();
+}
+
+bool WasmObjectFile::isDefinedGlobalIndex(uint32_t Index) const {
+  return Index >= NumImportedGlobals && isValidGlobalIndex(Index);
+}
+
+bool WasmObjectFile::isValidFunctionSymbolIndex(uint32_t Index) const {
+  return Index < Symbols.size() && Symbols[Index].isTypeFunction();
+}
+
+wasm::WasmFunction &WasmObjectFile::getDefinedFunction(uint32_t Index) {
   assert(isDefinedFunctionIndex(Index));
   return Functions[Index - NumImportedFunctions];
 }
 
+wasm::WasmGlobal &WasmObjectFile::getDefinedGlobal(uint32_t Index) {
+  assert(isDefinedGlobalIndex(Index));
+  return Globals[Index - NumImportedGlobals];
+}
+
 Error WasmObjectFile::parseStartSection(const uint8_t *Ptr, const uint8_t *End) {
   StartFunction = readVaruint32(Ptr);
   if (!isValidFunctionIndex(StartFunction))
@@ -888,21 +924,10 @@ uint32_t WasmObjectFile::getSymbolFlags(DataRefImpl Symb) const {
     Result |= SymbolRef::SF_Global;
   if (Sym.isHidden())
     Result |= SymbolRef::SF_Hidden;
-
-  switch (Sym.Type) {
-  case WasmSymbol::SymbolType::FUNCTION_IMPORT:
-    Result |= SymbolRef::SF_Undefined | SymbolRef::SF_Executable;
-    break;
-  case WasmSymbol::SymbolType::FUNCTION_EXPORT:
-    Result |= SymbolRef::SF_Executable;
-    break;
-  case WasmSymbol::SymbolType::GLOBAL_IMPORT:
+  if (!Sym.isDefined())
     Result |= SymbolRef::SF_Undefined;
-    break;
-  case WasmSymbol::SymbolType::GLOBAL_EXPORT:
-    break;
-  }
-
+  if (Sym.isTypeFunction())
+    Result |= SymbolRef::SF_Executable;
   return Result;
 }
 
@@ -927,7 +952,7 @@ const WasmSymbol &WasmObjectFile::getWasmSymbol(const SymbolRef &Symb) const {
 }
 
 Expected<StringRef> WasmObjectFile::getSymbolName(DataRefImpl Symb) const {
-  return getWasmSymbol(Symb).Name;
+  return getWasmSymbol(Symb).Info.Name;
 }
 
 Expected<uint64_t> WasmObjectFile::getSymbolAddress(DataRefImpl Symb) const {
@@ -935,18 +960,17 @@ Expected<uint64_t> WasmObjectFile::getSymbolAddress(DataRefImpl Symb) const {
 }
 
 uint64_t WasmObjectFile::getWasmSymbolValue(const WasmSymbol& Sym) const {
-  switch (Sym.Type) {
-  case WasmSymbol::SymbolType::FUNCTION_IMPORT:
-  case WasmSymbol::SymbolType::GLOBAL_IMPORT:
-  case WasmSymbol::SymbolType::FUNCTION_EXPORT:
-    return Sym.ElementIndex;
-  case WasmSymbol::SymbolType::GLOBAL_EXPORT: {
-    uint32_t GlobalIndex = Sym.ElementIndex - NumImportedGlobals;
-    assert(GlobalIndex < Globals.size());
-    const wasm::WasmGlobal &Global = Globals[GlobalIndex];
-    // WasmSymbols correspond only to I32_CONST globals
-    assert(Global.InitExpr.Opcode == wasm::WASM_OPCODE_I32_CONST);
-    return Global.InitExpr.Value.Int32;
+  switch (Sym.Info.Kind) {
+  case wasm::WASM_SYMBOL_TYPE_FUNCTION:
+  case wasm::WASM_SYMBOL_TYPE_GLOBAL:
+    return Sym.Info.ElementIndex;
+  case wasm::WASM_SYMBOL_TYPE_DATA: {
+    // The value of a data symbol is the segment offset, plus the symbol
+    // offset within the segment.
+    uint32_t SegmentIndex = Sym.Info.DataRef.Segment;
+    const wasm::WasmDataSegment &Segment = DataSegments[SegmentIndex].Data;
+    assert(Segment.Offset.Opcode == wasm::WASM_OPCODE_I32_CONST);
+    return Segment.Offset.Value.Int32 + Sym.Info.DataRef.Offset;
   }
   }
   llvm_unreachable("invalid symbol type");
@@ -970,12 +994,12 @@ Expected<SymbolRef::Type>
 WasmObjectFile::getSymbolType(DataRefImpl Symb) const {
   const WasmSymbol &Sym = getWasmSymbol(Symb);
 
-  switch (Sym.Type) {
-  case WasmSymbol::SymbolType::FUNCTION_IMPORT:
-  case WasmSymbol::SymbolType::FUNCTION_EXPORT:
+  switch (Sym.Info.Kind) {
+  case wasm::WASM_SYMBOL_TYPE_FUNCTION:
     return SymbolRef::ST_Function;
-  case WasmSymbol::SymbolType::GLOBAL_IMPORT:
-  case WasmSymbol::SymbolType::GLOBAL_EXPORT:
+  case wasm::WASM_SYMBOL_TYPE_GLOBAL:
+    return SymbolRef::ST_Other;
+  case wasm::WASM_SYMBOL_TYPE_DATA:
     return SymbolRef::ST_Data;
   }
 
@@ -985,14 +1009,24 @@ WasmObjectFile::getSymbolType(DataRefImpl Symb) const {
 
 Expected<section_iterator>
 WasmObjectFile::getSymbolSection(DataRefImpl Symb) const {
-  DataRefImpl Ref;
   const WasmSymbol& Sym = getWasmSymbol(Symb);
-  if (Sym.Type == WasmSymbol::SymbolType::GLOBAL_EXPORT)
-    Ref.d.a = DataSection;
-  else if (Sym.Type == WasmSymbol::SymbolType::FUNCTION_EXPORT)
-    Ref.d.a = CodeSection;
-  else
+  if (Sym.isUndefined())
     return section_end();
+
+  DataRefImpl Ref;
+  switch (Sym.Info.Kind) {
+  case wasm::WASM_SYMBOL_TYPE_FUNCTION:
+    Ref.d.a = CodeSection;
+    break;
+  case wasm::WASM_SYMBOL_TYPE_GLOBAL:
+    Ref.d.a = GlobalSection;
+    break;
+  case wasm::WASM_SYMBOL_TYPE_DATA:
+    Ref.d.a = DataSection;
+    break;
+  default:
+    llvm_unreachable("Unknown WasmSymbol::SymbolType");
+  }
   return section_iterator(SectionRef(Ref, this));
 }