diff options
| author | 2026-10-14 09:09:21 +0330 | |
|---|---|---|
| committer | 2026-10-14 09:09:21 +0330 | |
| commit | dc7f7407e08f54e4a2a3c1d1723b2a7d6959532d (patch) | |
| tree | d1de9f471a99951c57896f85b5e5523eeb96cee1 /docs/history/13-gap-fixes/code/core.c | |
| parent | todo: sync docs, examples and fixtures with the include format, and test acto... (diff) | |
docs: archive the frozen stage code as one compressed tarball
docs/history kept six stages with a full copy of the project under code/,
3.8 mb of sources duplicated from stage to stage and already superseded. store
them as docs/history/code-snapshots.tar.gz, 0.66 mb, and extract one in place
to read it. every stage's notes.md stays browsable, and the index says where the
code went and how to get it back.
the top-level README points at the archive too. its other two links into
docs/history, 21-micro and 35-bench, were notes that were never kept and do not
resolve; the index now records that.
Diffstat (limited to 'docs/history/13-gap-fixes/code/core.c')
| -rw-r--r-- | docs/history/13-gap-fixes/code/core.c | 1183 |
1 files changed, 0 insertions, 1183 deletions
diff --git a/docs/history/13-gap-fixes/code/core.c b/docs/history/13-gap-fixes/code/core.c deleted file mode 100644 index ce353c8..0000000 --- a/docs/history/13-gap-fixes/code/core.c +++ /dev/null @@ -1,1183 +0,0 @@ -/* 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; -} |
