/* zygote core: puts the genome (the zc compiler and its runtime, both vm code)
   into memory and runs it. on arm64, every block of vm code is translated to
   arm64 the first time it is reached, straight from live memory. stores that
   land on translated words throw those translations away, so code that
   rewrites itself, including the resident compiler, just gets retranslated
   on the next visit. on other hosts (or with -DZYINTERP) a plain interpreter
   with the same semantics runs instead. ZYTRACE=1 logs translations on stderr. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#if defined(__aarch64__) && !defined(ZYINTERP)
#define ZYJIT 1
#include <sys/mman.h>
#ifdef __APPLE__
#include <pthread.h>
#include <libkern/OSCacheControl.h>
#endif
#endif
#include "genome.h"

#ifndef JTYPE
#define JTYPE char
#endif
char Q(void);
void G(char);
extern JTYPE J;

#define MW (1 << 20)	/* memory, in words */
#define DS0 (MW - 16)	/* data stack grows down from here */
#define RS0 0xF0000	/* return stack grows up from here */
#define DSLIM (0xFC000 + 1100)	/* data stack overflows below this (a block pushes at most ~1024) */
#define RSLIM (0xF8000 - 8)	/* return stack overflows above this */
/* why the cpu stopped, when it wasn't a halt */
static int stopped(int p)
{
	if (p == MW + 1) { fprintf(stderr, "zy: data stack overflow\n"); return 2; }
	if (p == MW + 2) { fprintf(stderr, "zy: return stack overflow\n"); return 2; }
	return 0;
}
#define CODEW (4 << 20)	/* 16 MB of code, in instruction words */
#define MAXB 65536
#define BLKW 1024	/* longest block, in vm words */

static int m[MW];
static int trace;

/* ---- virtual enhancements ----
   up to 512 custom opcodes (22 .. 533), wired in at runtime by the install
   opcode (21). an enhancement is a short program over native micro-ops,
   written either as a recipe (text) or as straight-line vm code that gets
   lifted. both become ssa, go through the optimizer below, and then run in
   the interpreter or get inlined by the jit as native code. */
#define NENH 512
#define XOP0 22
enum { U_LI, U_MOV, U_ADD, U_SUB, U_MUL, U_SDIV, U_UDIV, U_SREM, U_UREM, U_AND, U_OR, U_XOR,
	U_SHL, U_SHR, U_SAR, U_NEG, U_NOT, U_LT, U_LTU, U_EQ, U_NE, U_MIN, U_MAX, U_MINU, U_MAXU,
	U_MULHS, U_MULHU, U_CLZ, U_ABS, U_SEL, U_LD, U_ST, U_N };
static const char *unames[U_N] = { "li", "mov", "add", "sub", "mul", "sdiv", "udiv", "srem", "urem",
	"and", "or", "xor", "shl", "shr", "sar", "neg", "not", "lt", "ltu", "eq", "ne", "min", "max",
	"minu", "maxu", "mulhs", "mulhu", "clz", "abs", "sel", "ld", "st" };
static const signed char uarity[U_N] = { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2,
	2, 2, 2, 2, 2, 2, 1, 1, 3, 1, 2 };
typedef struct { int op, d, a, b, c, imm; } Uop;	/* ssa: d is a fresh value, a b c are values */
typedef struct {
	int live, kind, nin, nout, n, nv, out[8];
	Uop *u;
	signed char *reg;	/* physical register per value, for the jit; 0 if it didn't fit */
} Enh;
static Enh enh[NENH];
static int need_flush;

#define MAXUOP 4096
static Uop ub[MAXUOP]; static int un, unv, uerr;	/* the program being built */
static int unew(int op, int a, int b, int c, int imm)
{
	Uop *u;
	if (un >= MAXUOP) { uerr = -5; return 0; }
	u = &ub[un++]; u->op = op; u->d = unv++; u->a = a; u->b = b; u->c = c; u->imm = imm;
	return u->d;
}
static int mread(int a) { return (unsigned)a < MW ? m[a] : 0; }

/* recipe text: one statement per line or per ';'
     r0 = sdiv r0 r1      dst = op operands, operands are rN, parameter names or numbers
     r2 = r0              a copy, or a number
     st r1 r0             memory[r1] = r0
   inputs arrive in r0.. (and under the parameter names), outputs leave from r0.. */
static int parse_recipe(int src, int names, int nin, int nout, int *out)
{
	int cur[16], i, p = src, n, k, op, args[3], na, dst, isst;
	char tok[8][32]; int nt;
	for (i = 0; i < 16; i++) cur[i] = i < nin ? i : -1;
	for (;;) {
		/* read one statement into tokens */
		nt = 0;
		for (;;) {
			int c = mread(p);
			while (c == ' ' || c == '\t' || c == '\r') c = mread(++p);
			if (!c || c == '\n' || c == ';') break;
			if (c == '=') { if (nt < 8) strcpy(tok[nt++], "="); p++; continue; }
			n = 0;
			while (c && c != ' ' && c != '\t' && c != '\n' && c != ';' && c != '=' && c != '\r') { if (n < 31) tok[nt < 8 ? nt : 7][n++] = (char)c; c = mread(++p); }
			if (nt < 8) tok[nt++][n] = 0;
		}
		if (nt) {
			isst = !strcmp(tok[0], "st");
			if (!isst && (nt < 3 || strcmp(tok[1], "="))) return -2;
			/* destination register */
			dst = -1;
			if (!isst) {
				if (tok[0][0] == 'r' && tok[0][1] >= '0' && tok[0][1] <= '9') dst = atoi(tok[0] + 1);
				else for (i = 0; i < nin && names; i++) {
					int s = mread(names + i), j = 0;
					while (mread(s + j) && mread(s + j) == (unsigned char)tok[0][j]) j++;
					if (!mread(s + j) && !tok[0][j]) dst = i;
				}
				if (dst < 0 || dst > 15) return -2;
			}
			k = isst ? 1 : 2;	/* first token after "=" (or after st) */
			op = -1;
			if (!isst && nt > 3) { for (i = 0; i < U_N; i++) if (!strcmp(tok[k], unames[i])) op = i; if (op < 0) return -2; k++; }
			if (isst) op = U_ST;
			na = 0;
			for (; k < nt; k++) {
				char *t = tok[k], *e; int v = -1;
				if (na >= 3) return -2;
				if (t[0] == 'r' && t[1] >= '0' && t[1] <= '9') { int r = atoi(t + 1); if (r > 15) return -2; if (cur[r] < 0) cur[r] = unew(U_LI, 0, 0, 0, 0); v = cur[r]; }
				else if ((t[0] >= '0' && t[0] <= '9') || t[0] == '-') { long x = strtol(t, &e, 0); if (*e) return -2; v = unew(U_LI, 0, 0, 0, (int)x); }
				else {
					for (i = 0; i < nin && names; i++) {
						int s = mread(names + i), j = 0;
						while (mread(s + j) && mread(s + j) == (unsigned char)t[j]) j++;
						if (!mread(s + j) && !t[j]) v = cur[i] < 0 ? (cur[i] = unew(U_LI, 0, 0, 0, 0)) : cur[i];
					}
					if (v < 0) return -2;
				}
				args[na++] = v;
			}
			if (op < 0) {	/* x = y */
				if (na != 1) return -2;
				cur[dst] = args[0];
			} else {
				if (na != (op == U_LI ? 0 : uarity[op])) {
					if (!(op == U_LI && na == 1)) return -2;
				}
				if (op == U_LI) cur[dst] = args[0];
				else if (op == U_ST) unew(U_ST, args[0], args[1], 0, 0);
				else cur[dst] = unew(op, args[0], na > 1 ? args[1] : 0, na > 2 ? args[2] : 0, 0);
			}
			if (uerr) return uerr;
		}
		if (!mread(p)) break;
		p++;
	}
	for (i = 0; i < nout; i++) { if (cur[i] < 0) cur[i] = unew(U_LI, 0, 0, 0, 0); out[i] = cur[i]; }
	return uerr;
}

