x86-64 jit: inline new_k, recycle_leaf and own fast paths, in o3 regions and plain blocks

a call to rt.new_k / rt.recycle_leaf with a constant class, or to rt.own,
does its class-list pop or push (or owner store) inline and goes on after
the call; an empty list, memdebug, a held range, a block outside memory, a
translated word or a type/class mismatch takes the ordinary call. in a
region this replaces the o3_invoke round trip. o3 frees of leaf objects now
use recycle_leaf too (new_k stamps the type inside o3 since b86db60).
ZYNOFASTALLOC=1 turns it off; ZYPERFMAP=1 writes a perf map of translated code.
tests/programs/o3_freelist.zc: reuse, zeroing, an empty list, untyped
neighbours, memdebug; jit vs ZYNOFASTALLOC vs ZYO3INTERP.

2 files changed, 214 insertions, 3 deletions

diff --git a/src/core/core.c b/src/core/core.c
index 3133c55..ce9e5ca 100644
--- a/src/core/core.c
+++ b/src/core/core.c
@@ -6249,6 +6249,7 @@ static void x64_enh(Enh *e)
    with native calls stays on the region interpreter, as does every region
    under ZYO3INTERP=1. */
 static VM_TLS int x64_o3interp;
+static void perfmap_note(JW *start, JW *end, const char *kind, int a, int b);
 static VM_TLS signed char rxr[MAXUOP * 4 + 16];
 #define RXNREG 6
 static void rsave(void) { int j; for (j = 0; j < RXNREG; j++) push_r(xreg[j]); }
@@ -6470,6 +6471,173 @@ static void rcall_x64(Rg *R, RB *B)
 	for (e = 0; e < R->ne; e++) if (R->ent[e] == B->x2) { jmp_to((JW *)R->stub[e]); hopped = 1; break; }
 	if (!hopped) { mov_r32i(r_ax, (unsigned)B->x2); jmp_to(x_disp); }
 }
