[lld][WebAssembly] Linker relaxation: rewrite `global.get GOT.mem.value` to `i32.const <value>`

[SingleAccretion]

As part of our compiler, we hand-emit a small number of helper methods in pure WASM, of a kind like below:

void helper_11(arg1, arg2) {
    extern int compiler_generated_data_symbol_11;
    return SomeMethod(&compiler_generated_data_symbol_11, arg1, arg2);
}

Historically this was done without the need to consider -fPIC, but recently we've started thinking about supporting that too. However, we would also like to emit code that is "PIC-agnostic" (this is how the compiler works for other targets).

In a non-PIC build, the example from above will emit something like:

 000042: 41 80 80 80 80 00          | i32.const 0
           000043: R_WASM_MEMORY_ADDR_SLEB 1 <compiler_generated_data_symbol_11>

And that's also what we emit currently (more or less).

For "PIC-agnostic" code, we could emit the same using GOT, like so:

 000053: 23 80 80 80 80 00          | global.get 0 <GOT.mem.compiler_generated_data_symbol_11>
           000054: R_WASM_GLOBAL_INDEX_LEB 1 <compiler_generated_data_symbol_11>

To keep (roughly) the same code size and runtime performance. However, we will then have a bunch of immutable GOT.* globals that don't really serve much purpose in a non-PIE link.

But this seems avoidable if all the references to these GOT globals could be rewritten in-place to i32.consts with the actual value.

[llvmbot]

@llvm/issue-subscribers-lld-wasm

Author: None (SingleAccretion)

As part of our compiler, we hand-emit a small number of helper methods in pure WASM, of a kind like below: ```c void helper_11(arg1, arg2) { extern int compiler_generated_data_symbol_11; return SomeMethod(&compiler_generated_data_symbol_11, arg1, arg2); } ``` Historically this was done without the need to consider `-fPIC`, but recently we've started thinking about supporting that too. However, we would also like to emit code that is "PIC-agnostic" (this is how the compiler works for other targets).

In a non-PIC build, the example from above will emit something like:

 000042: 41 80 80 80 80 00          | i32.const 0
           000043: R_WASM_MEMORY_ADDR_SLEB 1 <compiler_generated_data_symbol_11>

And that's also what we emit currently (more or less).

For "PIC-agnostic" code, we could emit the same using GOT, like so:

 000053: 23 80 80 80 80 00          | global.get 0 <GOT.mem.compiler_generated_data_symbol_11>
           000054: R_WASM_GLOBAL_INDEX_LEB 1 <compiler_generated_data_symbol_11>

To keep (roughly) the same code size and runtime performance. However, we will then have a bunch of immutable GOT.* globals that don't really serve much purpose in a non-PIE link.

But this seems avoidable if all the references to these GOT globals could be rewritten in-place to i32.consts with the actual value.

[sbc100]

We don't currently have any linker relaxations in the wasm linker. While it is likely feasible it might be fairly big change since it would represent the first of its it kind. I guess it would likely require a new relocation type too?

I'm not very familiar with the detail of how relaxation would normally work. Is the idea that the linker see that the R_WASM_GLOBAL_INDEX_LEB was receeded by the global.get instruction and then rewrite it as i32.const + a R_WASM_MEMORY_ADDR_SLEB relocation? Would would we add an new relocation type that is only used for global.get + R_WASM_GLOBAL_INDEX_LEB?

[sbc100]

Also, given that running wasm-opt on the resulting binary will optimize away all the resulting constant wasm globals, I'm not really sure its work investing in having lld do this.

[SingleAccretion]

Is the idea that the linker see that the R_WASM_GLOBAL_INDEX_LEB was receeded by the global.get instruction and then rewrite it as i32.const + a R_WASM_MEMORY_ADDR_SLEB relocation? Would would we add an new relocation type that is only used for global.get + R_WASM_GLOBAL_INDEX_LEB?

I don't see why we need a new relocation type. My idea was simply this:

1. When doing final relocation of R_WASM_GLOBAL_INDEX_LEB for a GOT global.get (and assuming the actual value is known at compile time, i. e. this the case of linking -fPIC objects into non--pie/-shared code), instead of rewriting it to the GOT global's index, rewrite the whole instruction to i32.const <actual symbol value>.
2. When emitting GOT globals skip those that didn't end up being used (it'll need some bookkeeping similar to GC liveness bits I suppose, but maybe that already exists).

The actual implementation may be more complicated due to e. g. --compress-relocations, but I wouldn't expect it to be that much more tricky.

Also, given that running wasm-opt on the resulting binary will optimize away all the resulting constant wasm globals, I'm not really sure its work investing in having lld do this.

Not all scenarios can (or want) to use wasm-opt. E. g. we don't use it by default because it can alter function indices. All WASMp2-targeting code doesn't use it (and can't, currently at least). So that's the main motivation (along with the fact that if we were say to use wasm-opt for this small optimization only, it would be at least an order of magnitude slower than if done in the linker [in terms of this optimization's isolated cost]).

[sbc100]

1. When doing final relocation of R_WASM_GLOBAL_INDEX_LEB for a GOT global.get (and assuming the actual value is known at compile time, i. e. this the case of linking -fPIC objects into non--pie/-shared code), instead of rewriting it to the GOT global's index, rewrite the whole instruction to i32.const <actual symbol value>.

I'm just not sure how easy that is to express in the lld code.

I guess the implementation would look something like:

1. Look at the location one byte before the relocation
2. If that byte is the encoding of the global.get then overwrite it with the encoding of i32.const and apply the relaxed relocation type.
3. If there is no preceeding byte, or it doesn't match the encoding of global.get then apply the original relocation.

Up until now we don't do any instruction decoding as part of applying relocation, so this would be a bit of a departure. Do you know if this is essentially how linker relaxation works on other platforms? (i.e. does it do instruction decoding apply relaxation only in some cases?)

I guess we would need to know if we are in a code section at all to avoid false positive detection of the i32.const instruction that is actually just data (i.e. in a custom section).

[SingleAccretion]

I'm just not sure how easy that is to express in the lld code. ...I guess the implementation would look something like:

Right. I'll look into this issue at some point, and if it turns out too clunky/complex, well, I'll just close this issue.

(i.e. does it do instruction decoding apply relaxation only in some cases?)

I am not an expert on these things, but TLS relaxations in ELF at least are notoriously fickle and need an exact NOP (byte/fill) pattern to be applied. Maybe that's not "decoding" per se though.

I guess we would need to know if we are in a code section at all to avoid false positive detection of the i32.const instruction that is actually just data (i.e. in a custom section).

There is an even more "interesting" possibility that may render this idea actually infeasible... Consider:

v128.const <....>
   global.get byte <-- put into the constant by some trickster
   5 bytes         <-- R_WASM_GLOBAL_INDEX_LEB <GOT global>, e. g. via .reloc

Taking this kind of object file format abuse into account actually does require full instruction decoding.

[SingleAccretion]

Taking this kind of object file format abuse into account actually does require full instruction decoding.

This, though, makes the idea not worth it. So closing.

[dschuff]

@SingleAccretion I don't want to hijack this thread but your comment above made me curious about why wasm-opt can't be used in your use case, and I filed WebAssembly/binaryen#7712. Would you mind taking a look? Thanks!