1316804 - Wasm baseline: De-pessimize brTable

Status: RESOLVED INACTIVE

(Core :: JavaScript: WebAssembly, enhancement, P5)

Description

[Lars T Hansen [:lth]]

brTable pessimizes by always dispatching to code that pops the stack and then jumps to the code for the target case.  If no cleanup is needed we could just branch conditionally to the target; if the same amount of cleanup is needed for all cases then the cleanup can be done before the dispatch.  Both are highly likely.

Comment 1

[Daniel Näslund [:dannas]]

I'll take a stab at this one.

Comment 2

[Daniel Näslund [:dannas]]

Attachment: bug1316804_WIP_depessimize_brtable.patch

Attaching a WIP just so I can claim this issue. It contains a naive attempt at detecting when the value stack needs to be pushed and some inline questions.

Here's a series of statements. Are they correct? There's a few questions sprinkled in as well. 

My problem: The labels representing the block targets of the br_table aren't bound until each endBlock() function is called. Thus, I can't just "connect" them as-is.

* jumpTable() uses a mechanism similar to this x64 snippet for emitting the asm jumptable:

        jmp     [QWORD PTR .startOfJumpTable[0+rdi*8]]
.startOfJumpTable:
        .quad   .block0
        .quad   .block1
        .quad   .block2
        .quad   .block3

* CodeLabel is an abstraction for dealing with memory indirect addressing ( more specifically the .quad .blockX lines above).

* A jump instruction can can have an operand that points to a Label that hasn't yet been bound (for x64 that is handled by AssemblerX86Shared::jSrc).

* A CodeLabel can't in its current form point to a Label that hasn't been bound.

* A CodeLabel uses absolute addresses. Those can't be resolved until the "linking phase". Done in ModuleGenerator::finishLinkData. But the fact that the addresses are absolute is probably ortogonal to this issue. Until the linking phase, the CodeLabels stores the addresses as relative addresses.

Suggestions for solutions:
1. From jumpTable(), we need to add the code pointer to have it in the right position in the emitted code, but we could delay binding. See the patch for a comment placed next to the code. We would somehow keep track of which CodeLabels are affected and bind them to the right block labels in endBlock().

...or...

2. We could add a writeJumpEntry() method for the MacroAssemblers/Assemblers that does something similar to how jumps are handled.

Comment 3

[Lars T Hansen [:lth]]

(In reply to Daniel Näslund [:dannas] from comment #2)
> Created attachment 8899286 [details] [diff] [review]
> bug1316804_WIP_depessimize_brtable.patch
> 
> My problem: The labels representing the block targets of the br_table aren't
> bound until each endBlock() function is called. Thus, I can't just "connect"
> them as-is.
> 
> * jumpTable() uses a mechanism similar to this x64 snippet for emitting the
> asm jumptable:

Pretty much.  tableSwitch loads the absolute address of the table generated in jumpTable, then loads a pointer from that table, then jumps to that address.  The jump in tableSwitch is indirect so the second load is hidden.  The jump table is a list of absolute code addresses.

> * CodeLabel is an abstraction for dealing with memory indirect addressing (
> more specifically the .quad .blockX lines above).

With absolute addresses in code, I would say.  The machinery is used to emit code pointers into the table, and to capture the absolute (code) address of the table itself.

> * A jump instruction can can have an operand that points to a Label that
> hasn't yet been bound (for x64 that is handled by AssemblerX86Shared::jSrc).

Right, for all forward jumps the label will be unbound.

> * A CodeLabel can't in its current form point to a Label that hasn't been
> bound.

I believe that's true.

> * A CodeLabel uses absolute addresses. Those can't be resolved until the
> "linking phase".

Right.

> Done in ModuleGenerator::finishLinkData. But the fact that
> the addresses are absolute is probably ortogonal to this issue. Until the
> linking phase, the CodeLabels stores the addresses as relative addresses.

Yes, looks that way to me too.

> Suggestions for solutions:
> 1. From jumpTable(), we need to add the code pointer to have it in the right
> position in the emitted code, but we could delay binding. See the patch for
> a comment placed next to the code. We would somehow keep track of which
> CodeLabels are affected and bind them to the right block labels in
> endBlock().
> 
> ...or...
> 
> 2. We could add a writeJumpEntry() method for the MacroAssemblers/Assemblers
> that does something similar to how jumps are handled.

...or...

3.  Emit the jump table and probably the table switch (since it needs the address of the table) after the last block that is referenced from the table switch.  All labels are known at that point, though I'm not yet sure how we'd collect the necessary information.  After all it doesn't matter where the code is, the branch in emitBrTable() will branch to the tableswitch code regardless of where it is.

Which of these three is simplest I don't know.  They all require some extra storage but that can come out of the TempAllocator probably (and we already allocate the stub label vector there now).

I'm wondering, before you start implementing all of this, can you implement the analysis so that we know it is affordable and so that we can determine (by running it on actual code) how often the optimization applies?

Comment 4

[Lars T Hansen [:lth]]

We'll get to this if it becomes necessary.