+/* ---- the allocator's fast paths, inline ----
+   a call to rt.new_k or rt.recycle_leaf with a constant size class, or to
+   rt.own, is a dozen loads and stores when the class list can serve it, far less
+   than the call: from a compiled region the call even leaves through o3_invoke,
+   which runs the callee on the vm and comes back. so the jit does those stores
+   itself, in a region and in plain translated code, and goes on at the call's
+   return point; anything unusual (an empty list, memdebug, a held range, a block
+   outside memory, a word the jit has translated, a type or class that doesn't
+   match, a size new_k would clamp) takes the ordinary call, which does exactly
+   what it did before. no collection can happen on the fast paths, so the o3
+   rules hold. the runtime hands over the addresses after its stack registration
+   (stack.h SC_FAST); ZYNOFASTALLOC=1 turns all of it off. */
+static VM_TLS int x64_nofast;
+typedef struct { Cell freel, dbg, hlo, hhi, bump, newk, rleaf, own; } FastCfg;
+static int x64_fastcfg(FastCfg *f)
+{
+	Cell c = stack_control;
+	if (x64_nofast || c <= 0 || !inmem(c + SC_FAST_END - 1) || m[c + SC_FAST] != SC_FAST_TAG) return 0;
+	f->freel = m[c + SC_FREE]; f->dbg = m[c + SC_DBG]; f->hlo = m[c + SC_HOLD_LOW]; f->hhi = m[c + SC_HOLD_HIGH];
+	f->bump = m[c + SC_BUMP]; f->newk = m[c + SC_NEW_K]; f->rleaf = m[c + SC_RECYCLE_LEAF]; f->own = m[c + SC_OWN];
+	/* every word it touches by address goes in a 32-bit displacement */
+	if (!inmem(f->freel + 31) || !inmem(f->dbg) || !inmem(f->hlo) || !inmem(f->hhi) || !inmem(f->bump)) return 0;
+	if (8 * (f->freel + 31) > 0x7fffffff || 8 * f->dbg > 0x7fffffff || 8 * f->hlo > 0x7fffffff || 8 * f->hhi > 0x7fffffff || 8 * f->bump > 0x7fffffff) return 0;
+	return 1;
+}
+static void mov_xi(int b, int x, int disp, int imm) { mem_op(0, 1, 0, 0xc7, 0, b, x, 8, disp); xd((unsigned)imm); }	/* qword [b + x*8 + disp] = imm */
+#define FAST_MAXJ 24
+/* new_k(n, t, k) for a constant k in 3..5: n at [rSP + sd + 16], t at +8, k
+   on top. the block goes in the slot n came from; the caller pops the other two.
+   every branch to the ordinary call is added to slow. */
+static void x64_fast_newk(FastCfg *f, int k, int sd, JW **slow, int *ns)
+{
+	int fk = (int)(f->freel + k), j;
+	JW *at, *below;
+	/* rax = the block, rsi = the next one */
+	mov_rm(r_ax, rMB, 8 * fk);
+	test_rr(r_ax, r_ax); slow[(*ns)++] = j32(c_e);
+	mov_rm(r_cx, rMB, (int)(8 * f->dbg)); test_rr(r_cx, r_cx); slow[(*ns)++] = j32(c_ne);
+	mov_ri(r_cx, MW - ((Cell)1 << k)); alu_rr(a_cmp, r_ax, r_cx); slow[(*ns)++] = j32(c_a);
+	mov_rm(r_cx, rMB, (int)(8 * f->hhi)); test_rr(r_cx, r_cx); at = j32(c_e);	/* new_k's held-range rule */
+	alu_rr(a_cmp, r_ax, r_cx); below = j32(c_ge);
+	lea(r_cx, r_ax, -1, 1, 1 << k); alu_rm(a_cmp, r_cx, rMB, (int)(8 * f->hlo)); slow[(*ns)++] = j32(c_g);
+	fix32(below, cp); fix32(at, cp);
+	mov_rx(r_si, rMB, r_ax, 8, 40);
+	test_rr(r_si, r_si); at = j32(c_e);
+	mov_ri(r_cx, MW - 7); alu_rr(a_cmp, r_si, r_cx); slow[(*ns)++] = j32(c_a);
+	fix32(at, cp);
+	mov_rm(r_di, rSP, sd + 16);			/* n: new_k clamps a negative one, the call can do that */
+	mov_ri(r_cx, 0x7fffffff); alu_rr(a_cmp, r_di, r_cx); slow[(*ns)++] = j32(c_a);
+	/* none of the words written may be translated code: the block, the list head, the next block's back link */
+	mov_rm(r_cx, rST, 32);
+	mov_rx(r_8, r_cx, r_ax, 1, 0);
+	for (j = 1; j < (1 << k) / 8; j++) mem_op(0, 1, 0, a_or * 8 + 3, r_8, r_cx, r_ax, 1, 8 * j);
+	test_rr(r_8, r_8); slow[(*ns)++] = j32(c_ne);
+	mem_op(0, 0, 0, 0x80, 7, r_cx, -1, 1, fk); xb(0); slow[(*ns)++] = j32(c_ne);
+	test_rr(r_si, r_si); at = j32(c_e);
+	mem_op(0, 0, 0, 0x80, 7, r_cx, r_si, 1, 6); xb(0); slow[(*ns)++] = j32(c_ne);
+	fix32(at, cp);
+	/* pop it */
+	mov_mr(rMB, 8 * fk, r_si);
+	test_rr(r_si, r_si); at = j32(c_e);
+	mov_xi(rMB, r_si, 48, 0);
+	fix32(at, cp);
+	shift_ri(4, r_di, 32); alu_ri(a_or, r_di, (k << 16) | 1); mov_xr(rMB, r_ax, 8, 8, r_di);	/* b[1]: class, live, n */
+	lea(r_cx, r_ax, -1, 1, 5);
+	mov_rr(r_di, r_cx); alu_ri(a_xor, r_di, 0x2B7E1516); mov_xr(rMB, r_ax, 8, 16, r_di);	/* b[2]: the check word */
+	mov_xi(rMB, r_ax, 24, 0);					/* b[3]: no owner */
+	mov_rm(r_di, rSP, sd + 8); mov_xr(rMB, r_ax, 8, 32, r_di);	/* b[4]: the type */
+	xor32(r_di);
+	for (j = 5; j < (1 << k); j++) mov_xr(rMB, r_ax, 8, 8 * j, r_di);	/* a zeroed payload */
+	mov_mr(rSP, sd + 16, r_cx);
+}
+/* recycle_leaf(p, t, k) for a constant k: p at [rSP + sd + 16], t at +8, k on
+   top. its 0 goes in p's slot; the caller pops the other two */
+static void x64_fast_rleaf(FastCfg *f, int k, int sd, JW **slow, int *ns)
+{
+	int fk = (int)(f->freel + k);
+	JW *at;
+	/* rax = p, the block is p - 5; rsi = the list head */
+	mov_rm(r_cx, rMB, (int)(8 * f->dbg)); test_rr(r_cx, r_cx); slow[(*ns)++] = j32(c_ne);
+	mov_rm(r_ax, rSP, sd + 16);
+	alu_ri(a_cmp, r_ax, HEAP_LO + 5); slow[(*ns)++] = j32(c_l);
+	alu_rm(a_cmp, r_ax, rMB, (int)(8 * f->bump)); slow[(*ns)++] = j32(c_ge);
+	mov_ri(r_cx, MW - 8); alu_rr(a_cmp, r_ax, r_cx); slow[(*ns)++] = j32(c_a);
+	mov_rr(r_di, r_ax); alu_ri(a_xor, r_di, 0x2B7E1516);
+	mem_op(0, 1, 0, a_cmp * 8 + 3, r_di, rMB, r_ax, 8, -24); slow[(*ns)++] = j32(c_ne);	/* the check word */
+	mov_rx(r_si, rMB, r_ax, 8, -32);
+	mov_r32i(r_di, 0xffff); alu_rr(a_and, r_di, r_si); alu_ri(a_cmp, r_di, 1); slow[(*ns)++] = j32(c_ne);	/* live, no other flag */
+	mov_rr(r_di, r_si); shift_ri(5, r_di, 16); alu_ri(a_and, r_di, 31); alu_ri(a_cmp, r_di, k); slow[(*ns)++] = j32(c_ne);
+	mov_rm(r_di, rSP, sd + 8); mem_op(0, 1, 0, a_cmp * 8 + 3, r_di, rMB, r_ax, 8, -8); slow[(*ns)++] = j32(c_ne);	/* the type */
+	mov_rm(r_si, rMB, 8 * fk);
+	test_rr(r_si, r_si); at = j32(c_e);
+	mov_ri(r_cx, MW - 7); alu_rr(a_cmp, r_si, r_cx); slow[(*ns)++] = j32(c_a);
+	fix32(at, cp);
+	mov_rm(r_cx, rST, 32);
+	mov_rx(r_8, r_cx, r_ax, 1, -5); test_rr(r_8, r_8); slow[(*ns)++] = j32(c_ne);
+	mem_op(0, 0, 0, 0x80, 7, r_cx, -1, 1, fk); xb(0); slow[(*ns)++] = j32(c_ne);
+	test_rr(r_si, r_si); at = j32(c_e);
+	mem_op(0, 0, 0, 0x80, 7, r_cx, r_si, 1, 6); xb(0); slow[(*ns)++] = j32(c_ne);
+	fix32(at, cp);
+	/* push it */
+	mov_xi(rMB, r_ax, -24, 0);
+	mov_xi(rMB, r_ax, -32, k << 16);
+	mov_xr(rMB, r_ax, 8, 0, r_si);
+	mov_xi(rMB, r_ax, 8, 0);
+	lea(r_di, r_ax, -1, 1, -5);
+	test_rr(r_si, r_si); at = j32(c_e);
+	mov_xr(rMB, r_si, 8, 48, r_di);
+	fix32(at, cp);
+	mov_mr(rMB, 8 * fk, r_di);
+	mov_mi(rSP, sd + 16, 0);
+}
+/* own(c, p): c at [rSP + sd + 8], p on top. c stays in its slot; the caller pops p.
+   a c that isn't a live unshared object is left alone, as own does; only a
+   translated owner word needs the call */
+static void x64_fast_own(FastCfg *f, int sd, JW **slow, int *ns)
+{
+	JW *skip[6];
+	int n = 0, j;
+	mov_rm(r_ax, rSP, sd + 8);
+	alu_ri(a_cmp, r_ax, HEAP_LO + 5); skip[n++] = j32(c_l);
+	alu_rm(a_cmp, r_ax, rMB, (int)(8 * f->bump)); skip[n++] = j32(c_ge);
+	mov_ri(r_cx, MW - 8); alu_rr(a_cmp, r_ax, r_cx); skip[n++] = j32(c_a);
+	mov_rr(r_di, r_ax); alu_ri(a_xor, r_di, 0x2B7E1516);
+	mem_op(0, 1, 0, a_cmp * 8 + 3, r_di, rMB, r_ax, 8, -24); skip[n++] = j32(c_ne);
+	mov_rx(r_si, rMB, r_ax, 8, -32); alu_ri(a_and, r_si, 9); alu_ri(a_cmp, r_si, 1); skip[n++] = j32(c_ne);	/* live, not shared */
+	mov_rm(r_cx, rST, 32);
+	mem_op(0, 0, 0, 0x80, 7, r_cx, r_ax, 1, -2); xb(0); slow[(*ns)++] = j32(c_ne);
+	mov_rm(r_si, rSP, sd); mov_xr(rMB, r_ax, 8, -16, r_si);
+	for (j = 0; j < n; j++) fix32(skip[j], cp);
+}
+/* jump on to the code after the call: its entry stub, or through the dispatcher */
+static void rhop(Rg *R, int to)
+{
+	int e;
+	for (e = 0; e < R->ne; e++) if (R->ent[e] == to) { jmp_to((JW *)R->stub[e]); return; }
+	mov_r32i(r_ax, (unsigned)to); jmp_to(x_disp);
+}
+/* the constant the block stored to stack slot `slot` (before its delta), or -1 */
+static Cell rso_const(RB *B, int slot)
+{
+	int j;
+	for (j = 0; j < B->nso; j++) if (B->so[2 * j] == slot) { int v = B->so[2 * j + 1]; return xkc[v] ? xkv[v] : -1; }
+	return -1;
+}
+/* in a region, the fast path of the call that ends block B, if it has one. it
+   falls through (rdx, the target, untouched) to the ordinary call when it can't
+   serve it */
+static void rfast_x64(Rg *R, RB *B)
+{
+	FastCfg f;
+	Cell target, k;
+	JW *slow[FAST_MAXJ];
+	int ns = 0, j;
+	if (!xkc[B->cv] || !x64_fastcfg(&f)) return;
+	target = xkv[B->cv];
+	if (target != f.newk && target != f.rleaf) return;
+	k = rso_const(B, B->delta);	/* the class is the last argument, on top */
+	if (k < 3 || k > 30 || (target == f.newk && k > 5)) return;
+	if (trace) fprintf(stderr, "o3: %s class %d inline at %d\n", target == f.newk ? "new_k" : "recycle_leaf", (int)k, B->x2 - 1);
+	rspill(R);
+	if (target == f.newk) x64_fast_newk(&f, (int)k, 0, slow, &ns);
+	else x64_fast_rleaf(&f, (int)k, 0, slow, &ns);
+	lea(rSP, rSP, -1, 1, 16);
+	rhop(R, B->x2);
+	for (j = 0; j < ns; j++) fix32(slow[j], cp);
+}
 static void remit_x64(Rg *R, RB *B)
 {
 	int i, j, d;
@@ -6516,6 +6684,7 @@ static void remit_x64(Rg *R, RB *B)
 		if (B->s2 >= 0) rjmp(jm32(), B->s2); else rexit(R, B->x2);
 		break;
 	case T_CALL:
+		rfast_x64(R, B);
 		rcall_x64(R, B);
 		break;
 	case T_RET:
@@ -6539,7 +6708,7 @@ static int rjit_x64(Rg *R)
 {
 	JW *start = cp, **lab;
 	int b, e, need = 64 * R->ne + 8192, rc = 0;
-	for (b = 0; b < R->nb; b++) need += 160 * R->b[b].n + 64 * R->b[b].nso + 256;
+	for (b = 0; b < R->nb; b++) need += 160 * R->b[b].n + 64 * R->b[b].nso + 256 + (R->b[b].term == T_CALL ? 1024 : 0);
 	if (cp - code + need > CODEW * 4 - (1 << 19)) return -2;
 	lab = malloc((size_t)R->nb * sizeof *lab);
 	rfa = malloc((size_t)(2 * R->nb + R->ne + 1) * sizeof *rfa); rfb = malloc((size_t)(2 * R->nb + R->ne + 1) * sizeof *rfb); nrf = 0;
@@ -6590,6 +6759,7 @@ static int rjit_x64(Rg *R)
 			fn_nat[R->fn].argc = R->argc;
 		}
 		if (trace) fprintf(stderr, "o3: %d..%d -> %d bytes of x86-64\n", R->lo, R->hi - 1, (int)(cp - start));
+		perfmap_note(start, cp, "o3_", R->lo, R->hi - 1);
 	} else cp = start;
 	free(lab); free(rfa); free(rfb);
 	return rc;
