From d4ec593acf9b1dc5dfbafc04d29e74ffa2442713 Mon Sep 17 00:00:00 2001 From: fennecdjay Date: Sun, 24 Nov 2019 23:39:03 +0100 Subject: [PATCH] :art: Pragma memoize --- Makefile | 1 - ast | 2 +- include/memoize.h | 4 +- src/emit/emit.c | 115 ++++++++++++++++++++++++++++++++++++++++--- src/emit/memoize.c | 98 +++++++++--------------------------- src/parse/check.c | 1 + src/parse/operator.c | 2 + src/parse/scan1.c | 1 + src/parse/scan2.c | 1 + 9 files changed, 139 insertions(+), 86 deletions(-) diff --git a/Makefile b/Makefile index 548e3bad..87ef2ce8 100644 --- a/Makefile +++ b/Makefile @@ -9,7 +9,6 @@ include config.mk GWION_PACKAGE=gwion CFLAGS += -DGWION_PACKAGE='"${GWION_PACKAGE}"' -CFLAGS += -DGWION_NOLINT GIT_BRANCH=$(shell git branch | grep "*" | cut -d" " -f2) diff --git a/ast b/ast index 820ad7c1..ab88e5f5 160000 --- a/ast +++ b/ast @@ -1 +1 @@ -Subproject commit 820ad7c108f5dbd692cb39fec04e69dc90a986c1 +Subproject commit ab88e5f56ae040323c1a09a3e66b50d606567de9 diff --git a/include/memoize.h b/include/memoize.h index 72c9ed88..c95e3b2d 100644 --- a/include/memoize.h +++ b/include/memoize.h @@ -2,8 +2,8 @@ #define __MEMOIZE typedef struct Memoize_ * Memoize; -Memoize memoize_ini(const Emitter, const Func, const enum Kind); +Memoize memoize_ini(const Emitter, const Func); void memoize_end(MemPool, Memoize); -INSTR(MemoizeCall); +INSTR(MemoizeIni); INSTR(MemoizeStore); #endif diff --git a/src/emit/emit.c b/src/emit/emit.c index c6ce831c..14b51d4a 100644 --- a/src/emit/emit.c +++ b/src/emit/emit.c @@ -936,8 +936,45 @@ ANN static void emit_args(const Emitter emit, const Func f) { } } +typedef struct { + const Emitter emit; + const Func_Def fdef; + struct Vector_ branch; + const m_uint offset; + m_uint arg_offset; +} MemoizeEmitter; + +ANN static Instr me_push(const MemoizeEmitter *me, const m_uint sz) { + const Instr instr = emit_kind(me->emit, sz, 0, regpushmem); + instr->m_val = me->arg_offset; + return instr; +} + +static m_bool me_cmp(MemoizeEmitter *me, const Arg_List arg) { + const Emitter emit = me->emit; + const Symbol sym = insert_symbol("=="); + struct Exp_ exp = { .nspc=me->fdef->base->func->value_ref->from->owner }; + struct Op_Import opi = { .op=sym, .lhs=arg->type, .rhs=arg->type, .pos=me->fdef->pos, .data=(uintptr_t)&exp.d }; + CHECK_BB(op_emit_bool(emit, &opi)) + const Instr instr = emit_add_instr(emit, BranchEqInt); + vector_add(&me->branch, (vtype)instr); + return GW_OK; +} + +ANN static m_bool me_arg(MemoizeEmitter *me) { + Arg_List arg = me->fdef->base->args; + do { + const m_uint sz = arg->type->size; + (void)me_push(me, sz); + const Instr instr = me_push(me, sz); + instr->m_val += me->offset + SZ_INT *2; + CHECK_BB(me_cmp(me, arg)) + me->arg_offset += arg->type->size; + } while((arg = arg->next)); + return GW_OK; +} + ANN static Instr emit_call(const Emitter emit, const Func f) { - const Instr memoize = !(emit->info->memoize && GET_FLAG(f, pure)) ? NULL : emit_add_instr(emit, MemoizeCall); const Instr prelude = get_prelude(emit, f); prelude->m_val = f->def->stack_depth; const m_uint member = GET_FLAG(f, member) ? SZ_INT : 0; @@ -950,8 +987,6 @@ ANN static Instr emit_call(const Emitter emit, const Func f) { emit_args(emit, f); ++prelude->m_val2; } - if(memoize) - memoize->m_val = prelude->m_val2 + 1; return emit_add_instr(emit, Overflow); } @@ -1565,6 +1600,14 @@ ANN static m_bool emit_stmt_match(const Emitter emit, const struct Stmt_Match_* return ret; } +ANN static m_bool emit_stmt_pp(const Emitter emit, const struct Stmt_PP_* stmt) { + if(stmt->pp_type == ae_pp_pragma) { + if(!strncmp(stmt->data, "memoize", strlen("memoize"))) + emit->info->memoize = strtol(stmt->data + 7, NULL, 10); + } + return GW_OK; +} + #define emit_stmt_while emit_stmt_flow #define emit_stmt_until emit_stmt_flow DECL_STMT_FUNC(emit, m_bool , Emitter) @@ -1762,8 +1805,10 @@ ANN static void emit_func_def_return(const Emitter emit) { instr->m_val = val; } vector_clear(&emit->code->stack_return); - if(emit->info->memoize && GET_FLAG(emit->env->func, pure)) - emit_add_instr(emit, MemoizeStore); + if(emit->info->memoize && GET_FLAG(emit->env->func, pure)) { + const Instr instr = emit_add_instr(emit, MemoizeStore); + instr->m_val = emit->env->func->def->stack_depth; + } } ANN static VM_Code emit_internal(const Emitter emit, const Func f) { @@ -1808,7 +1853,64 @@ ANN static m_bool emit_func_def_body(const Emitter emit, const Func_Def fdef) { return GW_OK; } +ANN static Instr me_top(MemoizeEmitter *me) { + const Instr idx = emit_add_instr(me->emit, MemSetImm); + idx->m_val = me->offset; + const Instr pc = emit_add_instr(me->emit, MemSetImm); + pc->m_val = me->offset + SZ_INT; + return pc; +} + +ANN static void me_ini(MemoizeEmitter *me) { + const Instr ini = emit_add_instr(me->emit, MemoizeIni); + ini->m_val = me->offset; + ini->m_val2 = me->fdef->stack_depth + me->fdef->base->ret_type->size; +} + +ANN static void me_end(MemoizeEmitter *me, const m_uint pc) { + for(m_uint i = 0; i < vector_size(&me->branch); ++i) + ((Instr)vector_at(&me->branch, i))->m_val = pc; +} + +ANN static void me_bottom(MemoizeEmitter *me, const m_uint pc) { + const Instr idx = emit_add_instr(me->emit, RegPushMem4); + idx->m_val = me->offset; + emit_add_instr(me->emit, int_pre_inc); + regpop(me->emit, SZ_INT); + const Instr loop = emit_add_instr(me->emit, Goto); + loop->m_val = pc; +} + +ANN static void me_ret(MemoizeEmitter *me) { + const Instr instr = emit_kind(me->emit, me->fdef->base->ret_type->size, 0, regpushmem); + instr->m_val = (me->offset + SZ_INT)*2; + emit_add_instr(me->emit, FuncReturn); +} + +ANN static m_bool me_run(MemoizeEmitter *me, const m_uint pc) { + me_ini(me); + if(me->fdef->base->args) + CHECK_BB(me_arg(me)) + me_ret(me); + me_end(me, emit_code_size(me->emit)); + me_bottom(me, pc); + return GW_OK; +} + +ANN static m_bool emit_memoize(const Emitter emit, const Func_Def fdef) { + MemoizeEmitter me = { .emit=emit, .fdef=fdef, .offset=fdef->stack_depth }; + const Instr pc = me_top(&me); + const m_uint top = emit_code_size(emit); + vector_init(&me.branch); + const m_bool ret = me_run(&me, top); + vector_release(&me.branch); + pc->m_val2 = emit_code_size(emit); + return ret; +} + ANN static m_bool emit_fdef(const Emitter emit, const Func_Def fdef) { + if(emit->info->memoize && GET_FLAG(fdef->base->func, pure)) + CHECK_BB(emit_memoize(emit, fdef)) CHECK_BB(emit_func_def_body(emit, fdef)) emit_func_def_return(emit); return GW_OK; @@ -1820,8 +1922,7 @@ ANN static void emit_fdef_finish(const Emitter emit, const Func_Def fdef) { if(!emit->env->class_def && !GET_FLAG(fdef, global) && !fdef->base->tmpl) emit_func_def_global(emit, func->value_ref); if(emit->info->memoize && GET_FLAG(func, pure)) - func->code->memoize = memoize_ini(emit, func, - kindof(fdef->base->ret_type->size, !fdef->base->ret_type->size)); + func->code->memoize = memoize_ini(emit, func); } ANN static m_bool emit_func_def(const Emitter emit, const Func_Def fdef) { diff --git a/src/emit/memoize.c b/src/emit/memoize.c index 3abeccb9..c93eaae7 100644 --- a/src/emit/memoize.c +++ b/src/emit/memoize.c @@ -11,100 +11,48 @@ struct Memoize_ { struct Vector_ v; m_uint arg_sz; m_uint ret_sz; - struct pool *p; size_t limit; size_t curr; - m_bool member; - enum Kind kind; }; -static inline void memoize_return1(m_bit* tgt, const m_bit* src, - const m_uint size NUSED) { - *(m_uint*)tgt = *(m_uint*)src; -} - -static inline void memoize_return2(m_bit* tgt, const m_bit* src, - const m_uint size NUSED) { - *(m_float*)tgt = *(m_float*)src; -} - -static inline void memoize_return3(m_bit* tgt, const m_bit* src, - const m_uint size) { - memcpy(tgt, src, size); -} - -static inline void memoize_return4(m_bit* tgt NUSED, - const m_bit* src NUSED, - const m_uint size NUSED) {} - -static void(*mreturn[])(m_bit*, const m_bit*, const m_uint) = - { memoize_return1, memoize_return2, memoize_return3, memoize_return4}; - -Memoize memoize_ini(const Emitter emit, const Func f, const enum Kind kind) { +Memoize memoize_ini(const Emitter emit, const Func f) { Memoize m = mp_calloc(emit->gwion->mp, Memoize); vector_init(&m->v); m->ret_sz = f->def->base->ret_type->size; - m->kind = kind; - if(!GET_FLAG(f, member)) - m->arg_sz = f->def->stack_depth; - else { - m->member = SZ_INT; - m->arg_sz = f->def->stack_depth - SZ_INT; - } + m->arg_sz = f->def->stack_depth; m->limit = emit->info->memoize; - m->p = new_pool((uint32_t)(m->arg_sz + m->ret_sz)); return m; } void memoize_end(MemPool p, Memoize m) { + for(m_uint i = 0; i < vector_size(&m->v); ++i) + mp_free2(p, m->arg_sz + m->arg_sz, (void*)vector_at(&m->v, i)); vector_release(&m->v); - mp_end(m->p); - xfree(m->p); mp_free(p, Memoize, m); } -static inline void memoize_set(Memoize m, const m_bit* arg) { - m_bit* data = _mp_calloc2(m->p, 0); - memcpy(data, arg, m->arg_sz); - if(vector_size(&m->v) < m->limit) - vector_add(&m->v, (vtype)data); - else - vector_set(&m->v, m->curr++ % m->limit, (vtype)data); -} - -m_bool memoize_get(VM_Shred shred) { - const VM_Code code = *(VM_Code*)REG(-SZ_INT); - const Memoize m = code->memoize; - if(!m) - return GW_OK; - const m_bit* arg = REG(-(SZ_INT + m->arg_sz + (m_uint)m->member)); - const m_uint size = vector_size(&m->v); - for(m_uint i = 0; i < size; ++i) { - m_bit* data = (m_bit*)vector_at(&m->v, i); - if(memcmp(arg, data, m->arg_sz)) - continue; - POP_REG(shred, SZ_INT + (m->arg_sz - m->ret_sz) + (m_uint)m->member) - mreturn[m->kind](shred->reg-m->ret_sz, data + m->arg_sz, m->ret_sz); - return GW_OK; - } - memoize_set(m, arg); - return 0; +ANN static inline m_bit* get_data(MemPool mp, Memoize m) { + if(vector_size(&m->v) >= m->limit) + return (m_bit*)vector_at(&m->v, m->curr++ % m->limit); + m_bit* data = mp_calloc2(mp, m->arg_sz + m->ret_sz); + vector_add(&m->v, (vtype)data); + return data; } -INSTR(MemoizeCall) { - if(memoize_get(shred)) - shred->pc += instr->m_val; +INSTR(MemoizeStore) { + const Memoize m = shred->code->memoize; + m_bit* data = get_data(shred->info->vm->gwion->mp, m); + memcpy(data, shred->mem, m->arg_sz); + memcpy(data + m->arg_sz, shred->reg - m->ret_sz, m->ret_sz); + vector_add(&m->v, (vtype)data); } -INSTR(MemoizeStore) { +INSTR(MemoizeIni) { + const m_uint idx = *(m_uint*)MEM(instr->m_val); const Memoize m = shred->code->memoize; - const m_bit* arg = MEM(m->member); - const m_uint size = vector_size(&m->v); - for(m_uint i = size + 1; --i;) { - m_bit* data = (m_bit*)vector_at(&m->v, i-1); - if(memcmp(data, arg, m->arg_sz)) - continue; - mreturn[m->kind](data + m->arg_sz, shred->reg-m->ret_sz, m->ret_sz); - return; - } + if(idx < VLEN(&m->v)) { + const m_bit* data = (m_bit*)vector_at(&m->v, idx); + memcpy(MEM(instr->m_val + SZ_INT *2), data, instr->m_val2); + } else + shred->pc = *(m_uint*)MEM(instr->m_val + SZ_INT); } diff --git a/src/parse/check.c b/src/parse/check.c index 26b48600..f79ca2bc 100644 --- a/src/parse/check.c +++ b/src/parse/check.c @@ -1225,6 +1225,7 @@ ANN static m_bool check_stmt_match(const Env env, const Stmt_Match stmt) { #define check_stmt_while check_stmt_flow #define check_stmt_until check_stmt_flow +#define check_stmt_pp dummy_func DECL_STMT_FUNC(check, m_bool , Env) ANN m_bool check_stmt(const Env env, const Stmt stmt) { diff --git a/src/parse/operator.c b/src/parse/operator.c index 45b5773c..938ca489 100644 --- a/src/parse/operator.c +++ b/src/parse/operator.c @@ -229,6 +229,8 @@ ANN Instr op_emit(const Emitter emit, const struct Op_Import* opi) { Type r = opi->rhs; do { const Vector v = (Vector)map_get(&nspc->info->op_map, (vtype)opi->op); +if(!v)continue; +assert(v); const M_Operator* mo = operator_find(v, l, r); if(mo) { if(mo->em) diff --git a/src/parse/scan1.c b/src/parse/scan1.c index 32b68fb3..42f12321 100644 --- a/src/parse/scan1.c +++ b/src/parse/scan1.c @@ -319,6 +319,7 @@ ANN m_bool scan1_union_def(const Env env, const Union_Def udef) { #define scan1_stmt_break (void*)dummy_func #define scan1_stmt_jump (void*)dummy_func #define scan1_stmt_return scan1_stmt_exp +#define scan1_stmt_pp (void*)dummy_func DECL_STMT_FUNC(scan1, m_bool, Env) ANN static inline m_bool scan1_stmt(const Env env, const Stmt stmt) { diff --git a/src/parse/scan2.c b/src/parse/scan2.c index 20451ee0..41397c26 100644 --- a/src/parse/scan2.c +++ b/src/parse/scan2.c @@ -274,6 +274,7 @@ ANN m_bool scan2_union_def(const Env env, const Union_Def udef) { #define scan2_stmt_continue (void*)dummy_func #define scan2_stmt_break (void*)dummy_func #define scan2_stmt_return scan2_stmt_exp +#define scan2_stmt_pp dummy_func DECL_STMT_FUNC(scan2, m_bool, Env) -- 2.43.0