From 5a4da8bac457f0e70e690a572eba9cf754e69a37 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 23 Jun 2024 23:31:46 +0300 Subject: initial interpeter testing --- src/common.h | 126 ++++++++++++++++++++++++++++++++++++++ src/ejit.c | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/interp.c | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/source.mk | 2 + src/vec.h | 95 +++++++++++++++++++++++++++++ 5 files changed, 603 insertions(+) create mode 100644 src/common.h create mode 100644 src/ejit.c create mode 100644 src/interp.c create mode 100644 src/source.mk create mode 100644 src/vec.h (limited to 'src') diff --git a/src/common.h b/src/common.h new file mode 100644 index 0000000..21e881b --- /dev/null +++ b/src/common.h @@ -0,0 +1,126 @@ +#ifndef EJIT_COMMON_H +#define EJIT_COMMON_H + +#include +#include "vec.h" + +enum ejit_opcode { + MOVI, + MOVR, + MOVR_F, + + LDI8, + LDI16, + LDI32, + LDI64, + LDIU8, + LDIU16, + LDIU32, + LDIU64, + LDIF, + LDID, + + LDXI8, + LDXI16, + LDXI32, + LDXI64, + LDXIU8, + LDXIU16, + LDXIU32, + LDXIU64, + LDXIF, + LDXID, + + STI8, + STI16, + STI32, + STI64, + STIU8, + STIU16, + STIU32, + STIU64, + STIF, + STID, + + STXI8, + STXI16, + STXI32, + STXI64, + STXIU8, + STXIU16, + STXIU32, + STXIU64, + STXIF, + STXID, + + ADDR, + ADDR_F, + SUBR, + SUBR_F, + + BLTR, + + PARAM, + PARAM_F, + + ARG, + ARG_I, + ARG_F, + ARG_FI, + + ESCAPEI, + ESCAPEI_F, + + CALLI, + CALLI_F, + + RET, + RET_I, + RET_F, + RET_FI, + + RETVAL, + RETVAL_F, + + START, + END, + + OPCODE_COUNT, +}; + +struct ejit_insn { + union { + enum ejit_opcode op; + void *addr; + }; + + size_t r0; + size_t r1; + union { + size_t r2; + void *p; + long o; + double d; + }; +}; + +struct ejit_func { + struct vec insns; + enum ejit_type rtype; + + size_t gpr; + size_t fpr; + + void *arena; + size_t size; +}; + + +union interp_ret { + long r; + double d; +}; + +union interp_ret ejit_interp(struct ejit_func *f, size_t argc, struct ejit_arg args[argc], bool run, void ***labels_wb); + +#endif /* EJIT_COMMON_H */ diff --git a/src/ejit.c b/src/ejit.c new file mode 100644 index 0000000..bd5a652 --- /dev/null +++ b/src/ejit.c @@ -0,0 +1,190 @@ +#include +#include + +#include + +#include "common.h" + +static void emit_insn_i(struct ejit_func *f, enum ejit_opcode op, size_t r0, size_t r1, long o) +{ + struct ejit_insn i = {.op = op, .r0 = r0, .r1 = r1, .o = o}; + vec_append(&f->insns, &i); +} + +static void emit_insn_r(struct ejit_func *f, enum ejit_opcode op, size_t r0, size_t r1, size_t r2) +{ + struct ejit_insn i = {.op = op, .r0 = r0, .r1 = r1, .r2 = r2}; + vec_append(&f->insns, &i); +} + +static void emit_insn_p(struct ejit_func *f, enum ejit_opcode op, size_t r0, size_t r1, void *p) +{ + struct ejit_insn i = {.op = op, .r0 = r0, .r1 = r1, .p = p}; + vec_append(&f->insns, &i); +} + +static void emit_insn_f(struct ejit_func *f, enum ejit_opcode op, size_t r0, size_t r1, double d) +{ + struct ejit_insn i = {.op = op, .r0 = r0, .r1 = r1, .d = d}; + vec_append(&f->insns, &i); +} + +struct ejit_func *ejit_create_func(enum ejit_type rtype, size_t argc, const struct ejit_operand args[argc]) +{ + struct ejit_func *f = malloc(sizeof(struct ejit_func)); + assert(f); + + f->rtype = rtype; + + f->insns = vec_create(sizeof(struct ejit_insn)); + f->arena = NULL; + f->size = 0; + + emit_insn_i(f, START, 0, 0, 0); + + for (size_t i = 0; i < argc; ++i) { + switch (args[i].kind) { + case EJIT_OPERAND_GPR: emit_insn_i(f, PARAM, args[i].r, 0, i); break; + case EJIT_OPERAND_FPR: emit_insn_i(f, PARAM_F, args[i].r, 0, i); break; + default: abort(); + } + } + + return f; +} + +void ejit_compile_func(struct ejit_func *f, size_t gpr, size_t fpr) +{ + f->gpr = gpr; + f->fpr = fpr; + /** @todo try to implement JIT */ + /* otherwise, convert opcodes to address labels */ + + void **labels; + /* just get labels, don't actually run anything yet */ + ejit_interp(f, 0, NULL, false, &labels); + foreach_vec(ii, f->insns) { + struct ejit_insn i = vect_at(struct ejit_insn, f->insns, ii); + i.addr = labels[i.op]; + vect_at(struct ejit_insn, f->insns, ii) = i; + } +} + +void ejit_destroy_func(struct ejit_func *f) +{ + if (f->arena) + munmap(f->arena, f->size); + + vec_destroy(&f->insns); + free(f); +} + +struct ejit_label ejit_label(struct ejit_func *f) +{ + return (struct ejit_label){.addr = vec_len(&f->insns)}; +} + +void ejit_patch(struct ejit_func *f, struct ejit_reloc r, struct ejit_label l) +{ + struct ejit_insn i = vect_at(struct ejit_insn, f->insns, r.insn); + /** @todo some assert that checks the opcode? */ + i.o = l.addr; + vect_at(struct ejit_insn, f->insns, r.insn) = i; +} + +void ejit_calli(struct ejit_func *s, struct ejit_func *f, size_t argc, const struct ejit_operand args[argc]) +{ + for (size_t i = 0; i < argc; ++i) { + switch (args[i].kind) { + case EJIT_OPERAND_GPR: emit_insn_i(s, ARG, args[i].r, args[i].type, 0); break; + case EJIT_OPERAND_FPR: emit_insn_i(s, ARG_F, args[i].r, args[i].type, 0); break; + case EJIT_OPERAND_IMM: emit_insn_i(s, ARG_I, 0, args[i].type, args[i].r); break; + case EJIT_OPERAND_FLT: emit_insn_f(s, ARG_FI, 0, args[i].type, args[i].d); break; + default: abort(); + } + } + + emit_insn_p(s, CALLI, 0, 0, f); +} + +void ejit_escapei(struct ejit_func *s, ejit_escape_t f, size_t argc, const struct ejit_operand args[argc]) +{ + for (size_t i = 0; i < argc; ++i) { + switch (args[i].kind) { + case EJIT_OPERAND_GPR: emit_insn_i(s, ARG, args[i].r, 0, 0); break; + case EJIT_OPERAND_FPR: emit_insn_i(s, ARG_F, args[i].r, 0, 0); break; + case EJIT_OPERAND_IMM: emit_insn_i(s, ARG_I, 0, 0, args[i].r); break; + case EJIT_OPERAND_FLT: emit_insn_f(s, ARG_FI, 0, 0, args[i].d); break; + default: abort(); + } + } + + emit_insn_p(s, ESCAPEI, 0, 0, f); +} + +void ejit_escapei_f(struct ejit_func *s, ejit_escape_f_t f, size_t argc, const struct ejit_operand args[argc]) +{ + for (size_t i = 0; i < argc; ++i) { + switch (args[i].kind) { + case EJIT_OPERAND_GPR: emit_insn_i(s, ARG, args[i].r, 0, 0); break; + case EJIT_OPERAND_FPR: emit_insn_i(s, ARG_F, args[i].r, 0, 0); break; + case EJIT_OPERAND_IMM: emit_insn_i(s, ARG_I, 0, 0, args[i].r); break; + case EJIT_OPERAND_FLT: emit_insn_f(s, ARG_FI, 0, 0, args[i].d); break; + default: abort(); + } + } + + emit_insn_p(s, ESCAPEI_F, 0, 0, f); +} + +void ejit_ret(struct ejit_func *s, struct ejit_gpr r0) +{ + emit_insn_r(s, RET, r0.r, 0, 0); +} + +void ejit_ret_f(struct ejit_func *s, struct ejit_fpr r0) +{ + emit_insn_r(s, RET_F, r0.f, 0, 0); +} + +void ejit_ret_i(struct ejit_func *s, long i) +{ + emit_insn_i(s, RET_I, 0, 0, i); +} + +void ejit_ret_fi(struct ejit_func *s, double f) +{ + emit_insn_f(s, RET_FI, 0, 0, f); +} + +void ejit_addr(struct ejit_func *s, struct ejit_gpr r0, struct ejit_gpr r1, struct ejit_gpr r2) +{ + emit_insn_r(s, ADDR, r0.r, r1.r, r2.r); +} + +void ejit_addr_f(struct ejit_func *s, struct ejit_fpr r0, struct ejit_fpr r1, struct ejit_fpr r2) +{ + emit_insn_r(s, ADDR_F, r0.f, r1.f, r2.f); +} + +void ejit_subr(struct ejit_func *s, struct ejit_gpr r0, struct ejit_gpr r1, struct ejit_gpr r2) +{ + emit_insn_r(s, SUBR, r0.r, r1.r, r2.r); +} + +void ejit_subr_f(struct ejit_func *s, struct ejit_fpr r0, struct ejit_fpr r1, struct ejit_fpr r2) +{ + emit_insn_r(s, SUBR_F, r0.f, r1.f, r2.f); +} + +void ejit_movi(struct ejit_func *s, struct ejit_gpr r0, long o) +{ + emit_insn_i(s, MOVI, r0.r, 0, o); +} + +struct ejit_reloc ejit_bltr(struct ejit_func *s, struct ejit_gpr r0, struct ejit_gpr r1) +{ + struct ejit_label label = ejit_label(s); + emit_insn_i(s, BLTR, r0.r, r1.r, 0); + return (struct ejit_reloc){.insn = label.addr}; +} diff --git a/src/interp.c b/src/interp.c new file mode 100644 index 0000000..4678aa1 --- /dev/null +++ b/src/interp.c @@ -0,0 +1,190 @@ +#include + +#include "common.h" + + +union interp_ret ejit_interp(struct ejit_func *f, size_t argc, struct ejit_arg args[argc], bool run, void ***labels_wb) +{ + static void *labels[OPCODE_COUNT] = { + [MOVI] = &&movi, + [MOVR] = &&movr, + [MOVR_F] = &&movr_f, + + [ADDR] = &&addr, + [ADDR_F] = &&addr_f, + [SUBR] = &&subr, + [SUBR_F] = &&subr_f, + + [BLTR] = &&bltr, + + [RET] = &&ret, + [RET_I] = &&ret_i, + [RET_F] = &&ret_f, + [RET_FI] = &&ret_fi, + + [ARG] = &&arg, + [ARG_I] = &&arg_i, + [ARG_F] = &&arg_f, + [ARG_FI] = &&arg_fi, + + [PARAM] = &¶m, + [PARAM_F] = &¶m_f, + + [CALLI] = &&calli, + [CALLI_F] = &&calli_f, + + [START] = &&start, + [END] = &&end, + }; + + if (!run) { + *labels_wb = labels; + return (union interp_ret){.r = 0}; + } + + /** @todo this can be optimized by for example using a common buffer + * 'stack' */ + long *gpr = malloc(f->gpr * sizeof(long)); + long *fpr = malloc(f->fpr * sizeof(long)); + struct vec call_args = vec_create(sizeof(struct ejit_arg)); + struct ejit_insn *insns = f->insns.buf; + + struct ejit_insn i; + long retval = 0; double retval_f = 0.; + size_t pc = 0; + +#define DO(x) x: { i = insns[pc]; +#define JUMP(a) goto *insns[pc = a].addr; +#define DISPATCH() } goto *insns[++pc].addr; + + DO(start); + DISPATCH(); + + DO(end); + goto out_int; + DISPATCH(); + + DO(movi); + gpr[i.r0] = i.o; + DISPATCH(); + + DO(movr); + gpr[i.r0] = gpr[i.r1]; + DISPATCH(); + + DO(movr_f); + fpr[i.r0] = fpr[i.r1]; + DISPATCH(); + + DO(addr); + gpr[i.r0] = gpr[i.r1] + gpr[i.r2]; + DISPATCH(); + + DO(addr_f); + fpr[i.r0] = fpr[i.r1] + fpr[i.r2]; + DISPATCH(); + + DO(subr); + gpr[i.r0] = gpr[i.r1] - gpr[i.r2]; + DISPATCH(); + + DO(subr_f); + fpr[i.r0] = fpr[i.r1] - fpr[i.r2]; + DISPATCH(); + + DO(bltr); + if (gpr[i.r0] < gpr[i.r1]) + JUMP(i.o); + + DISPATCH(); + + DO(param); + gpr[i.r0] = args[i.o].l; + DISPATCH(); + + DO(param_f); + fpr[i.r0] = args[i.o].d; + DISPATCH(); + + DO(arg); + struct ejit_arg a = ejit_build_arg(i.r1, gpr[i.r0]); + vec_append(&call_args, &a); + DISPATCH(); + + DO(arg_i); + struct ejit_arg a = ejit_build_arg(i.r1, i.o); + vec_append(&call_args, &a); + DISPATCH(); + + DO(arg_f); + struct ejit_arg a = ejit_build_arg_f(i.r1, fpr[i.r0]); + vec_append(&call_args, &a); + DISPATCH(); + + DO(arg_fi); + struct ejit_arg a = ejit_build_arg_f(i.r1, i.d); + vec_append(&call_args, &a); + DISPATCH(); + + DO(calli); + struct ejit_func *f = i.p; + retval = ejit_run_func(f, vec_len(&call_args), call_args.buf); + vec_reset(&call_args); + DISPATCH(); + + DO(calli_f); + struct ejit_func *f = i.p; + retval_f = ejit_run_func_f(f, vec_len(&call_args), call_args.buf); + vec_reset(&call_args); + DISPATCH(); + + /* dispatch is technically unnecessary for returns, but keep it for + * symmetry */ + DO(ret); + retval = gpr[i.r0]; + goto out_int; + DISPATCH(); + + DO(ret_i); + retval = i.o; + goto out_int; + DISPATCH(); + + DO(ret_f); + retval_f = fpr[i.r0]; + goto out_float; + DISPATCH(); + + DO(ret_fi); + retval_f = i.d; + goto out_float; + DISPATCH(); + +#undef DISPATCH +#undef JUMP +#undef DO + +out_int: + vec_destroy(&call_args); + free(gpr); + free(fpr); + return (union interp_ret){.r = retval}; + +out_float: + vec_destroy(&call_args); + free(gpr); + free(fpr); + return (union interp_ret){.d = retval_f}; +} + +long ejit_run_func(struct ejit_func *f, size_t argc, struct ejit_arg args[argc]) +{ + assert(f->rtype == EJIT_VOID || ejit_int_type(f->rtype)); + return ejit_interp(f, argc, args, true, NULL).r; +} + +double ejit_run_func_f(struct ejit_func *f, size_t argc, struct ejit_arg args[argc]) +{ + assert(ejit_float_type(f->rtype)); + return ejit_interp(f, argc, args, true, NULL).d; +} diff --git a/src/source.mk b/src/source.mk new file mode 100644 index 0000000..907befa --- /dev/null +++ b/src/source.mk @@ -0,0 +1,2 @@ +LOCAL_SOURCES != echo src/*.c +EJIT_SOURCES := $(EJIT_SOURCES) $(LOCAL_SOURCES) diff --git a/src/vec.h b/src/vec.h new file mode 100644 index 0000000..7a1d5cb --- /dev/null +++ b/src/vec.h @@ -0,0 +1,95 @@ +#ifndef VEC_H +#define VEC_H + +#include +#include +#include +#include + +struct vec { + size_t n; + size_t s; + size_t ns; + void *buf; +}; + +#define foreach_vec(iter, v) \ + for (size_t iter = 0; iter < vec_len(&v); ++iter) + +#define vect_at(type, v, i) \ + *(type *)vec_at(&v, i) + +#define vect_append(type, v, e) \ + vec_append(&v, (type *)(e)) + +#define vect_back(type, v) \ + *(type *)vec_back(&v) + +#define vect_pop(type, v) \ + *(type *)vec_pop(&v) + +#define vec_uninit(v) \ + (v.buf == NULL) + +static inline struct vec vec_create(size_t ns) +{ + return (struct vec) { + .n = 0, + .s = 1, + .ns = ns, + .buf = malloc(ns), + }; +} + +static inline size_t vec_len(struct vec *v) +{ + return v->n; +} + +static inline void *vec_at(struct vec *v, size_t i) +{ + assert(i < v->n && "out of vector bounds"); + return v->buf + i * v->ns; +} + +static inline void *vec_back(struct vec *v) +{ + assert(v->n); + return v->buf + (v->n - 1) * v->ns; +} + +static inline void *vec_pop(struct vec *v) +{ + assert(v->n && "attempting to pop empty vector"); + v->n--; + return v->buf + v->n * v->ns; +} + +static inline void vec_append(struct vec *v, void *n) +{ + v->n++; + if (v->n >= v->s) { + v->s *= 2; + v->buf = realloc(v->buf, v->s * v->ns); + } + + void *p = vec_at(v, v->n - 1); + memcpy(p, n, v->ns); +} + +static inline void vec_reset(struct vec *v) +{ + v->n = 0; +} + +static inline void vec_destroy(struct vec *v) { + free(v->buf); +} + +typedef int (*vec_comp_t)(void *a, void *b); +static inline void vec_sort(struct vec *v, vec_comp_t comp) +{ + qsort(v->buf, v->n, v->ns, (__compar_fn_t)comp); +} + +#endif /* VEC_H */ -- cgit v1.2.3