@@ -6608,11 +6778,25 @@ static void rcompile(Rg *R, int eager)
 	if (rjit_x64(R) == -1) { R->nonat = 1; if (trace) fprintf(stderr, "o3: %d..%d stays on the region interpreter\n", R->lo, R->hi - 1); }
 }
 
+/* ZYPERFMAP=1 writes /tmp/perf-<pid>.map, so `perf report` names translated
+   code by the vm addresses it came from (zc_<first>_<last>, zc_o3_<lo>_<hi>) */
+static FILE *perfmap;
+static void perfmap_note(JW *start, JW *end, const char *kind, int a, int b)
+{
+	static int tried;
+	if (!tried) {
+		char path[64];
+		tried = 1;
+		if (getenv("ZYPERFMAP")) { snprintf(path, sizeof path, "/tmp/perf-%d.map", (int)getpid()); perfmap = fopen(path, "w"); }
+	}
+	if (perfmap) { fprintf(perfmap, "%lx %lx zc_%s%d_%d\n", (unsigned long)(uintptr_t)start, (unsigned long)((char *)end - (char *)start), kind, a, b); fflush(perfmap); }
+}
 static void *translate(int p)
 {
 	JW *start;
-	int i = p, n = 0, k, t, used[64], nused = 0, j2, ju;
-	Cell w;
+	int i = p, n = 0, k, t, used[64], nused = 0, j2, ju, lastlit = -1;
+	Cell w, lastv = 0;
+	FastCfg fc;
 	if (cp - code > CODEW * 4 - (1 << 19) || !ix_room()) flush();
 	start = cp;
 	vd = 0;
@@ -6632,6 +6816,25 @@ static void *translate(int p)
 				i += 2;
 				continue;
 			}
