[WebAssembly] Fix local references to weak aliases

[sbc100]

Summary

When weak aliases are used with in same translation
unit we need to be able to directly reference to alias
and not just the thing it is aliases. We do this by
defining both a wasm import and a wasm export in this
case that result in a single Symbol. This change is
a partial revert of rL314245. A corresponding lld
change address the previous issues we had with this.

See: https://github.com/WebAssembly/tool-conventions/issues/34

LLD change: https://reviews.llvm.org/D41473

[sbc100]

• update test

[ncw]

Ouch, hacky hacky!

I can see why you're tempted to do a quick fix to "get it working", so that it's not broken over Christmas. I don't mind this - as the Wasm-LLD maintainer you can commit what you want. On the other hand, no-one's using it in production yet and if it's broken until we get round to the "proper" fix in January maybe that's OK.

To me, taking half a step back like this feels like a more scary change than pressing on and fixing the index used by relocations. Plus, this doesn't fix table relocations, it's only a half fix, so it doesn't even put the code back into a "working" state.

My first step for fixing the table relocations would be to revert this and carry on from where we were before. If that's your intention too, I guess I don't need to review the change, if the plan is for it to be reverted soon.

Thanks for the prompt response on this issue anyway! I was expecting it sit and wait over Christmas, not to cause a panic before we leave on holiday.

[sbc100]

https://reviews.llvm.org/D41473

In D41472#961910, @ncw wrote:

Ouch, hacky hacky!

I can see why you're tempted to do a quick fix to "get it working", so that it's not broken over Christmas. I don't mind this - as the Wasm-LLD maintainer you can commit what you want. On the other hand, no-one's using it in production yet and if it's broken until we get round to the "proper" fix in January maybe that's OK.

To me, taking half a step back like this feels like a more scary change than pressing on and fixing the index used by relocations. Plus, this doesn't fix table relocations, it's only a half fix, so it doesn't even put the code back into a "working" state.

My first step for fixing the table relocations would be to revert this and carry on from where we were before. If that's your intention too, I guess I don't need to review the change, if the plan is for it to be reverted soon.

Thanks for the prompt response on this issue anyway! I was expecting it sit and wait over Christmas, not to cause a panic before we leave on holiday.

I agree that we are pushing the limits here of modeling the symbol table via imports and exports, so it can seem a little hacky. In the long run I agree that we may need to model the symbol table more explicitly, but I think that is a large scale change, that will take some planning. This kind of incremental fix isn't meant to block the way for more sweeping one. I actually think that modeling a weak alias as both an import and an export is quite a neat tick :) The import can then be resolved by its own export, in the absence of any strong symbol. In a sense the object both exports a version of this symbol and also depends on an external version.

Hopefully this fix will also help with the table relocations issue you found since it gives the alias and the non-alias different function indexes.

I'm sorry I landed this unilaterally. I very much appreciate the work you've been doing on wasm+lld.

[ncw]

In D41472#962451, @sbc100 wrote:

I agree that we are pushing the limits here of modeling the symbol table via imports and exports, so it can seem a little hacky. In the long run I agree that we may need to model the symbol table more explicitly, but I think that is a large scale change, that will take some planning. This kind of incremental fix isn't meant to block the way for more sweeping one. I actually think that modeling a weak alias as both an import and an export is quite a neat tick :) The import can then be resolved by its own export, in the absence of any strong symbol. In a sense the object both exports a version of this symbol and also depends on an external version.

I'm not so sure about "neat". Here's how it is in my head: in the frontend (LLVM IR) the fundamental unit of linkage is the "symbol", pretty-much identical to the C concept. In the LLD linker, the "symbol" is also the fundamental unit for all function/global relocations. When the frontend wants one function to call another, that's always communicated to the linker via the "symbol" abstraction, which handles weak/strong and all sort of other link-time redirections.

So we really want to be sure that the LLD symbols map one-to-one to the frontend symbols. The "clean" way to do that is to have the frontend IR symbols map one-to-one to "something" in the object file, and then back out again into LLD. Then we have a fairly clean mental model that we can reason about - MCSymbols are encoded into the object file, then reassembled one-to-one into lld::wasm::Symbols in LLD.

That's why I liked not having symbols duplicated in the imports/exports. I get worried when I see logic one place for duplicating things, and then de-duplicating elsewhere, because it needs to be kept in-sync, and it's harder to understand what's going on.

On the other hand, it works well mentally to take those MCSymbols, split them into two non-overlapping sets, the imports/exports, and then reassemble them back again in LLD. I do hope that we can move back to that model, for the sake of simplicity.

Hopefully this fix will also help with the table relocations issue you found since it gives the alias and the non-alias different function indexes.

