llvm dev - Jul 2017 - [LLD] Adding WebAssembly support to lld

Hi llvmers,

As you may know, work has been progressing on the experimental
WebAssembly backend in llvm.  However,  there is currently not a good
linking story.  Most the of existing linking strategies (i.e. those in
the emscripten toolchain) involve bitcode linking and whole program
compilation at link time.

To improve this situation I've been working on adding a wasm backend
for lld.   My current work is here: https://reviews.llvm.org/D34851

Although this port is not ready for production use (its missing
several key features such as comdat support and full support for weak
aliases) its already getting a some testing on the wasm waterfall:
https://wasm-stat.us/builders/linux

I'm hopeful that my patch may now be at an MVP stage that could be
considered for merging into upstream lld.  Thoughts?  LLD maintainers,
would you support the addition of a new backend?

cheers,
sam

Can you link to docs about the wasm object format? (both relocatable and
executable)

Also, traditional object file linkers are primarily concerned with
concatenating binary blobs with small amount of patching of said binary
blobs based on computed virtual (memory) addresses. Or perhaps to put it
another way, what traditional object file linkers do is construct program
images meant to be mapped directly into memory.

My understanding is that wasm is pretty different from this (though "linker
frontend" things like the symbol resolution process is presumably similar).
Looking at Writer::run in your patch it seems like wasm is indeed very
different. E.g. the linker is aware of things like "types" and knowing
internal structure of functions (e.g. write_sig knows about how many
parameters a function has)

Can you elaborate on semantically what the linker is actually doing for
wasm?

-- Sean Silva

On Fri, Jun 30, 2017 at 4:46 PM, Sam Clegg via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi llvmers,
>
> As you may know, work has been progressing on the experimental
> WebAssembly backend in llvm.  However,  there is currently not a good
> linking story.  Most the of existing linking strategies (i.e. those in
> the emscripten toolchain) involve bitcode linking and whole program
> compilation at link time.
>
> To improve this situation I've been working on adding a wasm backend
> for lld.   My current work is here: https://reviews.llvm.org/D34851
>
> Although this port is not ready for production use (its missing
> several key features such as comdat support and full support for weak
> aliases) its already getting a some testing on the wasm waterfall:
> https://wasm-stat.us/builders/linux
>
> I'm hopeful that my patch may now be at an MVP stage that could be
> considered for merging into upstream lld.  Thoughts?  LLD maintainers,
> would you support the addition of a new backend?
>
> cheers,
> sam
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/331b03a0/attachment.html>

Hi Sam,

First, I want to know the symbol resolution semantics. I can imagine that
that is set in stone yet, but just that you guys are still discussing what
would be the best semantics or file format for the linkable wasm object
file. I think by knowing more about the format and semantics, we can give
you guys valuable feedback, as we've been actively working on the linker
for a few years now. (And we know a lot of issues in existing object file
format, so I don't want you guys to copy these failures.)

As Sean pointed out, this looks very different from ELF or COFF in object
construction. Does this mean the linker has to reconstruct everything? The
ELF and COFF linkers are multi-threaded, as each thread can work on
different sections simultaneously when writing to an output file. I wonder
if it's still doable in wasm.

Also, I wonder if there's a way to parallelize symbol resolution. Since
there's no linkable wasm programs, we can take a radical approach.

Have you ever considered making the file format more efficiently than ELF
or COFF so that they are linked really fast? For example, in order to avoid
a lot of (possibly very long due to name mangling) symbols, you could store
SHA hashes or something so that linkers are able to handle symbols as an
array of fixed-size elements.

That is just an example. There are a lot of possible improvements we can
make for a completely new file format.

On Fri, Jun 30, 2017 at 5:19 PM, Sean Silva via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Can you link to docs about the wasm object format? (both relocatable and
> executable)
>
> Also, traditional object file linkers are primarily concerned with
> concatenating binary blobs with small amount of patching of said binary
> blobs based on computed virtual (memory) addresses. Or perhaps to put it
> another way, what traditional object file linkers do is construct program
> images meant to be mapped directly into memory.
>
> My understanding is that wasm is pretty different from this (though
> "linker frontend" things like the symbol resolution process is
presumably
> similar). Looking at Writer::run in your patch it seems like wasm is indeed
> very different. E.g. the linker is aware of things like "types"
and knowing
> internal structure of functions (e.g. write_sig knows about how many
> parameters a function has)
>
> Can you elaborate on semantically what the linker is actually doing for
> wasm?
>
> -- Sean Silva
>
> On Fri, Jun 30, 2017 at 4:46 PM, Sam Clegg via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi llvmers,
>>
>> As you may know, work has been progressing on the experimental
>> WebAssembly backend in llvm.  However,  there is currently not a good
>> linking story.  Most the of existing linking strategies (i.e. those in
>> the emscripten toolchain) involve bitcode linking and whole program
>> compilation at link time.
>>
>> To improve this situation I've been working on adding a wasm
backend
>> for lld.   My current work is here: https://reviews.llvm.org/D34851
>>
>> Although this port is not ready for production use (its missing
>> several key features such as comdat support and full support for weak
>> aliases) its already getting a some testing on the wasm waterfall:
>> https://wasm-stat.us/builders/linux
>>
>> I'm hopeful that my patch may now be at an MVP stage that could be
>> considered for merging into upstream lld.  Thoughts?  LLD maintainers,
>> would you support the addition of a new backend?
>>
>> cheers,
>> sam
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/1c0d6f50/attachment.html>

On Fri, Jun 30, 2017 at 5:19 PM, Sean Silva <chisophugis at gmail.com>
wrote:
> Can you link to docs about the wasm object format? (both relocatable and
> executable)
>
The executable format is described here:
https://github.com/WebAssembly/design/blob/master/BinaryEncoding.md

The relocatable format that the 'wasm32-unknown-unknown-wam' llvm
target currently emits (and this lld port currently accepts) is still
a work in progress and is (probably somewhat incompletely) described
here:
https://github.com/WebAssembly/tool-conventions/blob/master/Linking.md
> Also, traditional object file linkers are primarily concerned with
> concatenating binary blobs with small amount of patching of said binary
> blobs based on computed virtual (memory) addresses. Or perhaps to put it
> another way, what traditional object file linkers do is construct program
> images meant to be mapped directly into memory.
>
> My understanding is that wasm is pretty different from this (though
"linker
> frontend" things like the symbol resolution process is presumably
similar).
> Looking at Writer::run in your patch it seems like wasm is indeed very
> different. E.g. the linker is aware of things like "types" and
knowing
> internal structure of functions (e.g. write_sig knows about how many
> parameters a function has)
>
> Can you elaborate on semantically what the linker is actually doing for
> wasm?
You are correct that the wasm linker does have more work to do than a
traditional linker.  There are more sections that the linker will need
to re-construct fully.  This is because there is more high level
information required in the wasm format.  For example, as you point
out, the type of each function.   Functions also live in their own
index space outside of the program's memory space.  This means that
the simple approach of traditional linkers where almost everything can
be boiled down to virtual addresses don't make as much sense here.
This is part of the reason why early attempts to use ELF as the
encapsulation format were abandoned:  wasm is different enough that is
didn't make sense.

Having said that, we've tried to ensure that the code and data
sections can be blindly concatenated (modulo relocations), and that
should allow for the some of the multi-threaded optimizations in lld
to be leveraged.
>
> -- Sean Silva
>
> On Fri, Jun 30, 2017 at 4:46 PM, Sam Clegg via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> Hi llvmers,
>>
>> As you may know, work has been progressing on the experimental
>> WebAssembly backend in llvm.  However,  there is currently not a good
>> linking story.  Most the of existing linking strategies (i.e. those in
>> the emscripten toolchain) involve bitcode linking and whole program
>> compilation at link time.
>>
>> To improve this situation I've been working on adding a wasm
backend
>> for lld.   My current work is here: https://reviews.llvm.org/D34851
>>
>> Although this port is not ready for production use (its missing
>> several key features such as comdat support and full support for weak
>> aliases) its already getting a some testing on the wasm waterfall:
>> https://wasm-stat.us/builders/linux
>>
>> I'm hopeful that my patch may now be at an MVP stage that could be
>> considered for merging into upstream lld.  Thoughts?  LLD maintainers,
>> would you support the addition of a new backend?
>>
>> cheers,
>> sam
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>