diff options
Diffstat (limited to 'docs/history/17-o3-boundaries/code/core.c')
| -rw-r--r-- | docs/history/17-o3-boundaries/code/core.c | 2030 |
1 files changed, 0 insertions, 2030 deletions
diff --git a/docs/history/17-o3-boundaries/code/core.c b/docs/history/17-o3-boundaries/code/core.c deleted file mode 100644 index 7f4aa33..0000000 --- a/docs/history/17-o3-boundaries/code/core.c +++ /dev/null @@ -1,2030 +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). kind 2 - is an o3 region (below). - returns 0, or -1 bad descriptor, -2 recipe syntax, -4 code doesn't lift, - -5 too big. */ -static int o3install(int d); -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 (kind == 2) return o3install(d); - 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; -} - -/* ---- o3: optimized regions ---- - o3 code comes from the compiler as a region: a range [lo, hi) of vm words - plus the frame slots that nothing takes the address of, each with one of 7 - registers (install kind 2: [-, 2, lo, hi, n, slot, register, ...]). the region is cut into basic blocks. each - block is lifted to ssa: the vm stack is tracked symbolically, so only what - is left on it at the end of the block touches memory, the slots live in - registers across blocks (VGET reads one at block entry, the block's end - says what each one holds now), the frame pointer is var 0, and enhancements - are spliced in. every block then goes through the optimizer above. a - backend compiles the whole region at once: arm64, llvm at O3, or the - region interpreter below. the region is entered at lo and at the return - points of its calls. a register can stand for several slots (variables - whose scopes don't overlap), and spilling writes it to all of them. calls, - returns, jumps out, and anything a block can't - lift leave it: the slots go back to the frame first, so the code outside - sees the usual memory. stores to its own code drop it; it lifts again on - its next entry. */ -#define ZFP 0xA0000 /* the frame pointer word */ -#define U_VGET U_N /* a var at block entry; imm = var */ -#define U_SLD (U_N + 1) /* the stack word at offset imm from the top at block entry */ -#define RMAXV 8 -#define RMAXE 256 -enum { T_BR, T_CBR, T_JMP, T_CALL, T_RET }; -typedef struct { - int a, n, nv, delta, nso, term, cv, s1, s2, x1, x2; - int vs[RMAXV]; /* each var's value at the end, -1 if unchanged */ - int *so; /* stack words to write at the end: offset, value */ - Uop *u; -} RB; -typedef struct { - int idx, lo, hi, nv, slot[RMAXV], lifted, dead, nonat, nb, ne, maxnv; - int np, ps[32], pv[32]; /* frame slot -> var; vars in scopes that never overlap share one */ - int ent[RMAXE], entb[RMAXE]; - RB *b; - void *nat, *stub[RMAXE]; /* the backend's code */ -} Rg; -#define MAXRG 4096 -static Rg *rgs[MAXRG]; -static int nrg; -static unsigned short o3ent[MW]; /* region + 1 at an entry point */ -static unsigned char o3ei[MW]; /* which of its entries */ -static void rforget(Rg *R); /* the backend drops its code */ -static void rmark(Rg *R); /* the backend watches the region's words */ -static void rcompile(Rg *R, int eager); - -static int nargs(int op) { return op >= U_N ? 0 : uarity[op]; } -static void rclear(Rg *R) -{ - int b; - rforget(R); - for (b = 0; b < R->nb; b++) { free(R->b[b].u); free(R->b[b].so); } - free(R->b); R->b = 0; R->nb = 0; R->lifted = 0; -} -static void rdrop_all(void) { int j; for (j = 0; j < nrg; j++) if (rgs[j]->lifted) rclear(rgs[j]); } - -/* lifting one block */ -static Rg *R_; -static unsigned char *lead_; -static int *bidx_, *wl_, nw_; -static int lv_[RMAXV], lw_[RMAXV]; -#define SB 1100 -static int skv[2 * SB], stp, slo, shi; -static unsigned char skk[2 * SB]; -static int afp[MAXUOP * 4 + 16]; /* value -> 1 + its offset from fp, if it is fp + k */ -static int emap[MAXUOP * 4 + 16]; - -static int rvar(int v) -{ - if (lv_[v] < 0) { lv_[v] = raw(U_VGET, 0, 0, 0, v); if (!v) afp[lv_[v]] = 1; } - return lv_[v]; -} -static int slotvar(int off) { int j; for (j = 0; j < R_->np; j++) if (R_->ps[j] == off) return R_->pv[j]; return 0; } -static int rbin(int op, int x, int y, int z) -{ - int r = oe(op, x, y, z, 0); - if (op == U_ADD && !afp[r]) { - if (afp[x] && isk[y]) afp[r] = afp[x] + kv[y]; - else if (afp[y] && isk[x]) afp[r] = afp[y] + kv[x]; - } - return r; -} -static int rld(int a) -{ - int v; - if (isk[a] && kv[a] == ZFP) return rvar(0); - if (afp[a] && (v = slotvar(afp[a] - 1))) return rvar(v); - return oe(U_LD, a, 0, 0, 0); -} -static int rst(int a, int b) -{ - int v; - if (isk[a] && kv[a] == ZFP) return 0; /* moving the frame: not in here */ - if (afp[a] && (v = slotvar(afp[a] - 1))) { lv_[v] = b; lw_[v] = 1; return 1; } - oe(U_ST, a, b, 0, 0); - return 1; -} -static int sget(int o) -{ - if (o < -SB || o >= SB) { uerr = -6; return 0; } - if (!skk[o + SB]) { - if (o < 0) { uerr = -6; return 0; } - skv[o + SB] = raw(U_SLD, 0, 0, 0, o); skk[o + SB] = 1; - } - if (o < slo) slo = o; - if (o >= shi) shi = o + 1; - return skv[o + SB]; -} -static void sset(int o, int v) -{ - if (o < -SB || o >= SB) { uerr = -6; return; } - skv[o + SB] = v; skk[o + SB] = 1; - if (o < slo) slo = o; - if (o >= shi) shi = o + 1; -} -static int spop(void) { return sget(stp++); } -static void spush(int v) { sset(--stp, v); } -static int rblk(int t) { return t >= R_->lo && t < R_->hi && lead_[t - R_->lo] ? bidx_[t - R_->lo] : -1; } -/* an enhancement, spliced into the block */ -static int rsplice(Enh *e) -{ - int i, j; - for (j = e->nin; j--;) emap[j] = spop(); - for (i = 0; i < e->n && !uerr; i++) { - Uop *u = &e->u[i]; - int na = nargs(u->op), a = na > 0 ? emap[u->a] : 0, b = na > 1 ? emap[u->b] : 0, c = na > 2 ? emap[u->c] : 0; - if (u->op == U_LI) emap[u->d] = K(u->imm); - else if (u->op == U_LD) emap[u->d] = rld(a); - else if (u->op == U_ST) { if (!rst(a, b)) uerr = -4; } - else emap[u->d] = rbin(u->op, a, b, c); - } - for (j = 0; j < e->nout; j++) spush(emap[e->out[j]]); - return uerr; -} -static int lift_block(int bi) -{ - static const int map[] = { U_ADD, U_SUB, U_MUL, U_AND, U_OR, U_XOR, U_SAR, U_LT }; - RB *B = &R_->b[bi]; - int i = B->a, w, k, x, y, t, j, o, n = 0, *live; - on = 0; onv = 0; uerr = 0; - memset(afp, 0, sizeof afp); memset(skk, 0, sizeof skk); - stp = slo = shi = 0; - for (j = 0; j < RMAXV; j++) { lv_[j] = -1; lw_[j] = 0; } - B->term = T_JMP; B->cv = -1; B->s1 = B->s2 = -1; B->x1 = B->x2 = 0; - for (;;) { - if (uerr) return uerr; - if (i != B->a && (t = rblk(i)) >= 0) { B->term = T_BR; B->s1 = t; goto done; } - if (i < R_->lo || i >= R_->hi) goto leave_at; - w = m[i]; - if (w & 1) { spush(K(w >> 1)); i++; continue; } - k = w / 2; - switch (k) { - case 0: B->cv = K(-1); goto done; /* halt */ - case 1: x = spop(); spush(rld(x)); break; - case 2: - x = sget(stp); - if (isk[x] && kv[x] == ZFP) goto leave_at; - x = spop(); y = spop(); rst(x, y); - break; - case 3: /* pick: a constant depth */ - x = sget(stp); - if (!isk[x] || kv[x] < 0 || kv[x] > 1024) goto leave_at; - stp++; spush(sget(stp + kv[x])); - break; - case 4: stp++; break; - case 5: x = sget(stp); y = sget(stp + 1); sset(stp, y); sset(stp + 1, x); break; - case 6: B->cv = spop(); B->term = T_CALL; B->x2 = i + 1; goto done; - case 7: - x = spop(); - if (isk[x] && (t = rblk(kv[x])) >= 0) { B->term = T_BR; B->s1 = t; } - else B->cv = x; - goto done; - case 8: - x = sget(stp); - if (!isk[x]) goto leave_at; - stp++; y = spop(); - if (isk[y]) { /* a known condition */ - if (kv[y]) { i++; continue; } - if ((t = rblk(kv[x])) >= 0) { B->term = T_BR; B->s1 = t; } else B->cv = K(kv[x]); - goto done; - } - B->term = T_CBR; B->cv = y; - B->x1 = kv[x]; B->s1 = rblk(kv[x]); - B->x2 = i + 1; B->s2 = rblk(i + 1); - goto done; - case 9: B->term = T_RET; goto done; - case 13: case 14: case 15: case 16: case 17: case 18: case 19: case 20: - x = spop(); y = spop(); spush(rbin(map[k - 13], y, x, 0)); - break; - default: - if (k >= XOP0 && k < XOP0 + NENH && enh[k - XOP0].live) { if (rsplice(&enh[k - XOP0])) return uerr; break; } - goto leave_at; /* i/o, install, unwired: done the usual way */ - } - i++; - } -leave_at: - B->term = T_JMP; B->cv = K(i); -done: - if (uerr) return uerr; - B->delta = stp; - B->so = malloc((shi - slo + 1) * 2 * sizeof(int)); - B->nso = 0; - for (o = stp > slo ? stp : slo; o < shi; o++) - if (skk[o + SB]) { - x = skv[o + SB]; - if (ob[x].op == U_SLD && ob[x].imm == o) continue; /* still the word that was there */ - if (afp[x] && slotvar(afp[x] - 1)) return -7; /* a register var's address can't wait in memory */ - B->so[2 * B->nso] = o; B->so[2 * B->nso + 1] = x; B->nso++; - } - for (j = 0; j < RMAXV; j++) B->vs[j] = -1; - for (j = 1; j < R_->nv; j++) - if (lw_[j] && !(ob[lv_[j]].op == U_VGET && ob[lv_[j]].imm == j)) B->vs[j] = lv_[j]; - /* dead code: what the block leaves behind and its stores are live */ - live = calloc(onv + 1, sizeof *live); - for (j = 0; j < B->nso; j++) live[B->so[2 * j + 1]] = 1; - for (j = 1; j < R_->nv; j++) if (B->vs[j] >= 0) live[B->vs[j]] = 1; - if (B->term == T_CBR || B->term == T_JMP || B->term == T_CALL) live[B->cv] = 1; - for (i = on; i--;) { - Uop *u = &ob[i]; - if (u->op != U_ST && !live[u->d]) { u->op = -1; continue; } - k = nargs(u->op); - if (k > 0) live[u->a] = 1; - if (k > 1) live[u->b] = 1; - if (k > 2) live[u->c] = 1; - } - free(live); - B->u = malloc((on + 1) * sizeof(Uop)); - for (i = 0; i < on; i++) if (ob[i].op >= 0) B->u[n++] = ob[i]; - B->n = n; B->nv = onv; - if (onv > R_->maxnv) R_->maxnv = onv; - return 0; -} -static void addl(int x, int en) -{ - int e; - if (x < R_->lo || x >= R_->hi) return; - if (!lead_[x - R_->lo]) { lead_[x - R_->lo] = 1; wl_[nw_++] = x; } - if (en) { for (e = 0; e < R_->ne && R_->ent[e] != x; e++); if (e == R_->ne && e < RMAXE) R_->ent[R_->ne++] = x; } -} -/* blocks, then each one lifted and optimized */ -static int rlift(Rg *R) -{ - int n = R->hi - R->lo, L, i, w, k, t, b, e, r = 0, cnt; - if (R->lifted) rclear(R); - R_ = R; - lead_ = calloc(n, 1); bidx_ = malloc(n * sizeof(int)); wl_ = malloc(n * sizeof(int)); nw_ = 0; - R->ne = 0; - addl(R->lo, 1); - while (nw_) { - L = wl_[--nw_]; - for (i = L, cnt = 0;;) { - if (i >= R->hi || (i != L && lead_[i - R->lo])) break; - if (cnt++ >= 1000) { addl(i, 0); break; } - w = m[i]; - if (w & 1) { - if (i + 1 < R->hi && !(m[i + 1] & 1) && (k = m[i + 1] / 2) >= 6 && k <= 8) { - t = w >> 1; - if (k == 6) addl(i + 2, 1); /* a call comes back here */ - else if (k == 7) addl(t, 0); - else { addl(t, 0); addl(i + 2, 0); } - break; - } - i++; - continue; - } - k = w / 2; - if (k == 6) { addl(i + 1, 1); break; } - if (k == 8) { addl(i + 1, 0); break; } - if (k == 0 || k == 7 || k == 9) break; - i++; - } - } - for (i = 0, b = 0; i < n; i++) if (lead_[i]) bidx_[i] = b++; - R->nb = b; R->b = calloc(b, sizeof(RB)); R->maxnv = 0; - for (i = 0; i < n; i++) if (lead_[i]) R->b[bidx_[i]].a = R->lo + i; - for (b = 0; b < R->nb && !r; b++) r = lift_block(b); - for (e = 0; e < R->ne; e++) R->entb[e] = bidx_[R->ent[e] - R->lo]; - free(lead_); free(bidx_); free(wl_); - if (r) { - if (trace) fprintf(stderr, "o3: %d..%d doesn't lift (%d)\n", R->lo, R->hi - 1, r); - R->lifted = 1; rclear(R); return r; - } - for (e = 0; e < R->ne; e++) { o3ent[R->ent[e]] = R->idx + 1; o3ei[R->ent[e]] = e; } - R->lifted = 1; - rmark(R); - if (trace) { - int ops = 0; - for (b = 0; b < R->nb; b++) ops += R->b[b].n; - fprintf(stderr, "o3: %d..%d: %d blocks, %d entries, %d vars, %d micro-ops\n", R->lo, R->hi - 1, R->nb, R->ne, R->nv - 1, ops); - if (getenv("ZYO3DUMP")) - for (b = 0; b < R->nb; b++) { - RB *B = &R->b[b]; - fprintf(stderr, " b%d @%d: %d ops, sp %+d, term %d cv v%d s %d/%d x %d/%d\n", b, B->a, B->n, B->delta, B->term, B->cv, B->s1, B->s2, B->x1, B->x2); - for (i = 0; i < B->n; i++) { - Uop *u = &B->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 if (u->op == U_VGET) fprintf(stderr, " v%d = var%d\n", u->d, u->imm); - else if (u->op == U_SLD) fprintf(stderr, " v%d = s[%d]\n", u->d, u->imm); - else { fprintf(stderr, " v%d = %s v%d", u->d, unames[u->op], u->a); if (nargs(u->op) > 1) fprintf(stderr, " v%d", u->b); if (nargs(u->op) > 2) fprintf(stderr, " v%d", u->c); fprintf(stderr, "\n"); } - } - for (i = 0; i < B->nso; i++) fprintf(stderr, " s[%d] = v%d\n", B->so[2 * i], B->so[2 * i + 1]); - for (i = 1; i < R->nv; i++) if (B->vs[i] >= 0) fprintf(stderr, " var%d = v%d\n", i, B->vs[i]); - } - } - return 0; -} -/* install kind 2 */ -static int o3install(int d) -{ - int lo = mread(d + 2), hi = mread(d + 3), n = mread(d + 4), i, r; - Rg *R; - if (lo <= 0 || hi <= lo || hi > MW || hi - lo > 1000000 || (unsigned)n > 32 || nrg >= MAXRG) return -1; - R = calloc(1, sizeof *R); - R->idx = nrg; rgs[nrg++] = R; - R->lo = lo; R->hi = hi; R->nv = 1; R->np = n; - for (i = 1; i < RMAXV; i++) R->slot[i] = -1; - for (i = 0; i < n; i++) { /* pairs: frame slot, register 1..7 */ - int s = mread(d + 5 + 2 * i), v = mread(d + 6 + 2 * i); - if ((unsigned)s >= 4096 || v < 1 || v >= RMAXV) { R->dead = 1; return -1; } - R->ps[i] = s; R->pv[i] = v; - if (R->slot[v] < 0) R->slot[v] = s; - if (v >= R->nv) R->nv = v + 1; - } - for (i = 1; i < R->nv; i++) if (R->slot[i] < 0) R->slot[i] = R->ps[0]; - if ((r = rlift(R))) { R->dead = 1; return r; } - rcompile(R, 1); - return 0; -} -/* the region entered at p, lifted again if it has to be, or 0 */ -static Rg *rat(int p) -{ - Rg *R = rgs[o3ent[p] - 1]; - if (R->dead) { o3ent[p] = 0; return 0; } - if (!R->lifted && rlift(R)) { R->dead = 1; o3ent[p] = 0; return 0; } - if (o3ei[p] >= R->ne || R->ent[o3ei[p]] != p) { o3ent[p] = 0; return 0; } - return R; -} - -#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(0xa9b97bfd); /* stp x29, x30, [sp, #-112]! */ - 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(0xa9056ffa); /* stp x26, x27, [sp, #80] */ - E(0xf90033fc); /* str x28, [sp, #96] */ - 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(0xa9456ffa); /* ldp x26, x27, [sp, #80] */ - E(0xf94033fc); /* ldr x28, [sp, #96] */ - E(0xa8c77bfd); /* ldp x29, x30, [sp], #112 */ - 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; - rdrop_all(); - 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 < nrg; j++) - if (rgs[j]->lifted && rgs[j]->lo <= a && a < rgs[j]->hi) { - if (trace) fprintf(stderr, "o3: dropped %d..%d (a store to %d)\n", rgs[j]->lo, rgs[j]->hi - 1, a); - rclear(rgs[j]); - memset(cov, 0, sizeof cov); - 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; - for (j = 0; j < nrg; j++) if (rgs[j]->lifted) rmark(rgs[j]); - 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); -} - -/* one micro-op, operands in registers. tmp is a scratch register for the - remainders; x16 and x17 are scratch too. */ -static void emit_uop(int op, int d, int a, int b, int c, int tmp) -{ - switch (op) { - 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, tmp, a, b); E(0x1b008000 | b << 16 | a << 10 | tmp << 5 | d); break; /* msub */ - case U_UREM: op3(0x1ac00800, tmp, a, b); E(0x1b008000 | b << 16 | a << 10 | tmp << 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; - } -} -/* an enhancement, inlined: inputs from the data stack into w0..w15, the - optimized micro-ops, outputs back. constants are made where they're used, - or folded into the instruction (a fixed address, a small addend). */ -static int ekc[MAXUOP * 4 + 16], ekv[MAXUOP * 4 + 16]; -static void emit_enh_e(Enh *e, int s) -{ - signed char *r = e->reg; - int i, j, delta, na; - 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 (i = 0; i < e->nv; i++) ekc[i] = 0; - for (i = 0; i < e->n; i++) if (e->u[i].op == U_LI) { ekc[e->u[i].d] = 1; ekv[e->u[i].d] = e->u[i].imm; } -#define EOP(x) (ekc[x] ? (li(r[x], ekv[x]), r[x]) : r[x]) - 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 = 0, b = 0, c = 0; - if (u->op == U_LI) continue; - if (u->op == U_LD && ekc[u->a] && (unsigned)ekv[u->a] < MW) { - if (ekv[u->a] < 4096) ldr_u(d, M, ekv[u->a] * 4); else ldr_rr(d, M, EOP(u->a), UXTW); - continue; - } - if ((u->op == U_ADD || u->op == U_SUB) && ekc[u->b] && ekv[u->b] >= 0 && ekv[u->b] < 4096) { - E((u->op == U_ADD ? 0x11000000 : 0x51000000) | ekv[u->b] << 10 | EOP(u->a) << 5 | d); - continue; - } - na = nargs(u->op); - if (na > 0) a = EOP(u->a); - if (na > 1) b = EOP(u->b); - if (na > 2) c = EOP(u->c); - emit_uop(u->op, d, a, b, c, 16); - } - 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(EOP(e->out[j]), SP, 4 * (e->nout - 1 - j)); -#undef EOP -} -static void emit_enh(int s) { emit_enh_e(&enh[s], s); } -/* lit .. lit xop: the enhancement specialized on the literals that feed its - last inputs, so the optimizer sees them as constants (x / 7 becomes a - multiply, lfa(k) a load and an add). 0 if it worked. */ -static int spec_enh(int s, int *ks, int nk, Enh *te) -{ - Enh *e = &enh[s]; - int nin = e->nin - nk, i, j, out[8], na; - static int mp[MAXUOP * 4 + 16]; - if (e->nv > MAXUOP * 4) return -1; - un = 0; unv = nin; uerr = 0; - for (j = 0; j < nin; j++) mp[j] = j; - for (j = 0; j < nk; j++) mp[nin + j] = unew(U_LI, 0, 0, 0, ks[j]); - for (i = 0; i < e->n; i++) { - Uop *u = &e->u[i]; - na = nargs(u->op); - j = unew(u->op, na > 0 ? mp[u->a] : 0, na > 1 ? mp[u->b] : 0, na > 2 ? mp[u->c] : 0, u->imm); - if (u->op != U_ST) mp[u->d] = j; - } - for (j = 0; j < e->nout; j++) out[j] = mp[e->out[j]]; - memset(te, 0, sizeof *te); - if (uerr || optimize(te, nin, out, e->nout)) return -1; - regalloc(te); - if (!te->reg) { free(te->u); return -1; } - return 0; -} - -/* ---- o3 regions on arm64 ---- - vars live in w0..w7 (w0 is the frame pointer), block values in w8..w14, - w26..w28 and the homes of unused vars. constants have no register: they - are made in a scratch register where they're used (w16, w17, w15), or - folded into the instruction. x15..x17 are scratch. */ -static signed char rreg[MAXUOP * 4 + 16]; -static unsigned char rk[MAXUOP * 4 + 16], rhome[MAXUOP * 4 + 16]; -static int rkv[MAXUOP * 4 + 16], rlast[MAXUOP * 4 + 16]; -static unsigned **rfa; static int *rfb, rnf; /* branches to blocks, fixed up at the end */ - -static void rforget(Rg *R) -{ - int e; - if (R->nat) for (e = 0; e < R->ne; e++) if (tab[R->ent[e]] == R->stub[e]) tab[R->ent[e]] = 0; - R->nat = 0; -} -static void rmark(Rg *R) { int x; for (x = R->lo; x < R->hi; x++) cov[x] = 1; } -static int ralloc(Rg *R, RB *B) -{ - int i, j, k, n = B->n; - unsigned fr = 0x7f00u | 0x1c000000u; /* w8..w14, w26..w28 */ - for (j = R->nv; j < 8; j++) fr |= 1u << j; - for (i = 0; i < B->nv; i++) { rlast[i] = -2; rk[i] = 0; rhome[i] = 0; rreg[i] = -1; } - for (i = 0; i < n; i++) { - Uop *u = &B->u[i]; int na = nargs(u->op); - if (na > 0) rlast[u->a] = i; - if (na > 1) rlast[u->b] = i; - if (na > 2) rlast[u->c] = i; - } - for (j = 0; j < B->nso; j++) rlast[B->so[2 * j + 1]] = n; - for (j = 1; j < R->nv; j++) if (B->vs[j] >= 0) rlast[B->vs[j]] = n; - if (B->term == T_CBR || B->term == T_JMP || B->term == T_CALL) rlast[B->cv] = n; - for (i = 0; i < n; i++) { - Uop *u = &B->u[i]; int na = nargs(u->op), ops[3], d = u->d; - ops[0] = u->a; ops[1] = u->b; ops[2] = u->c; - for (j = 0; j < na; j++) { int x = ops[j]; if (rlast[x] == i && rreg[x] >= 0 && !rhome[x]) fr |= 1u << rreg[x]; } - if (u->op == U_ST) continue; - if (u->op == U_LI) { rk[d] = 1; rkv[d] = u->imm; continue; } - if (u->op == U_VGET) { rreg[d] = (signed char)u->imm; rhome[d] = 1; continue; } - for (k = 0; k < 32 && !(fr >> k & 1); k++); - if (k == 32) return -1; - fr &= ~(1u << k); rreg[d] = (signed char)k; - if (rlast[d] == -2) fr |= 1u << k; - } - return 0; -} -static int ropr(int x, int s) { if (rk[x]) { li(s, rkv[x]); return s; } return rreg[x]; } -/* w t <-> the data stack word o places from the top at block entry */ -static void rsw(int t, int o, int store) -{ - int by = o * 4; - if (by >= 0 && by < 16384) { if (store) str_u(t, SP, by); else ldr_u(t, SP, by); } - else if (by >= -256 && by < 256) E((store ? 0xb8000000u : 0xb8400000u) | (unsigned)(by & 0x1ff) << 12 | SP << 5 | t); /* stur, ldur */ - else { li(16, by); addx_ext(16, SP, 16, SXTW); if (store) str_u(t, 16, 0); else ldr_u(t, 16, 0); } -} -static void addsp(int by) -{ - if (by > 0 && by < 4096) E(0x91000294 | by << 10); - else if (by < 0 && -by < 4096) E(0xd1000294 | (-by) << 10); - else if (by) { li(16, by); addx_ext(SP, SP, 16, SXTW); } -} -static void rspill(Rg *R) -{ - int v; - for (v = 0; v < R->np; v++) { E(0x11000000 | R->ps[v] << 10 | 16); str_rr(R->pv[v], M, 16, UXTW); } /* add w16, w0, #slot */ -} -static void rload(Rg *R) -{ - int v; - li(16, ZFP); ldr_rr(0, M, 16, UXTW); - for (v = 1; v < R->nv; v++) { E(0x11000000 | R->slot[v] << 10 | 16); ldr_rr(v, M, 16, UXTW); } -} -static void rexitk(Rg *R, int t) { rspill(R); li(W0, t); b_to(x_disp); } -static void rbranch(int b) { rfa[rnf] = cp; rfb[rnf++] = b; E(0x14000000); } -/* m[a] = v, checked like the jit's own stores: a word some translation covers goes through hook */ -static void rstore(int a, int v) -{ - unsigned *p1, *p2, *p3; - int j; - E(0x7144001f | a << 5); /* cmp wa, #MW */ - p1 = cp; E(0x54000002); /* b.hs done */ - ldrx_u(15, ST, 32); - E(0x38604800 | a << 16 | 15 << 5 | 15); /* ldrb w15, [x15, wa, uxtw] */ - p2 = cp; E(0x35000000 | 15); /* cbnz w15, slow */ - str_rr(v, M, a, UXTW); - p3 = cp; E(0x14000000); - cb_fix(p2, cp); - E(0xd10203ff); /* sub sp, sp, #128 */ - for (j = 0; j < 16; j += 2) E(0xa9000000 | (j / 2 * 2) << 15 | (j + 1) << 10 | 31 << 5 | j); /* stp xj, xj+1, [sp, #8j] */ - movw(15, a); movw(1, v); movw(0, 15); - ldrx_u(16, ST, 64); blr(16); - for (j = 0; j < 16; j += 2) E(0xa9400000 | (j / 2 * 2) << 15 | (j + 1) << 10 | 31 << 5 | j); - E(0x910203ff); /* add sp, sp, #128 */ - cb_fix(p1, cp); - *p3 |= (cp - p3) & 0x3ffffff; -} -static void rpmove(Rg *R, RB *B) -{ - int dst[RMAXV], src[RMAXV], n = 0, j, k, x; - for (j = 1; j < R->nv; j++) - if (B->vs[j] >= 0 && !rk[B->vs[j]] && rreg[B->vs[j]] != j) { dst[n] = j; src[n] = rreg[B->vs[j]]; n++; } - while (n) { - for (j = 0; j < n; j++) { for (k = 0; k < n && src[k] != dst[j]; k++); if (k == n) break; } - if (j < n) { movw(dst[j], src[j]); n--; dst[j] = dst[n]; src[j] = src[n]; continue; } - x = src[0]; movw(16, x); /* a cycle: park one */ - for (k = 0; k < n; k++) if (src[k] == x) src[k] = 16; - } - for (j = 1; j < R->nv; j++) if (B->vs[j] >= 0 && rk[B->vs[j]]) li(j, rkv[B->vs[j]]); -} -static void emit_uop(int op, int d, int a, int b, int c, int tmp); -static int remit(Rg *R, int bi) -{ - RB *B = &R->b[bi]; - int i, j, d, a, b, c; - unsigned *p; - if (ralloc(R, B)) return -1; - for (i = 0; i < B->n; i++) { - Uop *u = &B->u[i]; - switch (u->op) { - case U_LI: case U_VGET: continue; - case U_SLD: rsw(rreg[u->d], u->imm, 0); continue; - case U_LD: - if (rk[u->a] && (unsigned)rkv[u->a] < MW) { /* a fixed address */ - if (rkv[u->a] < 4096) ldr_u(rreg[u->d], M, rkv[u->a] * 4); - else { li(16, rkv[u->a]); ldr_rr(rreg[u->d], M, 16, UXTW); } - continue; - } - break; - case U_ST: a = ropr(u->a, 16); rstore(a, ropr(u->b, 17)); continue; - case U_ADD: case U_SUB: - if (rk[u->b] && rkv[u->b] >= 0 && rkv[u->b] < 4096) { - E((u->op == U_ADD ? 0x11000000 : 0x51000000) | rkv[u->b] << 10 | ropr(u->a, 16) << 5 | rreg[u->d]); - continue; - } - break; - } - d = rreg[u->d]; - a = nargs(u->op) > 0 ? ropr(u->a, 16) : 0; - b = nargs(u->op) > 1 ? ropr(u->b, 17) : 0; - c = nargs(u->op) > 2 ? ropr(u->c, 15) : 0; - emit_uop(u->op, d, a, b, c, 15); - } - for (j = 0; j < B->nso; j++) rsw(ropr(B->so[2 * j + 1], 17), B->so[2 * j], 1); - if (B->term == T_CBR || B->term == T_JMP || B->term == T_CALL) { - if (rk[B->cv]) li(17, rkv[B->cv]); else movw(17, rreg[B->cv]); - } - addsp(B->delta * 4); - rpmove(R, B); - switch (B->term) { - case T_BR: rbranch(B->s1); break; - case T_CBR: - if (B->s1 >= 0) { rfa[rnf] = cp; rfb[rnf++] = B->s1; E(0x34000000 | 17); } /* cbz w17, taken */ - else { p = cp; E(0x35000000 | 17); rexitk(R, B->x1); cb_fix(p, cp); } - if (B->s2 >= 0) rbranch(B->s2); else rexitk(R, B->x2); - break; - case T_CALL: rspill(R); li(16, B->x2); str_post(16, RP, 4); movw(W0, 17); b_to(x_disp); break; - case T_RET: rspill(R); ldr_pre(W0, RP, -4); b_to(x_disp); break; - default: rspill(R); movw(W0, 17); b_to(x_disp); - } - return 0; -} -/* the whole region: entry stubs that load the vars, then the blocks */ -static int rjit(Rg *R, int wr) -{ - unsigned *start = cp, **lab; - int b, e, j, bad = 0; - long need = (long)(R->hi - R->lo) * 96 + (long)R->ne * 32 + 4096; - if (need > (code + CODEW) - cp) return -1; - if (wr) jitwrite(1); - lab = malloc((R->nb + 1) * sizeof *lab); - rfa = malloc((2 * R->nb + R->ne + 4) * sizeof *rfa); rfb = malloc((2 * R->nb + R->ne + 4) * sizeof *rfb); rnf = 0; - for (e = 0; e < R->ne; e++) { R->stub[e] = cp; rload(R); rbranch(R->entb[e]); } - for (b = 0; b < R->nb && !bad; b++) { lab[b] = cp; bad = remit(R, b); } - if (!bad) { - for (j = 0; j < rnf; j++) { - unsigned *at = rfa[j], *to = lab[rfb[j]]; - if ((*at & 0xfc000000u) == 0x14000000u) *at |= (to - at) & 0x3ffffff; else cb_fix(at, to); - } - R->nat = start; - for (e = 0; e < R->ne; e++) tab[R->ent[e]] = R->stub[e]; - syncicache(start, cp); - if (trace) fprintf(stderr, "o3: %d..%d -> %ld bytes of arm64\n", R->lo, R->hi - 1, (long)((char *)cp - (char *)start)); - } else { - cp = start; - if (trace) fprintf(stderr, "o3: %d..%d: a block needs too many registers\n", R->lo, R->hi - 1); - } - free(lab); free(rfa); free(rfb); - if (wr) jitwrite(0); - return bad; -} -static void rcompile(Rg *R, int eager) -{ - if (R->nat || R->nonat) return; - if (rjit(R, eager) && cp - code < CODEW / 2) R->nonat = 1; /* registers, not space: give up on it */ -} - -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(); - if (o3ent[p]) { /* an o3 region starts here */ - Rg *R = rat(p); - if (R) { rcompile(R, 0); if (R->nat && tab[p]) return tab[p]; } - } - 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) { - int L = 0, x, s, nk, ks[8], j; - Enh te; - while (L < 8 && i + L < MW && (m[i + L] & 1)) L++; - x = i + L < MW ? m[i + L] : 1; - if (!(x & 1) && (s = x / 2 - XOP0) >= 0 && s < NENH && enh[s].live && enh[s].nin) { - nk = L < enh[s].nin ? L : enh[s].nin; - for (j = 0; j < nk; j++) ks[j] = m[i + L - nk + j] >> 1; - if (!spec_enh(s, ks, nk, &te)) { - for (j = 0; j < L - nk; j++) { li(X9, m[i + j] >> 1); str_pre(X9, SP, -4); } - for (j = 0; j <= L; j++) cov[i + j] = 1; - emit_enh_e(&te, s); - free(te.u); free(te.reg); - i += L + 1; n += L; - continue; - } - } - 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 unsigned char rcov[MW]; /* 1 on the words of a lifted o3 region */ -static int rdrop(int a); -static void ldrop_all(void) -{ - rdrop_all(); memset(rcov, 0, sizeof rcov); - 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 (rcov[a] && rdrop(a)) 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; - for (j = 0; j < nrg; j++) if (rgs[j]->lifted) for (x = rgs[j]->lo; x < rgs[j]->hi; 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, ""); -} -/* one micro-op as ir: the same semantics as ev() */ -static LLVMValueRef ir_op(int op, LLVMValueRef a, LLVMValueRef b, LLVMValueRef c) -{ - LLVMValueRef z = K32(0), q, d, t, c1, c2, r = 0; - LLVMTypeRef i64 = i64t; - switch (op) { - 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 (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 (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 = op == U_MULHS ? LLVMBuildSExt(bd, a, i64, "") : LLVMBuildZExt(bd, a, i64, ""); - LLVMValueRef y = 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; - } - return r; -} -/* an enhancement as ir */ -static void ir_enh(Enh *e) -{ - LLVMValueRef *v = calloc(e->nv + 1, sizeof *v), s = gets(); - int i, j; - 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_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; } - default: r = ir_op(u->op, a, b, c); - } - 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 - -/* ---- o3 regions without the arm64 jit: compiled by llvm, or run here ---- */ -#ifndef ZYLLVM -static unsigned char rcov[MW]; /* 1 on the words of a lifted region */ -#endif -static int rvals[MAXUOP * 4 + 16]; -static int rdrop(int a) /* a store landed on region code: drop those regions */ -{ - int j, x, hit = 0; - for (j = 0; j < nrg; j++) - if (rgs[j]->lifted && rgs[j]->lo <= a && a < rgs[j]->hi) { - if (trace) fprintf(stderr, "o3: dropped %d..%d (a store to %d: %d)\n", rgs[j]->lo, rgs[j]->hi - 1, a, m[a]); - rclear(rgs[j]); hit = 1; - } - if (hit) { - memset(rcov, 0, sizeof rcov); - for (j = 0; j < nrg; j++) if (rgs[j]->lifted) for (x = rgs[j]->lo; x < rgs[j]->hi; x++) rcov[x] = 1; - } - return hit; -} -#ifdef ZYLLVM -static int lhook(int a, int v); -#define RSTORE(a, b) do { if ((unsigned)(a) < MW) { if (lcov[a]) lhook(a, b); else m[a] = b; } } while (0) -#else -#define RSTORE(a, b) do { if ((unsigned)(a) < MW) { m[a] = b; if (rcov[a]) rdrop(a); } } while (0) -#endif -/* the region interpreter: ssa values in an array, vars in locals */ -static int rexec(Rg *R, int e, int *ps, int *pr) -{ - int var[RMAXV], nv2[RMAXV], *v = rvals, s = *ps, r = *pr, b = R->entb[e], fp, j, i, t, o; - var[0] = fp = mread(ZFP); - for (j = 1; j < R->nv; j++) var[j] = mread(fp + R->slot[j]); - for (;;) { - RB *B = &R->b[b]; - for (i = 0; i < B->n; i++) { - Uop *u = &B->u[i]; - switch (u->op) { - case U_LI: v[u->d] = u->imm; break; - case U_VGET: v[u->d] = var[u->imm]; break; - case U_SLD: v[u->d] = mread(s + u->imm); break; - case U_LD: v[u->d] = mread(v[u->a]); break; - case U_ST: RSTORE(v[u->a], v[u->b]); break; - default: v[u->d] = ev(u->op, v[u->a], v[u->b], v[u->c]); - } - } - for (j = 0; j < B->nso; j++) { o = s + B->so[2 * j]; if ((unsigned)o < MW) m[o] = v[B->so[2 * j + 1]]; } - s += B->delta; - for (j = 1; j < R->nv; j++) if (B->vs[j] >= 0) nv2[j] = v[B->vs[j]]; - for (j = 1; j < R->nv; j++) if (B->vs[j] >= 0) var[j] = nv2[j]; - if (B->term == T_BR) { b = B->s1; continue; } - if (B->term == T_CBR) { - if (!v[B->cv]) { if (B->s1 >= 0) { b = B->s1; continue; } t = B->x1; } - else { if (B->s2 >= 0) { b = B->s2; continue; } t = B->x2; } - } else if (B->term == T_JMP) t = v[B->cv]; - else if (B->term == T_CALL) { m[r++] = B->x2; t = v[B->cv]; } - else t = m[--r]; - break; - } - for (j = 0; j < R->np; j++) if ((unsigned)(fp + R->ps[j]) < MW) m[fp + R->ps[j]] = var[R->pv[j]]; - *ps = s; *pr = r; - return t; -} -#ifndef ZYLLVM -static void rforget(Rg *R) { (void)R; } -static void rmark(Rg *R) { int x; for (x = R->lo; x < R->hi; x++) rcov[x] = 1; } -static void rcompile(Rg *R, int eager) { (void)R; (void)eager; } -#endif -#ifdef ZYLLVM - -/* ---- o3 regions in llvm: one function per region, vars in allocas (so - mem2reg makes them ssa across blocks), each block's micro-ops as ir, then - the O3 pipeline. f(mem, regs, entry) returns the next vm address. */ -typedef int (*RFn)(int *mem, int *regs, int ent); -static int nregions; -static LLVMValueRef rvv[RMAXV]; -static void rforget(Rg *R) { R->nat = 0; } -static void rmark(Rg *R) { int x; for (x = R->lo; x < R->hi; x++) rcov[x] = lcov[x] = 1; } -static void rspill_ir(Rg *R) -{ - LLVMValueRef fp = LLVMBuildLoad2(bd, i32t, rvv[0], ""); - int j; - for (j = 0; j < R->np; j++) st(add(fp, R->ps[j]), LLVMBuildLoad2(bd, i32t, rvv[R->pv[j]], "")); -} -static LLVMBasicBlockRef rexit_bb(Rg *R, int t) -{ - LLVMBasicBlockRef here = LLVMGetInsertBlock(bd), x = newbb(); - LLVMPositionBuilderAtEnd(bd, x); - rspill_ir(R); leave(K32(t)); - LLVMPositionBuilderAtEnd(bd, here); - return x; -} -/* m[a] = v, through lhook if some compiled code covers the word */ -static void rstore_ir(LLVMValueRef a, LLVMValueRef b) -{ - LLVMBasicBlockRef in = newbb(), cv = newbb(), plain = newbb(), out = newbb(); - LLVMValueRef v, args[2]; LLVMTypeRef at[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; - callp((void *)lhook, i32t, at, 2, args); - LLVMBuildBr(bd, out); - LLVMPositionBuilderAtEnd(bd, out); -} -static void *lregion(Rg *R) -{ - char name[40]; LLVMTypeRef pt[3], ft; LLVMValueRef ent, sw, *val, s0, fp, r; - LLVMBasicBlockRef *bb, eb, dflt; - LLVMOrcExecutorAddress addr; LLVMErrorRef err; LLVMPassBuilderOptionsRef po; - int b, i, j, e; - sprintf(name, "o3_%d_%d", R->lo, nregions++); - mod_ = LLVMModuleCreateWithNameInContext(name, ctx); - pt[0] = ptrt; pt[1] = ptrt; pt[2] = i32t; - ft = LLVMFunctionType(i32t, pt, 3, 0); - fn_ = LLVMAddFunction(mod_, name, ft); - vm_ = LLVMGetParam(fn_, 0); vregs = LLVMGetParam(fn_, 1); ent = LLVMGetParam(fn_, 2); - LLVMPositionBuilderAtEnd(bd, newbb()); - vs = LLVMBuildAlloca(bd, i32t, "s"); vr = LLVMBuildAlloca(bd, i32t, "r"); - for (j = 0; j < R->nv; j++) rvv[j] = LLVMBuildAlloca(bd, i32t, ""); - { 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); } - bb = malloc(R->nb * sizeof *bb); - for (b = 0; b < R->nb; b++) bb[b] = newbb(); - dflt = newbb(); - sw = LLVMBuildSwitch(bd, ent, dflt, (unsigned)R->ne); - for (e = 0; e < R->ne; e++) { - eb = newbb(); - LLVMAddCase(sw, K32(e), eb); - LLVMPositionBuilderAtEnd(bd, eb); - fp = ld(K32(ZFP)); - LLVMBuildStore(bd, fp, rvv[0]); - for (j = 1; j < R->nv; j++) LLVMBuildStore(bd, safeld(add(fp, R->slot[j])), rvv[j]); - LLVMBuildBr(bd, bb[R->entb[e]]); - } - LLVMPositionBuilderAtEnd(bd, dflt); leave(K32(-1)); - val = calloc(R->maxnv + 1, sizeof *val); - for (b = 0; b < R->nb; b++) { - RB *B = &R->b[b]; - LLVMPositionBuilderAtEnd(bd, bb[b]); - s0 = gets(); - for (i = 0; i < B->n; i++) { - Uop *u = &B->u[i]; - LLVMValueRef a = nargs(u->op) > 0 ? val[u->a] : 0, x = nargs(u->op) > 1 ? val[u->b] : 0, c = nargs(u->op) > 2 ? val[u->c] : 0; - switch (u->op) { - case U_LI: val[u->d] = K32(u->imm); break; - case U_VGET: val[u->d] = LLVMBuildLoad2(bd, i32t, rvv[u->imm], ""); break; - case U_SLD: val[u->d] = ld(add(s0, u->imm)); break; - case U_LD: val[u->d] = safeld(a); break; - case U_ST: rstore_ir(a, x); break; - default: val[u->d] = ir_op(u->op, a, x, c); - } - } - for (j = 0; j < B->nso; j++) st(add(s0, B->so[2 * j]), val[B->so[2 * j + 1]]); - sets(add(s0, B->delta)); - for (j = 1; j < R->nv; j++) if (B->vs[j] >= 0) LLVMBuildStore(bd, val[B->vs[j]], rvv[j]); - switch (B->term) { - case T_BR: LLVMBuildBr(bd, bb[B->s1]); break; - case T_CBR: - LLVMBuildCondBr(bd, LLVMBuildICmp(bd, LLVMIntEQ, val[B->cv], K32(0), ""), - B->s1 >= 0 ? bb[B->s1] : rexit_bb(R, B->x1), B->s2 >= 0 ? bb[B->s2] : rexit_bb(R, B->x2)); - break; - case T_CALL: - r = LLVMBuildLoad2(bd, i32t, vr, ""); st(r, K32(B->x2)); LLVMBuildStore(bd, add(r, 1), vr); - rspill_ir(R); leave(val[B->cv]); - break; - case T_RET: - r = add(LLVMBuildLoad2(bd, i32t, vr, ""), -1); LLVMBuildStore(bd, r, vr); - rspill_ir(R); leave(ld(r)); - break; - default: rspill_ir(R); leave(val[B->cv]); - } - } - free(val); free(bb); - po = LLVMCreatePassBuilderOptions(); - if ((err = LLVMRunPasses(mod_, "default<O3>", 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, "o3: %d..%d compiled by llvm\n", R->lo, R->hi - 1); - return (void *)(size_t)addr; -} -static void rcompile(Rg *R, int eager) -{ - (void)eager; - if (R->nat || R->nonat || !llvm_ok) return; - if (!(R->nat = lregion(R))) R->nonat = 1; -} -#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; } - if (xfer && o3ent[p]) { /* an o3 region */ - Rg *R = rat(p); - if (R) { -#ifdef ZYLLVM - rcompile(R, 0); - if (R->nat) { regs[0] = s; regs[1] = r; p = ((RFn)R->nat)(m, regs, o3ei[p]); s = regs[0]; r = regs[1]; } - else -#endif - p = rexec(R, o3ei[p], &s, &r); - continue; - } - } -#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 -#else - if (rcov[a]) { m[a] = b; rdrop(a); } 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(); } -#else - if (need_flush) { need_flush = 0; rdrop_all(); memset(rcov, 0, sizeof rcov); } -#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; -} |