/* straight-line vm code from addr up to its ret, run symbolically */
static int lift_vm(int a, int len, int nin, int nout, int *out)
{
	int st[256], sp = 0, i, w, k, x, y;
	for (i = 0; i < nin; i++) st[sp++] = i;
	for (i = 0; i < len; i++) {
		w = mread(a + i);
		if (w & 1) { if (sp >= 256) return -4; st[sp++] = unew(U_LI, 0, 0, 0, w >> 1); continue; }
		k = w / 2;
		if (k == 9) break;
		switch (k) {
		case 1: if (sp < 1) return -4; st[sp - 1] = unew(U_LD, st[sp - 1], 0, 0, 0); break;
		case 2: if (sp < 2) return -4; unew(U_ST, st[sp - 1], st[sp - 2], 0, 0); sp -= 2; break;
		case 3:	/* pick needs a constant index */
			if (sp < 1) return -4;
			x = st[sp - 1];
			if (x < nin) return -4;
			{ int j; for (j = 0; j < un && ub[j].d != x; j++); if (j == un || ub[j].op != U_LI) return -4; y = ub[j].imm; }
			if (y < 0 || y >= sp - 1) return -4;
			st[sp - 1] = st[sp - 2 - y];
			break;
		case 4: if (sp < 1) return -4; sp--; break;
		case 5: if (sp < 2) return -4; x = st[sp - 1]; st[sp - 1] = st[sp - 2]; st[sp - 2] = x; break;
		case 13: case 14: case 15: case 16: case 17: case 18: case 19: case 20: {
			static const int map[] = { U_ADD, U_SUB, U_MUL, U_AND, U_OR, U_XOR, U_SAR, U_LT };
			if (sp < 2) return -4;
			x = st[sp - 1]; y = st[sp - 2]; sp -= 2;
			st[sp++] = unew(map[k - 13], y, x, 0, 0);
			break; }
		default: return -4;	/* control flow, i/o and other enhancements don't lift */
		}
		if (uerr) return uerr;
	}
	if (sp != nout) return -4;
	for (i = 0; i < nout; i++) out[i] = st[i];
	return uerr;
}

/* ---- the optimizer ----
   one forward pass of copy propagation, constant folding, algebraic
   simplification, division by constants (the multiply-high trick) and
   common subexpression elimination, then dead code removal. */
static int ev(int op, int a, int b, int c)
{
	unsigned ua = (unsigned)a, ub_ = (unsigned)b;
	switch (op) {
	case U_ADD: return (int)(ua + ub_);
	case U_SUB: return (int)(ua - ub_);
	case U_MUL: return (int)(ua * ub_);
	case U_SDIV: return b == 0 ? 0 : (a == (int)0x80000000 && b == -1) ? a : a / b;
	case U_UDIV: return b == 0 ? 0 : (int)(ua / ub_);
	case U_SREM: return b == 0 ? a : (a == (int)0x80000000 && b == -1) ? 0 : a % b;
	case U_UREM: return b == 0 ? a : (int)(ua % ub_);
	case U_AND: return a & b;
	case U_OR: return a | b;
	case U_XOR: return a ^ b;
	case U_SHL: return (int)(ua << (b & 31));
	case U_SHR: return (int)(ua >> (b & 31));
	case U_SAR: return a >> (b & 31);
	case U_NEG: return (int)(0u - ua);
	case U_NOT: return ~a;
	case U_LT: return a < b;
	case U_LTU: return ua < ub_;
	case U_EQ: return a == b;
	case U_NE: return a != b;
	case U_MIN: return a < b ? a : b;
	case U_MAX: return a > b ? a : b;
	case U_MINU: return ua < ub_ ? a : b;
	case U_MAXU: return ua > ub_ ? a : b;
	case U_MULHS: return (int)(((long long)a * (long long)b) >> 32);
	case U_MULHU: return (int)(((unsigned long long)ua * ub_) >> 32);
	case U_CLZ: { int n = 0; if (!ua) return 32; while (!(ua & 0x80000000u)) { ua <<= 1; n++; } return n; }
	case U_ABS: return a < 0 ? (int)(0u - ua) : a;
	case U_SEL: return a ? b : c;
	}
	return 0;
}
static void smagic(int d, int *mul, int *sh)	/* hacker's delight, signed */
{
	const unsigned two31 = 0x80000000u;
	unsigned ad = d < 0 ? 0u - (unsigned)d : (unsigned)d, t = two31 + ((unsigned)d >> 31);
	unsigned anc = t - 1 - t % ad, q1 = two31 / anc, r1 = two31 - q1 * anc, q2 = two31 / ad, r2 = two31 - q2 * ad, delta;
	int p = 31;
	do {
		p++;
		q1 *= 2; r1 *= 2; if (r1 >= anc) { q1++; r1 -= anc; }
		q2 *= 2; r2 *= 2; if (r2 >= ad) { q2++; r2 -= ad; }
		delta = ad - r2;
	} while (q1 < delta || (q1 == delta && r1 == 0));
	*mul = (int)(q2 + 1); if (d < 0) *mul = -*mul;
	*sh = p - 32;
}
static void umagic(unsigned d, unsigned *mul, int *add, int *sh)	/* hacker's delight, unsigned */
{
	unsigned nc = 0xFFFFFFFFu - (0u - d) % d, q1, r1, q2, r2, delta;
	int p = 31;
	*add = 0;
	q1 = 0x80000000u / nc; r1 = 0x80000000u - q1 * nc;
	q2 = 0x7FFFFFFFu / d; r2 = 0x7FFFFFFFu - q2 * d;
	do {
		p++;
		if (r1 >= nc - r1) { q1 = 2 * q1 + 1; r1 = 2 * r1 - nc; } else { q1 = 2 * q1; r1 = 2 * r1; }
		if (r2 + 1 >= d - r2) { if (q2 >= 0x7FFFFFFFu) *add = 1; q2 = 2 * q2 + 1; r2 = 2 * r2 + 1 - d; }
		else { if (q2 >= 0x80000000u) *add = 1; q2 = 2 * q2; r2 = 2 * r2 + 1; }
		delta = d - 1 - r2;
	} while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
	*mul = q2 + 1; *sh = p - 32;
}

static Uop ob[MAXUOP]; static int on, onv;
static int *omap, *isk, *kv;	/* old value -> new value; constness of new values */
static int pure(int op) { return op != U_LD && op != U_ST; }
static int ispow2(unsigned x) { return x && !(x & (x - 1)); }
static int lg2(unsigned x) { int n = 0; while (x > 1) { x >>= 1; n++; } return n; }
static int oe(int op, int a, int b, int c, int imm);
static int K(int v) { return oe(U_LI, 0, 0, 0, v); }
static int raw(int op, int a, int b, int c, int imm)
{
	Uop *u; int i;
	if (pure(op))	/* cse */
		for (i = 0; i < on; i++) {
			u = &ob[i];
			if (u->op == op && u->a == a && u->b == b && u->c == c && u->imm == imm) return u->d;
		}
	if (on >= MAXUOP) { uerr = -5; return 0; }
	u = &ob[on++]; u->op = op; u->d = onv++; u->a = a; u->b = b; u->c = c; u->imm = imm;
	isk[u->d] = op == U_LI; kv[u->d] = imm;
	return u->d;
}
static int sdivk(int a, int d)	/* a / d for a constant d, no divide instruction */
{
	int mul, sh, q, t;
	if (d == 1) return a;
	if (d == -1) return oe(U_NEG, a, 0, 0, 0);
	if (d == (int)0x80000000) return oe(U_EQ, a, K(d), 0, 0);
	if (ispow2((unsigned)(d < 0 ? -d : d))) {
		int k = lg2((unsigned)(d < 0 ? -d : d));
		t = oe(U_SAR, a, K(31), 0, 0);
		t = oe(U_SHR, t, K(32 - k), 0, 0);
		q = oe(U_SAR, oe(U_ADD, a, t, 0, 0), K(k), 0, 0);
		return d < 0 ? oe(U_NEG, q, 0, 0, 0) : q;
	}
	smagic(d, &mul, &sh);
	q = oe(U_MULHS, a, K(mul), 0, 0);
	if (d > 0 && mul < 0) q = oe(U_ADD, q, a, 0, 0);
	if (d < 0 && mul > 0) q = oe(U_SUB, q, a, 0, 0);
	if (sh) q = oe(U_SAR, q, K(sh), 0, 0);
	return oe(U_ADD, q, oe(U_SHR, q, K(31), 0, 0), 0, 0);
}
static int udivk(int a, unsigned d)
{
	unsigned mul; int add, sh, t;
	if (d == 1) return a;
	if (ispow2(d)) return oe(U_SHR, a, K(lg2(d)), 0, 0);
	if (d > 0x80000000u) return oe(U_XOR, oe(U_LTU, a, K((int)d), 0, 0), K(1), 0, 0);	/* a >= d */
	umagic(d, &mul, &add, &sh);
	t = oe(U_MULHU, a, K((int)mul), 0, 0);
	if (!add) return sh ? oe(U_SHR, t, K(sh), 0, 0) : t;
	t = oe(U_ADD, oe(U_SHR, oe(U_SUB, a, t, 0, 0), K(1), 0, 0), t, 0, 0);
	return sh > 1 ? oe(U_SHR, t, K(sh - 1), 0, 0) : t;
}
static int oe(int op, int a, int b, int c, int imm)
{
	int ka, kb, A, B;
	if (op == U_LI) return raw(U_LI, 0, 0, 0, imm);
	if (op == U_MOV) return a;
	if (op == U_LD || op == U_ST) return raw(op, a, b, 0, 0);
	ka = isk[a]; kb = uarity[op] > 1 && isk[b];
	A = kv[a]; B = kv[b];
	/* everything constant: fold */
	if (ka && (uarity[op] < 2 || kb) && (uarity[op] < 3 || isk[c])) return K(ev(op, A, B, kv[c]));
	/* constants go right for commutative ops */
	if (ka && !kb && (op == U_ADD || op == U_MUL || op == U_AND || op == U_OR || op == U_XOR || op == U_EQ || op == U_NE ||
		op == U_MIN || op == U_MAX || op == U_MINU || op == U_MAXU || op == U_MULHS || op == U_MULHU)) {
		int t = a; a = b; b = t; kb = 1; B = A; ka = 0;
	}
	if (op == U_SEL && ka) return A ? b : c;
	if (op == U_SEL && b == c) return b;
	if (kb) switch (op) {
	case U_ADD: case U_SUB: case U_OR: case U_XOR: case U_SHL: case U_SHR: case U_SAR:
		if (!B || (op >= U_SHL && op <= U_SAR && !(B & 31))) return a;
		break;
	case U_MUL:
		if (B == 0) return K(0);
		if (B == 1) return a;
		if (B == -1) return oe(U_NEG, a, 0, 0, 0);
		if (ispow2((unsigned)B)) return oe(U_SHL, a, K(lg2((unsigned)B)), 0, 0);
		break;
	case U_AND: if (B == 0) return K(0); if (B == -1) return a; break;
	case U_SDIV: if (B == 0) return K(0); return sdivk(a, B);
	case U_SREM: if (B == 0) return a; if (B == 1 || B == -1) return K(0);
		return oe(U_SUB, a, oe(U_MUL, sdivk(a, B), b, 0, 0), 0, 0);
	case U_UDIV: if (B == 0) return K(0); return udivk(a, (unsigned)B);
	case U_UREM: if (B == 0) return a;
		if (ispow2((unsigned)B)) return oe(U_AND, a, K(B - 1), 0, 0);
		return oe(U_SUB, a, oe(U_MUL, udivk(a, (unsigned)B), b, 0, 0), 0, 0);
	}
	if (a == b && uarity[op] == 2) {
		if (op == U_SUB || op == U_XOR || op == U_LT || op == U_LTU || op == U_NE) return K(0);
		if (op == U_AND || op == U_OR || op == U_MIN || op == U_MAX || op == U_MINU || op == U_MAXU) return a;
		if (op == U_EQ) return K(1);
	}
	return raw(op, a, b, c, 0);
}
/* runs the optimizer over ub[0..un) with nin inputs; leaves the result in e */
static int optimize(Enh *e, int nin, int *out, int nout)
{
	int i, *live, n = 0;
	static int omap_[MAXUOP + 16], isk_[MAXUOP * 4], kv_[MAXUOP * 4];
	omap = omap_; isk = isk_; kv = kv_;
	on = 0; onv = nin;
	for (i = 0; i < nin; i++) { omap[i] = i; isk[i] = 0; }
	for (i = 0; i < un && !uerr; i++) {
		Uop *u = &ub[i];
		int a = uarity[u->op] > 0 || u->op == U_ST || u->op == U_LD ? omap[u->a] : 0;
		int b = uarity[u->op] > 1 || u->op == U_ST ? omap[u->b] : 0;
		int c = uarity[u->op] > 2 ? omap[u->c] : 0;
		if (u->op == U_ST) oe(U_ST, a, b, 0, 0);
		else omap[u->d] = oe(u->op, a, b, c, u->imm);
	}
	if (uerr) return uerr;
	/* dead code: outputs and stores are live */
	live = calloc(onv + 1, sizeof *live);
	for (i = 0; i < nout; i++) { e->out[i] = omap[out[i]]; live[e->out[i]] = 1; }
	for (i = on; i--;) {
		Uop *u = &ob[i];
		if (u->op != U_ST && !live[u->d]) { u->op = -1; continue; }
		if (uarity[u->op] > 0 || u->op == U_ST || u->op == U_LD) live[u->a] = 1;
		if (uarity[u->op] > 1 || u->op == U_ST) live[u->b] = 1;
		if (uarity[u->op] > 2) live[u->c] = 1;
	}
	free(live);
	e->u = malloc((on + 1) * sizeof(Uop));
	for (i = 0; i < on; i++) if (ob[i].op >= 0) e->u[n++] = ob[i];
	e->n = n; e->nv = onv; e->nin = nin; e->nout = nout;
	return 0;
}
/* run an installed enhancement on a downward-growing stack; returns the new top */
static int *xexec(Enh *e, int *sp)
{
	int vb[256], *v = e->nv <= 256 ? vb : malloc(e->nv * sizeof(int)), i, j;
	for (j = 0; j < e->nin; j++) v[j] = sp[e->nin - 1 - j];
	for (i = 0; i < e->n; i++) {
		Uop *u = &e->u[i];
		switch (u->op) {
		case U_LI: v[u->d] = u->imm; break;
		case U_LD: v[u->d] = mread(v[u->a]); break;
		case U_ST: if ((unsigned)v[u->a] < MW) m[v[u->a]] = v[u->b]; break;
		default: v[u->d] = ev(u->op, v[u->a], v[u->b], v[u->c]);
		}
	}
	sp += e->nin - e->nout;
	for (j = 0; j < e->nout; j++) sp[e->nout - 1 - j] = v[e->out[j]];
	if (v != vb) free(v);
	return sp;
}
static void xdump(int slot, Enh *e)
{
	int i;
	fprintf(stderr, "enh %d: %d in, %d out, %d ops\n", slot, e->nin, e->nout, e->n);
	for (i = 0; i < e->n; i++) {
		Uop *u = &e->u[i];
		if (u->op == U_ST) fprintf(stderr, "  st v%d v%d\n", u->a, u->b);
		else if (u->op == U_LI) fprintf(stderr, "  v%d = %d\n", u->d, u->imm);
		else { fprintf(stderr, "  v%d = %s v%d", u->d, unames[u->op], u->a); if (uarity[u->op] > 1) fprintf(stderr, " v%d", u->b); if (uarity[u->op] > 2) fprintf(stderr, " v%d", u->c); fprintf(stderr, "\n"); }
	}
	for (i = 0; i < e->nout; i++) fprintf(stderr, "  out%d = v%d\n", i, e->out[i]);
}
/* registers for the jit: values live in w0..w15, straight-line linear scan.
   if they don't fit, reg stays 0 and the jit calls the interpreter instead. */
static void regalloc(Enh *e)
{
	int *last = malloc(e->nv * sizeof(int)), i, j, k, fr = 0xffff;
	signed char *r = malloc(e->nv);
	for (i = 0; i < e->nv; i++) { last[i] = -2; r[i] = -1; }
	for (i = 0; i < e->n; i++) {
		Uop *u = &e->u[i];
		if (uarity[u->op] > 0 || u->op == U_ST || u->op == U_LD) last[u->a] = i;
		if (uarity[u->op] > 1 || u->op == U_ST) last[u->b] = i;
		if (uarity[u->op] > 2) last[u->c] = i;
	}
	for (i = 0; i < e->nout; i++) last[e->out[i]] = e->n;
#define TAKE(v) do { for (k = 0; k < 16 && !(fr >> k & 1); k++); if (k == 16) goto fail; fr &= ~(1 << k); r[v] = (signed char)k; } while (0)
	for (j = 0; j < e->nin; j++) if (last[j] >= -1 && last[j] != -2) TAKE(j);
	for (i = 0; i < e->n; i++) {
		Uop *u = &e->u[i]; int ops[3], no = 0;
		if (uarity[u->op] > 0 || u->op == U_ST || u->op == U_LD) ops[no++] = u->a;
		if (uarity[u->op] > 1 || u->op == U_ST) ops[no++] = u->b;
		if (uarity[u->op] > 2) ops[no++] = u->c;
		for (j = 0; j < no; j++) if (last[ops[j]] == i && r[ops[j]] >= 0 && (fr >> r[ops[j]] & 1) == 0) fr |= 1 << r[ops[j]];
		if (u->op != U_ST) TAKE(u->d);
		if (u->op != U_ST && last[u->d] == -2) fr |= 1 << r[u->d];	/* never used */
	}
#undef TAKE
	free(last); e->reg = r; return;
fail:
	free(last); free(r); e->reg = 0;
}
/* the install opcode. descriptor: slot, kind (0 recipe, 1 vm code), inputs,
   outputs, payload address, payload length, parameter names (or 0).
   returns 0, or -1 bad descriptor, -2 recipe syntax, -4 code doesn't lift,
   -5 too big. */
