From 25bf1a01695dd8797917f8e6967bf70b8b7db500 Mon Sep 17 00:00:00 2001 From: Stephen Dolan Date: Mon, 10 Jun 2013 01:17:58 +0100 Subject: Unify frame and data stacks --- execute.c | 96 +++++++++++++++++++++++++++++--------------------------- forkable_stack.h | 2 +- frame_layout.h | 29 ++++++++++------- 3 files changed, 69 insertions(+), 58 deletions(-) diff --git a/execute.c b/execute.c index 44cf2ba9..8e09db4e 100644 --- a/execute.c +++ b/execute.c @@ -21,7 +21,7 @@ struct jq_state { struct forkable_stack data_stk; - struct forkable_stack frame_stk; + stack_idx curr_frame; struct forkable_stack fork_stk; jv path; int subexp_nest; @@ -55,8 +55,8 @@ jv stack_pop(jq_state *jq) { struct forkpoint { FORKABLE_STACK_HEADER; struct forkable_stack_state saved_data_stack; - struct forkable_stack_state saved_call_stack; int path_len, subexp_nest; + stack_idx saved_curr_frame; uint16_t* return_address; }; @@ -64,17 +64,16 @@ struct forkpoint { void stack_save(jq_state *jq, uint16_t* retaddr){ struct forkpoint* fork = forkable_stack_push(&jq->fork_stk, sizeof(struct forkpoint)); forkable_stack_save(&jq->data_stk, &fork->saved_data_stack); - forkable_stack_save(&jq->frame_stk, &fork->saved_call_stack); fork->path_len = jv_get_kind(jq->path) == JV_KIND_ARRAY ? jv_array_length(jv_copy(jq->path)) : 0; fork->subexp_nest = jq->subexp_nest; + fork->saved_curr_frame = jq->curr_frame; fork->return_address = retaddr; } void stack_switch(jq_state *jq) { struct forkpoint* fork = forkable_stack_peek(&jq->fork_stk); forkable_stack_switch(&jq->data_stk, &fork->saved_data_stack); - forkable_stack_switch(&jq->frame_stk, &fork->saved_call_stack); } void path_append(jq_state* jq, jv component) { @@ -91,11 +90,11 @@ void path_append(jq_state* jq, jv component) { uint16_t* stack_restore(jq_state *jq){ while (!forkable_stack_empty(&jq->data_stk) && forkable_stack_pop_will_free(&jq->data_stk)) { - jv_free(stack_pop(jq)); - } - while (!forkable_stack_empty(&jq->frame_stk) && - forkable_stack_pop_will_free(&jq->frame_stk)) { - frame_pop(&jq->frame_stk); + if (forkable_stack_peek(&jq->data_stk) != forkable_stack_from_idx(&jq->data_stk, jq->curr_frame)) { + jv_free(stack_pop(jq)); + } else { + jq->curr_frame = frame_pop(&jq->data_stk, jq->curr_frame); + } } if (forkable_stack_empty(&jq->fork_stk)) { @@ -105,7 +104,7 @@ uint16_t* stack_restore(jq_state *jq){ struct forkpoint* fork = forkable_stack_peek(&jq->fork_stk); uint16_t* retaddr = fork->return_address; forkable_stack_restore(&jq->data_stk, &fork->saved_data_stack); - forkable_stack_restore(&jq->frame_stk, &fork->saved_call_stack); + jq->curr_frame = fork->saved_curr_frame; int path_len = fork->path_len; if (jv_get_kind(jq->path) == JV_KIND_ARRAY) { assert(path_len >= 0); @@ -156,28 +155,30 @@ jv jq_next(jq_state *jq) { uint16_t opcode = *pc; if (jq->debug_trace_enabled) { - dump_operation(frame_current_bytecode(&jq->frame_stk), pc); + dump_operation(frame_current_bytecode(&jq->data_stk, jq->curr_frame), pc); printf("\t"); const struct opcode_description* opdesc = opcode_describe(opcode); data_stk_elem* param = 0; - int stack_in = opdesc->stack_in; - if (stack_in == -1) stack_in = pc[1]; - for (int i=0; idata_stk); - } else { - printf(" | "); - param = forkable_stack_peek_next(&jq->data_stk, param); + if (!backtracking) { + int stack_in = opdesc->stack_in; + if (stack_in == -1) stack_in = pc[1]; + for (int i=0; idata_stk); + } else { + printf(" | "); + param = forkable_stack_peek_next(&jq->data_stk, param); + } + if (!param) break; + jv_dump(jv_copy(param->val), 0); + //printf("<%d>", jv_get_refcnt(param->val)); + //printf(" -- "); + //jv_dump(jv_copy(jq->path), 0); } - if (!param) break; - jv_dump(jv_copy(param->val), 0); - //printf("<%d>", jv_get_refcnt(param->val)); - //printf(" -- "); - //jv_dump(jv_copy(jq->path), 0); + } else { + printf("\t"); } - if (backtracking) printf("\t"); - printf("\n"); } if (backtracking) { @@ -190,7 +191,7 @@ jv jq_next(jq_state *jq) { default: assert(0 && "invalid instruction"); case LOADK: { - jv v = jv_array_get(jv_copy(frame_current_bytecode(&jq->frame_stk)->constants), *pc++); + jv v = jv_array_get(jv_copy(frame_current_bytecode(&jq->data_stk, jq->curr_frame)->constants), *pc++); assert(jv_is_valid(v)); jv_free(stack_pop(jq)); stack_push(jq, v); @@ -240,7 +241,7 @@ jv jq_next(jq_state *jq) { jv v = stack_pop(jq); uint16_t level = *pc++; uint16_t vidx = *pc++; - frame_ptr fp = frame_get_level(&jq->frame_stk, frame_current(&jq->frame_stk), level); + frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); jv* var = frame_local_var(fp, vidx); assert(jv_get_kind(*var) == JV_KIND_ARRAY); *var = jv_array_append(*var, v); @@ -272,7 +273,7 @@ jv jq_next(jq_state *jq) { case RANGE: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->frame_stk, frame_current(&jq->frame_stk), level); + frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); jv* var = frame_local_var(fp, v); jv max = stack_pop(jq); if (jv_get_kind(*var) != JV_KIND_NUMBER || @@ -299,7 +300,7 @@ jv jq_next(jq_state *jq) { case LOADV: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->frame_stk, frame_current(&jq->frame_stk), level); + frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); jv* var = frame_local_var(fp, v); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -315,7 +316,7 @@ jv jq_next(jq_state *jq) { case LOADVN: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->frame_stk, frame_current(&jq->frame_stk), level); + frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); jv* var = frame_local_var(fp, v); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -331,7 +332,7 @@ jv jq_next(jq_state *jq) { case STOREV: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->frame_stk, frame_current(&jq->frame_stk), level); + frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); jv* var = frame_local_var(fp, v); jv val = stack_pop(jq); if (jq->debug_trace_enabled) { @@ -499,7 +500,7 @@ jv jq_next(jq_state *jq) { for (int i = 1; i < nargs; i++) { cfunc_input[i] = stack_pop(jq); } - struct cfunction* func = &frame_current_bytecode(&jq->frame_stk)->globals->cfunctions[*pc++]; + struct cfunction* func = &frame_current_bytecode(&jq->data_stk, jq->curr_frame)->globals->cfunctions[*pc++]; top = cfunction_invoke(func, cfunc_input); if (jv_is_valid(top)) { stack_push(jq, top); @@ -511,37 +512,42 @@ jv jq_next(jq_state *jq) { } case CALL_JQ: { + jv input = stack_pop(jq); uint16_t nclosures = *pc++; uint16_t* retaddr = pc + 2 + nclosures*2; - frame_ptr new_frame = frame_push(&jq->frame_stk, - make_closure(&jq->frame_stk, frame_current(&jq->frame_stk), pc), + frame_ptr new_frame = frame_push(&jq->data_stk, jq->curr_frame, + make_closure(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), pc), retaddr); pc += 2; - frame_ptr old_frame = forkable_stack_peek_next(&jq->frame_stk, new_frame); + frame_ptr old_frame = frame_current(&jq->data_stk, jq->curr_frame); + jq->curr_frame = forkable_stack_to_idx(&jq->data_stk, forkable_stack_peek(&jq->data_stk)); + assert(nclosures == frame_self(new_frame)->bc->nclosures); for (int i=0; iframe_stk, old_frame, pc); + *frame_closure_arg(new_frame, i) = make_closure(&jq->data_stk, old_frame, pc); pc += 2; } - pc = frame_current_bytecode(&jq->frame_stk)->code; + pc = frame_current_bytecode(&jq->data_stk, jq->curr_frame)->code; + stack_push(jq, input); break; } case RET: { - uint16_t* retaddr = *frame_current_retaddr(&jq->frame_stk); + jv value = stack_pop(jq); + uint16_t* retaddr = *frame_current_retaddr(&jq->data_stk, jq->curr_frame); if (retaddr) { // function return pc = retaddr; - frame_pop(&jq->frame_stk); + jq->curr_frame = frame_pop(&jq->data_stk, jq->curr_frame); } else { // top-level return, yielding value - jv value = stack_pop(jq); stack_save(jq, pc - 1); stack_push(jq, jv_null()); stack_switch(jq); return value; } + stack_push(jq, value); break; } case ON_BACKTRACK(RET): { @@ -559,12 +565,12 @@ void jq_init(struct bytecode* bc, jv input, jq_state **jq, int flags) { memset(new_jq, 0, sizeof(*new_jq)); new_jq->path = jv_null(); forkable_stack_init(&new_jq->data_stk, sizeof(data_stk_elem) * 100); - forkable_stack_init(&new_jq->frame_stk, 1024); forkable_stack_init(&new_jq->fork_stk, 1024); - stack_push(new_jq, input); struct closure top = {bc, -1}; - frame_push(&new_jq->frame_stk, top, 0); + frame_push(&new_jq->data_stk, 0, top, 0); + new_jq->curr_frame = forkable_stack_to_idx(&new_jq->data_stk, forkable_stack_peek(&new_jq->data_stk)); + stack_push(new_jq, input); stack_save(new_jq, bc->code); stack_switch(new_jq); if (flags & JQ_DEBUG_TRACE) { @@ -586,10 +592,8 @@ void jq_teardown(jq_state **jq) { assert(forkable_stack_empty(&old_jq->fork_stk)); assert(forkable_stack_empty(&old_jq->data_stk)); - assert(forkable_stack_empty(&old_jq->frame_stk)); forkable_stack_free(&old_jq->fork_stk); forkable_stack_free(&old_jq->data_stk); - forkable_stack_free(&old_jq->frame_stk); jv_free(old_jq->path); jv_mem_free(old_jq); diff --git a/forkable_stack.h b/forkable_stack.h index 74fcf433..5f51da6e 100644 --- a/forkable_stack.h +++ b/forkable_stack.h @@ -155,7 +155,7 @@ static void forkable_stack_restore(struct forkable_stack* s, struct forkable_sta forkable_stack_check(s); } -typedef int stack_idx; +typedef int stack_idx; // never zero when valid static stack_idx forkable_stack_to_idx(struct forkable_stack* s, void* ptr) { char* item = ptr; diff --git a/frame_layout.h b/frame_layout.h index dbbe3000..29511f29 100644 --- a/frame_layout.h +++ b/frame_layout.h @@ -10,6 +10,7 @@ struct closure { struct continuation { struct bytecode* bc; stack_idx env; + stack_idx next; uint16_t* retaddr; }; @@ -49,10 +50,12 @@ static jv* frame_local_var(frame_ptr fr, int var) { } -static frame_ptr frame_current(struct forkable_stack* stk) { - frame_ptr fp = forkable_stack_peek(stk); - if (forkable_stack_peek_next(stk, fp)) { - struct bytecode* bc = frame_self(forkable_stack_peek_next(stk, fp))->bc; +static frame_ptr frame_current(struct forkable_stack* stk, stack_idx idx) { + frame_ptr fp = forkable_stack_from_idx(stk, idx); + + if (frame_self(fp)->next) { + frame_ptr fpnext = forkable_stack_from_idx(stk, frame_self(fp)->next); + struct bytecode* bc = frame_self(fpnext)->bc; assert(frame_self(fp)->retaddr >= bc->code && frame_self(fp)->retaddr < bc->code + bc->codelen); } else { assert(frame_self(fp)->retaddr == 0); @@ -60,11 +63,11 @@ static frame_ptr frame_current(struct forkable_stack* stk) { return fp; } -static struct bytecode* frame_current_bytecode(struct forkable_stack* stk) { - return frame_self(frame_current(stk))->bc; +static struct bytecode* frame_current_bytecode(struct forkable_stack* stk, stack_idx curr) { + return frame_self(frame_current(stk, curr))->bc; } -static uint16_t** frame_current_retaddr(struct forkable_stack* stk) { - return &frame_self(frame_current(stk))->retaddr; +static uint16_t** frame_current_retaddr(struct forkable_stack* stk, stack_idx curr) { + return &frame_self(frame_current(stk, curr))->retaddr; } static frame_ptr frame_get_parent(struct forkable_stack* stk, frame_ptr fr) { @@ -78,11 +81,12 @@ static frame_ptr frame_get_level(struct forkable_stack* stk, frame_ptr fr, int l return fr; } -static frame_ptr frame_push(struct forkable_stack* stk, struct closure cl, uint16_t* retaddr) { +static frame_ptr frame_push(struct forkable_stack* stk, stack_idx curr, struct closure cl, uint16_t* retaddr) { frame_ptr fp = forkable_stack_push(stk, frame_size(cl.bc)); struct continuation* cc = frame_self(fp); cc->bc = cl.bc; cc->env = cl.env; + cc->next = curr; cc->retaddr = retaddr; for (int i=0; inlocals; i++) { *frame_local_var(fp, i) = jv_invalid(); @@ -90,8 +94,10 @@ static frame_ptr frame_push(struct forkable_stack* stk, struct closure cl, uint1 return fp; } -static void frame_pop(struct forkable_stack* stk) { - frame_ptr fp = frame_current(stk); +static stack_idx frame_pop(struct forkable_stack* stk, stack_idx curr) { + frame_ptr fp = frame_current(stk, curr); + stack_idx next = frame_self(fp)->next; + assert(fp == forkable_stack_peek(stk)); if (forkable_stack_pop_will_free(stk)) { int nlocals = frame_self(fp)->bc->nlocals; for (int i=0; i Date: Thu, 13 Jun 2013 21:50:32 +0100 Subject: Unify all stacks. Passes tests, but needs cleanup. --- execute.c | 168 +++++++++++++++++++++++++++-------------------------- forkable_stack.h | 172 ------------------------------------------------------- frame_layout.h | 46 +++++++-------- newstack.h | 103 +++++++++++++++++++++++++++++++++ 4 files changed, 212 insertions(+), 277 deletions(-) delete mode 100644 forkable_stack.h create mode 100644 newstack.h diff --git a/execute.c b/execute.c index 8e09db4e..1c6c24a3 100644 --- a/execute.c +++ b/execute.c @@ -8,7 +8,6 @@ #include "opcode.h" #include "bytecode.h" -#include "forkable_stack.h" #include "frame_layout.h" #include "jv_alloc.h" @@ -20,60 +19,63 @@ #include "builtin.h" struct jq_state { - struct forkable_stack data_stk; - stack_idx curr_frame; - struct forkable_stack fork_stk; + struct stack stk; + stack_ptr curr_frame; + stack_ptr stk_top; + stack_ptr fork_top; + jv path; int subexp_nest; int debug_trace_enabled; int initial_execution; }; -typedef struct { - FORKABLE_STACK_HEADER; - jv val; -} data_stk_elem; - void stack_push(jq_state *jq, jv val) { assert(jv_is_valid(val)); - data_stk_elem* s = forkable_stack_push(&jq->data_stk, sizeof(data_stk_elem)); - s->val = val; + jq->stk_top = stack_push_block(&jq->stk, jq->stk_top, sizeof(jv)); + jv* sval = stack_block(&jq->stk, jq->stk_top); + *sval = val; } jv stack_pop(jq_state *jq) { - data_stk_elem* s = forkable_stack_peek(&jq->data_stk); - jv val = s->val; - if (!forkable_stack_pop_will_free(&jq->data_stk)) { + jv* sval = stack_block(&jq->stk, jq->stk_top); + jv val = *sval; + if (!stack_pop_will_free(&jq->stk, jq->stk_top)) { val = jv_copy(val); } - forkable_stack_pop(&jq->data_stk); + jq->stk_top = stack_pop_block(&jq->stk, jq->stk_top, sizeof(jv)); assert(jv_is_valid(val)); return val; } struct forkpoint { - FORKABLE_STACK_HEADER; - struct forkable_stack_state saved_data_stack; + stack_ptr saved_data_stack; + stack_ptr saved_curr_frame; int path_len, subexp_nest; - stack_idx saved_curr_frame; uint16_t* return_address; }; +struct stack_pos { + stack_ptr saved_data_stack, saved_curr_frame; +}; + +struct stack_pos stack_get_pos(jq_state* jq) { + struct stack_pos sp = {jq->stk_top, jq->curr_frame}; + return sp; +} -void stack_save(jq_state *jq, uint16_t* retaddr){ - struct forkpoint* fork = forkable_stack_push(&jq->fork_stk, sizeof(struct forkpoint)); - forkable_stack_save(&jq->data_stk, &fork->saved_data_stack); +void stack_save(jq_state *jq, uint16_t* retaddr, struct stack_pos sp){ + jq->fork_top = stack_push_block(&jq->stk, jq->fork_top, sizeof(struct forkpoint)); + struct forkpoint* fork = stack_block(&jq->stk, jq->fork_top); + fork->saved_data_stack = jq->stk_top; + fork->saved_curr_frame = jq->curr_frame; fork->path_len = jv_get_kind(jq->path) == JV_KIND_ARRAY ? jv_array_length(jv_copy(jq->path)) : 0; fork->subexp_nest = jq->subexp_nest; - fork->saved_curr_frame = jq->curr_frame; fork->return_address = retaddr; -} - -void stack_switch(jq_state *jq) { - struct forkpoint* fork = forkable_stack_peek(&jq->fork_stk); - forkable_stack_switch(&jq->data_stk, &fork->saved_data_stack); + jq->stk_top = sp.saved_data_stack; + jq->curr_frame = sp.saved_curr_frame; } void path_append(jq_state* jq, jv component) { @@ -88,22 +90,23 @@ void path_append(jq_state* jq, jv component) { } uint16_t* stack_restore(jq_state *jq){ - while (!forkable_stack_empty(&jq->data_stk) && - forkable_stack_pop_will_free(&jq->data_stk)) { - if (forkable_stack_peek(&jq->data_stk) != forkable_stack_from_idx(&jq->data_stk, jq->curr_frame)) { + while (stack_top(&jq->stk) != jq->fork_top) { + if (stack_pop_will_free(&jq->stk, jq->stk_top)) { jv_free(stack_pop(jq)); + } else if (stack_pop_will_free(&jq->stk, jq->curr_frame)) { + jq->curr_frame = frame_pop(&jq->stk, jq->curr_frame); } else { - jq->curr_frame = frame_pop(&jq->data_stk, jq->curr_frame); + assert(0); } } - if (forkable_stack_empty(&jq->fork_stk)) { + if (jq->fork_top == 0) { return 0; } - struct forkpoint* fork = forkable_stack_peek(&jq->fork_stk); + struct forkpoint* fork = stack_block(&jq->stk, jq->fork_top); uint16_t* retaddr = fork->return_address; - forkable_stack_restore(&jq->data_stk, &fork->saved_data_stack); + jq->stk_top = fork->saved_data_stack; jq->curr_frame = fork->saved_curr_frame; int path_len = fork->path_len; if (jv_get_kind(jq->path) == JV_KIND_ARRAY) { @@ -113,20 +116,21 @@ uint16_t* stack_restore(jq_state *jq){ assert(path_len == 0); } jq->subexp_nest = fork->subexp_nest; - forkable_stack_pop(&jq->fork_stk); + jq->fork_top = stack_pop_block(&jq->stk, jq->fork_top, sizeof(struct forkpoint)); return retaddr; } -static struct closure make_closure(struct forkable_stack* stk, frame_ptr fr, uint16_t* pc) { +static struct closure make_closure(struct jq_state* jq, stack_ptr fridx, uint16_t* pc) { uint16_t level = *pc++; uint16_t idx = *pc++; - fr = frame_get_level(stk, fr, level); + fridx = frame_get_level(&jq->stk, fridx, level); + frame_ptr fr = frame_current(&jq->stk, fridx); if (idx & ARG_NEWCLOSURE) { int subfn_idx = idx & ~ARG_NEWCLOSURE; assert(subfn_idx < frame_self(fr)->bc->nsubfunctions); struct closure cl = {frame_self(fr)->bc->subfunctions[subfn_idx], - forkable_stack_to_idx(stk, fr)}; + fridx}; return cl; } else { return *frame_closure_arg(fr, idx); @@ -155,22 +159,22 @@ jv jq_next(jq_state *jq) { uint16_t opcode = *pc; if (jq->debug_trace_enabled) { - dump_operation(frame_current_bytecode(&jq->data_stk, jq->curr_frame), pc); + dump_operation(frame_current_bytecode(&jq->stk, jq->curr_frame), pc); printf("\t"); const struct opcode_description* opdesc = opcode_describe(opcode); - data_stk_elem* param = 0; + stack_ptr param = 0; if (!backtracking) { int stack_in = opdesc->stack_in; if (stack_in == -1) stack_in = pc[1]; for (int i=0; idata_stk); + param = jq->stk_top; } else { printf(" | "); - param = forkable_stack_peek_next(&jq->data_stk, param); + param = *stack_block_next(&jq->stk, param); } if (!param) break; - jv_dump(jv_copy(param->val), 0); + jv_dump(jv_copy(*(jv*)stack_block(&jq->stk, param)), 0); //printf("<%d>", jv_get_refcnt(param->val)); //printf(" -- "); //jv_dump(jv_copy(jq->path), 0); @@ -181,6 +185,7 @@ jv jq_next(jq_state *jq) { printf("\n"); } + if (backtracking) { opcode = ON_BACKTRACK(opcode); backtracking = 0; @@ -191,7 +196,7 @@ jv jq_next(jq_state *jq) { default: assert(0 && "invalid instruction"); case LOADK: { - jv v = jv_array_get(jv_copy(frame_current_bytecode(&jq->data_stk, jq->curr_frame)->constants), *pc++); + jv v = jv_array_get(jv_copy(frame_current_bytecode(&jq->stk, jq->curr_frame)->constants), *pc++); assert(jv_is_valid(v)); jv_free(stack_pop(jq)); stack_push(jq, v); @@ -241,7 +246,7 @@ jv jq_next(jq_state *jq) { jv v = stack_pop(jq); uint16_t level = *pc++; uint16_t vidx = *pc++; - frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); + frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, vidx); assert(jv_get_kind(*var) == JV_KIND_ARRAY); *var = jv_array_append(*var, v); @@ -273,7 +278,7 @@ jv jq_next(jq_state *jq) { case RANGE: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); + frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); jv max = stack_pop(jq); if (jv_get_kind(*var) != JV_KIND_NUMBER || @@ -288,9 +293,10 @@ jv jq_next(jq_state *jq) { jv curr = jv_copy(*var); *var = jv_number(jv_number_value(*var) + 1); - stack_save(jq, pc - 3); + struct stack_pos spos = stack_get_pos(jq); stack_push(jq, jv_copy(max)); - stack_switch(jq); + stack_save(jq, pc - 3, spos); + stack_push(jq, curr); } break; @@ -300,7 +306,7 @@ jv jq_next(jq_state *jq) { case LOADV: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); + frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -316,7 +322,7 @@ jv jq_next(jq_state *jq) { case LOADVN: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); + frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -332,7 +338,7 @@ jv jq_next(jq_state *jq) { case STOREV: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_get_level(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), level); + frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); jv val = stack_pop(jq); if (jq->debug_trace_enabled) { @@ -349,8 +355,7 @@ jv jq_next(jq_state *jq) { jv v = stack_pop(jq); stack_push(jq, jq->path); - stack_save(jq, pc - 1); - stack_switch(jq); + stack_save(jq, pc - 1, stack_get_pos(jq)); stack_push(jq, jv_number(jq->subexp_nest)); stack_push(jq, v); @@ -369,9 +374,9 @@ jv jq_next(jq_state *jq) { jv path = jq->path; jq->path = stack_pop(jq); - stack_save(jq, pc - 1); + struct stack_pos spos = stack_get_pos(jq); stack_push(jq, jv_copy(path)); - stack_switch(jq); + stack_save(jq, pc - 1, spos); stack_push(jq, path); jq->subexp_nest = old_subexp_nest; @@ -460,10 +465,10 @@ jv jq_next(jq_state *jq) { path_append(jq, key); stack_push(jq, value); } else { - stack_save(jq, pc - 1); + struct stack_pos spos = stack_get_pos(jq); stack_push(jq, container); stack_push(jq, jv_number(idx)); - stack_switch(jq); + stack_save(jq, pc - 1, spos); path_append(jq, key); stack_push(jq, value); } @@ -481,8 +486,7 @@ jv jq_next(jq_state *jq) { } case FORK: { - stack_save(jq, pc - 1); - stack_switch(jq); + stack_save(jq, pc - 1, stack_get_pos(jq)); pc++; // skip offset this time break; } @@ -500,7 +504,7 @@ jv jq_next(jq_state *jq) { for (int i = 1; i < nargs; i++) { cfunc_input[i] = stack_pop(jq); } - struct cfunction* func = &frame_current_bytecode(&jq->data_stk, jq->curr_frame)->globals->cfunctions[*pc++]; + struct cfunction* func = &frame_current_bytecode(&jq->stk, jq->curr_frame)->globals->cfunctions[*pc++]; top = cfunction_invoke(func, cfunc_input); if (jv_is_valid(top)) { stack_push(jq, top); @@ -515,36 +519,37 @@ jv jq_next(jq_state *jq) { jv input = stack_pop(jq); uint16_t nclosures = *pc++; uint16_t* retaddr = pc + 2 + nclosures*2; - frame_ptr new_frame = frame_push(&jq->data_stk, jq->curr_frame, - make_closure(&jq->data_stk, frame_current(&jq->data_stk, jq->curr_frame), pc), - retaddr); + stack_ptr old_frame = jq->curr_frame; + jq->curr_frame = frame_push(&jq->stk, jq->curr_frame, + make_closure(jq, jq->curr_frame, pc), + retaddr, jq->stk_top); pc += 2; - frame_ptr old_frame = frame_current(&jq->data_stk, jq->curr_frame); - jq->curr_frame = forkable_stack_to_idx(&jq->data_stk, forkable_stack_peek(&jq->data_stk)); + frame_ptr new_frame = frame_current(&jq->stk, jq->curr_frame); assert(nclosures == frame_self(new_frame)->bc->nclosures); for (int i=0; idata_stk, old_frame, pc); + *frame_closure_arg(new_frame, i) = make_closure(jq, old_frame, pc); pc += 2; } - pc = frame_current_bytecode(&jq->data_stk, jq->curr_frame)->code; + pc = frame_current_bytecode(&jq->stk, jq->curr_frame)->code; stack_push(jq, input); break; } case RET: { jv value = stack_pop(jq); - uint16_t* retaddr = *frame_current_retaddr(&jq->data_stk, jq->curr_frame); + assert(jq->stk_top == frame_self(frame_current(&jq->stk, jq->curr_frame))->retdata); + uint16_t* retaddr = *frame_current_retaddr(&jq->stk, jq->curr_frame); if (retaddr) { // function return pc = retaddr; - jq->curr_frame = frame_pop(&jq->data_stk, jq->curr_frame); + jq->curr_frame = frame_pop(&jq->stk, jq->curr_frame); } else { // top-level return, yielding value - stack_save(jq, pc - 1); + struct stack_pos spos = stack_get_pos(jq); stack_push(jq, jv_null()); - stack_switch(jq); + stack_save(jq, pc - 1, spos); return value; } stack_push(jq, value); @@ -564,15 +569,15 @@ void jq_init(struct bytecode* bc, jv input, jq_state **jq, int flags) { new_jq = jv_mem_alloc(sizeof(*new_jq)); memset(new_jq, 0, sizeof(*new_jq)); new_jq->path = jv_null(); - forkable_stack_init(&new_jq->data_stk, sizeof(data_stk_elem) * 100); - forkable_stack_init(&new_jq->fork_stk, 1024); + stack_init(&new_jq->stk); + new_jq->stk_top = 0; + new_jq->fork_top = 0; + new_jq->curr_frame = 0; struct closure top = {bc, -1}; - frame_push(&new_jq->data_stk, 0, top, 0); - new_jq->curr_frame = forkable_stack_to_idx(&new_jq->data_stk, forkable_stack_peek(&new_jq->data_stk)); + new_jq->curr_frame = frame_push(&new_jq->stk, new_jq->curr_frame, top, 0, new_jq->stk_top); stack_push(new_jq, input); - stack_save(new_jq, bc->code); - stack_switch(new_jq); + stack_save(new_jq, bc->code, stack_get_pos(new_jq)); if (flags & JQ_DEBUG_TRACE) { new_jq->debug_trace_enabled = 1; } else { @@ -590,10 +595,11 @@ void jq_teardown(jq_state **jq) { while (stack_restore(old_jq)) {} - assert(forkable_stack_empty(&old_jq->fork_stk)); - assert(forkable_stack_empty(&old_jq->data_stk)); - forkable_stack_free(&old_jq->fork_stk); - forkable_stack_free(&old_jq->data_stk); + assert(stack_top(&old_jq->stk) == 0); + assert(old_jq->stk_top == 0); + assert(old_jq->fork_top == 0); + assert(old_jq->curr_frame == 0); + stack_free(&old_jq->stk); jv_free(old_jq->path); jv_mem_free(old_jq); diff --git a/forkable_stack.h b/forkable_stack.h deleted file mode 100644 index 5f51da6e..00000000 --- a/forkable_stack.h +++ /dev/null @@ -1,172 +0,0 @@ -#ifndef FORKABLE_STACK_H -#define FORKABLE_STACK_H -#include -#include -#include -#include "jv_alloc.h" - -struct forkable_stack_header { - /* distance in bytes between this header and the header - of the next object on the stack */ - int next_delta; -}; - -#define FORKABLE_STACK_HEADER struct forkable_stack_header fk_header_ - -struct forkable_stack { - // Stack grows down from stk+length - char* stk; - - // stk+length is just past end of allocated area - // stk = jv_mem_alloc(length) - int length; - - // stk+pos is header of top object, or stk+length if empty - int pos; - - // everything after-or-including stk+savedlimit must be preserved - int savedlimit; -}; - -static void forkable_stack_check(struct forkable_stack* s) { - assert(s->stk); - assert(s->length > 0); - assert(s->pos >= 0 && s->pos <= s->length); - assert(s->savedlimit >= 0 && s->savedlimit <= s->length); -} - -static int forkable_stack_empty(struct forkable_stack* s) { - return s->pos == s->length; -} - -static void forkable_stack_init(struct forkable_stack* s, size_t sz) { - s->stk = jv_mem_alloc(sz); - s->length = sz; - s->pos = s->length; - s->savedlimit = s->length; - forkable_stack_check(s); -} - -static void forkable_stack_free(struct forkable_stack* s) { - assert(forkable_stack_empty(s)); - assert(s->savedlimit == s->length); - jv_mem_free(s->stk); - s->stk = 0; -} - -static void* forkable_stack_push(struct forkable_stack* s, size_t sz_size) { - assert(sz_size > 0 && sz_size % sizeof(struct forkable_stack_header) == 0); - int size = (int)sz_size; - forkable_stack_check(s); - int curr = s->pos < s->savedlimit ? s->pos : s->savedlimit; - if (curr - size < 0) { - int oldlen = s->length; - s->length = (size + oldlen + 1024) * 2; - s->stk = jv_mem_realloc(s->stk, s->length); - int shift = s->length - oldlen; - memmove(s->stk + shift, s->stk, oldlen); - s->pos += shift; - s->savedlimit += shift; - curr += shift; - } - int newpos = curr - size; - assert(newpos < s->pos); - void* ret = (void*)(s->stk + newpos); - ((struct forkable_stack_header*)ret)->next_delta = s->pos - newpos; - s->pos = newpos; - forkable_stack_check(s); - return ret; -} - -static void* forkable_stack_peek(struct forkable_stack* s) { - assert(!forkable_stack_empty(s)); - forkable_stack_check(s); - return (void*)(s->stk + s->pos); -} - -static void* forkable_stack_peek_next(struct forkable_stack* s, void* top) { - forkable_stack_check(s); - struct forkable_stack_header* elem = top; - int elempos = (char*)top - s->stk; - assert(elempos >= 0 && elempos < s->length); - assert(elempos + elem->next_delta <= s->length); - if (elempos + elem->next_delta < s->length) { - return (void*)(s->stk + elempos + elem->next_delta); - } else { - return 0; - } -} - -// Returns 1 if the next forkable_stack_pop will permanently remove an -// object from the stack (i.e. the top object was not saved with a fork) -static int forkable_stack_pop_will_free(struct forkable_stack* s) { - return s->pos < s->savedlimit; -} - -static void forkable_stack_pop(struct forkable_stack* s) { - forkable_stack_check(s); - struct forkable_stack_header* elem = forkable_stack_peek(s); - int reclaim_upto = s->pos + elem->next_delta < s->savedlimit ? - s->pos + elem->next_delta : s->savedlimit; - assert(reclaim_upto <= s->length); - int reclaimed = reclaim_upto > s->pos ? reclaim_upto - s->pos : 0; - assert(0 <= reclaimed && s->pos + reclaimed <= s->length); - // s->pos <= i < reclaim_upto means that position i is to be freed - assert((reclaimed > 0) == forkable_stack_pop_will_free(s)); - int new_pos = s->pos + elem->next_delta; - jv_mem_invalidate(elem, reclaimed); - s->pos = new_pos; -} - - - -struct forkable_stack_state { - // We save the previous pos, savedlimit as - // length-pos, length-savedlimit since these - // values are stable across stack reallocations. - int prev_pos_delta, prev_limit_delta; -}; - -static void forkable_stack_save(struct forkable_stack* s, struct forkable_stack_state* state) { - forkable_stack_check(s); - state->prev_pos_delta = s->length - s->pos; - state->prev_limit_delta = s->length - s->savedlimit; - if (s->pos < s->savedlimit) s->savedlimit = s->pos; -} - -static void forkable_stack_switch(struct forkable_stack* s, struct forkable_stack_state* state) { - forkable_stack_check(s); - int curr_pos = s->pos; - s->pos = s->length - state->prev_pos_delta; - state->prev_pos_delta = s->length - curr_pos; - - int curr_limit = s->savedlimit; - if (curr_pos < curr_limit) s->savedlimit = curr_pos; - //state->prevlimit = curr_limit; FIXME clean up - forkable_stack_check(s); -} - -static void forkable_stack_restore(struct forkable_stack* s, struct forkable_stack_state* state) { - forkable_stack_check(s); - assert(s->savedlimit <= s->length - state->prev_pos_delta); - assert(s->savedlimit <= s->length - state->prev_limit_delta); - s->pos = s->length - state->prev_pos_delta; - s->savedlimit = s->length - state->prev_limit_delta; - forkable_stack_check(s); -} - -typedef int stack_idx; // never zero when valid - -static stack_idx forkable_stack_to_idx(struct forkable_stack* s, void* ptr) { - char* item = ptr; - int pos = item - s->stk; - assert(pos >= 0 && pos < s->length); - return s->length - pos; -} - -static void* forkable_stack_from_idx(struct forkable_stack* s, stack_idx idx) { - assert(idx >= 1 && idx <= s->length); - return &s->stk[s->length - idx]; -} - -#endif diff --git a/frame_layout.h b/frame_layout.h index 29511f29..0210c0c4 100644 --- a/frame_layout.h +++ b/frame_layout.h @@ -1,21 +1,20 @@ #ifndef FRAME_LAYOUT_H -#include "forkable_stack.h" +#include "newstack.h" #include "bytecode.h" struct closure { struct bytecode* bc; - stack_idx env; + stack_ptr env; }; struct continuation { struct bytecode* bc; - stack_idx env; - stack_idx next; + stack_ptr env; + stack_ptr retdata; uint16_t* retaddr; }; typedef union frame_elem { - FORKABLE_STACK_HEADER; struct continuation cont; struct closure closure; jv jsonval; @@ -50,11 +49,12 @@ static jv* frame_local_var(frame_ptr fr, int var) { } -static frame_ptr frame_current(struct forkable_stack* stk, stack_idx idx) { - frame_ptr fp = forkable_stack_from_idx(stk, idx); +static frame_ptr frame_current(struct stack* stk, stack_ptr idx) { + frame_ptr fp = stack_block(stk, idx); - if (frame_self(fp)->next) { - frame_ptr fpnext = forkable_stack_from_idx(stk, frame_self(fp)->next); + stack_ptr next = *stack_block_next(stk, idx); + if (next) { + frame_ptr fpnext = stack_block(stk, next); struct bytecode* bc = frame_self(fpnext)->bc; assert(frame_self(fp)->retaddr >= bc->code && frame_self(fp)->retaddr < bc->code + bc->codelen); } else { @@ -63,49 +63,47 @@ static frame_ptr frame_current(struct forkable_stack* stk, stack_idx idx) { return fp; } -static struct bytecode* frame_current_bytecode(struct forkable_stack* stk, stack_idx curr) { +static struct bytecode* frame_current_bytecode(struct stack* stk, stack_ptr curr) { return frame_self(frame_current(stk, curr))->bc; } -static uint16_t** frame_current_retaddr(struct forkable_stack* stk, stack_idx curr) { +static uint16_t** frame_current_retaddr(struct stack* stk, stack_ptr curr) { return &frame_self(frame_current(stk, curr))->retaddr; } -static frame_ptr frame_get_parent(struct forkable_stack* stk, frame_ptr fr) { - return forkable_stack_from_idx(stk, frame_self(fr)->env); +static stack_ptr frame_get_parent(struct stack* stk, stack_ptr fr) { + return frame_self(stack_block(stk, fr))->env; } -static frame_ptr frame_get_level(struct forkable_stack* stk, frame_ptr fr, int level) { +static stack_ptr frame_get_level(struct stack* stk, stack_ptr fr, int level) { for (int i=0; ibc = cl.bc; cc->env = cl.env; - cc->next = curr; + cc->retdata = datastk; cc->retaddr = retaddr; for (int i=0; inlocals; i++) { *frame_local_var(fp, i) = jv_invalid(); } - return fp; + return fpidx; } -static stack_idx frame_pop(struct forkable_stack* stk, stack_idx curr) { +static stack_ptr frame_pop(struct stack* stk, stack_ptr curr) { frame_ptr fp = frame_current(stk, curr); - stack_idx next = frame_self(fp)->next; - assert(fp == forkable_stack_peek(stk)); - if (forkable_stack_pop_will_free(stk)) { + if (stack_pop_will_free(stk, curr)) { int nlocals = frame_self(fp)->bc->nlocals; for (int i=0; ibc)); } #endif diff --git a/newstack.h b/newstack.h new file mode 100644 index 00000000..267ae768 --- /dev/null +++ b/newstack.h @@ -0,0 +1,103 @@ +#include +#include +#include +#include +struct determine_alignment { + char x; + union { + int i; + double d; + uint64_t u64; + size_t sz; + void* ptr; + } u; +}; + +enum {ALIGNMENT = offsetof(struct determine_alignment, u)}; + +size_t align_round_up(size_t sz) { + return ((sz + (ALIGNMENT - 1)) / ALIGNMENT) * ALIGNMENT; +} + +typedef int stack_ptr; + +struct stack { + char* mem_end; // one-past-the-end of allocated region + stack_ptr bound; + stack_ptr limit; // 0 - stack is empty +}; + +void stack_init(struct stack* s) { + s->mem_end = 0; + s->bound = ALIGNMENT; + s->limit = 0; +} + +void stack_free(struct stack* s) { + char* mem_start = s->mem_end - ( -s->bound + ALIGNMENT); + free(mem_start); + stack_init(s); +} + +stack_ptr stack_top(struct stack* s) { + return s->limit; +} + +int stack_pop_will_free(struct stack* s, stack_ptr p) { + return p == s->limit; +} + +void* stack_block(struct stack* s, stack_ptr p) { + return (void*)(s->mem_end + p); +} + +stack_ptr* stack_block_next(struct stack* s, stack_ptr p) { + return &(((stack_ptr*)stack_block(s, p))[-1]); +} + +void stack_reallocate(struct stack* s, size_t sz) { + int old_mem_length = -(s->bound) + ALIGNMENT; + char* old_mem_start = s->mem_end - old_mem_length; + + int new_mem_length = align_round_up((old_mem_length + sz + 256) * 2); + char* new_mem_start = realloc(old_mem_start, new_mem_length); + memmove(new_mem_start + (new_mem_length - old_mem_length), + new_mem_start, old_mem_length); + s->mem_end = new_mem_start + new_mem_length; + s->bound = -(new_mem_length - ALIGNMENT); +} + +stack_ptr stack_push_block(struct stack* s, stack_ptr p, size_t sz) { + int alloc_sz = align_round_up(sz) + ALIGNMENT; + stack_ptr r = s->limit - alloc_sz; + if (r < s->bound) { + stack_reallocate(s, alloc_sz); + } + s->limit = r; + *stack_block_next(s, r) = p; + return r; +} + +stack_ptr stack_pop_block(struct stack* s, stack_ptr p, size_t sz) { + stack_ptr r = *stack_block_next(s, p); + if (p == s->limit) { + int alloc_sz = align_round_up(sz) + ALIGNMENT; + s->limit += alloc_sz; + } + return r; +} + +#if 0 +int main() { + stack s; + stack_init(&s); + stack_ptr top = 0; + top = stack_push_block(&s, top, sizeof(double)); + double* d1 = stack_block(&s, top); + *d1 = 42; + top = stack_push_block(&s, top, sizeof(double)); + double* d2 = stack_block(&s, top); + *d2 = 33; + +} +#endif -- cgit v1.2.3 From 5f5c1dc5a6231bb8891cbdf5910000e55a45fcd9 Mon Sep 17 00:00:00 2001 From: Stephen Dolan Date: Fri, 14 Jun 2013 01:20:24 +0100 Subject: Simplify frame logic. --- execute.c | 32 +++++++++++----------- frame_layout.h | 85 +++++++++++++++++++++------------------------------------- newstack.h | 15 ----------- 3 files changed, 47 insertions(+), 85 deletions(-) diff --git a/execute.c b/execute.c index 1c6c24a3..6fadc4ec 100644 --- a/execute.c +++ b/execute.c @@ -125,11 +125,11 @@ static struct closure make_closure(struct jq_state* jq, stack_ptr fridx, uint16_ uint16_t level = *pc++; uint16_t idx = *pc++; fridx = frame_get_level(&jq->stk, fridx, level); - frame_ptr fr = frame_current(&jq->stk, fridx); + struct frame* fr = frame_current(&jq->stk, fridx); if (idx & ARG_NEWCLOSURE) { int subfn_idx = idx & ~ARG_NEWCLOSURE; - assert(subfn_idx < frame_self(fr)->bc->nsubfunctions); - struct closure cl = {frame_self(fr)->bc->subfunctions[subfn_idx], + assert(subfn_idx < fr->bc->nsubfunctions); + struct closure cl = {fr->bc->subfunctions[subfn_idx], fridx}; return cl; } else { @@ -159,7 +159,7 @@ jv jq_next(jq_state *jq) { uint16_t opcode = *pc; if (jq->debug_trace_enabled) { - dump_operation(frame_current_bytecode(&jq->stk, jq->curr_frame), pc); + dump_operation(frame_current(&jq->stk, jq->curr_frame)->bc, pc); printf("\t"); const struct opcode_description* opdesc = opcode_describe(opcode); stack_ptr param = 0; @@ -196,7 +196,7 @@ jv jq_next(jq_state *jq) { default: assert(0 && "invalid instruction"); case LOADK: { - jv v = jv_array_get(jv_copy(frame_current_bytecode(&jq->stk, jq->curr_frame)->constants), *pc++); + jv v = jv_array_get(jv_copy(frame_current(&jq->stk, jq->curr_frame)->bc->constants), *pc++); assert(jv_is_valid(v)); jv_free(stack_pop(jq)); stack_push(jq, v); @@ -246,7 +246,7 @@ jv jq_next(jq_state *jq) { jv v = stack_pop(jq); uint16_t level = *pc++; uint16_t vidx = *pc++; - frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); + struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, vidx); assert(jv_get_kind(*var) == JV_KIND_ARRAY); *var = jv_array_append(*var, v); @@ -278,7 +278,7 @@ jv jq_next(jq_state *jq) { case RANGE: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); + struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); jv max = stack_pop(jq); if (jv_get_kind(*var) != JV_KIND_NUMBER || @@ -306,7 +306,7 @@ jv jq_next(jq_state *jq) { case LOADV: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); + struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -322,7 +322,7 @@ jv jq_next(jq_state *jq) { case LOADVN: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); + struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -338,7 +338,7 @@ jv jq_next(jq_state *jq) { case STOREV: { uint16_t level = *pc++; uint16_t v = *pc++; - frame_ptr fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); + struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); jv* var = frame_local_var(fp, v); jv val = stack_pop(jq); if (jq->debug_trace_enabled) { @@ -504,7 +504,7 @@ jv jq_next(jq_state *jq) { for (int i = 1; i < nargs; i++) { cfunc_input[i] = stack_pop(jq); } - struct cfunction* func = &frame_current_bytecode(&jq->stk, jq->curr_frame)->globals->cfunctions[*pc++]; + struct cfunction* func = &frame_current(&jq->stk, jq->curr_frame)->bc->globals->cfunctions[*pc++]; top = cfunction_invoke(func, cfunc_input); if (jv_is_valid(top)) { stack_push(jq, top); @@ -525,22 +525,22 @@ jv jq_next(jq_state *jq) { retaddr, jq->stk_top); pc += 2; - frame_ptr new_frame = frame_current(&jq->stk, jq->curr_frame); - assert(nclosures == frame_self(new_frame)->bc->nclosures); + struct frame* new_frame = frame_current(&jq->stk, jq->curr_frame); + assert(nclosures == new_frame->bc->nclosures); for (int i=0; istk, jq->curr_frame)->code; + pc = frame_current(&jq->stk, jq->curr_frame)->bc->code; stack_push(jq, input); break; } case RET: { jv value = stack_pop(jq); - assert(jq->stk_top == frame_self(frame_current(&jq->stk, jq->curr_frame))->retdata); - uint16_t* retaddr = *frame_current_retaddr(&jq->stk, jq->curr_frame); + assert(jq->stk_top == frame_current(&jq->stk, jq->curr_frame)->retdata); + uint16_t* retaddr = frame_current(&jq->stk, jq->curr_frame)->retaddr; if (retaddr) { // function return pc = retaddr; diff --git a/frame_layout.h b/frame_layout.h index 0210c0c4..18a0a652 100644 --- a/frame_layout.h +++ b/frame_layout.h @@ -7,88 +7,65 @@ struct closure { stack_ptr env; }; -struct continuation { +union frame_entry { + struct closure closure; + jv localvar; +}; + +struct frame { struct bytecode* bc; stack_ptr env; stack_ptr retdata; uint16_t* retaddr; + /* bc->nclosures closures followed by bc->nlocals local variables */ + union frame_entry entries[0]; }; -typedef union frame_elem { - struct continuation cont; - struct closure closure; - jv jsonval; -} *frame_ptr; - -/* - * Frame layout - * fr[0] - FORKABLE_STACK_HEADER (next pointer) - * fr[1] - self (used to store return addresses, etc) - * fr[2...nclosures+2] - closure params - * fr[nclosures+2..nclosures+nlocals+2] - local variables - */ - static int frame_size(struct bytecode* bc) { - return sizeof(union frame_elem) * (bc->nclosures + bc->nlocals + 2); -} - -static struct continuation* frame_self(frame_ptr fr) { - return &fr[1].cont; + return sizeof(struct frame) + sizeof(union frame_entry) * (bc->nclosures + bc->nlocals); } -static struct closure* frame_closure_arg(frame_ptr fr, int closure) { +static struct closure* frame_closure_arg(struct frame* fr, int closure) { assert(closure >= 0); - assert(closure < frame_self(fr)->bc->nclosures); - return &fr[2+closure].closure; + assert(closure < fr->bc->nclosures); + return &fr->entries[closure].closure; } -static jv* frame_local_var(frame_ptr fr, int var) { +static jv* frame_local_var(struct frame* fr, int var) { assert(var >= 0); - assert(var < frame_self(fr)->bc->nlocals); - return &fr[2 + frame_self(fr)->bc->nclosures + var].jsonval; + assert(var < fr->bc->nlocals); + return &fr->entries[fr->bc->nclosures + var].localvar; } - -static frame_ptr frame_current(struct stack* stk, stack_ptr idx) { - frame_ptr fp = stack_block(stk, idx); +static struct frame* frame_current(struct stack* stk, stack_ptr idx) { + struct frame* fp = stack_block(stk, idx); stack_ptr next = *stack_block_next(stk, idx); if (next) { - frame_ptr fpnext = stack_block(stk, next); - struct bytecode* bc = frame_self(fpnext)->bc; - assert(frame_self(fp)->retaddr >= bc->code && frame_self(fp)->retaddr < bc->code + bc->codelen); + struct frame* fpnext = stack_block(stk, next); + struct bytecode* bc = fpnext->bc; + assert(fp->retaddr >= bc->code && fp->retaddr < bc->code + bc->codelen); } else { - assert(frame_self(fp)->retaddr == 0); + assert(fp->retaddr == 0); } return fp; } -static struct bytecode* frame_current_bytecode(struct stack* stk, stack_ptr curr) { - return frame_self(frame_current(stk, curr))->bc; -} -static uint16_t** frame_current_retaddr(struct stack* stk, stack_ptr curr) { - return &frame_self(frame_current(stk, curr))->retaddr; -} - -static stack_ptr frame_get_parent(struct stack* stk, stack_ptr fr) { - return frame_self(stack_block(stk, fr))->env; -} - static stack_ptr frame_get_level(struct stack* stk, stack_ptr fr, int level) { for (int i=0; ienv; } return fr; } static stack_ptr frame_push(struct stack* stk, stack_ptr curr, struct closure cl, uint16_t* retaddr, stack_ptr datastk) { stack_ptr fpidx = stack_push_block(stk, curr, frame_size(cl.bc)); - frame_ptr fp = stack_block(stk, fpidx); - struct continuation* cc = frame_self(fp); - cc->bc = cl.bc; - cc->env = cl.env; - cc->retdata = datastk; - cc->retaddr = retaddr; + struct frame* fp = stack_block(stk, fpidx); + fp->bc = cl.bc; + fp->env = cl.env; + fp->retdata = datastk; + fp->retaddr = retaddr; for (int i=0; inlocals; i++) { *frame_local_var(fp, i) = jv_invalid(); } @@ -96,14 +73,14 @@ static stack_ptr frame_push(struct stack* stk, stack_ptr curr, struct closure cl } static stack_ptr frame_pop(struct stack* stk, stack_ptr curr) { - frame_ptr fp = frame_current(stk, curr); + struct frame* fp = frame_current(stk, curr); if (stack_pop_will_free(stk, curr)) { - int nlocals = frame_self(fp)->bc->nlocals; + int nlocals = fp->bc->nlocals; for (int i=0; ibc)); + return stack_pop_block(stk, curr, frame_size(fp->bc)); } #endif diff --git a/newstack.h b/newstack.h index 267ae768..0da9dc5d 100644 --- a/newstack.h +++ b/newstack.h @@ -86,18 +86,3 @@ stack_ptr stack_pop_block(struct stack* s, stack_ptr p, size_t sz) { } return r; } - -#if 0 -int main() { - stack s; - stack_init(&s); - stack_ptr top = 0; - top = stack_push_block(&s, top, sizeof(double)); - double* d1 = stack_block(&s, top); - *d1 = 42; - top = stack_push_block(&s, top, sizeof(double)); - double* d2 = stack_block(&s, top); - *d2 = 33; - -} -#endif -- cgit v1.2.3 From 05d90517b029abfc92db3c3ef184b4821b282a6c Mon Sep 17 00:00:00 2001 From: Stephen Dolan Date: Fri, 14 Jun 2013 22:08:18 +0100 Subject: Clean up lots of stack and frame logic. Move frame defs to execute.c --- exec_stack.h | 79 +++++++++++++++++++++++++ execute.c | 179 ++++++++++++++++++++++++++++++++++++++++----------------- frame_layout.h | 86 --------------------------- newstack.h | 88 ---------------------------- 4 files changed, 206 insertions(+), 226 deletions(-) create mode 100644 exec_stack.h delete mode 100644 frame_layout.h delete mode 100644 newstack.h diff --git a/exec_stack.h b/exec_stack.h new file mode 100644 index 00000000..62358cd9 --- /dev/null +++ b/exec_stack.h @@ -0,0 +1,79 @@ +#include +#include +#include +#include + +struct determine_alignment { + char x; + union { int i; double d; uint64_t u64; size_t sz; void* ptr; } u; +}; +enum {ALIGNMENT = offsetof(struct determine_alignment, u)}; + +static size_t align_round_up(size_t sz) { + return ((sz + (ALIGNMENT - 1)) / ALIGNMENT) * ALIGNMENT; +} + +typedef int stack_ptr; + +struct stack { + char* mem_end; // one-past-the-end of allocated region + stack_ptr bound; + stack_ptr limit; // 0 - stack is empty +}; + +static void stack_init(struct stack* s) { + s->mem_end = 0; + s->bound = ALIGNMENT; + s->limit = 0; +} + +static void stack_free(struct stack* s) { + assert(s->limit == 0 && "stack freed while not empty"); + char* mem_start = s->mem_end - ( -s->bound + ALIGNMENT); + free(mem_start); + stack_init(s); +} + +static int stack_pop_will_free(struct stack* s, stack_ptr p) { + return p == s->limit; +} + +static void* stack_block(struct stack* s, stack_ptr p) { + return (void*)(s->mem_end + p); +} + +static stack_ptr* stack_block_next(struct stack* s, stack_ptr p) { + return &((stack_ptr*)stack_block(s, p))[-1]; +} + +static void stack_reallocate(struct stack* s, size_t sz) { + int old_mem_length = -(s->bound) + ALIGNMENT; + char* old_mem_start = s->mem_end - old_mem_length; + + int new_mem_length = align_round_up((old_mem_length + sz + 256) * 2); + char* new_mem_start = realloc(old_mem_start, new_mem_length); + memmove(new_mem_start + (new_mem_length - old_mem_length), + new_mem_start, old_mem_length); + s->mem_end = new_mem_start + new_mem_length; + s->bound = -(new_mem_length - ALIGNMENT); +} + +static stack_ptr stack_push_block(struct stack* s, stack_ptr p, size_t sz) { + int alloc_sz = align_round_up(sz) + ALIGNMENT; + stack_ptr r = s->limit - alloc_sz; + if (r < s->bound) { + stack_reallocate(s, alloc_sz); + } + s->limit = r; + *stack_block_next(s, r) = p; + return r; +} + +static stack_ptr stack_pop_block(struct stack* s, stack_ptr p, size_t sz) { + stack_ptr r = *stack_block_next(s, p); + if (p == s->limit) { + int alloc_sz = align_round_up(sz) + ALIGNMENT; + s->limit += alloc_sz; + } + return r; +} diff --git a/execute.c b/execute.c index 6fadc4ec..bbf94e5a 100644 --- a/execute.c +++ b/execute.c @@ -5,11 +5,10 @@ #include "execute.h" +#include "exec_stack.h" #include "opcode.h" #include "bytecode.h" -#include "frame_layout.h" - #include "jv_alloc.h" #include "jq_parser.h" #include "locfile.h" @@ -30,6 +29,110 @@ struct jq_state { int initial_execution; }; +struct closure { + struct bytecode* bc; + stack_ptr env; +}; + +union frame_entry { + struct closure closure; + jv localvar; +}; + +struct frame { + struct bytecode* bc; + stack_ptr env; + stack_ptr retdata; + uint16_t* retaddr; + /* bc->nclosures closures followed by bc->nlocals local variables */ + union frame_entry entries[0]; +}; + +static int frame_size(struct bytecode* bc) { + return sizeof(struct frame) + sizeof(union frame_entry) * (bc->nclosures + bc->nlocals); +} + +static struct frame* frame_current(struct jq_state* jq) { + struct frame* fp = stack_block(&jq->stk, jq->curr_frame); + + stack_ptr next = *stack_block_next(&jq->stk, jq->curr_frame); + if (next) { + struct frame* fpnext = stack_block(&jq->stk, next); + struct bytecode* bc = fpnext->bc; + assert(fp->retaddr >= bc->code && fp->retaddr < bc->code + bc->codelen); + } else { + assert(fp->retaddr == 0); + } + return fp; +} + +static stack_ptr frame_get_level(struct jq_state* jq, int level) { + stack_ptr fr = jq->curr_frame; + for (int i=0; istk, fr); + fr = fp->env; + } + return fr; +} + +static jv* frame_local_var(struct jq_state* jq, int var, int level) { + struct frame* fr = stack_block(&jq->stk, frame_get_level(jq, level)); + assert(var >= 0); + assert(var < fr->bc->nlocals); + return &fr->entries[fr->bc->nclosures + var].localvar; +} + +static struct closure make_closure(struct jq_state* jq, uint16_t* pc) { + uint16_t level = *pc++; + uint16_t idx = *pc++; + stack_ptr fridx = frame_get_level(jq, level); + struct frame* fr = stack_block(&jq->stk, fridx); + if (idx & ARG_NEWCLOSURE) { + int subfn_idx = idx & ~ARG_NEWCLOSURE; + assert(subfn_idx < fr->bc->nsubfunctions); + struct closure cl = {fr->bc->subfunctions[subfn_idx], + fridx}; + return cl; + } else { + int closure = idx; + assert(closure >= 0); + assert(closure < fr->bc->nclosures); + return fr->entries[closure].closure; + } +} + +static struct frame* frame_push(struct jq_state* jq, struct closure callee, + uint16_t* argdef, int nargs) { + stack_ptr new_frame_idx = stack_push_block(&jq->stk, jq->curr_frame, frame_size(callee.bc)); + struct frame* new_frame = stack_block(&jq->stk, new_frame_idx); + new_frame->bc = callee.bc; + new_frame->env = callee.env; + assert(nargs == new_frame->bc->nclosures); + union frame_entry* entries = new_frame->entries; + for (int i=0; iclosure = make_closure(jq, argdef + i * 2); + entries++; + } + for (int i=0; inlocals; i++) { + entries->localvar = jv_invalid(); + entries++; + } + jq->curr_frame = new_frame_idx; + return new_frame; +} + +static void frame_pop(struct jq_state* jq) { + assert(jq->curr_frame); + struct frame* fp = frame_current(jq); + if (stack_pop_will_free(&jq->stk, jq->curr_frame)) { + int nlocals = fp->bc->nlocals; + for (int i=0; icurr_frame = stack_pop_block(&jq->stk, jq->curr_frame, frame_size(fp->bc)); +} + void stack_push(jq_state *jq, jv val) { assert(jv_is_valid(val)); jq->stk_top = stack_push_block(&jq->stk, jq->stk_top, sizeof(jv)); @@ -90,11 +193,11 @@ void path_append(jq_state* jq, jv component) { } uint16_t* stack_restore(jq_state *jq){ - while (stack_top(&jq->stk) != jq->fork_top) { + while (!stack_pop_will_free(&jq->stk, jq->fork_top)) { if (stack_pop_will_free(&jq->stk, jq->stk_top)) { jv_free(stack_pop(jq)); } else if (stack_pop_will_free(&jq->stk, jq->curr_frame)) { - jq->curr_frame = frame_pop(&jq->stk, jq->curr_frame); + frame_pop(jq); } else { assert(0); } @@ -121,22 +224,6 @@ uint16_t* stack_restore(jq_state *jq){ } -static struct closure make_closure(struct jq_state* jq, stack_ptr fridx, uint16_t* pc) { - uint16_t level = *pc++; - uint16_t idx = *pc++; - fridx = frame_get_level(&jq->stk, fridx, level); - struct frame* fr = frame_current(&jq->stk, fridx); - if (idx & ARG_NEWCLOSURE) { - int subfn_idx = idx & ~ARG_NEWCLOSURE; - assert(subfn_idx < fr->bc->nsubfunctions); - struct closure cl = {fr->bc->subfunctions[subfn_idx], - fridx}; - return cl; - } else { - return *frame_closure_arg(fr, idx); - } -} - void print_error(jv value) { assert(!jv_is_valid(value)); jv msg = jv_invalid_get_msg(value); @@ -159,7 +246,7 @@ jv jq_next(jq_state *jq) { uint16_t opcode = *pc; if (jq->debug_trace_enabled) { - dump_operation(frame_current(&jq->stk, jq->curr_frame)->bc, pc); + dump_operation(frame_current(jq)->bc, pc); printf("\t"); const struct opcode_description* opdesc = opcode_describe(opcode); stack_ptr param = 0; @@ -196,7 +283,7 @@ jv jq_next(jq_state *jq) { default: assert(0 && "invalid instruction"); case LOADK: { - jv v = jv_array_get(jv_copy(frame_current(&jq->stk, jq->curr_frame)->bc->constants), *pc++); + jv v = jv_array_get(jv_copy(frame_current(jq)->bc->constants), *pc++); assert(jv_is_valid(v)); jv_free(stack_pop(jq)); stack_push(jq, v); @@ -246,8 +333,7 @@ jv jq_next(jq_state *jq) { jv v = stack_pop(jq); uint16_t level = *pc++; uint16_t vidx = *pc++; - struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); - jv* var = frame_local_var(fp, vidx); + jv* var = frame_local_var(jq, vidx, level); assert(jv_get_kind(*var) == JV_KIND_ARRAY); *var = jv_array_append(*var, v); break; @@ -278,8 +364,7 @@ jv jq_next(jq_state *jq) { case RANGE: { uint16_t level = *pc++; uint16_t v = *pc++; - struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); - jv* var = frame_local_var(fp, v); + jv* var = frame_local_var(jq, v, level); jv max = stack_pop(jq); if (jv_get_kind(*var) != JV_KIND_NUMBER || jv_get_kind(max) != JV_KIND_NUMBER) { @@ -306,8 +391,7 @@ jv jq_next(jq_state *jq) { case LOADV: { uint16_t level = *pc++; uint16_t v = *pc++; - struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); - jv* var = frame_local_var(fp, v); + jv* var = frame_local_var(jq, v, level); if (jq->debug_trace_enabled) { printf("V%d = ", v); jv_dump(jv_copy(*var), 0); @@ -322,8 +406,7 @@ jv jq_next(jq_state *jq) { case LOADVN: { uint16_t level = *pc++; uint16_t v = *pc++; - struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); - jv* var = frame_local_var(fp, v); + jv* var = frame_local_var(jq, v, level); if (jq->debug_trace_enabled) { printf("V%d = ", v); jv_dump(jv_copy(*var), 0); @@ -338,8 +421,7 @@ jv jq_next(jq_state *jq) { case STOREV: { uint16_t level = *pc++; uint16_t v = *pc++; - struct frame* fp = frame_current(&jq->stk, frame_get_level(&jq->stk, jq->curr_frame, level)); - jv* var = frame_local_var(fp, v); + jv* var = frame_local_var(jq, v, level); jv val = stack_pop(jq); if (jq->debug_trace_enabled) { printf("V%d = ", v); @@ -504,7 +586,7 @@ jv jq_next(jq_state *jq) { for (int i = 1; i < nargs; i++) { cfunc_input[i] = stack_pop(jq); } - struct cfunction* func = &frame_current(&jq->stk, jq->curr_frame)->bc->globals->cfunctions[*pc++]; + struct cfunction* func = &frame_current(jq)->bc->globals->cfunctions[*pc++]; top = cfunction_invoke(func, cfunc_input); if (jv_is_valid(top)) { stack_push(jq, top); @@ -519,32 +601,23 @@ jv jq_next(jq_state *jq) { jv input = stack_pop(jq); uint16_t nclosures = *pc++; uint16_t* retaddr = pc + 2 + nclosures*2; - stack_ptr old_frame = jq->curr_frame; - jq->curr_frame = frame_push(&jq->stk, jq->curr_frame, - make_closure(jq, jq->curr_frame, pc), - retaddr, jq->stk_top); - pc += 2; - - struct frame* new_frame = frame_current(&jq->stk, jq->curr_frame); - assert(nclosures == new_frame->bc->nclosures); - for (int i=0; istk, jq->curr_frame)->bc->code; + struct frame* new_frame = frame_push(jq, make_closure(jq, pc), + pc + 2, nclosures); + new_frame->retdata = jq->stk_top; + new_frame->retaddr = retaddr; + pc = new_frame->bc->code; stack_push(jq, input); break; } case RET: { jv value = stack_pop(jq); - assert(jq->stk_top == frame_current(&jq->stk, jq->curr_frame)->retdata); - uint16_t* retaddr = frame_current(&jq->stk, jq->curr_frame)->retaddr; +