Hmm, you're right, I believe that the fix works. But it's harder to see, since it doesn't fall out the modelling exactly.

We have two different concepts to model:

• Weak/strong. A "weak" symbol could be resolved by the linker to point to another translation unit. A strong symbol will always refer in LLD to the function body that the frontend knew about, or cause a linker error otherwise. If I understand correctly, the idea of putting some symbols in both imports and exports is to model the properties of weak symbols? The idea that the symbol is provided by this translation unit, but also could be brought in from another file. Only weak symbols will have the imports/exports duplication.
• Aliases. In the case of strong aliases (I'm guessing here...) the Wasm file will still have two exports for the same symbol, but no import(?) We certainly have to emit the two exports, since the file is genuinely providing two different symbols for other files to call. And it's not a weak alias, so it won't generate an additional import in your code(?)

Strong/weak wasn't really a problem before, that side of things actually worked. It was only aliases where the model didn't match the implementation.

The change to go back to duplicating imports/exports doesn't really fix the aliases problem, it just changes the weak/strong implementation (which wasn't the "root cause" of the issue). And by some clever coding you've altered the weak-symbol implementation to now handle weak-aliases. Cunning! But it's a case of the "tail wagging the dog" when a problem with aliases causes the weak-symbol modelling to be changed to accommodate it.

In the case of strong aliases, we still have a mental mismatch between the modelling and the implementation. We still have two symbols, and the single function entry in the "Wasm index space of functions". It's only by luck that we get away with it. Having said that, I can't think of a bug that would result. But it's awkward, and it's bound to break something eventually.

---

Whew! Long comment, sorry. I don't mean to argue, I just like to give my reasons if I'm suggesting a particular idea!

I think we're agreed. The change you've made here is OK and should work, but a follow-up fix would be nice. I could have a go at that in January, but feel free if you want to look at it sooner.

include/llvm/Object/Wasm.h

enum class SymbolType {
     FUNCTION_IMPORT,
     FUNCTION_EXPORT,
     GLOBAL_IMPORT,
     GLOBAL_EXPORT,
     DEBUG_FUNCTION_NAME,
   };
 
   WasmSymbol(StringRef Name, SymbolType Type, uint32_t Section,
-             uint32_t ElementIndex, uint32_t ImportIndex = 0)
+             uint32_t ElementIndex, uint32_t FunctionType = 0)
       : Name(Name), Type(Type), Section(Section), ElementIndex(ElementIndex),
-        ImportIndex(ImportIndex) {}
+        FunctionType(FunctionType) {}
 
   StringRef Name;
   SymbolType Type;
   uint32_t Section;
   uint32_t Flags = 0;
 
   // Index into either the function or global index space.
   uint32_t ElementIndex;
 
-  // For imports, the index into the import table
-  uint32_t ImportIndex;
+  // For function, the type index
+  uint32_t FunctionType;
+
+  // Symbols can be both exported and imported (in the case of the weakly
+  // defined symbol).  In this the import index is stored as AltIndex.
+  uint32_t AltIndex = 0;
+  bool HasAltIndex = false;
+
+  void setAltIndex(uint32_t Index) {
+    HasAltIndex = true;
+    AltIndex = Index;
+  }
 
   bool isFunction() const {
     return Type == WasmSymbol::SymbolType::FUNCTION_IMPORT ||
            Type == WasmSymbol::SymbolType::FUNCTION_EXPORT ||
            Type == WasmSymbol::SymbolType::DEBUG_FUNCTION_NAME;
   }
 
 
