Re: Understanding SNAP
- From: Peter Cawley <corsix@xxxxxxxxxx>
- To: luajit@xxxxxxxxxxxxx
- Date: Sat, 30 Sep 2017 23:33:57 +0100
On Wed, Sep 27, 2017 at 12:41 PM, Raj <rajlistuser@xxxxxxxxx> wrote:
I did not quite understand what is meant by: "all slots inherited from
the parent are live in a register between pass 2 and pass 3"
Consider the case where a particular value is in say the register
"rax" in the parent trace (at the point of the snapshot), and the side
trace wants that value to be in say the register "rcx". This is an
easy case to handle: LuaJIT just needs to emit "mov rcx, rax" (though
there is slightly more complexity: it also has to ensure that nobody
needed the old value of "rcx" before doing so). Now consider a
different case: a particular value is in memory location "[rsp +
0x40]" in the parent trace, whereas the side trace wants it to be in
"[rsp + 0x24]". This is rather more awkward, for a few reasons:
* "rsp" need not have the same value in the parent and child traces.
* There is no CPU instruction to move a value from one memory
address to another, so the value has to go via a register, i.e. load
from [rsp + 0x40] to temp, then store from tmp to [rsp + 0x24].
(Pedants will point out instructions like push and pop and movs, which
can each reference two memory locations in a single instruction, but
they are not easily applicable.)
* There are potentially more stack locations to keep track of than
there are registers to keep track of (~256 versus ~32 on x64).
* What was an adjacent pair of independent 4-byte spill slots in the
parent trace might become a single 8-byte spill slot in the side trace
(or vice versa).
Rather than try to tackle this complexity, the current algorithm
always turns a stack-to-stack move into a stack-to-register move plus
a register-to-stack move, and it performs all stack-to-register moves
before performing any register-to-stack moves. If you consider the
machine code which LuaJIT emits in this scenario, it'll be along the
lines of:
1. Do all the simple register-to-register moves.
2. pass3: Do all stack-to-register moves.
3. Adjust rsp, update traceno, and other bookkeeping.
4. pass2: Do register-to-stack moves.
5. Do register-to-stack copies.
NB: As LuaJIT generates machine code backwards, this order is the
inverse order of what you see if you read asm_head_side from top to
bottom.
Because all stack-to-register moves happen before any
register-to-stack moves, there is a point in time where all values
exist in registers (in my list above, this is the point in time
numbered "3.", whereas in the comment you reference, this point in
time is called "between pass 2 and pass 3"). As an x64 CPU only
(conceptually) has 16 general-purpose registers and 16 floating-point
registers, the limitation that all values need to simultaneously exist
in a register at this point in time means that a side trace can
inherit no more than 16 floating-point values from a parent trace, and
no more than 15 (or 14 if LJ_GC64) non-floating-point values from a
parent trace. You're seeing an error thrown in pass2 because pass2 is
the point where registers get allocated for keeping a stack spill
slot, and all the registers have already been given out.
The trace where I am getting register coalescing too complex is this.
(slightly edited to add cr/lf in SNAP lines to make it more readable)
If my counting is correct, there are 3 floating-point SLOADs / PVALs,
and 17 non-floating-point SLOADs / PVALs. As 17 is greater than 15,
you have a problem (just naively counting doesn't tell the whole
story, as you could get lucky and have some spill slots coincide
between the parent and the child, but counting is a good first-order
approximation, and you've not provided the reg/sp column in your trace
output, nor have you provided the stack/register layout at 695/4, so
counting is the best I can do with what you've provided).
I am now looking to figure out what exactly is causing the register
coalescing too complex, and what changes can I make in the source to
help luajit to avoid this.
Given the current algorithm in LuaJIT, the only useful advice I can
give is: reduce the number of values which need to be inherited from
the parent trace. For example, if this is a loop, and some of the
inherited values are local variables whose lifetime ends at the end of
the loop iteration, and said variables are not mutated in the side
trace, then perhaps you could look into ending their lifetime earlier
(i.e. with explicit "do ... end" scoping within the loop body).
Alternatively, perhaps you could turn some of the inherited locals
into upvalues (possibly paired with a pattern of pulling upvalues into
locals for short scoped blocks).
Alternatively, if you're feeling adventurous, you could try changing
LuaJIT's coalescing algorithm so as to not require all inherited
values to exist in a register simultaneously. I've taken a small stab
at this in
https://github.com/corsix/LuaJIT/commits/nyicoal , which
may or may not help your situation (and may or may not introduce
strange bugs to your program - use at your own risk).
Other related posts:
