Allow wasm-ld to handle JS symbols and their reverse dependencies (no more deps_info.py).

[sbc100]

The reverse dependencies from JS symbols back to native symbols have caused a lot of problems over the years and it would be great to handle a better way. The current system of using deps_info.py has several problems/downsides:

1. Need to run all inputs through llvm-nm (there have been correctness and performance issues with this code over time).
2. Does not work with user JS libraries (not extensible).
3. Is hard to maintain (especially in face of symbols used by libc.. where the dependency on the JS symbol is not from user code, but from system library code).

@juj has PR (#15982) that tries to extent support to user libraries. It does this by processing the libraries twice, once before and one after linking.

As it happens, the existing LLD_REPORT_UNDEFINED also process the libraries an extra time before calling the linker. It does this to produce a list of all possible JS symbols which it can then pass to wasm-ld as valid undefined symbols. LLD_REPORT_UNDEFINED is designed to allow wasm-ld to do all symbol resolution and report undefined symbols, as opposed to delaying this until later in JS (where the error message less useful/actionable because they don't refer to individual object files).

While reviewing #15982 I came up with an idea to extend LLD_REPORT_UNDEFINED to include support for reverse dependences. The idea is to give wasm-ld enough information that is aware of all symbols and their dependencies (including all JS symbols).

Today, if you use LLD_REPORT_UNDEFINED we generate a simple list of symbols from the JS library files and pass that to the linker with --allow-undefined-file=all.syms. For example given the follow JS library file:

mergeInto(LibraryManager.library, {                                                                                                
  foo: function(x) {  return 42 },         
  bar: function(x) {  return 43 }.                                                                                  
});    

We would generate all.syms containing:

foo
bar

So the linker can know that foo and bar are external, and any other missing symbols should result in an error.

My idea would to exten this format to include dependencies. e.g.:

mergeInto(LibraryManager.library, {         
  foo__deps: ['native_func', 'other_native_func']                                                                                       
  foo: function(x) {  return 42 },         
  bar: function(x) {  return 43 }.                                                                                  
});    

Would generate:

foo: native_func, other_native_func
bar

Then the linker would know that if foo is undefined in the program (and therefore imported) it would be required to also export native_func and other_native_func.

Adding this extra would not incur additional performance overhead on top of that already uncured by LLD_REPORT_UNDEFINED, but it would require:

1. Extension to the --allow-undefined-file file format in wasm-ld. Since this would more likely be emscripten-specific that could be contravertial.
2. Making LLD_REPORT_UNDEFINED the default, and accepting the performance code of processing libraries twice.

What we stand to gain:

1. No more deps_info.py!
2. No more running llvm-nm on input files!
3. No more issues with indirect dependencies via system libraries.
4. Better error messages from the linker.

[tlively]

I think this is a great idea! It seems similar to having some sort of "virtual object file" for JS code that participates in symbol resolution and gc but doesn't actually link in any code.

I get why the libraries would need to be processed before linking to get a list of their symbols and dependencies, but why would they need to be processed again after linking?

[sbc100]

The second time we run the compiler it would be to actually generate the final JS from the subset of JS functions that are actually needed.. perhaps there is some way we could share state between the first and second run.

Also, we have some features that simple won't work pre-link. For example:

#if hasExportedFunction('foo')
#endif

This requires the linker to already have run. I admit the presence of such a feature is tricky, even if we do run the compiler twice because it means we will get different results.

[dschuff]

The "virtual object file" idea exists in ELF (it's called a stub object) and I think there may also be some kind of equivalent in MachO too?). We almost got around to using something like that for PNaCl to solve similar problems with bitcode/native dependencies and the 2-phase linking that PNaCl had.
I'm not actually familiar with the undefined-file format, but I guess it if it's just a list of symbols to treat as undefined, it's more or less a text-based subset of a stub object. I don't know if lld has any notion of an object with a linking interface but no code or data, but if so I guess it might not be too hard in principle to have wasm stub object. That would of course be more work (i.e. generating a full wasm file with a symbol table, compared to just dumping symbol names into a text file like we do now) but it would be more flexible and have all the capabilities of a real object file; not clear whether that would be worthwhile.

[sbc100]

I thought about doing this an object file. For example, one option would be to take each library_foo.js file convert into a .a archive containing single .cpp source containing an EM_JS function. However the major downside of this approach is that it would mean doing codegen + clang + ar under the hood during linking. This is because the JS library contents very much depends on command line settings and so need to re-generated on each link command .. they cannot be shared across link commands easily.

If it wasn't for this major issue I would agree that creating object files would be better, but that we want to generate them on-demand from python I think a simple text format is preferable.

[sbc100]

I the idea of some kind of stub object did cross my mind, but again I think we want to avoid running the compiler or linker to generate these things if we can.

BTW your link to "stub object" documentation seem like it might be some kind of solaris only. I can't find anything in GNU gcc or ld documentation about such a thing.

[dschuff]

Yeah, it could be. Solaris uses ELF and is mostly the same as GNU, but not exactly the same in all the details.
As for running the compiler to generate it, I was actually imagining generating them on-demand, in a way that would be largely equivalent to how you're talking about generating an extended undefined-file on demand. That's what I meant by the "extra work" to generate the binary format. I hadn't thought about using the compiler, actually. I guess you could shorten codegen + clang + ar to just codegen + as by generating assembly instead of C (you wouldn't really need ar if you are just generating objects on demand, would you?). But it does still seem slower than just generating a text file consumed by the linker.