static int install(int d)
{
	int slot = mread(d), kind = mread(d + 1), nin = mread(d + 2), nout = mread(d + 3);
	int pay = mread(d + 4), len = mread(d + 5), names = mread(d + 6), out[8], r;
	Enh ne;
	if ((unsigned)slot >= NENH || (unsigned)nin > 8 || (unsigned)nout > 8 || (kind != 0 && kind != 1)) return -1;
	un = 0; unv = nin; uerr = 0;
	r = kind == 0 ? parse_recipe(pay, names, nin, nout, out) : lift_vm(pay, len, nin, nout, out);
	if (r) { if (trace) fprintf(stderr, "enh %d: install failed (%d)\n", slot, r); return r; }
	memset(&ne, 0, sizeof ne);
	if ((r = optimize(&ne, nin, out, nout))) return r;
	ne.kind = kind; ne.live = 1;
	regalloc(&ne);
	if (enh[slot].live) { free(enh[slot].u); free(enh[slot].reg); }
	enh[slot] = ne;
	need_flush = 1;
	if (trace) xdump(slot, &enh[slot]);
	return 0;
}
#ifdef ZYJIT
static unsigned char cov[MW];	/* 1 if a live translation covers the word */
static void *tab[MW];		/* vm address -> translation */
static struct { int a, b; } bl[MAXB];	/* live translations cover [a,b); a < 0 is dead */
static int nbl;
static unsigned *code, *cp, *x_enter, *x_exit, *x_disp, *x_first;
static long S[13];	/* m, s, r, tab, cov, Q, G, &J, store hook, install, enhancement fallback, stack limits */

enum { W0 = 0, W1 = 1, X9 = 9, X10, X11, M = 19, SP = 20, RP = 21, TAB = 22, ST = 23 };

static void E(unsigned x) { *cp++ = x; }
static void li(int d, int v)
{
	unsigned u = (unsigned)v;
	E(0x52800000 | (u & 0xffff) << 5 | d);
	if (u >> 16) E(0x72a00000 | (u >> 16) << 5 | d);
}
static void ldr_post(int t, int n, int i) { E(0xb8400400 | (i & 0x1ff) << 12 | n << 5 | t); }
static void ldr_pre(int t, int n, int i) { E(0xb8400c00 | (i & 0x1ff) << 12 | n << 5 | t); }
static void str_pre(int t, int n, int i) { E(0xb8000c00 | (i & 0x1ff) << 12 | n << 5 | t); }
static void str_post(int t, int n, int i) { E(0xb8000400 | (i & 0x1ff) << 12 | n << 5 | t); }
static void ldr_u(int t, int n, int o) { E(0xb9400000 | (o / 4) << 10 | n << 5 | t); }
static void str_u(int t, int n, int o) { E(0xb9000000 | (o / 4) << 10 | n << 5 | t); }
static void ldrx_u(int t, int n, int o) { E(0xf9400000 | (o / 8) << 10 | n << 5 | t); }
static void ldr_rr(int t, int n, int r, int ext) { E(0xb8600800 | r << 16 | ext << 13 | 1 << 12 | n << 5 | t); }
static void str_rr(int t, int n, int r, int ext) { E(0xb8200800 | r << 16 | ext << 13 | 1 << 12 | n << 5 | t); }
static void ldp_post(int t, int u, int n, int i) { E(0x28c00000 | ((i / 4) & 0x7f) << 15 | u << 10 | n << 5 | t); }
static void op3(unsigned op, int d, int n, int r) { E(op | r << 16 | n << 5 | d); }
static void addx_ext(int d, int n, int r, int ext) { E(0x8b200000 | r << 16 | ext << 13 | 2 << 10 | n << 5 | d); }
static void movw(int d, int r) { E(0x2a0003e0 | r << 16 | d); }
static void blr(int n) { E(0xd63f0000 | n << 5); }
static void b_to(unsigned *t) { long o = t - cp; E(0x14000000 | (o & 0x3ffffff)); }
static void cb_fix(unsigned *at, unsigned *to) { *at |= ((to - at) & 0x7ffff) << 5; }
#define SXTW 6
#define UXTW 2

static void build_stubs(void)
{
	cp = code;
	x_enter = cp;			/* int enter(long *S, void *code) */
	E(0xa9bb7bfd);			/* stp x29, x30, [sp, #-80]! */
	E(0x910003fd);			/* mov x29, sp */
	E(0xa90153f3);			/* stp x19, x20, [sp, #16] */
	E(0xa9025bf5);			/* stp x21, x22, [sp, #32] */
	E(0xf9001bf7);			/* str x23, [sp, #48] */
	E(0xa90467f8);			/* stp x24, x25, [sp, #64] */
	E(0xaa0003f7);			/* mov x23, x0 */
	ldrx_u(M, ST, 0);
	ldrx_u(24, ST, 88); ldrx_u(25, ST, 96);	/* x24, x25: the stack limits, as addresses */
	ldr_u(X9, ST, 8); addx_ext(SP, M, X9, UXTW);
	ldr_u(X9, ST, 16); addx_ext(RP, M, X9, UXTW);
	ldrx_u(TAB, ST, 24);
	E(0xd61f0020);			/* br x1 */
	x_exit = cp;			/* w0 = next vm address */
	op3(0xcb000000, X9, SP, M); E(0xd342fd29); str_u(X9, ST, 8);	/* s = (x20 - x19) >> 2 */
	op3(0xcb000000, X9, RP, M); E(0xd342fd29); str_u(X9, ST, 16);
	E(0xa94153f3);			/* ldp x19, x20, [sp, #16] */
	E(0xa9425bf5);			/* ldp x21, x22, [sp, #32] */
	E(0xf9401bf7);			/* ldr x23, [sp, #48] */
	E(0xa94467f8);			/* ldp x24, x25, [sp, #64] */
	E(0xa8c57bfd);			/* ldp x29, x30, [sp], #80 */
	E(0xd65f03c0);			/* ret */
	{
	unsigned *ovd = cp, *ovr;
	li(W0, MW + 1); b_to(x_exit);	/* data stack overflow */
	ovr = cp;
	li(W0, MW + 2); b_to(x_exit);	/* return stack overflow */
	x_disp = cp;			/* w0 = target: check the stacks, chain through tab[] or fall back to c */
	E(0xeb18029f);			/* cmp x20, x24 */
	E(0x54000003 | ((ovd - cp) & 0x7ffff) << 5);	/* b.lo data overflow */
	E(0xeb1902bf);			/* cmp x21, x25 */
	E(0x54000002 | ((ovr - cp) & 0x7ffff) << 5);	/* b.hs return overflow */
	}
	E(0x7144001f);			/* cmp w0, #MW */
	E(0x54000002 | ((x_exit - cp) & 0x7ffff) << 5);	/* b.hs exit */
	E(0xf8605ac9);			/* ldr x9, [x22, w0, uxtw #3] */
	E(0xb4000009 | ((x_exit - cp) & 0x7ffff) << 5);	/* cbz x9, exit */
	E(0xd61f0120);			/* br x9 */
	x_first = cp;
}

static void flush(void)
{
	memset(tab, 0, sizeof tab);
	memset(cov, 0, sizeof cov);
	nbl = 0;
	cp = x_first;
	if (trace) fprintf(stderr, "jit: flushed\n");
}

static void jitwrite(int on)
{
#ifdef __APPLE__
	pthread_jit_write_protect_np(!on);
#else
	(void)on;
#endif
}

static void syncicache(unsigned *a, unsigned *b)
{
#ifdef __APPLE__
	sys_icache_invalidate(a, (char *)b - (char *)a);
#else
	__builtin___clear_cache((char *)a, (char *)b);
#endif
}

/* store hook for words that are covered by a translation */
static int hook(int a, int v)
{
	int j, x, hit = 0;
	if (m[a] == v) return 0;
	m[a] = v;
	for (j = 0; j < nbl; j++)
		if (bl[j].a >= 0 && bl[j].a <= a && a < bl[j].b) {
			tab[bl[j].a] = 0;
			for (x = bl[j].a; x < bl[j].b; x++) cov[x] = 0;
			if (trace) fprintf(stderr, "jit: dropped %d..%d\n", bl[j].a, bl[j].b - 1);
			bl[j].a = -1;
			hit = 1;
		}
	for (j = 0; j < nbl; j++)
		if (bl[j].a >= 0) for (x = bl[j].a; x < bl[j].b; x++) cov[x] = 1;
	return hit;
}

static void op(int i, int k)	/* everything except control flow */
{
	unsigned *a, *b, *c, *z;
	switch (k) {
	case 1: ldr_u(X9, SP, 0); ldr_rr(X9, M, X9, SXTW); str_u(X9, SP, 0); return;
	case 2:	/* store: inline unless the target word is translated */
		ldp_post(X9, X10, SP, 8);
		E(0x7144013f);			/* cmp w9, #MW */
		a = cp; E(0x54000002);		/* b.hs done */
		ldrx_u(X11, ST, 32);
		E(0x3869496b);			/* ldrb w11, [x11, w9, uxtw] */
		b = cp; E(0x3500000b);		/* cbnz w11, slow */
		str_rr(X10, M, X9, UXTW);
		c = cp; E(0x14000000);		/* b done */
		cb_fix(b, cp);			/* slow: hook(a, v) */
		movw(W0, X9); movw(W1, X10); ldrx_u(X11, ST, 64); blr(X11);
		z = cp; E(0x34000000);		/* cbz w0, done */
		li(W0, i + 1); b_to(x_exit);	/* a translation died: resume at i+1 in c */
		cb_fix(a, cp); cb_fix(z, cp);
		*c |= (cp - c) & 0x3ffffff;
		return;
	case 3: ldr_u(X9, SP, 0); E(0x9100128a); ldr_rr(X9, X10, X9, SXTW); str_u(X9, SP, 0); return; /* add x10, x20, #4 */
	case 4: E(0x91001294); return;	/* add x20, x20, #4 */
	case 5: E(0x29402a89); E(0x2900268a); return;	/* ldp w9, w10, [x20]; stp w10, w9, [x20] */
	case 10: ldrx_u(X11, ST, 40); blr(X11); E(0x13001c09); str_pre(X9, SP, -4); return; /* sxtb w9, w0 */
	case 11:
		ldrx_u(X9, ST, 56);
		if (sizeof J == 1) E(0x39400129); else ldr_u(X9, X9, 0);	/* ldrb w9, [x9] */
		str_pre(X9, SP, -4);
		return;
	case 12: ldr_post(W0, SP, 4); E(0x13001c00); ldrx_u(X11, ST, 48); blr(X11); return; /* sxtb w0, w0 */
	}
	ldr_post(X9, SP, 4);
	ldr_u(X10, SP, 0);
	switch (k) {
	case 13: op3(0x0b000000, X10, X10, X9); break;
	case 14: op3(0x4b000000, X10, X10, X9); break;
	case 15: op3(0x1b007c00, X10, X10, X9); break;
	case 16: op3(0x0a000000, X10, X10, X9); break;
	case 17: op3(0x2a000000, X10, X10, X9); break;
	case 18: op3(0x4a000000, X10, X10, X9); break;
	case 19: op3(0x1ac02800, X10, X10, X9); break;
	default: E(0x6b09015f); E(0x1a9fa7ea);	/* cmp w10, w9; cset w10, lt */
	}
	str_u(X10, SP, 0);
}

/* an enhancement, inlined: inputs from the data stack into w0..w15, the
   optimized micro-ops, outputs back. x16 and x17 are scratch. */
static void emit_enh(int s)
{
	Enh *e = &enh[s];
	signed char *r = e->reg;
	int i, j, delta;
	if (!r) {	/* didn't fit in registers: x0 = data stack, w1 = slot, call the interpreter */
		E(0xaa1403e0); li(W1, s); ldrx_u(X11, ST, 80); blr(X11); E(0xaa0003f4);
		return;
	}
	for (j = 0; j < e->nin; j++) if (r[j] >= 0) ldr_u(r[j], SP, 4 * (e->nin - 1 - j));
	for (i = 0; i < e->n; i++) {
		Uop *u = &e->u[i];
		int d = u->op == U_ST ? 0 : r[u->d], a = r[u->a], b = r[u->b], c = r[u->c];
		switch (u->op) {
		case U_LI: li(d, u->imm); break;
		case U_ADD: op3(0x0b000000, d, a, b); break;
		case U_SUB: op3(0x4b000000, d, a, b); break;
		case U_MUL: op3(0x1b007c00, d, a, b); break;
		case U_SDIV: op3(0x1ac00c00, d, a, b); break;
		case U_UDIV: op3(0x1ac00800, d, a, b); break;
		case U_SREM: op3(0x1ac00c00, 16, a, b); E(0x1b008000 | b << 16 | a << 10 | 16 << 5 | d); break;	/* msub */
		case U_UREM: op3(0x1ac00800, 16, a, b); E(0x1b008000 | b << 16 | a << 10 | 16 << 5 | d); break;
		case U_AND: op3(0x0a000000, d, a, b); break;
		case U_OR: op3(0x2a000000, d, a, b); break;
		case U_XOR: op3(0x4a000000, d, a, b); break;
		case U_SHL: op3(0x1ac02000, d, a, b); break;
		case U_SHR: op3(0x1ac02400, d, a, b); break;
		case U_SAR: op3(0x1ac02800, d, a, b); break;
		case U_NEG: E(0x4b0003e0 | a << 16 | d); break;
		case U_NOT: E(0x2a2003e0 | a << 16 | d); break;
		case U_LT: E(0x6b00001f | b << 16 | a << 5); E(0x1a9fa7e0 | d); break;	/* cmp; cset lt */
		case U_LTU: E(0x6b00001f | b << 16 | a << 5); E(0x1a9f27e0 | d); break;	/* cset lo */
		case U_EQ: E(0x6b00001f | b << 16 | a << 5); E(0x1a9f17e0 | d); break;
		case U_NE: E(0x6b00001f | b << 16 | a << 5); E(0x1a9f07e0 | d); break;
		case U_MIN: E(0x6b00001f | b << 16 | a << 5); E(0x1a800000 | b << 16 | 11 << 12 | a << 5 | d); break;
		case U_MAX: E(0x6b00001f | b << 16 | a << 5); E(0x1a800000 | b << 16 | 12 << 12 | a << 5 | d); break;
		case U_MINU: E(0x6b00001f | b << 16 | a << 5); E(0x1a800000 | b << 16 | 3 << 12 | a << 5 | d); break;
		case U_MAXU: E(0x6b00001f | b << 16 | a << 5); E(0x1a800000 | b << 16 | 8 << 12 | a << 5 | d); break;
		case U_MULHS: E(0x9b207c00 | b << 16 | a << 5 | 16); E(0xd360fc00 | 16 << 5 | d); break;	/* smull; lsr #32 */
		case U_MULHU: E(0x9ba07c00 | b << 16 | a << 5 | 16); E(0xd360fc00 | 16 << 5 | d); break;
		case U_CLZ: E(0x5ac01000 | a << 5 | d); break;
		case U_ABS: E(0x7100001f | a << 5); E(0x5a800400 | a << 16 | 10 << 12 | a << 5 | d); break;	/* cmp #0; cneg */
		case U_SEL: E(0x7100001f | a << 5); E(0x1a800000 | c << 16 | 1 << 12 | b << 5 | d); break;	/* csel ne */
		case U_LD:	/* out of range reads 0, like the interpreter */
			E(0x52800011); E(0x7144001f | a << 5); E(0x54000042); ldr_rr(17, M, a, UXTW); movw(d, 17);
			break;
		case U_ST: E(0x7144001f | a << 5); E(0x54000042); str_rr(b, M, a, UXTW); break;
		}
	}
	delta = 4 * (e->nin - e->nout);
	if (delta > 0) E(0x91000294 | delta << 10);
	if (delta < 0) E(0xd1000294 | (-delta) << 10);
	for (j = 0; j < e->nout; j++) str_u(r[e->out[j]], SP, 4 * (e->nout - 1 - j));
}
static int inst_hook(int d) { return install(d); }
static long xrun(long sp, int slot) { return (long)xexec(&enh[slot], (int *)sp); }

static void *translate(int p)
{
	unsigned *start;
	int i = p, n = 0, w, k, t;
	if (cp - code > CODEW - 65536 || nbl >= MAXB) flush();
	start = cp;
	for (;;) {
		if (i >= MW) { E(0x12800000); b_to(x_exit); break; }	/* movn w0, #0: halt */
		if (n++ >= BLKW) { li(W0, i); b_to(x_disp); break; }
		w = m[i];
		cov[i] = 1;
		if (w & 1 && i + 1 < MW && !(m[i + 1] & 1) && (k = m[i + 1] / 2) >= 6 && k <= 8) {
			t = (w - 1) / 2;	/* literal + call/jmp/jz with a known target */
			cov[i + 1] = 1;
			if (k == 8) {
				unsigned *a;
				ldr_post(X10, SP, 4);
				a = cp; E(0x3500000a);	/* cbnz w10, fallthrough */
				li(W0, t); b_to(x_disp);
				cb_fix(a, cp);
				i += 2;
				continue;
			}
			li(X10, i + 2);
			if (k == 6) str_post(X10, RP, 4); else str_u(X10, RP, 0);
			li(W0, t); b_to(x_disp);
			i += 2;
			break;
		}
		if (w & 1) { li(X9, (w - 1) / 2); str_pre(X9, SP, -4); i++; continue; }
		k = w / 2;
		if (k == 0) { E(0x12800000); b_to(x_exit); i++; break; }
		if (k < 0 || k == 6 || k == 7) {
			ldr_post(W0, SP, 4);
			li(X10, i + 1);
			if (k == 6) str_post(X10, RP, 4); else str_u(X10, RP, 0);
			if (k < 0) { li(X11, 7 - k); addx_ext(RP, RP, X11, SXTW); }
			b_to(x_disp);
			i++;
			break;
		}
		if (k == 8) {	/* jz: taken leaves, not taken keeps going */
			ldp_post(X9, X10, SP, 8);
			E(0x3500006a);		/* cbnz w10, +3 */
			movw(W0, X9);
			b_to(x_disp);
			i++;
			continue;
		}
		if (k == 9) { ldr_pre(W0, RP, -4); b_to(x_disp); i++; break; }
		if (k == 21) {	/* install: call into c, then return to it so it can flush */
			ldr_u(W0, SP, 0); ldrx_u(X11, ST, 72); blr(X11); str_u(W0, SP, 0);
			li(W0, i + 1); b_to(x_exit); i++; break;
		}
		if (k >= XOP0 && k < XOP0 + NENH && enh[k - XOP0].live) { emit_enh(k - XOP0); i++; continue; }
		if (k > 20) { E(0x12800000); b_to(x_exit); i++; break; }	/* not wired: halt */
		op(i, k);
		i++;
	}
	bl[nbl].a = p;
	bl[nbl++].b = i;
	tab[p] = start;
	syncicache(start, cp);
	if (trace) fprintf(stderr, "jit: %d..%d -> %ld bytes\n", p, i - 1, (long)((char *)cp - (char *)start));
	return start;
}

