Are we inserting yk locations at the right places?

[vext01]

Last week I was making changes to yklua and noticed something strange to do with our yk locations. I think we are inserting them in the wrong places!

This may be part of the reason we see strange performance and/or "trace too long", but I haven't investigated further (yet).

Diff to yklua:

diff --git a/src/lcode.c b/src/lcode.c
index 6df4430..f3b402c 100644
--- a/src/lcode.c
+++ b/src/lcode.c
@@ -374,6 +374,7 @@ static void removelastinstruction (FuncState *fs) {
   fs->pc--;
 }

+#include <stdio.h>

 /*
 ** Emit instruction 'i', checking for array sizes and saving also its
@@ -391,10 +392,16 @@ int luaK_code (FuncState *fs, Instruction i) {
   luaM_growvector(fs->ls->L, f->yklocs, pc, f->sizeyklocs, YkLocation,
                   MAX_INT, "yklocs");
   f->yklocs[pc] = yk_location_null();
-  if ((GET_OPCODE(i) == OP_JMP) && (GETARG_sJ(i) < 0))
+  if ((GET_OPCODE(i) == OP_JMP) && (GETARG_sJ(i) < 0)) {
     f->yklocs[pc + GETARG_sJ(i)] = yk_location_new();
-  if (GET_OPCODE(i) == OP_FORLOOP)
+    // +1 so it matches luac output (1-based).
+    fprintf(stderr, "loop start (jmp) at %d (discovered via %d, sJ=%d)\n", pc + GETARG_sJ(i) + 1, pc + 1, GETARG_sJ(i));
+  }
+  if (GET_OPCODE(i) == OP_FORLOOP) {
     f->yklocs[pc - GETARG_Bx(i) - 2] = yk_location_new();
+    // +1 so it matches luac output (1-based).
+    fprintf(stderr, "loop start (forloop) at %d (discovered via %d, Bx=%d)\n", pc - GETARG_Bx(i) - 2 + 1, pc + 1, GETARG_Bx(i));
+  }
 #endif
   savelineinfo(fs, f, fs->ls->lastline);
   return pc;  /* index of new instruction */

^ This just prints:

• the pc of places we deem loop starts
• the pc of the bytecode that lead us to conclude that it's a loop start
• the lua bytecode instruction argument of interest

for loops

for_loop.lua:

for i = 0, 3 do
    print(i)
end

Then if we run luac we see the output of the above diff and theh disassembled bytcodes:

./src/luac -l for_loop.lua
loop start (forloop) at 7 (discovered via 9, Bx=0)

main <for_loop.lua:0,0> (10 instructions at 0x111b31d0)
0+ params, 6 slots, 1 upvalue, 4 locals, 1 constant, 0 functions
        1       [1]     VARARGPREP      0
        2       [1]     LOADI           0 0
        3       [1]     LOADI           1 3
        4       [1]     LOADI           2 1
        5       [1]     FORPREP         0 3     ; exit to 10
        6       [2]     GETTABUP        4 0 0   ; _ENV "print"
        7       [2]     MOVE            5 3
        8       [2]     CALL            4 2 1   ; 1 in 0 out
        9       [1]     FORLOOP         0 4     ; to 6
        10      [3]     RETURN          0 1 1   ; 0 out

The lua disassembler says the loop start is at pc=6, but we put it at pc=7. Note the jump operand is zero.

while loops

while loops are worse.

while_loop.lua:

local i  = 3
while i ~= 0 do
    i = i - 1
    print(i)
end

$ ./src/luac -l while_loop.lua
loop start (jmp) at 3 (discovered via 4, sJ=-1)
loop start (jmp) at 9 (discovered via 10, sJ=-1)

main <while_loop.lua:0,0> (11 instructions at 0x240211d0)
0+ params, 3 slots, 1 upvalue, 1 local, 1 constant, 0 functions
        1       [1]     VARARGPREP      0
        2       [1]     LOADI           0 3
        3       [2]     EQI             0 0 1
        4       [2]     JMP             6       ; to 11
        5       [3]     ADDI            0 0 -1
        6       [3]     MMBINI          0 1 7 0 ; __sub
        7       [4]     GETTABUP        1 0 0   ; _ENV "print"
        8       [4]     MOVE            2 0
        9       [4]     CALL            1 2 1   ; 1 in 0 out
        10      [4]     JMP             -8      ; to 3
        11      [5]     RETURN          1 1 1   ; 0 out

Here we detect both JMPs as loop starts, even though only one is a backward jump. By luck we correctly end up marking pc=3 as a loop start, but we also deem pc=9 as a loop start, which isn't right.

The bytecode operand is -1 for both jumps.

A theory I will investigate is that the operands are not fully "initialised" at this point in the system and the -1 (and maybe the 0 for for loops above) is a placeholder to be computed later. The solution may be to move the creation of the yk locations later into (e.g.) close_func() in the parser.

[ltratt]

Another way of seeing this should be that if you do yk_debug_str with opcode names (using the label trick from a few weeks back) we should always end with a JMP. If we don't... we might've made a mistake!

[vext01]

Testing it from that angle, applying this diff:

bencher11:yklua> git diff src/lvm.c                                                                         (git:main)
diff --git a/src/lvm.c b/src/lvm.c
index 8ca2df9..94bfb3f 100644
--- a/src/lvm.c
+++ b/src/lvm.c
@@ -1201,6 +1201,7 @@ Instruction load_inst(uint64_t pv, const Instruction *pc) {
 #define vmcase(l)      case l:
 #define vmbreak                break

+#include "lopnames.h"

 void luaV_execute (lua_State *L, CallInfo *ci) {
   LClosure *cl;
@@ -1233,6 +1234,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {
     vmfetch();
 #ifdef USE_YK
     YkLocation *ykloc = &cl->p->yklocs[pcRel(pc, cl->p)];
+    yk_debug_str((char *) opnames[GET_OPCODE(i)]);
     yk_mt_control_point(G(L)->yk_mt, ykloc);
 #endif
     #if 0

And making the loop run longer, for_loop.lua can be seen stopping tracing erroneously at the MOVE at pc=6:

    %301: i64 = zext %300
    %302: ptr = lookup_global @opnames
    %304: ptr = dyn_ptr_add %302, %301, 8
    %305: ptr = load %304
    ; debug_str: MOVE
    %307: ptr = load %16
    %308: ptr = ptr_add %307, 1416
    %309: ptr = load %308
    header_end [%0, %1, %2, %3, %4, %5, %6, %7, %8, %9, %10, %11, %12, %13, %14, %15, %16, %17, %18, %19, %20, %21, %22, %23, %24, %25, %26, %27, %28, %29, %30, %31, %32, %33, %34, %35, %36, %37, %38, %39, %40, %41, %42, 0i32, %212, %284, %
286, %300]
--- End jit-pre-opt ---

The same experiment on while_loop.lua stops tracing at the right place, but for the wrong reason (see my first post where pc=3 is identified as a loop due to pc=4).

I'm convinced that this is broken and will fix it now.