#include "module-run.h" #include #include #include /* ---- Compiled code (docs/design/021) * A module's blocks (its handlers' and views' code, and the folds' blocks * in them) as AArch64 code, made when the module loads. A block's code runs * a frame as run does: branches and loops are branches and calls, every * other instruction a call of the executor's step (module.c) unless it is * written here, as the hot ones are. The operand stack stays in the frame; * its height at each instruction is known when the module loads (the * verifier records it), so a slot is a fixed place in it. */ #if defined(__aarch64__) && defined(__linux__) #include #include struct PureJit { unsigned char *memory; /* the code, executable */ size_t size; struct Entry { uint32_t length; PureCompiled code; } *by_start; /* a block's code by its start */ uint32_t code_count; }; /* ---- Emitting instructions */ typedef struct { size_t at; int label; unsigned kind; } Fixup; /* kind: 0 B, 1 B.cond and CBZ/CBNZ, 2 TBZ/TBNZ */ typedef struct { uint32_t *words; size_t count, room; long *labels; /* each label's word, or -1 */ size_t label_count, label_room; Fixup *fixups; size_t fixup_count, fixup_room; bool failed; } Emit; static bool grow_array(void **array, size_t *room, size_t need, size_t size) { if (need <= *room) return true; size_t next = *room ? *room : 256; while (next < need) next *= 2; void *grown = realloc(*array, next * size); if (!grown) return false; *array = grown; *room = next; return true; } static void put(Emit *e, uint32_t word) { if (!grow_array((void **)&e->words, &e->room, e->count + 1, sizeof(*e->words))) { e->failed = true; return; } e->words[e->count++] = word; } static int new_label(Emit *e) { if (!grow_array((void **)&e->labels, &e->label_room, e->label_count + 1, sizeof(*e->labels))) { e->failed = true; return 0; } e->labels[e->label_count] = -1; return (int)e->label_count++; } static void bind(Emit *e, int label) { if (!e->failed) e->labels[label] = (long)e->count; } static void branch_to(Emit *e, uint32_t word, int label, unsigned kind) { if (!grow_array((void **)&e->fixups, &e->fixup_room, e->fixup_count + 1, sizeof(*e->fixups))) { e->failed = true; return; } e->fixups[e->fixup_count++] = (Fixup){e->count, label, kind}; put(e, word); } /* Branches given their offsets, once every label is bound. */ static bool resolve(Emit *e) { for (size_t i = 0; i < e->fixup_count && !e->failed; ++i) { Fixup f = e->fixups[i]; long target = e->labels[f.label]; if (target < 0) return false; long offset = target - (long)f.at; if (f.kind == 0) { if (offset < -(1L << 25) || offset >= (1L << 25)) return false; e->words[f.at] |= (uint32_t)offset & 0x3FFFFFF; } else if (f.kind == 2) { if (offset < -(1L << 13) || offset >= (1L << 13)) return false; e->words[f.at] |= ((uint32_t)offset & 0x3FFF) << 5; } else { if (offset < -(1L << 18) || offset >= (1L << 18)) return false; e->words[f.at] |= ((uint32_t)offset & 0x7FFFF) << 5; } } return !e->failed; } enum { X0 = 0, X1 = 1, X9 = 9, X10 = 10, X11 = 11, X12 = 12, X13 = 13, X14 = 14, X15 = 15, X16 = 16, X19 = 19, X20 = 20, X21 = 21, X22 = 22, X23 = 23, X24 = 24, X29 = 29, X30 = 30, SP = 31, XZR = 31 }; enum { D0 = 0, D1 = 1, D2 = 2, D3 = 3, D4 = 4, D8 = 8 }; enum { EQ = 0, NE = 1, HS = 2, LO = 3, MI = 4, PL = 5, VS = 6, VC = 7, HI = 8, LS = 9, GE = 10, LT = 11, GT = 12, LE = 13 }; /* A 64-bit constant into register d. */ static void mov_imm(Emit *e, unsigned d, uint64_t value) { put(e, 0xD2800000 | (uint32_t)(value & 0xFFFF) << 5 | d); /* MOVZ */ for (unsigned k = 1; k < 4; ++k) if (value >> (16 * k) & 0xFFFF) put(e, 0xF2800000 | k << 21 | (uint32_t)(value >> (16 * k) & 0xFFFF) << 5 | d); /* MOVK */ } /* LDR/STR of 64 bits at base + offset (a multiple of 8 below 32 KiB), or through x16 past it. */ static void load64(Emit *e, unsigned t, unsigned base, size_t offset) { if (offset % 8 == 0 && offset < 32768) { put(e, 0xF9400000 | (uint32_t)(offset / 8) << 10 | base << 5 | t); return; } mov_imm(e, X16, offset); put(e, 0xF8606800 | X16 << 16 | base << 5 | t); /* LDR Xt, [Xbase, X16] */ } static void store64(Emit *e, unsigned t, unsigned base, size_t offset) { if (offset % 8 == 0 && offset < 32768) { put(e, 0xF9000000 | (uint32_t)(offset / 8) << 10 | base << 5 | t); return; } mov_imm(e, X16, offset); put(e, 0xF8206800 | X16 << 16 | base << 5 | t); /* STR Xt, [Xbase, X16] */ } static void load_d(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0xFD400000 | (uint32_t)(offset / 8) << 10 | base << 5 | t); } static void store_d(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0xFD000000 | (uint32_t)(offset / 8) << 10 | base << 5 | t); } static void store_h(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0x79000000 | (uint32_t)(offset / 2) << 10 | base << 5 | t); } static void store_w(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0xB9000000 | (uint32_t)(offset / 4) << 10 | base << 5 | t); } static void mov_reg(Emit *e, unsigned d, unsigned n) { put(e, 0xAA0003E0 | n << 16 | d); } static void load8(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0x39400000 | (uint32_t)offset << 10 | base << 5 | t); } static void store8(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0x39000000 | (uint32_t)offset << 10 | base << 5 | t); } static void load16(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0x79400000 | (uint32_t)(offset / 2) << 10 | base << 5 | t); } static void load32(Emit *e, unsigned t, unsigned base, size_t offset) { put(e, 0xB9400000 | (uint32_t)(offset / 4) << 10 | base << 5 | t); } static void load64_index(Emit *e, unsigned t, unsigned base, unsigned index) { put(e, 0xF8607800 | index << 16 | base << 5 | t); } /* [base, index, LSL #3] */ static void add_imm(Emit *e, unsigned d, unsigned n, uint32_t imm) { put(e, 0x91000000 | imm << 10 | n << 5 | d); } /* imm < 4096 */ static void sub_imm(Emit *e, unsigned d, unsigned n, uint32_t imm) { put(e, 0xD1000000 | imm << 10 | n << 5 | d); } static void sub_w_imm(Emit *e, unsigned d, unsigned n, uint32_t imm) { put(e, 0x51000000 | imm << 10 | n << 5 | d); } static void add_reg(Emit *e, unsigned d, unsigned n, unsigned m) { put(e, 0x8B000000 | m << 16 | n << 5 | d); } static void sub_reg(Emit *e, unsigned d, unsigned n, unsigned m) { put(e, 0xCB000000 | m << 16 | n << 5 | d); } static void cmp_reg(Emit *e, unsigned n, unsigned m) { put(e, 0xEB00001F | m << 16 | n << 5); } static void cmp_imm(Emit *e, unsigned n, uint32_t imm) { put(e, 0xF100001F | imm << 10 | n << 5); } static void csel(Emit *e, unsigned d, unsigned n, unsigned m, unsigned cond) { put(e, 0x9A800000 | m << 16 | cond << 12 | n << 5 | d); } static void lsr_imm(Emit *e, unsigned d, unsigned n, unsigned shift) { put(e, 0xD340FC00 | shift << 16 | n << 5 | d); } static void lsr_reg(Emit *e, unsigned d, unsigned n, unsigned m) { put(e, 0x9AC02400 | m << 16 | n << 5 | d); } static void cset(Emit *e, unsigned d, unsigned cond) { put(e, 0x1A9F07E0 | (cond ^ 1) << 12 | d); } static void and_w(Emit *e, unsigned d, unsigned n, unsigned m) { put(e, 0x0A000000 | m << 16 | n << 5 | d); } static void orr_w(Emit *e, unsigned d, unsigned n, unsigned m) { put(e, 0x2A000000 | m << 16 | n << 5 | d); } static void and_w_one(Emit *e, unsigned d, unsigned n) { put(e, 0x12000000 | n << 5 | d); } /* AND Wd, Wn, #1 */ static void fp3(Emit *e, uint32_t op, unsigned d, unsigned n, unsigned m) { put(e, op | m << 16 | n << 5 | d); } static void fp2(Emit *e, uint32_t op, unsigned d, unsigned n) { put(e, op | n << 5 | d); } static const uint32_t FADD = 0x1E602800; static const uint32_t FSUB = 0x1E603800; static const uint32_t FMUL = 0x1E600800; static const uint32_t FDIV = 0x1E601800; static const uint32_t FMIN = 0x1E605800; static const uint32_t FMAX = 0x1E604800; static const uint32_t FABS = 0x1E60C000; static const uint32_t FNEG = 0x1E614000; static const uint32_t FRINTM = 0x1E654000; static const uint32_t UCVTF_X = 0x9E630000; static const uint32_t UCVTF_W = 0x1E630000; static const uint32_t FCVTZU_X = 0x9E790000; static const uint32_t FMOV_DX = 0x9E670000; static void fcmp(Emit *e, unsigned n, unsigned m) { put(e, 0x1E602000 | m << 16 | n << 5); } static void fcmp_zero(Emit *e, unsigned n) { put(e, 0x1E602008 | n << 5); } /* STP/LDP of two 64-bit registers at sp + offset (pre-indexed down, or plain). */ static void stp(Emit *e, unsigned a, unsigned b2, int offset, bool pre) { put(e, (pre ? 0xA9800000 : 0xA9000000) | ((uint32_t)(offset / 8) & 0x7F) << 15 | b2 << 10 | SP << 5 | a); } static void ldp(Emit *e, unsigned a, unsigned b2, int offset, bool post) { put(e, (post ? 0xA8C00000 : 0xA9400000) | ((uint32_t)(offset / 8) & 0x7F) << 15 | b2 << 10 | SP << 5 | a); } static void mov_w(Emit *e, unsigned d, uint32_t value) { /* MOVZ (and MOVK) Wd */ put(e, 0x52800000 | (value & 0xFFFF) << 5 | d); if (value >> 16) put(e, 0x72A00000 | (value >> 16) << 5 | d); } /* A call of a C function at address (in x16). */ static void call(Emit *e, uintptr_t address) { mov_imm(e, X16, address); put(e, 0xD63F0000 | X16 << 5); /* BLR x16 */ } static void b(Emit *e, int label) { branch_to(e, 0x14000000, label, 0); } static void b_cond(Emit *e, unsigned cond, int label) { branch_to(e, 0x54000000 | cond, label, 1); } static void cbz_w(Emit *e, unsigned t, int label) { branch_to(e, 0x34000000 | t, label, 1); } static void cbnz_w(Emit *e, unsigned t, int label) { branch_to(e, 0x35000000 | t, label, 1); } static void cbz_x(Emit *e, unsigned t, int label) { branch_to(e, 0xB4000000 | t, label, 1); } static void cbnz_x(Emit *e, unsigned t, int label) { branch_to(e, 0xB5000000 | t, label, 1); } static void cmp_w_imm(Emit *e, unsigned n, uint32_t imm) { put(e, 0x7100001F | imm << 10 | n << 5); } /* ---- A block */ enum { SLOT = sizeof(Slot) }; typedef struct { uint32_t start, end; int parent; int again, after; unsigned depth; uint32_t at; } LoopAt; /* again: its iteration's label; after: past it; depth: the loops open in it; at: its EACH or LOOP */ typedef struct { int label; PureFault kind; uint32_t pc; } FaultAt; typedef struct { const PureModule *m; PureBlock block; Emit *e; uint8_t *height; /* absolute, by instruction of the block */ int *loop_of; /* the innermost loop each instruction is in, or -1 */ int *opens; /* the loop an EACH or a LOOP opens */ LoopAt *loops; unsigned loop_count; int *op_label; /* each instruction's, and the block's end */ int exit; /* w0 holds how it went */ FaultAt *faults; /* the faults its code may give, each a short stub after it */ size_t fault_count, fault_room; } Block; /* A label whose code gives a fault of kind at pc. */ static int fault_at(Block *k, PureFault kind, uint32_t pc) { for (size_t i = 0; i < k->fault_count; ++i) if (k->faults[i].kind == kind && k->faults[i].pc == pc) return k->faults[i].label; if (!grow_array((void **)&k->faults, &k->fault_room, k->fault_count + 1, sizeof(*k->faults))) { k->e->failed = true; return k->exit; } k->faults[k->fault_count] = (FaultAt){new_label(k->e), kind, pc}; return k->faults[k->fault_count++].label; } static void fault_stubs(Block *k) { Emit *e = k->e; for (size_t i = 0; i < k->fault_count; ++i) { bind(e, k->faults[i].label); mov_w(e, X9, (uint32_t)k->faults[i].kind); store_w(e, X9, X19, offsetof(Frame, kind)); mov_w(e, X9, k->faults[i].pc); store_w(e, X9, X19, offsetof(Frame, fault_pc)); mov_w(e, X0, STEP_FAULT); b(e, k->exit); } } static void set_sp(Block *k, unsigned height) { mov_imm(k->e, X9, height); store64(k->e, X9, X19, offsetof(Frame, sp)); } /* Where a branch at from to target lands: the iteration of the innermost loop around from that ends at target, else target's instruction. */ static int landing(const Block *k, uint32_t from, uint32_t target) { for (int l = k->loop_of[from - k->block.start]; l >= 0; l = k->loops[l].parent) if (k->loops[l].end == target) return k->loops[l].again; return k->op_label[target - k->block.start]; } /* A loop's block ran once (iterate, module.c, as code): again (its block's * first instruction, an empty block's being this), or the loop closed. */ static void iteration(Block *k, const LoopAt *l) { Emit *e = k->e; const PureOp *op = &k->m->code[l->at]; int again = l->start == l->end ? l->again : k->op_label[l->start - k->block.start], done = new_label(e); load64(e, X9, X19, offsetof(Frame, loops)); add_imm(e, X9, X9, (uint32_t)((l->depth - 1) * sizeof(Loop))); load64(e, X10, X9, offsetof(Loop, mark)); /* the arena as the block began */ load64(e, X11, X19, offsetof(Frame, arena)); store64(e, X10, X11, offsetof(PureArena, used)); if (op->op == PURE_OP_EACH) { int counted = new_label(e); load8(e, X12, X9, offsetof(Loop, walk) + offsetof(Walk, removed)); load64(e, X13, X9, offsetof(Loop, walk) + offsetof(Walk, at)); cbnz_w(e, X12, counted); add_imm(e, X13, X13, 1); bind(e, counted); store8(e, XZR, X9, offsetof(Loop, walk) + offsetof(Walk, removed)); store64(e, X13, X9, offsetof(Loop, walk) + offsetof(Walk, at)); load64(e, X14, X9, offsetof(Loop, walk) + offsetof(Walk, end)); cmp_reg(e, X13, X14); b_cond(e, HS, done); load64(e, X10, X24, (op->arg >> 8 & 0xFF) * sizeof(PureList *)); /* the list walked: at most its items now */ load64(e, X10, X10, pure_list_layout[LIST_COUNT_AT]); cmp_reg(e, X13, X10); b_cond(e, HS, done); store64(e, X13, X22, offsetof(Event, row)); b(e, again); bind(e, done); load64(e, X10, X9, offsetof(Loop, around)); store64(e, X10, X22, offsetof(Event, walk)); load64(e, X10, X9, offsetof(Loop, row)); store64(e, X10, X22, offsetof(Event, row)); } else { load64(e, X13, X9, offsetof(Loop, k)); add_imm(e, X13, X13, 1); load64(e, X14, X9, offsetof(Loop, count)); cmp_reg(e, X13, X14); b_cond(e, HS, done); store64(e, X13, X9, offsetof(Loop, k)); /* its work counts each time round: its block and the LOOP, past the budget a fault at the LOOP */ uint64_t cost = (uint64_t)(l->end - l->start) + 1; int budgeted = new_label(e); load64(e, X10, X23, offsetof(PureApp, work_budget)); cbnz_x(e, X10, budgeted); mov_imm(e, X10, PURE_WORK_DEFAULT); bind(e, budgeted); load64(e, X11, X23, offsetof(PureApp, work)); sub_reg(e, X12, X10, X11); mov_imm(e, X15, cost); cmp_reg(e, X12, X15); b_cond(e, LO, fault_at(k, PURE_FAULT_WORK, l->at)); add_reg(e, X11, X11, X15); store64(e, X11, X23, offsetof(PureApp, work)); load64(e, X10, X9, offsetof(Loop, slot)); /* the slot: low + k */ if (op->arg & PURE_LOOP_INTEGER) { load64(e, X11, X9, offsetof(Loop, low)); add_reg(e, X11, X11, X13); store64(e, X11, X10, 0); } else { load_d(e, D0, X9, offsetof(Loop, low)); fp2(e, UCVTF_X, D1, X13); fp3(e, FADD, D0, D0, D1); store_d(e, D0, X10, 0); } b(e, again); bind(e, done); } load32(e, X10, X9, offsetof(Loop, outer)); /* closed */ store_w(e, X10, X19, offsetof(Frame, end)); load32(e, X10, X19, offsetof(Frame, depth)); sub_w_imm(e, X10, X10, 1); store_w(e, X10, X19, offsetof(Frame, depth)); } /* The iterations of the loops ending at pc, innermost first. */ static void loop_ends(Block *k, uint32_t pc) { Emit *e = k->e; for (uint64_t done = 0;;) { /* innermost first: the loop ending at pc nested deepest among those not done */ int pick = -1, deepest = -1; for (unsigned l = 0; l < k->loop_count; ++l) { if (k->loops[l].end != pc || (l < 64 && done >> l & 1)) continue; int depth = 0; for (int p = k->loops[l].parent; p >= 0; p = k->loops[p].parent) ++depth; if (depth > deepest) deepest = depth, pick = (int)l; } if (pick < 0) break; done |= UINT64_C(1) << pick; bind(e, k->loops[pick].again); iteration(k, &k->loops[pick]); bind(e, k->loops[pick].after); } } static void call_step(Block *k, uintptr_t function, uint32_t pc, unsigned height) { Emit *e = k->e; set_sp(k, height); mov_reg(e, X0, X19); mov_w(e, X1, pc); call(e, function); } /* Slots: a value's 8 bytes at its start, an index's list at owner. */ #define AT(h) ((size_t)(h) * SLOT) enum { OWNER = offsetof(Slot, bytes) + offsetof(PureBytes, owner) }; static void owner_is(Emit *e, unsigned height, uint32_t owner) { mov_w(e, X11, owner & 0xFFFF); store_h(e, X11, X20, AT(height) + OWNER); } /* The key in d0 as a bit of a list's (in x10) key set when it keeps one as * bits: the bit in w15 (0 or 1); to slow when it keeps none or a table. */ static void member_bit(Block *k, int slow, int out) { Emit *e = k->e; int none = new_label(e), got = new_label(e); load64(e, X11, X10, pure_list_layout[LIST_MEMBERS_AT]); cbz_x(e, X11, slow); load8(e, X12, X10, pure_list_layout[LIST_BITMAP_AT]); cbz_w(e, X12, slow); fp2(e, FCVTZU_X, X13, D0); /* a whole number from 0 below 2^22 (-0 as 0), else none */ fp2(e, UCVTF_X, D1, X13); fcmp(e, D0, D1); b_cond(e, NE, none); mov_imm(e, X14, (uint64_t)1 << 22); cmp_reg(e, X13, X14); b_cond(e, HS, none); load64(e, X14, X10, pure_list_layout[LIST_MEMBER_CAPACITY_AT]); lsr_imm(e, X15, X13, 6); cmp_reg(e, X15, X14); b_cond(e, HS, none); load64_index(e, X15, X11, X15); lsr_reg(e, X15, X15, X13); and_w_one(e, X15, X15); b(e, got); bind(e, none); mov_w(e, X15, 0); bind(e, got); (void)out; } /* Two numbers (d0 below d1) to one, a fault past the finite (NON_FINITE). */ static void binary(Block *k, const PureOp *op, uint32_t pc, unsigned height) { Emit *e = k->e; load_d(e, D0, X20, AT(height - 2)); load_d(e, D1, X20, AT(height - 1)); unsigned cond = EQ; switch (op->op) { case PURE_OP_ADD: fp3(e, FADD, D0, D0, D1); break; case PURE_OP_SUB: fp3(e, FSUB, D0, D0, D1); break; case PURE_OP_MUL: fp3(e, FMUL, D0, D0, D1); break; case PURE_OP_DIV: fcmp_zero(e, D1); b_cond(e, EQ, fault_at(k, PURE_FAULT_DIVIDE, pc)); fp3(e, FDIV, D0, D0, D1); break; case PURE_OP_MIN: fp3(e, FMIN, D0, D0, D1); break; case PURE_OP_MAX: fp3(e, FMAX, D0, D0, D1); break; case PURE_OP_AND: case PURE_OP_OR: fcmp_zero(e, D0); cset(e, X9, NE); fcmp_zero(e, D1); cset(e, X10, NE); if (op->op == PURE_OP_AND) and_w(e, X9, X9, X10); else orr_w(e, X9, X9, X10); fp2(e, UCVTF_W, D0, X9); store_d(e, D0, X20, AT(height - 2)); return; default: /* a comparison: a bool */ cond = op->op == PURE_OP_LT ? MI : op->op == PURE_OP_LE ? LS : op->op == PURE_OP_GT ? GT : op->op == PURE_OP_GE ? GE : op->op == PURE_OP_EQ ? EQ : NE; fcmp(e, D0, D1); cset(e, X9, cond); fp2(e, UCVTF_W, D0, X9); store_d(e, D0, X20, AT(height - 2)); return; } fp2(e, FABS, D2, D0); /* finite: below infinity (a NaN is unordered: HS too) */ fcmp(e, D2, D8); b_cond(e, HS, fault_at(k, PURE_FAULT_NON_FINITE, pc)); store_d(e, D0, X20, AT(height - 2)); } static void compile_op(Block *k, uint32_t pc) { Emit *e = k->e; const PureOp *op = &k->m->code[pc]; unsigned height = k->height[pc - k->block.start]; uint32_t arg = op->arg; switch (op->op) { case PURE_OP_CONST: mov_imm(e, X9, (uint64_t)op->integer); /* the bits: a number's, a bool's or an i64's */ store64(e, X9, X20, AT(height)); return; case PURE_OP_LOAD: load64(e, X9, X21, arg * sizeof(PureValue)); store64(e, X9, X20, AT(height)); return; case PURE_OP_STORE: case PURE_OP_CUR_STORE: load64(e, X9, X20, AT(height - 1)); store64(e, X9, X21, arg * sizeof(PureValue)); return; case PURE_OP_LOCAL_LOAD: load64(e, X10, X22, offsetof(Event, locals)); load64(e, X9, X10, (arg & 0xFF) * sizeof(PureValue)); store64(e, X9, X20, AT(height)); owner_is(e, height, arg >> 16); return; case PURE_OP_LOCAL_STORE: load64(e, X9, X20, AT(height - 1)); load64(e, X10, X22, offsetof(Event, locals)); store64(e, X9, X10, (arg & 0xFF) * sizeof(PureValue)); return; case PURE_OP_ROW: case PURE_OP_OUTER_ROW: load64(e, X9, X22, op->op == PURE_OP_ROW ? offsetof(Event, row) : offsetof(Event, outer)); fp2(e, UCVTF_X, D0, X9); store_d(e, D0, X20, AT(height)); owner_is(e, height, arg); return; case PURE_OP_INDEX_FIRST: store64(e, XZR, X20, AT(height)); owner_is(e, height, arg); return; case PURE_OP_LIST_COUNT: load64(e, X10, X24, arg * sizeof(PureList *)); load64(e, X9, X10, pure_list_layout[LIST_COUNT_AT]); fp2(e, UCVTF_X, D0, X9); store_d(e, D0, X20, AT(height)); return; case PURE_OP_NOT: load_d(e, D0, X20, AT(height - 1)); fcmp_zero(e, D0); cset(e, X9, EQ); fp2(e, UCVTF_W, D0, X9); store_d(e, D0, X20, AT(height - 1)); return; case PURE_OP_NEG: case PURE_OP_FLOOR: load_d(e, D0, X20, AT(height - 1)); fp2(e, op->op == PURE_OP_NEG ? FNEG : FRINTM, D0, D0); store_d(e, D0, X20, AT(height - 1)); return; case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_MIN: case PURE_OP_MAX: case PURE_OP_LT: case PURE_OP_LE: case PURE_OP_GT: case PURE_OP_GE: case PURE_OP_EQ: case PURE_OP_NE: case PURE_OP_AND: case PURE_OP_OR: binary(k, op, pc, height); return; case PURE_OP_INDEX_MOVE: { /* within its list: from 0 to its last item, by a whole number (else LIMIT) */ load_d(e, D0, X20, AT(height - 2)); load_d(e, D1, X20, AT(height - 1)); fp2(e, FRINTM, D2, D1); fcmp(e, D1, D2); b_cond(e, NE, fault_at(k, PURE_FAULT_LIMIT, pc)); load16(e, X10, X20, AT(height - 2) + OWNER); load64_index(e, X11, X24, X10); load64(e, X12, X11, pure_list_layout[LIST_COUNT_AT]); sub_imm(e, X13, X12, 1); cmp_imm(e, X12, 0); csel(e, X13, XZR, X13, EQ); fp2(e, UCVTF_X, D3, X13); fp3(e, FADD, D0, D0, D1); fp3(e, FMIN, D0, D0, D3); fp2(e, FMOV_DX, D4, XZR); fp3(e, FMAX, D0, D4, D0); store_d(e, D0, X20, AT(height - 2)); return; } case PURE_OP_LIST_HAS: { if (op->plan & PLAN_TEXT) break; int slow = new_label(e), done = new_label(e); load64(e, X10, X24, arg * sizeof(PureList *)); load_d(e, D0, X20, AT(height - 1)); member_bit(k, slow, done); fp2(e, UCVTF_W, D0, X15); store_d(e, D0, X20, AT(height - 1)); b(e, done); bind(e, slow); call_step(k, (uintptr_t)pure_run_step, pc, height); cbnz_w(e, X0, k->exit); bind(e, done); return; } case PURE_OP_LIST_FIND: { /* joined to its ITEM_GET: a DENSE list's field at its key */ const PureOp *get = &k->m->code[pc + 1]; if (!(op->plan & PLAN_JOINED) || op->plan & PLAN_TEXT || get->plan & PLAN_TEXT) break; int slow = new_label(e), done = new_label(e); load64(e, X10, X24, arg * sizeof(PureList *)); load8(e, X12, X10, pure_list_layout[LIST_FORM_AT]); cmp_w_imm(e, X12, 2); /* DENSE */ b_cond(e, NE, slow); load_d(e, D0, X20, AT(height - 1)); member_bit(k, slow, done); cbz_w(e, X15, fault_at(k, PURE_FAULT_NOT_FOUND, pc)); load64(e, X14, X10, pure_list_layout[LIST_COLUMNS_AT] + item_field(get->arg) * sizeof(void *)); load64_index(e, X9, X14, X13); store64(e, X9, X20, AT(height - 1)); b(e, done); bind(e, slow); call_step(k, (uintptr_t)pure_run_step, pc, height); cbnz_w(e, X0, k->exit); bind(e, done); return; } case PURE_OP_ITEM_GET: { /* a FLAT list's cell by its column */ if (op->plan & PLAN_TEXT) break; int slow = new_label(e), done = new_label(e); load64(e, X10, X24, list_of(arg) * sizeof(PureList *)); load8(e, X12, X10, pure_list_layout[LIST_FORM_AT]); cmp_w_imm(e, X12, 1); /* FLAT */ b_cond(e, NE, slow); load_d(e, D0, X20, AT(height - 1)); fp2(e, FCVTZU_X, X13, D0); load64(e, X12, X10, pure_list_layout[LIST_COUNT_AT]); cmp_reg(e, X13, X12); b_cond(e, HS, fault_at(k, PURE_FAULT_NOT_FOUND, pc)); load64(e, X14, X10, pure_list_layout[LIST_COLUMNS_AT] + item_field(arg) * sizeof(void *)); load64_index(e, X9, X14, X13); store64(e, X9, X20, AT(height - 1)); b(e, done); bind(e, slow); call_step(k, (uintptr_t)pure_run_step, pc, height); cbnz_w(e, X0, k->exit); bind(e, done); return; } case PURE_OP_JZ: load_d(e, 0, X20, (height - 1) * SLOT); put(e, 0x1E602008); /* FCMP d0, #0.0 */ b_cond(e, EQ, landing(k, pc, op->arg)); return; case PURE_OP_JMP: b(e, landing(k, pc, op->arg)); return; case PURE_OP_EACH: case PURE_OP_LOOP: { call_step(k, op->op == PURE_OP_EACH ? (uintptr_t)pure_run_each : (uintptr_t)pure_run_loop, pc, height); int open = new_label(e); cbz_w(e, X0, open); cmp_w_imm(e, X0, STEP_SKIP); b_cond(e, NE, k->exit); b(e, k->loops[k->opens[pc - k->block.start]].after); /* none: past its block, where its iteration would end */ bind(e, open); return; } case PURE_OP_BREAK: { int l = k->loop_of[pc - k->block.start]; mov_reg(e, X0, X19); call(e, (uintptr_t)pure_run_break); b(e, k->loops[l].after); return; } default: break; } call_step(k, (uintptr_t)pure_run_step, pc, height); cbnz_w(e, X0, k->exit); } /* The block's heights (absolute: a loop's block is verified from its own start), its loops, and each instruction's. */ static bool shape_block(Block *k) { const PureModule *m = k->m; uint32_t n = k->block.length; k->height = malloc(n + 1); k->loop_of = malloc((n + 1) * sizeof(*k->loop_of)); k->op_label = malloc((n + 1) * sizeof(*k->op_label)); k->loops = malloc((n + 1) * sizeof(*k->loops)); k->opens = malloc((n + 1) * sizeof(*k->opens)); if (!k->height || !k->loop_of || !k->op_label || !k->loops || !k->opens) return false; int open[PURE_MODULE_NESTING + 1]; unsigned base[PURE_MODULE_NESTING + 1], depth = 0; base[0] = 0; for (uint32_t pc = k->block.start; pc < k->block.start + n;) { while (depth && pc >= k->loops[open[depth - 1]].end) --depth; const PureOp *op = &m->code[pc]; unsigned at = base[depth] + m->height[pc]; k->height[pc - k->block.start] = (uint8_t)at; k->loop_of[pc - k->block.start] = depth ? open[depth - 1] : -1; if (op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) { unsigned pops = op->op == PURE_OP_LOOP || op->arg & PURE_EACH_SLICED ? 2 : 0; LoopAt *l = &k->loops[k->loop_count]; *l = (LoopAt){pc + 1, pc + 1 + (op->arg >> 16), depth ? open[depth - 1] : -1, new_label(k->e), new_label(k->e), depth + 1, pc}; k->opens[pc - k->block.start] = (int)k->loop_count; open[depth] = (int)k->loop_count++; base[++depth] = at - pops; ++pc; continue; } if (op->op == PURE_OP_FOLD) { /* its block is its own: not this one's code */ for (uint32_t i = pc + 1; i < after(op, pc); ++i) k->loop_of[i - k->block.start] = -1, k->height[i - k->block.start] = 0; } pc = after(op, pc); } for (uint32_t i = 0; i <= n; ++i) k->op_label[i] = new_label(k->e); k->exit = new_label(k->e); return !k->e->failed; } /* The block's code into e (leaving the stack end_height high), its start's word in *entry. */ static bool compile_block(const PureModule *m, PureBlock block, unsigned end_height, Emit *e, size_t *entry) { Block k = {.m = m, .block = block, .e = e}; bool ok = shape_block(&k); if (ok) { *entry = e->count; stp(e, X29, X30, -80, true); put(e, 0x910003FD); /* MOV x29, sp */ stp(e, X19, X20, 16, false); stp(e, X21, X22, 32, false); stp(e, X23, X24, 48, false); put(e, 0xFD000000 | (64 / 8) << 10 | SP << 5 | D8); /* STR d8, [sp, #64] */ mov_reg(e, X19, X0); load64(e, X20, X19, offsetof(Frame, stack)); load64(e, X21, X19, offsetof(Frame, values)); load64(e, X22, X19, offsetof(Frame, ev)); load64(e, X23, X19, offsetof(Frame, app)); mov_imm(e, X24, offsetof(PureApp, lists)); add_reg(e, X24, X23, X24); /* the app's lists */ mov_imm(e, X9, UINT64_C(0x7FF0000000000000)); fp2(e, FMOV_DX, D8, X9); /* infinity */ for (uint32_t pc = block.start; pc < block.start + block.length;) { loop_ends(&k, pc); bind(e, k.op_label[pc - block.start]); compile_op(&k, pc); const PureOp *op = &m->code[pc]; pc = op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP ? pc + 1 : after(op, pc); } uint32_t end = block.start + block.length; loop_ends(&k, end); bind(e, k.op_label[block.length]); set_sp(&k, end_height); /* the block ran: what it leaves (a view's value) is the frame's to give */ mov_w(e, X0, STEP_NEXT); bind(e, k.exit); put(e, 0xFD400000 | (64 / 8) << 10 | SP << 5 | D8); /* LDR d8, [sp, #64] */ ldp(e, X23, X24, 48, false); ldp(e, X21, X22, 32, false); ldp(e, X19, X20, 16, false); ldp(e, X29, X30, 80, true); put(e, 0xD65F03C0); /* RET */ fault_stubs(&k); } free(k.height); free(k.loop_of); free(k.op_label); free(k.loops); free(k.opens); free(k.faults); return ok && !e->failed; } /* ---- The module */ typedef struct { PureBlock block; unsigned leaves; size_t entry; } Made; /* A block to make, leaving leaves values on the stack. */ static bool want(PureBlock block, unsigned leaves, Made **made, size_t *count, size_t *room) { for (size_t i = 0; i < *count; ++i) if ((*made)[i].block.start == block.start && (*made)[i].block.length == block.length) return true; if (!grow_array((void **)made, room, *count + 1, sizeof(**made))) return false; (*made)[(*count)++] = (Made){block, leaves, 0}; return true; } struct PureJit *pure_jit_make(const PureModule *m) { const char *enabled = getenv("PURE_JIT"); if ((enabled && !strcmp(enabled, "0")) || !m->height || !m->code_count) return NULL; Made *made = NULL; size_t count = 0, room = 0; bool ok = true; /* The handlers' and the views' code, then the folds' blocks in what is made (they run as blocks of their own). */ for (uint32_t h = 0; ok && h < m->handlers; ++h) ok = want(m->handler[h].code, 0, &made, &count, &room); for (uint32_t v = 0; ok && v < m->views; ++v) if (m->view_code[v].length) ok = want(m->view_code[v], 1, &made, &count, &room); for (size_t i = 0; ok && i < count; ++i) for (uint32_t pc = made[i].block.start; ok && pc < made[i].block.start + made[i].block.length; ++pc) { const PureOp *op = &m->code[pc]; unsigned how = op->arg & PURE_FOLD_KIND; /* count and first leave a bool; the others a value and a bool */ if (op->op == PURE_OP_FOLD) ok = want((PureBlock){pc + 1, op->arg >> 16}, how == PURE_FOLD_COUNT || how == PURE_FOLD_FIRST ? 1 : 2, &made, &count, &room); } Emit e = {0}; for (size_t i = 0; ok && i < count; ++i) ok = compile_block(m, made[i].block, made[i].leaves, &e, &made[i].entry); ok = ok && resolve(&e); const char *dump = getenv("PURE_JIT_DUMP"); /* the code as it is made, to read with objdump -b binary -m aarch64 */ FILE *file = ok && dump ? fopen(dump, "wb") : NULL; if (file) { fwrite(e.words, sizeof(uint32_t), e.count, file); fclose(file); } struct PureJit *jit = NULL; /* by start, an empty block's at the code's end too */ if (ok && (jit = calloc(1, sizeof(*jit))) && (jit->by_start = calloc(m->code_count + 1, sizeof(*jit->by_start)))) { jit->size = (e.count * sizeof(uint32_t) + 4095) & ~(size_t)4095; jit->code_count = m->code_count; void *memory = mmap(NULL, jit->size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (memory != MAP_FAILED) { jit->memory = memory; memcpy(memory, e.words, e.count * sizeof(uint32_t)); __builtin___clear_cache((char *)memory, (char *)memory + e.count * sizeof(uint32_t)); if (mprotect(memory, jit->size, PROT_READ | PROT_EXEC)) ok = false; for (size_t i = 0; ok && i < count; ++i) jit->by_start[made[i].block.start] = (struct Entry){made[i].block.length, (PureCompiled)((uintptr_t)jit->memory + made[i].entry * sizeof(uint32_t))}; } else ok = false; } else ok = false; free(e.words); free(e.labels); free(e.fixups); free(made); if (!ok) { pure_jit_free(jit); return NULL; } return jit; } void pure_jit_free(struct PureJit *jit) { if (!jit) return; if (jit->memory) munmap(jit->memory, jit->size); free(jit->by_start); free(jit); } PureCompiled pure_jit_code(const struct PureJit *jit, PureBlock block) { if (!jit || block.start > jit->code_count) return NULL; const struct Entry *entry = &jit->by_start[block.start]; return entry->code && entry->length == block.length ? entry->code : NULL; } #else struct PureJit *pure_jit_make(const PureModule *m) { (void)m; return NULL; } void pure_jit_free(struct PureJit *jit) { (void)jit; } PureCompiled pure_jit_code(const struct PureJit *jit, PureBlock block) { (void)jit, (void)block; return NULL; } #endif