Can we do more table element stripping in RemoveUnusedModuleElements?

[sbc100]

In RemoveUnusedModuleElements we clear the entire table if there is no usage of the table in the module:

https://github.com/WebAssembly/binaryen/blob/master/src/passes/RemoveUnusedModuleElements.cpp#L226

However, perhaps we could be more course grain:

1. Find all the signatures used by all call_indirect instructions.
2. Remove any table elements that don't match one of those signatures.

I guess this might make the table kind of sparse? Would it be observable? Using one of these slots would generate an "invalid signature" and now it would become "empty table slot". I guess we could add per-signature trapping functions. These would never be reached and would preserve the "invalid signature" trap.

[kripken]

Good idea! I think this could be done if the table is neither imported nor exported (otherwise we don't see all the relevant calls into the table). That's the case in standalone mode at least in emscripten, and probably other places.

I think it's fine if we replace one trap by another, the binaryen optimizer already allows that.

[kripken]

After discussion in #8883, some thoughts on what more we can improve here: we could find all the functions in the table that have no possible call_indirects, and replace their element segment appearances with nulls. A null also traps, so that is equivalent enough.

We could then let other passes remove those nulls where possible (I'm not sure if we have such a pass - MemoryPacking does it for data segments, but maybe not element segments? If it doesn't handle element segments, generalizing it might make sense.)

[JPL11]

I checked what nulling entries does to the binary encoding. The writer uses the compact MVP form (one LEB function index per entry) only when every entry in the segment is a ref.func; a single null switches the whole segment to the expressions form, which costs 2 extra bytes for every surviving ref.func entry (opcode + index + end) and 3 bytes per null. So on an MVP style table with mostly live entries, nulling alone can make the binary larger; the second part (actually dropping the nulls) is what makes it pay off.

On the second part: MemoryPacking does not touch element segments today. I think the useful subset for tables is smaller than what it does for data segments: trim nulls from segment edges (bumping the offset constant for leading nulls), and split a segment around an interior null run only when the run is longer than the overhead of a new segment (flags + offset expr + count, roughly 6 to 8 bytes). Same preconditions as before: table neither imported nor exported, constant offsets, and the element type has to admit nulls.

If that sounds right, I would implement the two parts together (nulling in RemoveUnusedModuleElements plus the trimming/splitting) so no intermediate state regresses size, and gate the nulling on the segment either already using the expressions encoding or the packing being able to recover the cost. Happy to put the packing in a separate small pass or generalize MemoryPacking, whichever you prefer.

[kripken]

Ah, good point about nulls in tables being larger. In that case, we shouldn't replace them all with nulls, but we can replace them all with a single function with the simplest possible signature, whose body is an unreachable. That is, in this case we can merge functions more aggressively than MergeFunctions normally does.

I'm not sure where is best to do element segment packing, good question

[kripken]

Closing this, as the main thing has been implemented - we track call_indirect types to tables, and remove what we can.

The last thing that could be improved is merging trapping functions of different types, and/or replacing them with nulls, as mentioned above. But data in #8887 suggests this is not helpful in practice, and turns out to not be simple to do.

Separately, we could optimize element segments like we do data segments, but again, the benefit might be small.

[JPL11]

For the record, the measurements that led here, so they are findable from this issue: across six real binaries from three toolchains (Emscripten, wasi-sdk, Rust via Javy), zero table entries were removable. Emscripten output keeps the indirect function table imported or exported, so the preconditions never hold there, and WASI output has private tables but zero uncallable entries, since wasm-ld only emits address taken functions into the table and every such function's signature has a call_indirect somewhere. The one constructible win was 5 bytes in 658 KB, on a hand modified sql.js that no toolchain actually produces. Details and numbers in #8887.