[WebAssembly] Deduplicate imports of the same module name, field name, and type

[fitzgen]

Summary

When two symbols import the same thing, only one import should be emitted in the Wasm file.

Fixes https://bugs.llvm.org/show_bug.cgi?id=50938

[sbc100]

Nice! I think I'm sold on the idea that this a good think. I'm curious what @dschuff and @sunfish think? Is wasm-ld the right place to be doing this?

lld/test/wasm/duplicate-function-imports.ll

1 ↗

(On Diff #356845)

Why .ll and not .s here?

lld/test/wasm/duplicate-global-imports.s

31

Maybe we should do a global.get on each of these globals so we can see that the de-duplication is working in the relocations.

Sadly obj2yaml doesn't do disassembly so the test will be a little opaque, at least until https://reviews.llvm.org/D105539 lands

lld/test/wasm/duplicate-table-imports.s

41

Lets do a .get on each of the tables?

lld/wasm/SyntheticSections.h

198

Maybe just importedGlobals, importedFunctions and importedTables?

[sbc100]

lld/test/wasm/duplicate-global-imports.s

3

I think we can remove --no-gc-sections (if you use each on in a global.get) and --allow-undefined.

lld/test/wasm/duplicate-table-imports.s

3

Can you remove --allow-undefined ? And maybe you can --export-all rather then exporting each one ?

[fitzgen]

lld/test/wasm/duplicate-function-imports.ll

1 ↗

(On Diff #356845)

I used .ll because it was the first test I wrote and it was derived from the C snippet. I'm happy to change it to .s if you prefer.

lld/test/wasm/duplicate-global-imports.s

31

Regarding this and removing --no-gc-sections: is it generally preferred to create uses of things rather than to pass --no-gc-sections in tests?

Happy to update this either way, just curious.

lld/test/wasm/duplicate-table-imports.s

3

Will do.

41

There is a table.get for each table:

• read_funcref_1 does it for t1
• read_funcref_2 does it for t2
• read_externref does it for t3

lld/wasm/SyntheticSections.h

198

Sure thing, will change to these names.

[fitzgen]

lld/test/wasm/duplicate-table-imports.s

3

I switched to --export-all rather than explicitly enumerating each export, but removing --allow-undefined makes it error out because the t{1,2,3} symbols are undefined, and I don't know how to make a defined, imported table in a .s.

[sbc100]

lld/test/wasm/duplicate-function-imports.ll

1 ↗

(On Diff #356845)

Yes please, I've been trying to covert all the existing .ll tests .s for a while so would rather not any any new .ll if possible.

lld/test/wasm/duplicate-global-imports.s

31

My general philosophy is to try to minimize the number of flags passed in a given test. This tends to make to more obvious what is being tested (less noise) and makes makes it easier to find tests for a given open by simply grepping for it. There could also be an argument that we want to do most of our testing on the default path since that is the most well trodden one... maybe?

Of course its a balance and we don't want to be jumping through too many hoops to avoid extra flags.

[fitzgen]

Updated based on review feedback:

• Removed --allow-undefined and --no-gc-sections from duplicate-global-imports.s
• Added global.gets for each global in duplicate-global-imports.s
• Switched to --export-all instead of explicitly listing each export in duplicate-table-imports.s
• Renamed alreadyImportedStuff to importedStuff

[fitzgen]

Rewrote duplicate-function-imports.ll into duplicate-function-imports.s.

[dschuff]

Given that we're doing things like GC in the linker, and that the linker is already responsible for creating the imports in the first place (and already has several different options affecting that) I think this makes sense for the linker too.

[fitzgen]

Ran clang-format.

[sbc100]

lld/wasm/SyntheticSections.cpp

126

Do these need to be optional? Doesn't getImportModuleAndName unconditionally set them?

[fitzgen]

Make it so getImportModuleAndName does not take optional out parameters.

[sbc100]

lld/wasm/SyntheticSections.cpp

113

The fact that we need template here make me thing maybe we should just move importModule/importName into the symbol base class and we could then just do isUndefined() here... but that is a bigger change.

lld/wasm/SyntheticSections.h

156

What about putting ImportKey and this DenseMapInfo in that anonymous namespace since they should not be needed outside this file? Then we could avoid the prefix in lld::wasm::ImportKey maybe?

[sbc100]

lld/wasm/SyntheticSections.cpp

113

I created https://reviews.llvm.org/D106026.. I don't mind which one lands first.

[fitzgen]

lld/wasm/SyntheticSections.h

156

When I do this, I get the following warning a few times:

/home/nick/llvm-project/lld/wasm/SyntheticSections.h:165:7: warning: ‘lld::wasm::ImportSection’ has a field ‘lld::wasm::ImportSection::importedGlobals’ whose type uses the anonymous namespace [-Wsubobject-linkage]
  165 | class ImportSection : public SyntheticSection {
      |       ^~~~~~~~~~~~~

Do you still prefer this approach?

[fitzgen]

Do you have any idea what is up with https://reviews.llvm.org/harbormaster/unit/view/870129/ ? Locally the test passes just fine, and the types certainly look correct to me. It almost looks like whatever version of llvm-mc running in CI doesn't understand ref types properly? Pretty confused here.

[sbc100]

lld/wasm/SyntheticSections.h

156

Oh sorry, I didn't realize this was in a header. Ignore my previous comment.

[sbc100]

In D105519#2881482, @fitzgen wrote:

Do you have any idea what is up with https://reviews.llvm.org/harbormaster/unit/view/870129/ ? Locally the test passes just fine, and the types certainly look correct to me. It almost looks like whatever version of llvm-mc running in CI doesn't understand ref types properly? Pretty confused here.

@aardappel just added the type checker vary recently (https://reviews.llvm.org/D104945). So maybe you need to update your local branch?

[fitzgen]

In D105519#2883725, @sbc100 wrote:

In D105519#2881482, @fitzgen wrote:

Do you have any idea what is up with https://reviews.llvm.org/harbormaster/unit/view/870129/ ? Locally the test passes just fine, and the types certainly look correct to me. It almost looks like whatever version of llvm-mc running in CI doesn't understand ref types properly? Pretty confused here.

@aardappel just added the type checker vary recently (https://reviews.llvm.org/D104945). So maybe you need to update your local branch?

Ah yes, I think this is it. That patch mentions that .globaltype etc must come *before* the entity now, and I believe that is what is going wrong in this test case. Will update the patch in one sec.

[sbc100]

What do you think about landing https://reviews.llvm.org/D106026 first? (would avoid the use of template <typename UndefinedT> in this patch).

[fitzgen]

In D105519#2883746, @sbc100 wrote:

What do you think about landing https://reviews.llvm.org/D106026 first? (would avoid the use of template <typename UndefinedT> in this patch).

I don't really mind either way.

Obviously it is one tiny rebase less work for me if this lands first, but that's not much work and if that patch is green and ready to land, then I say go for it.

By the way, I am not LLVM committer, so I'll need your help actually landing this patch when the time comes.

[fitzgen]

Fixed failing tests.

[sbc100]

I'm OK landing this first. Just say when you ready. Still lgtm.

[fitzgen]

In D105519#2884167, @sbc100 wrote:

I'm OK landing this first. Just say when you ready. Still lgtm.

Thanks. This *should* be ready, except that there seems to be a few failures in CI: https://reviews.llvm.org/harbormaster/unit/114556/

AFAICT, they are all unrelated. Not sure whether these are known-flaky tests or how to retry them or what. Any ideas?

[sbc100]

In D105519#2887626, @fitzgen wrote:

In D105519#2884167, @sbc100 wrote:

I'm OK landing this first. Just say when you ready. Still lgtm.

Thanks. This *should* be ready, except that there seems to be a few failures in CI: https://reviews.llvm.org/harbormaster/unit/114556/

AFAICT, they are all unrelated. Not sure whether these are known-flaky tests or how to retry them or what. Any ideas?

They look unrelated. Can you try re-basing and re-uploading?

[fitzgen]

Rebased.

[MaskRay]

Reverted by 16aac493e59519377071e900d119ba2e7e5b525d due to an use-of-uninitialized-value bug.

lld/test/wasm/duplicate-table-imports.s

44

Newer tests in other lld ports use ## for non-CHECK-non-RUN comments.

lld/wasm/SyntheticSections.h

99

The coding standard doesn't use /*

[fitzgen]

In D105519#2888967, @MaskRay wrote:

Reverted by 16aac493e59519377071e900d119ba2e7e5b525d due to an use-of-uninitialized-value bug.

Do you have a link to a CI run with sanitizers enabled, or something like that, that shows which value is uninitialized? Thanks!

[MaskRay]

In D105519#2890670, @fitzgen wrote:

In D105519#2888967, @MaskRay wrote:

Reverted by 16aac493e59519377071e900d119ba2e7e5b525d due to an use-of-uninitialized-value bug.

Do you have a link to a CI run with sanitizers enabled, or something like that, that shows which value is uninitialized? Thanks!

https://lab.llvm.org/buildbot/#/builders/74/builds/6017/steps/10/logs/stdio

[fitzgen]

Is there documentation anywhere on how to build wasm-ld with memory sanitizer enabled?

I've tried this:

$ cmake -DLLVM_USE_SANITIZER=MemoryWithOrigins -DLLVM_ENABLE_PROJECTS=lld path/to/llvm
$ make -j8

but then I get memory sanitizer errors while running make like this:

[  5%] Building Attributes.inc...
Uninitialized bytes in __interceptor_memchr at offset 6 inside [0x7020000006c0, 7)
==1094381==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x52842d in llvm::StringRef::find(char, unsigned long) const /home/nick/llvm-project/llvm/include/llvm/ADT/StringRef.h:319:29
    #1 0x11b0ccf in llvm::StringRef::split(llvm::SmallVectorImpl<llvm::StringRef>&, char, int, bool) const /home/nick/llvm-project/llvm/lib/Support/StringRef.cpp:341:20
    #2 0x11da056 in llvm::Triple::Triple(llvm::Twine const&) /home/nick/llvm-project/llvm/lib/Support/Triple.cpp:770:19
    #3 0x12f4e33 in llvm::sys::getProcessTriple[abi:cxx11]() /home/nick/llvm-project/llvm/lib/Support/Host.cpp:1727:10
    #4 0x10b1bd5 in (anonymous namespace)::CommandLineParser::ParseCommandLineOptions(int, char const* const*, llvm::StringRef, llvm::raw_ostream*, bool) /home/nick/llvm-project/llvm/lib/Support/CommandLine.cpp:1345:17
    #5 0x10b1570 in llvm::cl::ParseCommandLineOptions(int, char const* const*, llvm::StringRef, llvm::raw_ostream*, char const*, bool) /home/nick/llvm-project/llvm/lib/Support/CommandLine.cpp:1320:24
    #6 0xff18e5 in main /home/nick/llvm-project/llvm/utils/TableGen/TableGen.cpp:283:3
    #7 0x7f773ee7acb1 in __libc_start_main csu/../csu/libc-start.c:314:16
    #8 0x428a1d in _start (/home/nick/llvm-project/obj/bin/llvm-tblgen+0x428a1d)

  Uninitialized value was stored to memory at
    #0 0x42e7c9 in __msan_memcpy (/home/nick/llvm-project/obj/bin/llvm-tblgen+0x42e7c9)
    #1 0x527135 in void std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_construct<char*>(char*, char*, std::forward_iterator_tag) /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/basic_string.tcc:225:6
    #2 0x11f977f in llvm::Twine::str[abi:cxx11]() const /home/nick/llvm-project/llvm/lib/Support/Twine.cpp:20:12
    #3 0x11d9f3d in llvm::Triple::Triple(llvm::Twine const&) /home/nick/llvm-project/llvm/lib/Support/Triple.cpp:765:16
    #4 0x12f4e33 in llvm::sys::getProcessTriple[abi:cxx11]() /home/nick/llvm-project/llvm/lib/Support/Host.cpp:1727:10
    #5 0x10b1bd5 in (anonymous namespace)::CommandLineParser::ParseCommandLineOptions(int, char const* const*, llvm::StringRef, llvm::raw_ostream*, bool) /home/nick/llvm-project/llvm/lib/Support/CommandLine.cpp:1345:17
    #6 0x10b1570 in llvm::cl::ParseCommandLineOptions(int, char const* const*, llvm::StringRef, llvm::raw_ostream*, char const*, bool) /home/nick/llvm-project/llvm/lib/Support/CommandLine.cpp:1320:24
    #7 0xff18e5 in main /home/nick/llvm-project/llvm/utils/TableGen/TableGen.cpp:283:3
    #8 0x7f773ee7acb1 in __libc_start_main csu/../csu/libc-start.c:314:16

  Uninitialized value was created by a heap allocation
    #0 0x4a30a9 in operator new(unsigned long) (/home/nick/llvm-project/obj/bin/llvm-tblgen+0x4a30a9)
    #1 0x7f773f19c87f in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::reserve(unsigned long) (/lib/x86_64-linux-gnu/libstdc++.so.6+0x14387f)
    #2 0xffffffffffffef9f  (<unknown module>)

SUMMARY: MemorySanitizer: use-of-uninitialized-value /home/nick/llvm-project/llvm/include/llvm/ADT/StringRef.h:319:29 in llvm::StringRef::find(char, unsigned long) const
Exiting
make[2]: *** [include/llvm/IR/CMakeFiles/intrinsics_gen.dir/build.make:136: include/llvm/IR/Attributes.inc] Error 77
make[2]: Leaving directory '/home/nick/llvm-project/obj'
make[1]: *** [CMakeFiles/Makefile2:11564: include/llvm/IR/CMakeFiles/intrinsics_gen.dir/all] Error 2
make[1]: Leaving directory '/home/nick/llvm-project/obj'
make: *** [Makefile:152: all] Error 2

[MaskRay]

In D105519#2895079, @fitzgen wrote:

Is there documentation anywhere on how to build wasm-ld with memory sanitizer enabled?

https://github.com/google/sanitizers/wiki/SanitizerBotReproduceBuild

msan isn't usable without an instrumented C++ standard library.
I personally use simplified https://github.com/MaskRay/Config/wiki/LLVM out/msan

[sbc100]

In D105519#2890670, @fitzgen wrote:

In D105519#2888967, @MaskRay wrote:

Reverted by 16aac493e59519377071e900d119ba2e7e5b525d due to an use-of-uninitialized-value bug.

Do you have a link to a CI run with sanitizers enabled, or something like that, that shows which value is uninitialized? Thanks!

If setting up a local asan build is painful (I've never don't it myself), and you think you know the source of the error you could also just re-land with the fix.

[fitzgen]

I'm pretty sure the issue was that I was comparing/hashing maximums in WasmLimits's operator== and hash traits unconditionally, rather than only if Flags & WASM_LIMITS_FLAG_HAS_MAX.

[fitzgen]

Updated to only hash/compare WasmLimits's Maximum when Flags & WASM_LIMITS_FLAGS_HAS_MAX. This should fix the use of uninitialized data that led to reverting the original commit.

[fitzgen]

@sbc100, would you mind relanding this for me? Thank you!

[sbc100]

lld/wasm/Writer.cpp

568 ↗

(On Diff #360936)

Is this chunk intentional?

[fitzgen]

lld/wasm/Writer.cpp

568 ↗

(On Diff #360936)

Whoops, I think this was a bad rebase. Apologies!

Updated patch incoming.

[fitzgen]

Removed chunk that shouldn't have been in this patch.

[TaoPan]

lld/wasm/SyntheticSections.h

134

Please be note this line introduced below build error:
FAILED: tools/lld/wasm/CMakeFiles/lldWasm.dir/MapFile.cpp.o
/usr/bin/c++ -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -DSTDC_CONSTANT_MACROS -DSTDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/lld/wasm -I/media/sdb/tao/llvm/llvm-project-debug/lld/wasm -I/media/sdb/tao/llvm/llvm-project-debug/lld/include -Itools/lld/include -Iinclude -I/media/sdb/tao/llvm/llvm-project-debug/llvm/include -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wdelete-non-virtual-dtor -Wno-comment -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -fno-exceptions -fno-rtti -std=c++14 -MD -MT tools/lld/wasm/CMakeFiles/lldWasm.dir/MapFile.cpp.o -MF tools/lld/wasm/CMakeFiles/lldWasm.dir/MapFile.cpp.o.d -o tools/lld/wasm/CMakeFiles/lldWasm.dir/MapFile.cpp.o -c /media/sdb/tao/llvm/llvm-project-debug/lld/wasm/MapFile.cpp
In file included from /media/sdb/tao/llvm/llvm-project-debug/lld/wasm/MapFile.cpp:28:0:
/media/sdb/tao/llvm/llvm-project-debug/lld/wasm/SyntheticSections.h:134:36: error: specialization of ‘template<class T> struct llvm::DenseMapInfo’ in different namespace [-fpermissive]
template <typename T> struct llvm::DenseMapInfo<lld::wasm::ImportKey<T>> {

^

In file included from /media/sdb/tao/llvm/llvm-project-debug/lld/wasm/MapFile.h:12:0,

from /media/sdb/tao/llvm/llvm-project-debug/lld/wasm/MapFile.cpp:21:

/media/sdb/tao/llvm/llvm-project-debug/llvm/include/llvm/ADT/ArrayRef.h:29:31: error: from definition of ‘template<class T> struct llvm::DenseMapInfo’ [-fpermissive]

template<typename T> struct DenseMapInfo;

[sbc100]

lld/wasm/SyntheticSections.h

134

What compiler are you using that gives this error? I'm guessing gcc or something that is not clang? (I'm surprised we didn't get any reports of bots failing? Any idea why your config might not be covered by any of the llvn bots?)

@fitzgen can you take a look?

[sbc100]

lld/wasm/SyntheticSections.h

134

Looks like there is already a fix in flight: https://reviews.llvm.org/D107422

[TaoPan]

lld/wasm/SyntheticSections.h

134

Yes, it's gcc dependent error, I used gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.12). My config command is

cmake -G Ninja -DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD=X86 -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra;compiler-rt;lld" ../llvm

Looks not very special. I know this error won't be triggered with "-D CMAKE_C_COMPILER=clang -D CMAKE_CXX_COMPILER=clang++".

[sbc100]

lld/wasm/SyntheticSections.h

134

Do we not have any bots that build with a recent enough gcc version to report this failure? Seems odd.

[TaoPan]

lld/wasm/SyntheticSections.h

134

I checked recent enough gcc version (11.2.0), this error can't be reproduced, it's gcc old version dependent error.

lld/test/wasm/duplicate-function-imports.s

+# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %s -o %t.o
+# RUN: wasm-ld -o %t1.wasm %t.o
+# RUN: obj2yaml %t1.wasm | FileCheck %s
+
+.globl f1
+.import_module f1, env
+.import_name f1, f
+.functype f1 () -> (i32)
+
+# Same import module/name/type as `f1`, should be de-duped.
+.globl f2
+.import_module f2, env
+.import_name f2, f
+.functype f2 () -> (i32)
+
+# Same import module/name, but different type. Should not be de-duped.
+.globl f3
+.import_module f3, env
+.import_name f3, f
+.functype f3 () -> (f32)
+
+.globl _start
+_start:
+  .functype _start () -> ()
+  call f1
+  drop
+  call f2
+  drop
+  call f3
+  drop
+  end_function
+
+
+# CHECK:        - Type:            TYPE
+# CHECK-NEXT:     Signatures:
+# CHECK-NEXT:       - Index:           0
+# CHECK-NEXT:         ParamTypes:      []
+# CHECK-NEXT:         ReturnTypes:
+# CHECK-NEXT:           - I32
+# CHECK-NEXT:       - Index:           1
+# CHECK-NEXT:         ParamTypes:      []
+# CHECK-NEXT:         ReturnTypes:
+# CHECK-NEXT:           - F32
+# CHECK-NEXT:       - Index:           2
+# CHECK-NEXT:         ParamTypes:      []
+# CHECK-NEXT:         ReturnTypes:     []
+# CHECK-NEXT:   - Type:            IMPORT
+# CHECK-NEXT:     Imports:
+# CHECK-NEXT:       - Module:          env
+# CHECK-NEXT:         Field:           f
+# CHECK-NEXT:         Kind:            FUNCTION
+# CHECK-NEXT:         SigIndex:        0
+# CHECK-NEXT:       - Module:          env
+# CHECK-NEXT:         Field:           f
+# CHECK-NEXT:         Kind:            FUNCTION
+# CHECK-NEXT:         SigIndex:        1
+# CHECK-NEXT:   - Type:

lld/test/wasm/duplicate-global-imports.s

+# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %s -o %t.o
+# RUN: wasm-ld --no-check-features -o %t1.wasm %t.o
+# RUN: obj2yaml %t1.wasm | FileCheck %s
+
+.global g1
+.import_module g1, env
+.import_name g1, g
+.globaltype g1, i64, immutable
+
+# Same import module/name/type as `g1`, should be de-duped.
+.global g2
+.import_module g2, env
+.import_name g2, g
+.globaltype g2, i64, immutable
+
+# Imported as an i32 instead of i64, so should not be de-duped.
+.global g3
+.import_module g3, env
+.import_name g3, g
+.globaltype g3, i32, immutable
+
+# Imported as mutable instead of immutable, so should not be de-duped.
+.global g4
+.import_module g4, env
+.import_name g4, g
+.globaltype g4, i64
+
+.globl _start
+_start:
+  .functype _start () -> ()
+  global.get g1
+  drop
+  global.get g2
+  drop
+  global.get g3
+  drop
+  global.get g4
+  drop
+  end_function
+
+
+# CHECK:        - Type:            IMPORT
+# CHECK-NEXT:     Imports:
+# CHECK-NEXT:      - Module:          env
+# CHECK-NEXT:        Field:           g
+# CHECK-NEXT:        Kind:            GLOBAL
+# CHECK-NEXT:        GlobalType:      I64
+# CHECK-NEXT:        GlobalMutable:   false
+# CHECK-NEXT:      - Module:          env
+# CHECK-NEXT:        Field:           g
+# CHECK-NEXT:        Kind:            GLOBAL
+# CHECK-NEXT:        GlobalType:      I32
+# CHECK-NEXT:        GlobalMutable:   false
+# CHECK-NEXT:      - Module:          env
+# CHECK-NEXT:        Field:           g
+# CHECK-NEXT:        Kind:            GLOBAL
+# CHECK-NEXT:        GlobalType:      I64
+# CHECK-NEXT:        GlobalMutable:   true
+# CHECK-NEXT:  - Type:
+
+# CHECK:         GlobalNames:
+# CHECK-NEXT:      - Index:           0
+# CHECK-NEXT:        Name:            g1
+# CHECK-NEXT:      - Index:           1
+# CHECK-NEXT:        Name:            g3
+# CHECK-NEXT:      - Index:           2
+# CHECK-NEXT:        Name:            g4
+# CHECK-NEXT:      - Index:           3
+# CHECK-NEXT:        Name:            __stack_pointer

lld/test/wasm/duplicate-table-imports.s

+# RUN: llvm-mc -mattr=+reference-types -triple=wasm32-unknown-unknown -filetype=obj -o %t.o %s
+# RUN: wasm-ld --no-entry --export-all --allow-undefined -o %t1.wasm %t.o
+# RUN: obj2yaml %t1.wasm | FileCheck %s
+
+.globl t1
+.import_module t1, env
+.import_name t1, t
+.tabletype t1, funcref
+
+# Same import module/name/type as `t1`, should be de-duped.
+.globl t2
+.import_module t2, env
+.import_name t2, t
+.tabletype t2, funcref
+
+# Imported as an externref instead of funcref, so should not be de-duped.
+.globl t3
+.import_module t3, env
+.import_name t3, t
+.tabletype t3, externref
+
+.globl read_funcref_1
+read_funcref_1:
+  .functype read_funcref_1 () -> (funcref)
+  i32.const 0
+  table.get t1
+  end_function
+
+.globl read_funcref_2
+read_funcref_2:
+  .functype read_funcref_2 () -> (funcref)
+  i32.const 0
+  table.get t2
+  end_function
+
+.globl read_externref
+read_externref:
+  .functype read_externref () -> (externref)
+  i32.const 0
+  table.get t3
+  end_function
+
+# XXX: the second imported table has index 1, not 0. I've verified by hand (with
+# `wasm2wat`) that the resulting Wasm file is correct: `t3` does end up at index
+# 1 and our `read_*` functions contain `table.get` instructions using the proper
+# table index immediates. This is also asserted (less legibly) in the hexdump of
+# their code bodies below. It looks like there's a bug in how `obj2yaml`
+# disassembles multiple table imports.
+
+# CHECK:        - Type:            IMPORT
+# CHECK-NEXT:     Imports:
+# CHECK-NEXT:       - Module:          env
+# CHECK-NEXT:         Field:           t
+# CHECK-NEXT:         Kind:            TABLE
+# CHECK-NEXT:         Table:
+# CHECK-NEXT:           Index:           0
+# CHECK-NEXT:           ElemType:        FUNCREF
+# CHECK-NEXT:           Limits:
+# CHECK-NEXT:             Minimum:         0x0
+# CHECK-NEXT:       - Module:          env
+# CHECK-NEXT:         Field:           t
+# CHECK-NEXT:         Kind:            TABLE
+# CHECK-NEXT:         Table:
+# CHECK-NEXT:           Index:           0
+# CHECK-NEXT:           ElemType:        EXTERNREF
+# CHECK-NEXT:           Limits:
+# CHECK-NEXT:             Minimum:         0x0
+# CHECK-NEXT:   - Type:
+
+# CHECK:        - Type:            CODE
+# CHECK-NEXT:     Functions:
+# CHECK-NEXT:       - Index:           0
+# CHECK-NEXT:         Locals:          []
+# CHECK-NEXT:         Body:            0B
+# CHECK-NEXT:       - Index:           1
+# CHECK-NEXT:         Locals:          []
+# CHECK-NEXT:         Body:            41002580808080000B
+# CHECK-NEXT:       - Index:           2
+# CHECK-NEXT:         Locals:          []
+# CHECK-NEXT:         Body:            41002580808080000B
+# CHECK-NEXT:       - Index:           3
+# CHECK-NEXT:         Locals:          []
+# CHECK-NEXT:         Body:            41002581808080000B
+# CHECK-NEXT:   - Type:            CUSTOM
+# CHECK-NEXT:     Name:            name
+# CHECK-NEXT:     FunctionNames:
+# CHECK-NEXT:       - Index:           0
+# CHECK-NEXT:         Name:            __wasm_call_ctors
+# CHECK-NEXT:       - Index:           1
+# CHECK-NEXT:         Name:            read_funcref_1
+# CHECK-NEXT:       - Index:           2
+# CHECK-NEXT:         Name:            read_funcref_2
+# CHECK-NEXT:       - Index:           3
+# CHECK-NEXT:         Name:            read_externref

lld/wasm/SyntheticSections.h

public:
   uint32_t registerType(const WasmSignature &sig);
   uint32_t lookupType(const WasmSignature &sig);
 
 protected:
   std::vector<const WasmSignature *> types;
   llvm::DenseMap<WasmSignature, int32_t> typeIndices;
 };
 
+/**
+ * A key for some kind of imported entity of type `T`.
+ *
+ * Used when de-duplicating imports.
+ */
+template <typename T> struct ImportKey {
+public:
+  enum class State { Plain, Empty, Tombstone };
+
+public:
+  T type;
+  llvm::Optional<StringRef> importModule;
+  llvm::Optional<StringRef> importName;
+  State state;
+
+public:
+  ImportKey(T type) : type(type), state(State::Plain) {}
+  ImportKey(T type, State state) : type(type), state(state) {}
+  ImportKey(T type, llvm::Optional<StringRef> importModule,
+            llvm::Optional<StringRef> importName)
+      : type(type), importModule(importModule), importName(importName),
+        state(State::Plain) {}
+};
+
+template <typename T>
+inline bool operator==(const ImportKey<T> &lhs, const ImportKey<T> &rhs) {
+  return lhs.state == rhs.state && lhs.importModule == rhs.importModule &&
+         lhs.importName == rhs.importName && lhs.type == rhs.type;
+}
+
+} // namespace wasm
+} // namespace lld
+
+// `ImportKey<T>` can be used as a key in a `DenseMap` if `T` can be used as a
+// key in a `DenseMap`.
+template <typename T> struct llvm::DenseMapInfo<lld::wasm::ImportKey<T>> {
+  static lld::wasm::ImportKey<T> getEmptyKey() {
+    typename lld::wasm::ImportKey<T> key(llvm::DenseMapInfo<T>::getEmptyKey());
+    key.state = lld::wasm::ImportKey<T>::State::Empty;
+    return key;
+  }
+  static lld::wasm::ImportKey<T> getTombstoneKey() {
+    typename lld::wasm::ImportKey<T> key(llvm::DenseMapInfo<T>::getEmptyKey());
+    key.state = lld::wasm::ImportKey<T>::State::Tombstone;
+    return key;
+  }
+  static unsigned getHashValue(const lld::wasm::ImportKey<T> &key) {
+    uintptr_t hash = hash_value(key.importModule);
+    hash = hash_combine(hash, key.importName);
+    hash = hash_combine(hash, llvm::DenseMapInfo<T>::getHashValue(key.type));
+    hash = hash_combine(hash, key.state);
+    return hash;
+  }
+  static bool isEqual(const lld::wasm::ImportKey<T> &lhs,
+                      const lld::wasm::ImportKey<T> &rhs) {
+    return lhs == rhs;
+  }
+};
+
+namespace lld {
+namespace wasm {
+
 class ImportSection : public SyntheticSection {
 public:
   ImportSection() : SyntheticSection(llvm::wasm::WASM_SEC_IMPORT) {}
   bool isNeeded() const override { return getNumImports() > 0; }
   void writeBody() override;
   void addImport(Symbol *sym);
   void addGOTEntry(Symbol *sym);
   void seal() { isSealed = true; }
public:
   std::vector<const Symbol *> gotSymbols;
 
 protected:
   bool isSealed = false;
   unsigned numImportedGlobals = 0;
   unsigned numImportedFunctions = 0;
   unsigned numImportedTags = 0;
   unsigned numImportedTables = 0;
+  llvm::DenseMap<ImportKey<WasmGlobalType>, uint32_t> importedGlobals;
+  llvm::DenseMap<ImportKey<WasmSignature>, uint32_t> importedFunctions;
+  llvm::DenseMap<ImportKey<WasmTableType>, uint32_t> importedTables;
 };
 
 class FunctionSection : public SyntheticSection {
 public:
   FunctionSection() : SyntheticSection(llvm::wasm::WASM_SEC_FUNCTION) {}
 
   bool isNeeded() const override { return inputFunctions.size() > 0; };
   void writeBody() override;

lld/wasm/SyntheticSections.cpp

void ImportSection::addGOTEntry(Symbol *sym) {
   assert(!isSealed);
   if (sym->hasGOTIndex())
     return;
   LLVM_DEBUG(dbgs() << "addGOTEntry: " << toString(*sym) << "\n");
   sym->setGOTIndex(numImportedGlobals++);
   gotSymbols.push_back(sym);
 }
 
+template <typename UndefinedT>
+static void getImportModuleAndName(Symbol *sym,
+                                   llvm::Optional<StringRef> *outModule,
+                                   llvm::Optional<StringRef> *outName) {
+  if (auto *undef = dyn_cast<UndefinedT>(sym)) {
+    *outModule = undef->importModule ? *undef->importModule : defaultModule;
+    *outName = undef->importName ? *undef->importName : sym->getName();
+  } else {
+    *outModule = defaultModule;
+    *outName = sym->getName();
+  }
+}
+
 void ImportSection::addImport(Symbol *sym) {
   assert(!isSealed);
+  llvm::Optional<StringRef> module;
+  llvm::Optional<StringRef> name;
+  if (auto *f = dyn_cast<FunctionSymbol>(sym)) {
+    getImportModuleAndName<UndefinedFunction>(sym, &module, &name);
+    ImportKey<WasmSignature> key(*(f->getSignature()), module, name);
+    auto entry =
+        importedFunctions.try_emplace(key, numImportedFunctions);
+    if (entry.second) {
       importedSymbols.emplace_back(sym);
-  if (auto *f = dyn_cast<FunctionSymbol>(sym))
       f->setFunctionIndex(numImportedFunctions++);
-  else if (auto *g = dyn_cast<GlobalSymbol>(sym))
+    } else {
+      f->setFunctionIndex(entry.first->second);
+    }
+  } else if (auto *g = dyn_cast<GlobalSymbol>(sym)) {
+    getImportModuleAndName<UndefinedGlobal>(sym, &module, &name);
+    ImportKey<WasmGlobalType> key(*(g->getGlobalType()), module, name);
+    auto entry = importedGlobals.try_emplace(key, numImportedGlobals);
+    if (entry.second) {
+      importedSymbols.emplace_back(sym);
       g->setGlobalIndex(numImportedGlobals++);
-  else if (auto *t = dyn_cast<TagSymbol>(sym))
+    } else {
+      g->setGlobalIndex(entry.first->second);
+    }
+  } else if (auto *t = dyn_cast<TagSymbol>(sym)) {
+    // NB: There's currently only one possible kind of tag, and no
+    // `UndefinedTag`, so we don't bother de-duplicating tag imports.
+    importedSymbols.emplace_back(sym);
     t->setTagIndex(numImportedTags++);
-  else
-    cast<TableSymbol>(sym)->setTableNumber(numImportedTables++);
+  } else {
+    auto *table = cast<TableSymbol>(sym);
+    getImportModuleAndName<UndefinedTable>(sym, &module, &name);
+    ImportKey<WasmTableType> key(*(table->getTableType()), module, name);
+    auto entry = importedTables.try_emplace(key, numImportedTables);
+    if (entry.second) {
+      importedSymbols.emplace_back(sym);
+      table->setTableNumber(numImportedTables++);
+    } else {
+      table->setTableNumber(entry.first->second);
+    }
+  }
 }
 
 void ImportSection::writeBody() {
   raw_ostream &os = bodyOutputStream;
 
   writeUleb128(os, getNumImports(), "import count");
 
   if (config->importMemory) {

llvm/include/llvm/BinaryFormat/Wasm.h

 };
 
 struct WasmLimits {
   uint8_t Flags;
   uint64_t Minimum;
   uint64_t Maximum;
 };
 
+inline bool operator==(const WasmLimits &LHS, const WasmLimits &RHS) {
+  return LHS.Flags == RHS.Flags && LHS.Minimum == RHS.Minimum &&
+         LHS.Maximum == RHS.Maximum;
+}
+
 struct WasmTableType {
   uint8_t ElemType;
   WasmLimits Limits;
 };
 
+inline bool operator==(const WasmTableType &LHS, const WasmTableType &RHS) {
+  return LHS.ElemType == RHS.ElemType && LHS.Limits == RHS.Limits;
+}
+
 struct WasmTable {
   uint32_t Index;
   WasmTableType Type;
   StringRef SymbolName; // from the "linking" section
 };
 
 struct WasmInitExpr {
   uint8_t Opcode;

llvm/include/llvm/BinaryFormat/WasmTraits.h

static unsigned getHashValue(const wasm::WasmGlobalType &GlobalType) {
     return hash_combine(GlobalType.Type, GlobalType.Mutable);
   }
   static bool isEqual(const wasm::WasmGlobalType &LHS,
                       const wasm::WasmGlobalType &RHS) {
     return LHS == RHS;
   }
 };
 
+// Traits for using WasmLimits in a DenseMap
+template <> struct DenseMapInfo<wasm::WasmLimits> {
+  static wasm::WasmLimits getEmptyKey() {
+    return wasm::WasmLimits{0xff, 0xff, 0xff};
+  }
+  static wasm::WasmLimits getTombstoneKey() {
+    return wasm::WasmLimits{0xee, 0xee, 0xee};
+  }
+  static unsigned getHashValue(const wasm::WasmLimits &Limits) {
+    unsigned Hash = hash_value(Limits.Flags);
+    Hash = hash_combine(Hash, Limits.Minimum);
+    Hash = hash_combine(Hash, Limits.Maximum);
+    return Hash;
+  }
+  static bool isEqual(const wasm::WasmLimits &LHS,
+                      const wasm::WasmLimits &RHS) {
+    return LHS == RHS;
+  }
+};
+
+// Traits for using WasmTableType in a DenseMap
+template <> struct DenseMapInfo<wasm::WasmTableType> {
+  static wasm::WasmTableType getEmptyKey() {
+    return wasm::WasmTableType{0,
+                               DenseMapInfo<wasm::WasmLimits>::getEmptyKey()};
+  }
+  static wasm::WasmTableType getTombstoneKey() {
+    return wasm::WasmTableType{
+        1, DenseMapInfo<wasm::WasmLimits>::getTombstoneKey()};
+  }
+  static unsigned getHashValue(const wasm::WasmTableType &TableType) {
+    return hash_combine(
+        TableType.ElemType,
+        DenseMapInfo<wasm::WasmLimits>::getHashValue(TableType.Limits));
+  }
+  static bool isEqual(const wasm::WasmTableType &LHS,
+                      const wasm::WasmTableType &RHS) {
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_BINARYFORMAT_WASMTRAITS_H