#else
/* portable path for hosts without the arm64 jit: a plain interpreter with
   the same semantics (shift counts wrap at 32, stores outside memory are
   ignored, loads outside memory read 0, leaving memory halts). */
#ifdef ZYLLVM
/* ---- llvm backend ----
   a tiered jit for hosts the arm64 backend doesn't cover. the interpreter
   counts how often each block start is reached; a hot block is translated to
   llvm ir (same block rules as the arm64 jit: it ends at call, jump, ret or
   halt, and keeps going past a jz), optimized at O2 and compiled with orc.
   enhancements are inlined as ir. stores into compiled words drop the blocks
   that cover them, so self-modifying code still works. */
#include <llvm-c/Core.h>
#include <llvm-c/Error.h>
#include <llvm-c/LLJIT.h>
#include <llvm-c/Orc.h>
#include <llvm-c/Target.h>
#include <llvm-c/Transforms/PassBuilder.h>
static int HOT = 5000;		/* runs before a block gets compiled: ZYHOT */
static const char *lpasses = "default<O2>";	/* ZYPASSES */
#define LMAXB 65536
typedef int (*Blk)(int *mem, int *regs);
static Blk lt[MW];			/* address -> compiled block */
static unsigned short hot[MW];
static unsigned char lcov[MW];		/* 1 if a compiled block covers the word */
static struct { int a, b; } lbl[LMAXB];
static int nlbl, llvm_ok, nblocks;
static LLVMOrcLLJITRef jit;
static LLVMOrcThreadSafeContextRef tsc;
static LLVMContextRef ctx;
static LLVMTypeRef i8t, i32t, i64t, ptrt, i1t;
static LLVMBuilderRef bd;
static LLVMValueRef fn_, vm_, vregs, vs, vr;	/* function, memory, regs, s and r slots */
static LLVMModuleRef mod_;

static void ldrop_all(void)
{
	memset(lt, 0, sizeof lt); memset(lcov, 0, sizeof lcov); memset(hot, 0, sizeof hot); nlbl = 0;
	if (trace) fprintf(stderr, "llvm: dropped every block\n");
}
/* a store to a word some block covers: write it, drop those blocks */
static int lhook(int a, int v)
{
	int j, x, hit = 0;
	if (m[a] == v) return 0;
	m[a] = v;
	for (j = 0; j < nlbl; j++)
		if (lbl[j].a >= 0 && lbl[j].a <= a && a < lbl[j].b) {
			lt[lbl[j].a] = 0; hot[lbl[j].a] = 0;
			if (trace) fprintf(stderr, "llvm: dropped %d..%d\n", lbl[j].a, lbl[j].b - 1);
			lbl[j].a = -1; hit = 1;
		}
	if (hit) {
		memset(lcov, 0, sizeof lcov);
		for (j = 0; j < nlbl; j++) if (lbl[j].a >= 0) for (x = lbl[j].a; x < lbl[j].b; x++) lcov[x] = 1;
	}
	return hit;
}
static int linstall(int d) { return install(d); }

