Move function local constants between function locals and temporaries

[Robbepop]

When translating a Wasm function, moving function local constant stack slot indices between the stack slot indices of the function's locals and its temporaries allows to optimize function calls in Wasmi.

Currently, since stack slot indices might be negative and since function local constants appear before a function's parameters and locals on the stack during execution, we cannot really use the parameters of the caller in the callee and instead have to copy them over to an entirely new function frame. If a function's parameters appeared first we could overlap both function frames and avoid this potentially costly copying during execution.

Currently, Wasmi puts those function local constants before the function's parameters and locals because this is the simplest way to achieve good performance during translation. As soon as a function local constant is allocated, we simply prepend it to the stack slots. We cannot know exactly how many function local constants there exist in a function prior to parsing and translating it properly, which is why we prepend them. Ideally, we'd put them in between a functions locals and temporaries - however then, we'd need to adjust a lot of instruction parameters upon translation finalization which is extremely costly. What we could do to solve this, is to run a heuristic before function translation which conservatively estimates how many function local constants there will be. Obviously, this heuristic needs to run very quickly and must not overestimate the amount of such constants too much. However, this could potentially fix the performance issues.

The heuristic must respect the following Wasm instructions and potentially even more:

• 0x23: global.get (with an immutable global)
• 0x41: i32.const
• 0x42: i64.const
• 0x43: f32.const
• 0x44: f64.const
• 0x41: i32.const
• 0xD0: ref.null (realized as i64.const in Wasmi)
• [0xFD, 0x0C]: v128.const

The heuristic can be improved by filtering out mutable globals in 0x23 or 0x41 and 0x42 values in the i32.const and i64.const cases respectively or by deduplicating constants immediately.

An exmaple of a bad case:

f64.const: 0x44 0x41 0x41 0x41 0x41 0x41 0x41 0x41 0x41 where 0x44 indicated f64.const and 0x41 are its bytes. A simple heuristic would think that there is 1 f64.const and 9 i32.const values while there is only a single f64.const.

[Robbepop]

I conducted initial work today and experimented with spidermonkey.wasm:

Stats

• (func 0):
  • Number of instructions: 14760
  • Stack slots reserved for function local constants: 1476
  • Stack slots reserved for parameters and locals: 57
  • Stack slots (total): 1533

Take-Aways

• Less than 4% of the total number of stack slots are reserved for Wasm's original parameters and locals.
• More than 96% are reserved for Wasmi's function locacl constants since Wasmi usually encodes constants only if they fit into 16-bit.
• Roughly 95% (=1415) of those function local constants could be removed if Wasmi inlined constants with 32-bits instead of 16-bits.

It might be a viable choice to not have function local constants at all, just like Stitch; OR have way fewer of them by restricting where they are applicable.