Optimize register preservation finalization

[Robbepop]

In the new wasmi register-machine translation we have to preserve values of local.get x registers if they are on the stack while an incoming local.set x or local.tee x overwrites the value of local x. In order to preserve the value of the local x we have to perform a register preservation which allocates a register at the highest index in descending order.

When translation of wasmi IR is finalized we then have to offset all those preservation register indices by the difference between the maximum non-preserved register index and the minimum preserved register index. Conservatively this operation needs to iterate over all generated wasmi IR instructions and for each check all their registers and potentially offset them if they are a preservation register. This might inspect tons of wasmi IR instructions that are not having any preservation registers.

This is very costly!

Current Solution and Proposal

In order to offset the costs a bit we currently check at which instruction index we first see a register preservation if any and only start from there which can reduce the amount of iteration by a bit. However, a much better improvement was to only ever touch those instruction that actually need to be adjusted.

This information can probably be inferred because we know whenever the stack pops off such a preserved register during translation. We could notify the register preservation finalization routine that this event occurred to track down the instructions that actually are required to be adjusted.

Difficulties

• The main difficulty with this optimization is to be sure that no instruction that needs adjustment is missed out this way. Inspecting instructions that are not required to be adjusted is never a problem disregarding performance.

• An additional complexity is that some instructions (e.g. call instructions) span multiple wasmi instruction words and therefore none of those instruction words belonging to a parent instruction that needs to be adjusted must be missed out.

• Iteration over all instruction to adjust their registers if needed:

  • https://github.com/paritytech/wasmi/blob/80e1d212a26da8950f11fa6c0812bcc70661c3ee/crates/wasmi/src/engine/regmach/translator/instr_encoder.rs#L762

• Where we know that we just popped a preserved register from the stack:

  • https://github.com/paritytech/wasmi/blob/80e1d212a26da8950f11fa6c0812bcc70661c3ee/crates/wasmi/src/engine/regmach/translator/stack/register_alloc.rs#L345