static LLVMValueRef K32(int v) { return LLVMConstInt(i32t, (unsigned)v, 0); }
static LLVMValueRef cptr(void *p) { return LLVMConstIntToPtr(LLVMConstInt(i64t, (unsigned long long)(size_t)p, 0), ptrt); }
static LLVMValueRef mslot(LLVMValueRef idx) { return LLVMBuildGEP2(bd, i32t, vm_, &idx, 1, ""); }
static LLVMValueRef ld(LLVMValueRef idx) { return LLVMBuildLoad2(bd, i32t, mslot(idx), ""); }
static void st(LLVMValueRef idx, LLVMValueRef v) { LLVMBuildStore(bd, v, mslot(idx)); }
static LLVMValueRef gets(void) { return LLVMBuildLoad2(bd, i32t, vs, ""); }
static void sets(LLVMValueRef v) { LLVMBuildStore(bd, v, vs); }
static LLVMValueRef add(LLVMValueRef a, int k) { return LLVMBuildAdd(bd, a, K32(k), ""); }
/* a load that reads 0 outside memory */
static LLVMValueRef safeld(LLVMValueRef a)
{
	LLVMValueRef in = LLVMBuildICmp(bd, LLVMIntULT, a, K32(MW), "");
	LLVMValueRef v = ld(LLVMBuildSelect(bd, in, a, K32(0), ""));
	return LLVMBuildSelect(bd, in, v, K32(0), "");
}
static void push(LLVMValueRef v) { LLVMValueRef s = add(gets(), -1); sets(s); st(s, v); }
/* leave the block: write s and r back, return the next vm address */
static void leave(LLVMValueRef next)
{
	LLVMValueRef r0 = K32(0), r1 = K32(1);
	LLVMBuildStore(bd, gets(), LLVMBuildGEP2(bd, i32t, vregs, &r0, 1, ""));
	LLVMBuildStore(bd, LLVMBuildLoad2(bd, i32t, vr, ""), LLVMBuildGEP2(bd, i32t, vregs, &r1, 1, ""));
	LLVMBuildRet(bd, next);
}
static LLVMBasicBlockRef newbb(void) { return LLVMAppendBasicBlockInContext(ctx, fn_, ""); }
static LLVMValueRef callp(void *f, LLVMTypeRef ret, LLVMTypeRef *at, int n, LLVMValueRef *args)
{
	LLVMTypeRef ft = LLVMFunctionType(ret, at, (unsigned)n, 0);
	return LLVMBuildCall2(bd, ft, cptr(f), args, (unsigned)n, "");
}
/* an enhancement as ir: the same semantics as ev() */
static void ir_enh(Enh *e)
{
	LLVMValueRef *v = calloc(e->nv + 1, sizeof *v), s = gets(), z = K32(0), q, d, t, c1, c2;
	int i, j;
	LLVMTypeRef i64 = i64t;
	for (j = 0; j < e->nin; j++) v[j] = ld(add(s, e->nin - 1 - j));
	for (i = 0; i < e->n; i++) {
		Uop *u = &e->u[i];
		LLVMValueRef a = u->op == U_LI ? 0 : v[u->a], b = uarity[u->op] > 1 || u->op == U_ST ? v[u->b] : 0, c = uarity[u->op] > 2 ? v[u->c] : 0, r = 0;
		switch (u->op) {
		case U_LI: r = K32(u->imm); break;
		case U_ADD: r = LLVMBuildAdd(bd, a, b, ""); break;
		case U_SUB: r = LLVMBuildSub(bd, a, b, ""); break;
		case U_MUL: r = LLVMBuildMul(bd, a, b, ""); break;
		case U_SDIV: case U_SREM:	/* /0 and INT_MIN/-1 are defined, like the cpu */
			c1 = LLVMBuildICmp(bd, LLVMIntEQ, b, z, "");
			c2 = LLVMBuildAnd(bd, LLVMBuildICmp(bd, LLVMIntEQ, a, K32((int)0x80000000), ""), LLVMBuildICmp(bd, LLVMIntEQ, b, K32(-1), ""), "");
			d = LLVMBuildSelect(bd, LLVMBuildOr(bd, c1, c2, ""), K32(1), b, "");
			if (u->op == U_SDIV) { q = LLVMBuildSDiv(bd, a, d, ""); r = LLVMBuildSelect(bd, c1, z, q, ""); }
			else { q = LLVMBuildSRem(bd, a, d, ""); r = LLVMBuildSelect(bd, c1, a, LLVMBuildSelect(bd, c2, z, q, ""), ""); }
			break;
		case U_UDIV: case U_UREM:
			c1 = LLVMBuildICmp(bd, LLVMIntEQ, b, z, "");
			d = LLVMBuildSelect(bd, c1, K32(1), b, "");
			if (u->op == U_UDIV) r = LLVMBuildSelect(bd, c1, z, LLVMBuildUDiv(bd, a, d, ""), "");
			else r = LLVMBuildSelect(bd, c1, a, LLVMBuildURem(bd, a, d, ""), "");
			break;
		case U_AND: r = LLVMBuildAnd(bd, a, b, ""); break;
		case U_OR: r = LLVMBuildOr(bd, a, b, ""); break;
		case U_XOR: r = LLVMBuildXor(bd, a, b, ""); break;
		case U_SHL: r = LLVMBuildShl(bd, a, LLVMBuildAnd(bd, b, K32(31), ""), ""); break;
		case U_SHR: r = LLVMBuildLShr(bd, a, LLVMBuildAnd(bd, b, K32(31), ""), ""); break;
		case U_SAR: r = LLVMBuildAShr(bd, a, LLVMBuildAnd(bd, b, K32(31), ""), ""); break;
		case U_NEG: r = LLVMBuildSub(bd, z, a, ""); break;
		case U_NOT: r = LLVMBuildNot(bd, a, ""); break;
		case U_LT: r = LLVMBuildZExt(bd, LLVMBuildICmp(bd, LLVMIntSLT, a, b, ""), i32t, ""); break;
		case U_LTU: r = LLVMBuildZExt(bd, LLVMBuildICmp(bd, LLVMIntULT, a, b, ""), i32t, ""); break;
		case U_EQ: r = LLVMBuildZExt(bd, LLVMBuildICmp(bd, LLVMIntEQ, a, b, ""), i32t, ""); break;
		case U_NE: r = LLVMBuildZExt(bd, LLVMBuildICmp(bd, LLVMIntNE, a, b, ""), i32t, ""); break;
		case U_MIN: r = LLVMBuildSelect(bd, LLVMBuildICmp(bd, LLVMIntSLT, a, b, ""), a, b, ""); break;
		case U_MAX: r = LLVMBuildSelect(bd, LLVMBuildICmp(bd, LLVMIntSGT, a, b, ""), a, b, ""); break;
		case U_MINU: r = LLVMBuildSelect(bd, LLVMBuildICmp(bd, LLVMIntULT, a, b, ""), a, b, ""); break;
		case U_MAXU: r = LLVMBuildSelect(bd, LLVMBuildICmp(bd, LLVMIntUGT, a, b, ""), a, b, ""); break;
		case U_MULHS: case U_MULHU: {
			LLVMValueRef x = u->op == U_MULHS ? LLVMBuildSExt(bd, a, i64, "") : LLVMBuildZExt(bd, a, i64, "");
			LLVMValueRef y = u->op == U_MULHS ? LLVMBuildSExt(bd, b, i64, "") : LLVMBuildZExt(bd, b, i64, "");
			r = LLVMBuildTrunc(bd, LLVMBuildLShr(bd, LLVMBuildMul(bd, x, y, ""), LLVMConstInt(i64, 32, 0), ""), i32t, "");
			break; }
		case U_CLZ: {
			unsigned id = LLVMLookupIntrinsicID("llvm.ctlz", 9);
			LLVMValueRef f = LLVMGetIntrinsicDeclaration(mod_, id, &i32t, 1), args[2];
			args[0] = a; args[1] = LLVMConstInt(i1t, 0, 0);
			r = LLVMBuildCall2(bd, LLVMIntrinsicGetType(ctx, id, &i32t, 1), f, args, 2, "");
			break; }
		case U_ABS: t = LLVMBuildICmp(bd, LLVMIntSLT, a, z, ""); r = LLVMBuildSelect(bd, t, LLVMBuildSub(bd, z, a, ""), a, ""); break;
		case U_SEL: r = LLVMBuildSelect(bd, LLVMBuildICmp(bd, LLVMIntNE, a, z, ""), b, c, ""); break;
		case U_LD: r = safeld(a); break;
		case U_ST: {
			LLVMBasicBlockRef yes = newbb(), done = newbb();
			LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntULT, a, K32(MW), ""), yes, done);
			LLVMPositionBuilderAtEnd(bd, yes); st(a, b); LLVMBuildBr(bd, done);
			LLVMPositionBuilderAtEnd(bd, done);
			break; }
		}
		if (u->op != U_ST) v[u->d] = r;
	}
	s = add(s, e->nin - e->nout); sets(s);
	for (j = 0; j < e->nout; j++) st(add(s, e->nout - 1 - j), v[e->out[j]]);
	free(v);
}
static void llvm_init(void)
{
	LLVMErrorRef err;
	if (getenv("ZYHOT")) HOT = atoi(getenv("ZYHOT"));
	if (HOT < 1) HOT = 1;
	if (HOT > 65000) HOT = 65000;
	if (getenv("ZYPASSES")) lpasses = getenv("ZYPASSES");
	LLVMInitializeNativeTarget(); LLVMInitializeNativeAsmPrinter();
	if ((err = LLVMOrcCreateLLJIT(&jit, 0))) { char *msg = LLVMGetErrorMessage(err); fprintf(stderr, "llvm: %s\n", msg); LLVMDisposeErrorMessage(msg); return; }
	tsc = LLVMOrcCreateNewThreadSafeContext();
	ctx = LLVMOrcThreadSafeContextGetContext(tsc);
	i1t = LLVMInt1TypeInContext(ctx); i8t = LLVMInt8TypeInContext(ctx); i32t = LLVMInt32TypeInContext(ctx);
	i64t = LLVMInt64TypeInContext(ctx); ptrt = LLVMPointerTypeInContext(ctx, 0);
	bd = LLVMCreateBuilderInContext(ctx);
	llvm_ok = 1;
}
/* compile the block at p; 0 if it couldn't be */
static Blk lcompile(int p)
{
	char name[32]; LLVMTypeRef pt[2], ft; LLVMValueRef s, a, b, v, r, args[2]; LLVMTypeRef at[2];
	LLVMOrcExecutorAddress addr; LLVMErrorRef err; LLVMPassBuilderOptionsRef po;
	int i = p, n = 0, w, k, t, done = 0;
	if (!llvm_ok || nlbl >= LMAXB) return 0;
	sprintf(name, "b%d_%d", p, nblocks++);
	mod_ = LLVMModuleCreateWithNameInContext(name, ctx);
	pt[0] = ptrt; pt[1] = ptrt;
	ft = LLVMFunctionType(i32t, pt, 2, 0);
	fn_ = LLVMAddFunction(mod_, name, ft);
	vm_ = LLVMGetParam(fn_, 0); vregs = LLVMGetParam(fn_, 1);
	LLVMPositionBuilderAtEnd(bd, newbb());
	vs = LLVMBuildAlloca(bd, i32t, "s"); vr = LLVMBuildAlloca(bd, i32t, "r");
	{ LLVMValueRef r0 = K32(0), r1 = K32(1);
	  sets(LLVMBuildLoad2(bd, i32t, LLVMBuildGEP2(bd, i32t, vregs, &r0, 1, ""), ""));
	  LLVMBuildStore(bd, LLVMBuildLoad2(bd, i32t, LLVMBuildGEP2(bd, i32t, vregs, &r1, 1, ""), ""), vr); }
	while (!done) {
		if (i >= MW) { leave(K32(MW)); break; }
		if (n++ >= 1024) { leave(K32(i)); break; }
		w = m[i];
		lcov[i] = 1;
		if (w & 1) {
			/* a literal followed by call, jump or jz: a known target */
			if (i + 1 < MW && !(m[i + 1] & 1) && (k = m[i + 1] / 2) >= 6 && k <= 8) {
				t = w >> 1; lcov[i + 1] = 1;
				if (k == 8) {
					LLVMBasicBlockRef tk = newbb(), go = newbb();
					s = gets(); a = ld(s); sets(add(s, 1));
					LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntEQ, a, K32(0), ""), tk, go);
					LLVMPositionBuilderAtEnd(bd, tk); leave(K32(t));
					LLVMPositionBuilderAtEnd(bd, go);
					i += 2; continue;
				}
				if (k == 6) { r = LLVMBuildLoad2(bd, i32t, vr, ""); st(r, K32(i + 2)); LLVMBuildStore(bd, add(r, 1), vr); }
				leave(K32(t)); i += 2; break;
			}
			push(K32(w >> 1)); i++; continue;
		}
		k = w / 2;
		s = gets();
		switch (k) {
		case 0: leave(K32(MW)); done = 1; break;
		case 1: st(s, safeld(ld(s))); break;
		case 2: {
			LLVMBasicBlockRef in = newbb(), cv = newbb(), plain = newbb(), out = newbb(), quit = newbb();
			a = ld(s); b = ld(add(s, 1)); sets(add(s, 2));
			LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntULT, a, K32(MW), ""), in, out);
			LLVMPositionBuilderAtEnd(bd, in);
			v = LLVMBuildLoad2(bd, i8t, LLVMBuildGEP2(bd, i8t, cptr(lcov), &a, 1, ""), "");
			LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntNE, v, LLVMConstInt(i8t, 0, 0), ""), cv, plain);
			LLVMPositionBuilderAtEnd(bd, plain); st(a, b); LLVMBuildBr(bd, out);
			LLVMPositionBuilderAtEnd(bd, cv);
			at[0] = i32t; at[1] = i32t; args[0] = a; args[1] = b;
			v = callp((void *)lhook, i32t, at, 2, args);
			LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntNE, v, K32(0), ""), quit, out);
			LLVMPositionBuilderAtEnd(bd, quit); leave(K32(i + 1));	/* a block died: back to the loop */
			LLVMPositionBuilderAtEnd(bd, out);
			break; }
		case 3: a = ld(s); st(s, safeld(LLVMBuildAdd(bd, add(s, 1), a, ""))); break;
		case 4: sets(add(s, 1)); break;
		case 5: a = ld(s); b = ld(add(s, 1)); st(s, b); st(add(s, 1), a); break;
		case 6: case 7:
			a = ld(s); sets(add(s, 1));
			if (k == 6) { r = LLVMBuildLoad2(bd, i32t, vr, ""); st(r, K32(i + 1)); LLVMBuildStore(bd, add(r, 1), vr); }
			leave(a); done = 1; break;
		case 8: {
			LLVMBasicBlockRef tk = newbb(), go = newbb();
			a = ld(s); b = ld(add(s, 1)); sets(add(s, 2));
			LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntEQ, b, K32(0), ""), tk, go);
			LLVMPositionBuilderAtEnd(bd, tk); leave(a);
			LLVMPositionBuilderAtEnd(bd, go);
			break; }
		case 9:
			r = add(LLVMBuildLoad2(bd, i32t, vr, ""), -1); LLVMBuildStore(bd, r, vr);
			leave(ld(r)); done = 1; break;
		case 10: v = callp((void *)Q, i8t, 0, 0, 0); push(LLVMBuildSExt(bd, v, i32t, "")); break;
		case 11:
			if (sizeof J == 1) push(LLVMBuildZExt(bd, LLVMBuildLoad2(bd, i8t, cptr(&J), ""), i32t, ""));
			else push(LLVMBuildLoad2(bd, i32t, cptr(&J), ""));
			break;
		case 12: at[0] = i8t; args[0] = LLVMBuildTrunc(bd, ld(s), i8t, ""); callp((void *)G, LLVMVoidTypeInContext(ctx), at, 1, args); sets(add(s, 1)); break;
		case 13: case 14: case 15: case 16: case 17: case 18: case 19: case 20:
			a = ld(s); b = ld(add(s, 1)); s = add(s, 1); sets(s);
			switch (k) {
			case 13: v = LLVMBuildAdd(bd, b, a, ""); break;
			case 14: v = LLVMBuildSub(bd, b, a, ""); break;
			case 15: v = LLVMBuildMul(bd, b, a, ""); break;
			case 16: v = LLVMBuildAnd(bd, b, a, ""); break;
			case 17: v = LLVMBuildOr(bd, b, a, ""); break;
			case 18: v = LLVMBuildXor(bd, b, a, ""); break;
			case 19: v = LLVMBuildAShr(bd, b, LLVMBuildAnd(bd, a, K32(31), ""), ""); break;
			default: v = LLVMBuildZExt(bd, LLVMBuildICmp(bd, LLVMIntSLT, b, a, ""), i32t, "");
			}
			st(s, v); break;
		case 21:	/* install: then back to the loop, which drops every block */
			at[0] = i32t; args[0] = ld(s);
			st(s, callp((void *)linstall, i32t, at, 1, args));
			leave(K32(i + 1)); done = 1; break;
		default:
			if (k >= XOP0 && k < XOP0 + NENH && enh[k - XOP0].live) { ir_enh(&enh[k - XOP0]); break; }
			leave(K32(MW)); done = 1;	/* not wired: halt */
		}
		i++;
	}
	lbl[nlbl].a = p; lbl[nlbl++].b = i;
	po = LLVMCreatePassBuilderOptions();
	if ((err = LLVMRunPasses(mod_, lpasses, 0, po))) { LLVMConsumeError(err); }
	LLVMDisposePassBuilderOptions(po);
	if ((err = LLVMOrcLLJITAddLLVMIRModule(jit, LLVMOrcLLJITGetMainJITDylib(jit), LLVMOrcCreateNewThreadSafeModule(mod_, tsc)))) {
		char *msg = LLVMGetErrorMessage(err); fprintf(stderr, "llvm: %s\n", msg); LLVMDisposeErrorMessage(msg); return 0;
	}
	if ((err = LLVMOrcLLJITLookup(jit, &addr, name))) { char *msg = LLVMGetErrorMessage(err); fprintf(stderr, "llvm: %s\n", msg); LLVMDisposeErrorMessage(msg); return 0; }
	if (trace) fprintf(stderr, "llvm: %d..%d compiled\n", p, i - 1);
	return (Blk)(size_t)addr;
}
#endif
#define LD(x) ((unsigned)(x) < MW ? m[x] : 0)
static int run(int p)
{
	int s = DS0, r = RS0, w, a, b, xfer = 1;
	unsigned long long steps = 0;
#ifdef ZYLLVM
	int regs[2];
	if (!getenv("ZYNOLLVM")) llvm_init();
#endif
	while ((unsigned)p < MW) {
		if (xfer && (s < DSLIM || r > RSLIM)) { p = s < DSLIM ? MW + 1 : MW + 2; break; }
#ifdef ZYLLVM
		if (xfer && llvm_ok) {	/* at a block start: run it compiled, or count it */
			xfer = 0;
			if (!lt[p] && hot[p] < 65535 && ++hot[p] == HOT && !(lt[p] = lcompile(p))) hot[p] = 65535;
			if (lt[p]) {
				regs[0] = s; regs[1] = r;
				p = lt[p](m, regs);
				s = regs[0]; r = regs[1];
				if (need_flush) { need_flush = 0; ldrop_all(); }
				xfer = 1;
				continue;
			}
		}
#endif
		w = m[p++];
		steps++;
		if (w & 1) { m[--s] = w >> 1; continue; }
		a = m[s]; b = m[s + 1];
		switch (w / 2) {
		case 1: m[s] = LD(a); break;
		case 2:
			if ((unsigned)a < MW) {
#ifdef ZYLLVM
				if (lcov[a]) lhook(a, b); else
#endif
				m[a] = b;
			}
			s += 2; break;
		case 3: m[s] = LD(s + 1 + a); break;
		case 4: s++; break;
		case 5: m[s] = b; m[s + 1] = a; break;
		case 6: m[r++] = p; p = a; s++; xfer = 1; break;
		case 7: p = a; s++; xfer = 1; break;
		case 8: if (!b) { p = a; xfer = 1; } s += 2; break;
		case 9: p = m[--r]; xfer = 1; break;
		case 10: m[--s] = (signed char)Q(); break;
		case 11: m[--s] = J; break;
		case 12: G((char)a); s++; break;
		case 13: m[++s] = b + a; break;
		case 14: m[++s] = (int)((unsigned)b - (unsigned)a); break;
		case 15: m[++s] = (int)((unsigned)b * (unsigned)a); break;
		case 16: m[++s] = b & a; break;
		case 17: m[++s] = b | a; break;
		case 18: m[++s] = b ^ a; break;
		case 19: m[++s] = b >> (a & 31); break;
		case 20: m[++s] = b < a; break;
		case 21:
			m[s] = install(a);
#ifdef ZYLLVM
			if (need_flush) { need_flush = 0; ldrop_all(); }
#endif
			break;
		default:
			if (w / 2 >= XOP0 && w / 2 < XOP0 + NENH && enh[w / 2 - XOP0].live) s = (int)(xexec(&enh[w / 2 - XOP0], m + s) - m);
			else p = MW;	/* halt: unwired opcodes and the reserved negative ones */
		}
	}
	if (trace) fprintf(stderr, "interp: %llu steps\n", steps);
	return stopped(p);
}
#endif