+			if (k == 6 && x64_fastcfg(&fc)) {	/* new_k, recycle_leaf or own: the fast path inline, the call beside it */
+				int kind = t == fc.newk ? 1 : t == fc.rleaf ? 2 : t == fc.own ? 3 : 0;
+				Cell kc = lastlit == i - 1 ? lastv : -1;
+				if (kind == 3 || (kind == 1 && kc >= 3 && kc <= 5) || (kind == 2 && kc >= 3 && kc <= 30)) {
+					JW *slow[FAST_MAXJ], *join;
+					int ns = 0, j;
+					if (kind == 1) x64_fast_newk(&fc, (int)kc, 8 * vd, slow, &ns);
+					else if (kind == 2) x64_fast_rleaf(&fc, (int)kc, 8 * vd, slow, &ns);
+					else x64_fast_own(&fc, 8 * vd, slow, &ns);
+					join = jm32();
+					for (j = 0; j < ns; j++) fix32(slow[j], cp);
+					mov_mi(rRP, 0, i + 2); alu_ri(a_add, rRP, 8);
+					disp_imm(t);
+					fix32(join, cp);
+					vd += kind == 3 ? 1 : 2;	/* the arguments are gone, the result is in the first one's slot */
+					i += 2;
+					continue;
+				}
+			}
 			if (k == 6) { mov_mi(rRP, 0, i + 2); alu_ri(a_add, rRP, 8); }
 			disp_imm(t);
 			i += 2;