public:
   }
 
   unsigned getVisibility() const {
     return Flags & wasm::WASM_SYMBOL_VISIBILITY_MASK;
   }
 
   void print(raw_ostream &Out) const {
     Out << "Name=" << Name << ", Type=" << static_cast<int>(Type)
-        << ", Flags=" << Flags << " ElemIndex=" << ElementIndex
-        << ", ImportIndex=" << ImportIndex;
+        << ", Flags=" << Flags << " ElemIndex=" << ElementIndex;
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
 
 struct WasmSection {

lib/MC/WasmObjectWriter.cpp

for (const MCSymbol &S : Asm.symbols()) {
     // because wasm always needs a type signature.
     if (WS.isFunction())
       registerFunctionType(WS);
 
     if (WS.isTemporary())
       continue;
 
     // If the symbol is not defined in this translation unit, import it.
-    if (!WS.isDefined(/*SetUsed=*/false)) {
+    if (!WS.isDefined(/*SetUsed=*/false) || WS.isVariable()) {
       WasmImport Import;
       Import.ModuleName = WS.getModuleName();
       Import.FieldName = WS.getName();
 
       if (WS.isFunction()) {
         Import.Kind = wasm::WASM_EXTERNAL_FUNCTION;
         Import.Type = getFunctionType(WS);
         SymbolIndices[&WS] = NumFuncImports;
for (const MCSymbol &S : Asm.symbols()) {
     // Find the target symbol of this weak alias and export that index
     const auto &WS = static_cast<const MCSymbolWasm &>(S);
     const MCSymbolWasm *ResolvedSym = ResolveSymbol(WS);
     DEBUG(dbgs() << WS.getName() << ": weak alias of '" << *ResolvedSym << "'\n");
     assert(SymbolIndices.count(ResolvedSym) > 0);
     uint32_t Index = SymbolIndices.find(ResolvedSym)->second;
     DEBUG(dbgs() << "  -> index:" << Index << "\n");
 
-    SymbolIndices[&WS] = Index;
+    //SymbolIndices[&WS] = Index;
     WasmExport Export;
     Export.FieldName = WS.getName();
     Export.Index = Index;
     if (WS.isFunction())
       Export.Kind = wasm::WASM_EXTERNAL_FUNCTION;
     else
       Export.Kind = wasm::WASM_EXTERNAL_GLOBAL;
     DEBUG(dbgs() << "  -> export " << Exports.size() << "\n");

lib/Object/WasmObjectFile.cpp

Error WasmObjectFile::parseNameSection(const uint8_t *Ptr, const uint8_t *End) {
   if (Ptr != End)
     return make_error<GenericBinaryError>("Name section ended prematurely",
                                           object_error::parse_failed);
   return Error::success();
 }
 
 void WasmObjectFile::populateSymbolTable() {
   // Add imports to symbol table
-  size_t ImportIndex = 0;
   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,
-                           ImportSection, GlobalIndex++, ImportIndex);
+                           ImportSection, 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,
-                           ImportSection, FunctionIndex++, ImportIndex);
+                           ImportSection, FunctionIndex++, Import.SigIndex);
       DEBUG(dbgs() << "Adding import: " << Symbols.back()
                    << " sym index:" << Symbols.size() << "\n");
       break;
     default:
       break;
     }
-    ImportIndex++;
   }
 
   // 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;
-      SymbolMap.try_emplace(Export.Name, Symbols.size());
+      auto Pair = SymbolMap.try_emplace(Export.Name, Symbols.size());
+      if (Pair.second) {
         Symbols.emplace_back(Export.Name, ExportType,
                              ExportSection, 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, ExportSection, Export.Index);
+        NewSym.setAltIndex(OldSym.ElementIndex);
+        Symbols[SymIndex] = NewSym;
+
+        DEBUG(dbgs() << "Replacing existing symbol:  " << NewSym
+                     << " sym index:" << SymIndex << "\n");
+      }
     }
   }
 }
 
 Error WasmObjectFile::parseLinkingSection(const uint8_t *Ptr,
                                           const uint8_t *End) {
   HasLinkingSection = true;
 

test/MC/WebAssembly/weak-alias.ll

 ; CHECK-NEXT:           Initial:         0x00000001
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           __indirect_function_table
 ; CHECK-NEXT:         Kind:            TABLE
 ; CHECK-NEXT:         Table:
 ; CHECK-NEXT:           ElemType:        ANYFUNC
 ; CHECK-NEXT:           Limits:
 ; CHECK-NEXT:             Initial:         0x00000000
+; CHECK-NEXT:       - Module:          env
+; CHECK-NEXT:         Field:           foo_alias
+; CHECK-NEXT:         Kind:            FUNCTION
+; CHECK-NEXT:         SigIndex:        0
+; CHECK-NEXT:       - Module:          env
+; CHECK-NEXT:         Field:           bar_alias
+; CHECK-NEXT:         Kind:            GLOBAL
+; CHECK-NEXT:         GlobalType:      I32
+; CHECK-NEXT:         GlobalMutable:   false
 ; CHECK-NEXT:   - Type:            FUNCTION
 ; CHECK-NEXT:     FunctionTypes:   [ 0, 0 ]
 ; CHECK-NEXT:   - Type:            GLOBAL
 ; CHECK-NEXT:     Globals:         
 ; CHECK-NEXT:       - Type:            I32
 ; CHECK-NEXT:         Mutable:         false
 ; CHECK-NEXT:         InitExpr:        
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           0
 ; CHECK-NEXT:       - Type:            I32
 ; CHECK-NEXT:         Mutable:         false
 ; CHECK-NEXT:         InitExpr:        
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           8
 ; CHECK-NEXT:   - Type:            EXPORT
 ; CHECK-NEXT:     Exports:         
 ; CHECK-NEXT:       - Name:            call_alias
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         Index:           0
+; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            foo
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         Index:           1
+; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:       - Name:            bar
 ; CHECK-NEXT:         Kind:            GLOBAL
-; CHECK-NEXT:         Index:           0
+; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            bar_alias_address
 ; CHECK-NEXT:         Kind:            GLOBAL
-; CHECK-NEXT:         Index:           1
+; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:       - Name:            foo_alias
 ; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         Index:           1
+; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:       - Name:            bar_alias
 ; CHECK-NEXT:         Kind:            GLOBAL
+; CHECK-NEXT:         Index:           1
+; CHECK-NEXT:   - Type:            CODE
+; CHECK-NEXT:     Relocations:     
+; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
 ; CHECK-NEXT:         Index:           0
-
-; CHECK:        - Type:            DATA
+; CHECK-NEXT:         Offset:          0x00000004
+; CHECK-NEXT:     Functions:       
+; CHECK-NEXT:       - Locals:          
+; CHECK-NEXT:         Body:            1080808080000B
+; CHECK-NEXT:       - Locals:          
+; CHECK-NEXT:         Body:            41000B
+; CHECK-NEXT:   - Type:            DATA
 ; CHECK-NEXT:     Relocations:     
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_MEMORY_ADDR_I32
 ; CHECK-NEXT:         Index:           0
 ; CHECK-NEXT:         Offset:          0x0000000F
 ; CHECK-NEXT:     Segments:        
 ; CHECK-NEXT:       - SectionOffset:   6
 ; CHECK-NEXT:         MemoryIndex:     0
 ; CHECK-NEXT:         Offset:          
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           0
 ; CHECK-NEXT:         Content:         '07000000'
 ; CHECK-NEXT:       - SectionOffset:   15
 ; CHECK-NEXT:         MemoryIndex:     0
 ; CHECK-NEXT:         Offset:          
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           8
 ; CHECK-NEXT:         Content:         '00000000'
 
 ; CHECK:        - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name
 ; CHECK-NEXT:     FunctionNames:   
 ; CHECK-NEXT:       - Index:           0
-; CHECK-NEXT:         Name:            call_alias
+; CHECK-NEXT:         Name:            foo_alias
 ; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Name:            call_alias
+; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Name:            foo
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            linking
 ; CHECK-NEXT:     DataSize:        12
 ; CHECK-NEXT:     SymbolInfo:      
-; CHECK-NEXT:       - Name:            call_alias
-; CHECK-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
-; CHECK-NEXT:       - Name:            foo
-; CHECK-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
 ; CHECK-NEXT:       - Name:            foo_alias
 ; CHECK-NEXT:         Flags:           [ BINDING_WEAK, VISIBILITY_HIDDEN ]
 ; CHECK-NEXT:       - Name:            bar_alias
 ; CHECK-NEXT:         Flags:           [ BINDING_WEAK, VISIBILITY_HIDDEN ]
+; CHECK-NEXT:       - Name:            call_alias
+; CHECK-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
+; CHECK-NEXT:       - Name:            foo
+; CHECK-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
 ; CHECK-NEXT:     SegmentInfo:    
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            .data.bar
 ; CHECK-NEXT:         Alignment:       8
 ; CHECK-NEXT:         Flags:           [ ]
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Name:            .data.bar_alias_address
 ; CHECK-NEXT:         Alignment:       8
 ; CHECK-NEXT:         Flags:           [ ]
 ; CHECK-NEXT: ...
 
 ; CHECK-SYMS: SYMBOL TABLE:
-; CHECK-SYMS-NEXT: 00000000 g     F name  call_alias
-; CHECK-SYMS-NEXT: 00000001 g     F name  foo
-; CHECK-SYMS-NEXT: 00000000 g     F EXPORT  .hidden call_alias
-; CHECK-SYMS-NEXT: 00000001 g     F EXPORT  .hidden foo
+; CHECK-SYMS-NEXT: 00000000 g     F name  foo_alias
+; CHECK-SYMS-NEXT: 00000001 g     F name  call_alias
+; CHECK-SYMS-NEXT: 00000002 g     F name  foo
+; CHECK-SYMS-NEXT: 00000002 gw    F EXPORT  .hidden foo_alias
+; CHECK-SYMS-NEXT: 00000000 gw      EXPORT  .hidden bar_alias
+; CHECK-SYMS-NEXT: 00000001 g     F EXPORT  .hidden call_alias
+; CHECK-SYMS-NEXT: 00000002 g     F EXPORT  .hidden foo
 ; CHECK-SYMS-NEXT: 00000000 g       EXPORT  bar
 ; CHECK-SYMS-NEXT: 00000008 g       EXPORT  bar_alias_address
-; CHECK-SYMS-NEXT: 00000001 gw    F EXPORT  .hidden foo_alias
-; CHECK-SYMS-NEXT: 00000000 gw      EXPORT  .hidden bar_alias