From a0c6ff2c222beb72493f2e40ed27492061dfdf22 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 31 Aug 2025 14:25:07 +0300 Subject: initial fptr ast programs --- .gitignore | 3 + .gitmodules | 3 + fptr_ast/Makefile | 10 ++ fptr_ast/common.h | 31 +++++ fptr_ast/deps/conts | 1 + fptr_ast/fptr.c | 387 ++++++++++++++++++++++++++++++++++++++++++++++++++++ fptr_ast/main.c | 155 +++++++++++++++++++++ fptr_ast/ref.c | 33 +++++ fptr_ast/struct.c | 330 ++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 953 insertions(+) create mode 100644 .gitignore create mode 100644 .gitmodules create mode 100644 fptr_ast/Makefile create mode 100644 fptr_ast/common.h create mode 160000 fptr_ast/deps/conts create mode 100644 fptr_ast/fptr.c create mode 100644 fptr_ast/main.c create mode 100644 fptr_ast/ref.c create mode 100644 fptr_ast/struct.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..58e9bf3 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +fptr_ast/ref +fptr_ast/struct +fptr_ast/fptr diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..ced0d1e --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "fptr_ast/deps/conts"] + path = fptr_ast/deps/conts + url = https://metanimi.dy.fi/cgit/conts diff --git a/fptr_ast/Makefile b/fptr_ast/Makefile new file mode 100644 index 0000000..530e543 --- /dev/null +++ b/fptr_ast/Makefile @@ -0,0 +1,10 @@ +all: struct fptr ref + +struct: struct.c main.c common.h + $(CC) -Wall -Wextra -g -O2 -Ideps/conts/include -DSTRUCT main.c -o struct + +fptr: fptr.c main.c common.h + $(CC) -Wall -Wextra -g -O2 -Ideps/conts/include -DFPTR main.c -o fptr + +ref: ref.c common.h + $(CC) -Wall -Wextra -g -O2 ref.c -o ref diff --git a/fptr_ast/common.h b/fptr_ast/common.h new file mode 100644 index 0000000..4812b59 --- /dev/null +++ b/fptr_ast/common.h @@ -0,0 +1,31 @@ +#ifndef COMMON_H +#define COMMON_H + +#include +#include + +#define MATRIX_SIZE 100 + +static inline void init_matrices(intptr_t *A, intptr_t *B) +{ + int counter = 0; + for (size_t i = 0; i < MATRIX_SIZE; ++i) + for (size_t j = 0; j < MATRIX_SIZE; ++j) { + A[i * MATRIX_SIZE + j] = counter; + B[i * MATRIX_SIZE + j] = counter; + counter++; + } +} + +static inline size_t hash(intptr_t *C) +{ + size_t h = 0; + for (size_t i = 0; i < MATRIX_SIZE; ++i) + for (size_t j = 0; j < MATRIX_SIZE; ++j) { + h += C[i * MATRIX_SIZE + j]; + } + + return h; +} + +#endif /* COMMON_H */ diff --git a/fptr_ast/deps/conts b/fptr_ast/deps/conts new file mode 160000 index 0000000..13d33be --- /dev/null +++ b/fptr_ast/deps/conts @@ -0,0 +1 @@ +Subproject commit 13d33be824a0f6a3952045df7b97b35fc69520a8 diff --git a/fptr_ast/fptr.c b/fptr_ast/fptr.c new file mode 100644 index 0000000..7959735 --- /dev/null +++ b/fptr_ast/fptr.c @@ -0,0 +1,387 @@ +#include +#include + +#include "common.h" + +typedef struct var { + char *name; + intptr_t v; +} var; + +#define VEC_NAME vars +#define VEC_TYPE var +#include +typedef struct vars vars; + +typedef struct proc { + vars vars; +} proc; + +static proc *gen_proc(int header, ...) +{ + (void)header; + + proc *proc = calloc(1, sizeof(struct proc)); + if (!proc) + return NULL; + + proc->vars = vars_create(0); + + va_list args; + va_start(args, header); + while (1) { + char *name = va_arg(args, char *); + + /* NULL sentinel */ + if (!name) + break; + + var var = { + .name = name, + .v = 0 + }; + vars_append(&proc->vars, var); + } + va_end(args); + + return proc; +} + +#define gen_proc(...) gen_proc(0, __VA_ARGS__, NULL) + +static void proc_set(proc *proc, char *name, intptr_t v) +{ + foreach(vars, var, &proc->vars) { + if (strcmp(var->name, name) != 0) + continue; + + var->v = v; + return; + } + + /* abort? */ +} + +typedef struct node node; + +typedef intptr_t (*node_run_t)(struct node *); + +typedef struct node { + node_run_t run; +} node; + +static intptr_t run(node *n) +{ + assert(n); + return n->run(n); +} + +typedef struct load { + node node; + node *addr; +} load; + +static intptr_t run_load(load *l) +{ + return *(intptr_t *)run(l->addr); +} + +static node *gen_load(node *addr) +{ + load *l = calloc(1, sizeof(load)); + if (!l) + return NULL; + + l->node.run = (node_run_t)run_load; + l->addr = addr; + return &l->node; +} + +typedef struct store { + node node; + node *addr; + node *val; +} store; + +static intptr_t run_store(store *s) +{ + intptr_t *dst = (intptr_t *)run(s->addr); + intptr_t val = run(s->val); + *dst = val; + return 0; +} + +static node *gen_store(node *addr, node *val) +{ + store *s = calloc(1, sizeof(store)); + if (!s) + return NULL; + + s->node.run = (node_run_t)run_store; + s->addr = addr; + s->val = val; + return &s->node; +} + +typedef struct add { + node node; + node *l; + node *r; +} add; + +static intptr_t run_add(add *a) +{ + intptr_t l = run(a->l); + intptr_t r = run(a->r); + return l + r; +} + +static node *gen_add(node *l, node *r) +{ + add *a = calloc(1, sizeof(add)); + if (!a) + return NULL; + + a->node.run = (node_run_t)run_add; + a->l = l; + a->r = r; + return &a->node; +} + +typedef struct mul { + node node; + node *l; + node *r; +} mul; + +static intptr_t run_mul(mul *m) +{ + intptr_t l = run(m->l); + intptr_t r = run(m->r); + return l * r; +} + +static node *gen_mul(node *l, node *r) +{ + mul *m = calloc(1, sizeof(mul)); + if (!m) + return NULL; + + m->node.run = (node_run_t)run_mul; + m->l = l; + m->r = r; + return &m->node; +} + +typedef struct var_n { + node node; + intptr_t *varref; +} var_n; + +static intptr_t run_var(var_n *v) +{ + return *v->varref; +} + +static node *gen_var(proc *proc, char *name) +{ + assert(proc && name); + + var_n *v = calloc(1, sizeof(var_n)); + if (!v) + return NULL; + + v->node.run = (node_run_t)run_var; + foreach(vars, var, &proc->vars) { + if (strcmp(var->name, name) != 0) + continue; + + v->varref = &var->v; + return &v->node; + } + + free(v); + return NULL; +} + +typedef struct varref { + node node; + intptr_t *varref; +} varref; + +static intptr_t run_varref(varref *v) +{ + return (intptr_t)v->varref; +} + +static node *gen_varref(proc *proc, char *name) +{ + assert(proc && name); + + /* technically speaking we could use the same trick here as in struct.c + * since var and varref are the same shape, but feels a bit dirty. */ + + varref *v = calloc(1, sizeof(varref)); + if (!v) + return NULL; + + v->node.run = (node_run_t)run_varref; + foreach(vars, var, &proc->vars) { + if (strcmp(var->name, name) != 0) + continue; + + v->varref = &var->v; + return &v->node; + } + + free(v); + return NULL; +} + +typedef struct const_n { + node node; + intptr_t v; +} const_n; + +static intptr_t run_const_n(const_n *c) +{ + return c->v; +} + +static node *gen_const(intptr_t v) +{ + const_n *c = calloc(1, sizeof(const_n)); + if (!c) + return NULL; + + c->node.run = (node_run_t)run_const_n; + c->v = v; + return &c->node; +} + +typedef struct assign { + node node; + node *dst; + node *src; +} assign; + +static intptr_t run_assign(assign *a) +{ + intptr_t *dst = (intptr_t *)run(a->dst); + intptr_t src = run(a->src); + *dst = src; + return 0; +} + +static node *gen_assign(node *dst, node *src) +{ + assign *a = calloc(1, sizeof(assign)); + if (!a) + return NULL; + + a->node.run = (node_run_t)run_assign; + a->dst = dst; + a->src = src; + return &a->node; +} + +typedef struct for_n { + node node; + node *init; + node *cond; + node *post; + node *body; +} for_n; + +static intptr_t run_for(for_n *f) +{ + for (run(f->init); run(f->cond); run(f->post)) + run(f->body); + + return 0; +} + +static node *gen_for(node *init, node *cond, node *post, node *body) +{ + for_n *f = calloc(1, sizeof(for_n)); + if (!f) + return NULL; + + f->node.run = (node_run_t)run_for; + f->init = init; + f->cond = cond; + f->post = post; + f->body = body; + return &f->node; +} + +typedef struct lt { + node node; + node *l; + node *r; +} lt; + +static intptr_t run_lt(lt *c) +{ + intptr_t l = run(c->l); + intptr_t r = run(c->r); + return l < r; +} + +static node *gen_lt(node *l, node *r) +{ + lt *c = calloc(1, sizeof(lt)); + if (!c) + return NULL; + + c->node.run = (node_run_t)run_lt; + c->l = l; + c->r = r; + return &c->node; +} + +#define VEC_NAME nodes +#define VEC_TYPE node * +#include +typedef struct nodes nodes; + +typedef struct body { + node node; + nodes list; +} body; + +static intptr_t run_body(body *b) +{ + foreach(nodes, node, &b->list) { + run(*node); + } + + return 0; +} + +static node *gen_body(int header, ...) +{ + (void)header; + body *b = calloc(1, sizeof(body)); + if (!b) + return NULL; + + b->node.run = (node_run_t)run_body; + b->list = nodes_create(0); + + va_list args; + va_start(args, header); + while (1) { + node *n = va_arg(args, node *); + if (!n) + break; + + nodes_append(&b->list, n); + } + + va_end(args); + + return &b->node; +} + +#define gen_body(...) gen_body(0, __VA_ARGS__, NULL) diff --git a/fptr_ast/main.c b/fptr_ast/main.c new file mode 100644 index 0000000..84d0b17 --- /dev/null +++ b/fptr_ast/main.c @@ -0,0 +1,155 @@ +#include +#include "common.h" + +#if defined(STRUCT) +#include "struct.c" +#elif defined(FPTR) +#include "fptr.c" +#endif + +int main() +{ + /* predefine variables so gen_varref can just return a pointer to speed + * things up and hopefully match real AST runners more closely */ + proc *proc = gen_proc( + /* input parameters, pointers to matrixes + * MATRIX_SIZE*MATRIX_SIZE */ + "A", "B", "C", + /* temporary variables */ + "R", "I", "J", "K"); + + /* A[I][K] */ + node *fetch_a = + gen_load( + gen_add( + gen_var(proc, "A"), + gen_mul( + gen_const(sizeof(intptr_t)), + gen_add( + gen_var(proc, "K"), + gen_mul( + gen_var(proc, "I"), + gen_const(MATRIX_SIZE)))))); + + /* B[K][J] */ + node *fetch_b = + gen_load( + gen_add( + gen_var(proc, "B"), + gen_mul( + gen_const(sizeof(intptr_t)), + gen_add( + gen_var(proc, "J"), + gen_mul( + gen_var(proc, "K"), + gen_const(MATRIX_SIZE)))))); + + /* R += fetch_a * fetch_b */ + node *inner_body = + gen_assign( + gen_varref(proc, "R"), + gen_add( + gen_var(proc, "R"), + gen_mul(fetch_a, fetch_b))); + + /* for (intptr_t K = 0; K < MATRIX_SIZE; ++K) inner_body */ + node *inner_loop = + gen_for( + gen_assign( + gen_varref(proc, "K"), + gen_const(0)), + + gen_lt( + gen_var(proc, "K"), + gen_const(MATRIX_SIZE)), + + gen_assign( + gen_varref(proc, "K"), + gen_add( + gen_var(proc, "K"), + gen_const(1))), + + inner_body); + + /* &C[I][J] */ + node *ref_c = + gen_add( + gen_var(proc, "C"), + gen_mul( + gen_const(sizeof(intptr_t)), + gen_add( + gen_var(proc, "J"), + gen_mul( + gen_var(proc, "I"), + gen_const(MATRIX_SIZE))))); + + /* R = 0; inner_loop; *ref_c = R */ + node *midder_body = + gen_body( + gen_assign( + gen_varref(proc, "R"), + gen_const(0)), + + inner_loop, + + gen_store( + ref_c, + gen_var(proc, "R"))); + + /* for (intptr_t J = 0; J < MATRIX_SIZE; ++J) midder_body */ + node *midder_loop = + gen_for( + gen_assign( + gen_varref(proc, "J"), + gen_const(0)), + + gen_lt( + gen_var(proc, "J"), + gen_const(MATRIX_SIZE)), + + gen_assign( + gen_varref(proc, "J"), + gen_add( + gen_var(proc, "J"), + gen_const(1))), + + midder_body); + + /* for (intptr_t I = 0; I < MATRIX_SIZE; ++I) midder_loop */ + node *outer_loop = + gen_for( + gen_assign( + gen_varref(proc, "I"), + gen_const(0)), + + gen_lt( + gen_var(proc, "I"), + gen_const(MATRIX_SIZE)), + + gen_assign( + gen_varref(proc, "I"), + gen_add( + gen_var(proc, "I"), + gen_const(1))), + + midder_loop); + + intptr_t *A = calloc(MATRIX_SIZE * MATRIX_SIZE, sizeof(intptr_t)); + assert(A); + + intptr_t *B = calloc(MATRIX_SIZE * MATRIX_SIZE, sizeof(intptr_t)); + assert(B); + + intptr_t *C = calloc(MATRIX_SIZE * MATRIX_SIZE, sizeof(intptr_t)); + assert(C); + + init_matrices(A, B); + + proc_set(proc, "A", (intptr_t)A); + proc_set(proc, "B", (intptr_t)B); + proc_set(proc, "C", (intptr_t)C); + + run(outer_loop); + + printf("%zu\n", hash(C)); +} diff --git a/fptr_ast/ref.c b/fptr_ast/ref.c new file mode 100644 index 0000000..6169a25 --- /dev/null +++ b/fptr_ast/ref.c @@ -0,0 +1,33 @@ +#include +#include +#include +#include "common.h" + +static void matrix_mult(intptr_t *A, intptr_t *B, intptr_t *C) +{ + for (size_t i = 0; i < MATRIX_SIZE; ++i) + for (size_t j = 0; j < MATRIX_SIZE; ++j) { + intptr_t r = 0; + for (size_t k = 0; k < MATRIX_SIZE; ++k) + r += A[i * MATRIX_SIZE + k] * B[k * MATRIX_SIZE + j]; + + C[i * MATRIX_SIZE + j] = r; + } +} + +int main() +{ + + intptr_t *A = calloc(MATRIX_SIZE * MATRIX_SIZE, sizeof(intptr_t)); + assert(A); + + intptr_t *B = calloc(MATRIX_SIZE * MATRIX_SIZE, sizeof(intptr_t)); + assert(B); + + intptr_t *C = calloc(MATRIX_SIZE * MATRIX_SIZE, sizeof(intptr_t)); + assert(C); + + init_matrices(A, B); + matrix_mult(A, B, C); + printf("%zu\n", hash(C)); +} diff --git a/fptr_ast/struct.c b/fptr_ast/struct.c new file mode 100644 index 0000000..f22fae4 --- /dev/null +++ b/fptr_ast/struct.c @@ -0,0 +1,330 @@ +#include +#include +#include +#include + +#include "common.h" + +typedef struct var { + char *name; + intptr_t v; +} var; + +#define VEC_NAME vars +#define VEC_TYPE var +#include +typedef struct vars vars; + +typedef struct proc { + vars vars; +} proc; + +static proc *gen_proc(int header, ...) +{ + (void)header; + + proc *proc = calloc(1, sizeof(struct proc)); + if (!proc) + return NULL; + + proc->vars = vars_create(0); + + va_list args; + va_start(args, header); + while (1) { + char *name = va_arg(args, char *); + + /* NULL sentinel */ + if (!name) + break; + + var var = { + .name = name, + .v = 0 + }; + vars_append(&proc->vars, var); + } + va_end(args); + + return proc; +} + +#define gen_proc(...) gen_proc(0, __VA_ARGS__, NULL) + +static void proc_set(proc *proc, char *name, intptr_t v) +{ + foreach(vars, var, &proc->vars) { + if (strcmp(var->name, name) != 0) + continue; + + var->v = v; + return; + } + + /* abort? */ +} + +/* forward declare */ +typedef struct node node; + +#define VEC_NAME nodes +#define VEC_TYPE node* +#include +typedef struct nodes nodes; + +typedef struct node { + enum kind { + NODE_LOAD = 1, + NODE_STORE, + NODE_ADD, + NODE_MUL, + NODE_VAR, + NODE_VARREF, + NODE_CONST, + NODE_ASSIGN, + NODE_FOR, + NODE_LT, + NODE_BODY, + } kind; + + /* generic values */ + struct node *n0; + struct node *n1; + struct node *n2; + struct node *n3; + intptr_t v; + + /* list of nodes. If we really tried to save space, we could make all + * nodes just be indexes into this nodes array, but that would mean that + * execution has to go through more layers of indirection, so I'm + * reserving n0/n1/n2/n3 for quicker lookup */ + nodes nodes; + + /* used by var/varref nodes to point to variable in proc context */ + intptr_t *varref; +} node; + +static node *gen_node(enum kind kind, node *n0, node *n1, node *n2, node *n3, intptr_t v) +{ + node *n = calloc(1, sizeof(node)); + if (!n) + return NULL; + + /* unused by generic nodes */ + n->nodes = nodes_create(0); + + n->kind = kind; + n->n0 = n0; + n->n1 = n1; + n->n2 = n2; + n->n3 = n3; + n->v = v; + return n; +} + + +#define get_n0(k, x) ({assert((x)->kind == (k)); (x)->n0;}) +#define get_n1(k, x) ({assert((x)->kind == (k)); (x)->n1;}) +#define get_n2(k, x) ({assert((x)->kind == (k)); (x)->n2;}) +#define get_n3(k, x) ({assert((x)->kind == (k)); (x)->n3;}) +#define get_v(k, x) ({assert((x)->kind == (k)); (x)->v;}) + +/* generic defines for 'trivial' nodes */ + +#define gen_load(addr) gen_node(NODE_LOAD, (addr), NULL, NULL, NULL, 0) +#define load_addr(x) get_n0(NODE_LOAD, (x)) + +#define gen_store(addr, val) gen_node(NODE_STORE, (addr), (val), NULL, NULL, 0) +#define store_addr(x) get_n0(NODE_STORE, (x)) +#define store_val(x) get_n1(NODE_STORE, (x)) + +#define gen_add(l, r) gen_node(NODE_ADD, (l), (r), NULL, NULL, 0) +#define add_l(x) get_n0(NODE_ADD, (x)) +#define add_r(x) get_n1(NODE_ADD, (x)) + +#define gen_mul(l, r) gen_node(NODE_MUL, (l), (r), NULL, NULL, 0) +#define mul_l(x) get_n0(NODE_MUL, (x)) +#define mul_r(x) get_n1(NODE_MUL, (x)) + +#define gen_const(c) gen_node(NODE_CONST, NULL, NULL, NULL, NULL, (c)) +#define const_v(x) get_v(NODE_CONST, (x)) + +#define gen_assign(dst, src) gen_node(NODE_ASSIGN, (dst), (src), NULL, NULL, 0) +#define assign_dst(x) get_n0(NODE_ASSIGN, (x)) +#define assign_src(x) get_n1(NODE_ASSIGN, (x)) + +#define gen_for(init, cond, post, body) gen_node(NODE_FOR, (init), (cond), (post), (body), 0) +#define for_init(x) get_n0(NODE_FOR, (x)) +#define for_cond(x) get_n1(NODE_FOR, (x)) +#define for_post(x) get_n2(NODE_FOR, (x)) +#define for_body(x) get_n3(NODE_FOR, (x)) + +#define gen_lt(l, r) gen_node(NODE_LT, (l), (r), NULL, NULL, 0) +#define lt_l(x) get_n0(NODE_LT, (x)) +#define lt_r(x) get_n1(NODE_LT, (x)) + +/* nodes that need special handling */ +static node *gen_body(int header, ...) +{ + node *body = calloc(1, sizeof(node)); + if (!body) + return NULL; + + body->kind = NODE_BODY; + body->nodes = nodes_create(0); + + va_list args; + va_start(args, header); + while (1) { + node *n = va_arg(args, node *); + if (!n) + break; + + nodes_append(&body->nodes, n); + } + va_end(args); + + return body; +} + +#define gen_body(...) gen_body(0, __VA_ARGS__, NULL) +#define body_list(x) ({assert((x)->kind == NODE_BODY); (x)->nodes;}) + +static node *gen_var(proc *proc, char *name) +{ + assert(proc && name); + + node *n = calloc(1, sizeof(node)); + if (!n) + return NULL; + + n->kind = NODE_VAR; + foreach(vars, var, &proc->vars) { + if (strcmp(var->name, name) != 0) + continue; + + /* assumes that the var list is static, which it really should + * be by this point */ + n->varref = &var->v; + return n; + } + + /* no such var (abort or return some more obvious error) */ + free(n); + return NULL; +} + +#define var(x) ({assert((x)->kind == NODE_VAR); (x)->varref;}) + +static node *gen_varref(proc *proc, char *name) +{ + /* node generation logic is the same, it's just the runtime that's + * different from gen_var, so just change NODE_VAR -> NODE_VARREF */ + node *n = gen_var(proc, name); + if (!n) + return NULL; + + n->kind = NODE_VARREF; + return n; +} + +#define varref(x) ({assert((x)->kind == NODE_VARREF); (x)->varref;}) + +/* predeclare */ +static intptr_t run(node *n); + +static intptr_t run_load(node *n) +{ + return *(intptr_t* )run(load_addr(n)); +} + +static intptr_t run_store(node *n) +{ + intptr_t *dst = (intptr_t *)run(store_addr(n)); + intptr_t val = run(store_val(n)); + *dst = val; + return 0; +} + +static intptr_t run_add(node *n) +{ + intptr_t l = run(add_l(n)); + intptr_t r = run(add_r(n)); + return l + r; +} + +static intptr_t run_mul(node *n) +{ + intptr_t l = run(mul_l(n)); + intptr_t r = run(mul_r(n)); + return l * r; +} + +static intptr_t run_var(node *n) +{ + return *var(n); +} + +static intptr_t run_varref(node *n) +{ + return (intptr_t)varref(n); +} + +static intptr_t run_const(node *n) +{ + return const_v(n); +} + +static intptr_t run_assign(node *n) +{ + intptr_t *dst = (intptr_t *)run(assign_dst(n)); + intptr_t src = run(assign_src(n)); + *dst = src; + return 0; +} + +static intptr_t run_for(node *n) +{ + for (run(for_init(n)); run(for_cond(n)); run(for_post(n))) + run(for_body(n)); + + return 0; +} + +static intptr_t run_lt(node *n) +{ + intptr_t l = run(lt_l(n)); + intptr_t r = run(lt_r(n)); + return l < r; +} + +static intptr_t run_body(node *n) +{ + nodes list = body_list(n); + foreach(nodes, node, &list) { + run(*node); + } + + return 0; +} + +static intptr_t run(node *n) +{ + switch (n->kind) { + case NODE_LOAD: return run_load(n); + case NODE_STORE: return run_store(n); + case NODE_ADD: return run_add(n); + case NODE_MUL: return run_mul(n); + case NODE_VAR: return run_var(n); + case NODE_VARREF: return run_varref(n); + case NODE_CONST: return run_const(n); + case NODE_ASSIGN: return run_assign(n); + case NODE_FOR: return run_for(n); + case NODE_LT: return run_lt(n); + case NODE_BODY: return run_body(n); + default: fprintf(stderr, "unimp\n"); + abort(); + } + + return 0; +} -- cgit v1.2.3