int main(void)
{
	trace = getenv("ZYTRACE") != 0;
	memcpy(m + GORG, genome, sizeof genome);
#ifdef ZYJIT
	{
	int p = GORG;
	union { unsigned *u; int (*f)(long *, void *); } enter;
#ifdef __APPLE__
	code = mmap(0, CODEW * 4, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON | MAP_JIT, -1, 0);
#else
	code = mmap(0, CODEW * 4, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
	if (code == MAP_FAILED) { perror("mmap"); return 1; }
	jitwrite(1);
	build_stubs();
	jitwrite(0);
	syncicache(code, cp);
	S[0] = (long)m; S[1] = DS0; S[2] = RS0; S[3] = (long)tab; S[4] = (long)cov;
	S[5] = (long)Q; S[6] = (long)G; S[7] = (long)&J; S[8] = (long)hook;
	S[9] = (long)inst_hook; S[10] = (long)xrun;
	S[11] = (long)(m + DSLIM); S[12] = (long)(m + RSLIM);
	enter.u = x_enter;
	while ((unsigned)p < MW) {
		void *c = tab[p];
		if (!c) { jitwrite(1); c = translate(p); jitwrite(0); }
		p = enter.f(S, c);
		if (need_flush) { need_flush = 0; jitwrite(1); flush(); jitwrite(0); }
	}
	return stopped(p);
	}
#else
	return run(GORG);
#endif
	return 0;
}