@@ -6681,6 +6884,7 @@ static void *translate(int p)
 			vd--;
 			if (small) mov_mi(rSP, SL(0), (int)v);
 			else { mov_ri(r_ax, v); stv(0, r_ax); }
+			lastlit = i; lastv = v;
 			i++; continue;
 		}
 		k = (int)(w / 2);
@@ -6790,6 +6994,7 @@ static void *translate(int p)
 	else for (ju = 0; ju < nused; ju++) dep_add(used[ju], j2);
 	tab[p] = start;
 	if (trace) fprintf(stderr, "jit: %d..%d -> %ld bytes\n", p, i - 1, (long)(cp - start));
+	perfmap_note(start, cp, "", p, i - 1);
 	return start;
 }
 static void x64_limits(void) { S[11] = (long)(m + stack_data_limit()); S[12] = (long)(m + stack_return_limit()); }
@@ -6874,6 +7079,7 @@ static int x64_boot(Cell sp, Cell rp, void *stop)
 	x64_noo3 = getenv("ZYNOO3") != 0;
 	x64_noenh = getenv("ZYNOENH") != 0;
 	x64_o3interp = getenv("ZYO3INTERP") != 0;
+	x64_nofast = getenv("ZYNOFASTALLOC") != 0;
 	jitwrite(1); build_stubs(); jitwrite(0); syncicache(code, cp);
 	S[0] = (long)m; S[1] = sp; S[2] = rp; S[3] = (long)tab; S[4] = (long)cov;
 	S[5] = (long)Q; S[6] = (long)G; S[7] = (long)&J; S[8] = (long)hook;
diff --git a/src/core/stack.h b/src/core/stack.h
index 8c7f7a2..dbc718a 100644
--- a/src/core/stack.h
+++ b/src/core/stack.h
@@ -15,6 +15,11 @@ enum {
 	SC_RETURN_LOW, SC_RETURN_TOP, SC_RETURN_NODE,
 	SC_FREE, SC_STOP, SC_BUMP, SC_MAX, SC_HOLD_LOW, SC_HOLD_HIGH, SC_CUT, SC_GC_ACTIVE, SC_COUNT
 };
+/* optional words after the registered ones, for the native allocator fast paths
+   in compiled o3 regions: a tag (a runtime without them never has it there), the
+   address of rt.dbg, and the entry addresses of rt.new_k, rt.recycle_leaf and rt.own */
+enum { SC_FAST = SC_COUNT, SC_DBG, SC_NEW_K, SC_RECYCLE_LEAF, SC_OWN, SC_FAST_END };
+#define SC_FAST_TAG 0x2B7E1517
 
 /* the including core supplies stack_memory_grow and refreshes m if it moves. */
 static Cell stack_get(int slot) { Cell p = m[stack_control + slot]; return inmem(p) ? m[p] : 0; }