summaryrefslogtreecommitdiff
path: root/main.c
diff options
context:
space:
mode:
Diffstat (limited to 'main.c')
-rw-r--r--main.c188
1 files changed, 166 insertions, 22 deletions
diff --git a/main.c b/main.c
index 51aafe4..13bfa69 100644
--- a/main.c
+++ b/main.c
@@ -10,24 +10,30 @@
#include "arena.h"
#include "dynarr.h"
+int no_opt = 0;
+
/* node graph */
typedef enum {
N_START,
N_RETURN,
+ N_KEEPALIVE,
N_LIT,
N_OP_ADD, N_OP_SUB, N_OP_MUL, N_OP_DIV,
N_OP_AND, N_OP_OR, N_OP_XOR,
- N_OP_NEG, N_OP_NOT
+ N_OP_NEG, N_OP_NOT,
+ N_VALUE
} NodeType;
const char *node_type_name[] = {
"start",
"return",
+ "keepalive",
"literal",
"add", "sub", "mul", "div",
"and", "or", "xor",
"neg", "not",
+ "value"
};
typedef enum {
@@ -59,19 +65,27 @@ typedef struct Node {
} Node;
typedef struct NameBinding {
- Str name;
struct NameBinding *prev;
+ Str name;
+ Node *node;
} NameBinding;
+typedef struct ScopeFrame {
+ struct ScopeFrame *prev;
+ NameBinding *latest;
+} ScopeFrame;
+
typedef struct {
- NameBinding *last;
+ ScopeFrame *tail, *free_scope;
+ NameBinding *free_bind;
} Scope;
typedef struct {
Arena arena;
Str name;
- Node *start, *stop;
+ Node *start, *stop, *keepalive;
Node *free_list;
+ Scope scope;
} Proc;
typedef struct {
@@ -210,6 +224,12 @@ void proc_print(Proc *p) {
if (p->start) {
printf("\t\"%.*s\" -> %d\n", (int)p->name.n, p->name.s, p->start->id);
node_print(p->start);
+ /*if (no_opt) {
+ for (NameBinding *b = p->scope.free_bind; b; b = b->prev) {
+ printf("\t\"%.*s\" [shape=none,fontcolor=blue]\n", (int)b->name.n, b->name.s);
+ printf("\t\"%.*s\" -> %d [arrowhead=none,style=dotted,color=blue]\n", (int)b->name.n, b->name.s, b->node->id);
+ }
+ }*/
}
}
@@ -276,19 +296,24 @@ Value node_compute(Node *n, Lexer *l) {
/* needs lexer for error reporting */
Node *node_peephole(Node *n, Proc *p, Lexer *l) {
- Value v = node_compute(n, l);
- if (n->type != N_LIT && v.type > T_CONST) {
- Node *r = node_new(p, N_LIT, p->start);
- r->val = v;
- r->src_pos = n->src_pos;
- node_kill(n, p);
- return r;
+ if (no_opt) return n;
+
+ if (n->type != N_LIT) {
+ Value v = node_compute(n, l);
+ if (v.type > T_CONST) {
+ Node *r = node_new(p, N_LIT, p->start);
+ r->val = v;
+ r->src_pos = n->src_pos;
+ node_kill(n, p);
+ return r;
+ }
}
Node **in = n->in.data;
/* TODO: figure out to do peepholes recursively, without fucking up the graph or having to clone everything */
if (node_op_communative(n->type)) {
/* transformations to help encourage constant folding */
+ /* the overall trend is to move them rightwards */
if (in[0]->type == N_LIT
&& in[1]->type == n->type
&& in[1]->in.data[0]->type != N_LIT
@@ -297,6 +322,8 @@ Node *node_peephole(Node *n, Proc *p, Lexer *l) {
Node *tmp = in[1]->in.data[0];
in[1]->in.data[0] = in[0];
in[0] = tmp;
+ /* TODO: ...would it break anything at all to just do in[1] = node_peephole(in[1], p, l)?
+ * probably not, right? */
} else if (in[0]->type == n->type
&& in[0]->in.data[0]->type != N_LIT
&& in[0]->in.data[1]->type == N_LIT
@@ -305,30 +332,130 @@ Node *node_peephole(Node *n, Proc *p, Lexer *l) {
Node *tmp = in[0]->in.data[1];
in[0]->in.data[1] = in[1];
in[1] = tmp;
+ } else if (in[0]->type == N_LIT && in[1]->type != N_LIT) {
+ /* op(lit, X) -> op(X, lit) */
+ Node *tmp = in[0];
+ in[0] = in[1];
+ in[1] = tmp;
}
}
return n;
}
+/* scope */
+
+NameBinding *scope_find(Scope *scope, Str name) {
+ for (ScopeFrame *f = scope->tail; f; f = f->prev) {
+ for (NameBinding *b = f->latest; b; b = b->prev) {
+ if (str_eql(b->name, name)) {
+ return b;
+ }
+ }
+ }
+ return NULL;
+}
+
+ScopeFrame *scope_push(Scope *scope, Arena *arena) {
+ ScopeFrame *f;
+ if (scope->free_scope) {
+ f = scope->free_scope;
+ scope->free_scope = f->prev;
+ } else {
+ f = new(arena, ScopeFrame);
+ }
+ f->prev = scope->tail;
+ scope->tail = f;
+ return f;
+}
+
+ScopeFrame *scope_pop(Scope *scope) {
+ ScopeFrame *f = scope->tail;
+ scope->tail = f->prev;
+ f->prev = scope->free_scope;
+ scope->free_scope = f;
+ for (NameBinding *b = f->latest; b; ) {
+ NameBinding *p = b->prev;
+ b->prev = scope->free_bind;
+ scope->free_bind = b;
+ b = p;
+ }
+ return scope->tail;
+}
+
+/* returns previous value */
+Node *scope_bind(Scope *scope, Str name, Node *value, Arena *arena) {
+ NameBinding *b = scope_find(scope, name);
+ Node *og = b ? b->node : NULL;
+ if (!b) {
+ if (scope->free_bind) {
+ b = scope->free_bind;
+ scope->free_bind = b->prev;
+ } else {
+ b = new(arena, NameBinding);
+ }
+ b->name = name;
+ b->prev = scope->tail->latest;
+ scope->tail->latest = b;
+ }
+ b->node = value;
+ return og;
+}
+
/* parsing */
Node *parse_expr(Lexer *l, Proc *p);
-Node *parse_return(Lexer *l, Proc *p) {
+void parse_return(Lexer *l, Proc *p) {
+ lex_next(l);
+ p->stop = node_new(p, N_RETURN, p->start, parse_expr(l, p));
+}
+
+void parse_let(Lexer *l, Proc *p) {
+recurse:
+ lex_expect(l, TM_IDENT);
+ Str name = l->ident;
+ lex_expect(l, TM_EQUALS);
+ lex_next(l);
+ Node *rhs = parse_expr(l, p);
+ node_add(p, rhs, p->keepalive);
+ Node *b = scope_bind(&p->scope, name, rhs, &p->arena);
+ if (b) {
+ lex_error_at(l, rhs->src_pos, LE_WARN, S("shadowing previous declaration"));
+ lex_error_at(l, b->src_pos, LE_WARN, S("declared here"));
+ }
+ if (l->tok == TOK_COMMA) goto recurse;
+}
+
+void parse_stmt(Lexer *l, Proc *p);
+
+/* TODO: return node from this! */
+void parse_block(Lexer *l, Proc *p) {
+ lex_next(l);
+ scope_push(&p->scope, &p->arena);
+ while (l->tok != TOK_RBRACE && l->tok != TOK_EOF) {
+ parse_stmt(l, p);
+ }
+ scope_pop(&p->scope);
+ lex_expected(l, TM_RBRACE);
lex_next(l);
- return node_new(p, N_RETURN, p->start, parse_expr(l, p));
}
-Node *parse_stmt(Lexer *l, Proc *p) {
+void parse_stmt(Lexer *l, Proc *p) {
/* TODO */
(void)l;
switch (l->tok) {
case TOK_RETURN:
- return parse_return(l, p);
+ parse_return(l, p);
+ break;
+ case TOK_LET:
+ parse_let(l, p);
+ break;
+ case TOK_LBRACE:
+ parse_block(l, p);
break;
default:
lex_expected(l, TM_RBRACE);
- return NULL;
+ break;
}
}
@@ -337,14 +464,18 @@ Proc *parse_proc(Lexer *l, Unit *u) {
Proc *proc = &u->procs.data[u->procs.len++];
memset(proc, 0, sizeof(Proc));
proc->start = node_new_empty(proc, N_START);
+ proc->keepalive = node_new_empty(proc, N_KEEPALIVE);
lex_expect(l, TM_IDENT);
proc->name = l->ident;
lex_expect(l, TM_LBRACE);
lex_next(l);
+ scope_push(&proc->scope, &proc->arena);
while (l->tok != TOK_RBRACE) {
lex_expected_not(l, TM_EOF);
- proc->stop = parse_stmt(l, proc);
+ parse_stmt(l, proc);
}
+ scope_pop(&proc->scope);
+ node_kill(proc->keepalive, proc);
lex_expected(l, TM_RBRACE);
lex_next(l);
return proc;
@@ -352,8 +483,13 @@ Proc *parse_proc(Lexer *l, Unit *u) {
Node *parse_term(Lexer *l, Proc *p) {
Node *node = NULL;
- int negate_after = l->tok == TOK_MINUS;
- if (TMASK(l->tok) & (TM_MINUS | TM_PLUS)) {
+ NodeType op_after = N_START;
+ if (TMASK(l->tok) & (TM_MINUS | TM_PLUS | TM_NOT)) {
+ switch (l->tok) {
+ case TOK_MINUS: op_after = N_OP_NEG; break;
+ case TOK_NOT: op_after = N_OP_NOT; break;
+ default: break;
+ }
lex_next(l);
}
if (l->tok == TOK_LPAREN) {
@@ -361,12 +497,20 @@ Node *parse_term(Lexer *l, Proc *p) {
node = parse_expr(l, p);
lex_expected(l, TM_RPAREN);
lex_next(l);
+ } else if (l->tok == TOK_IDENT) {
+ NameBinding *b = scope_find(&p->scope, l->ident);
+ if (b) {
+ node = b->node;
+ } else {
+ lex_error(l, LE_ERROR, S("undeclared identifier"));
+ }
+ lex_next(l);
} else {
lex_expected(l, TM_LIT_NUM);
int64_t val = 0;
for (int i = 0; i < l->ident.n; i++) {
if (!(l->ident.s[i] >= '0' && l->ident.s[i] <= '9')) {
- lex_error(l, LE_ERROR, S("Not a digit"));
+ lex_error(l, LE_ERROR, S("not a digit"));
break;
}
val = (val * 10) + (l->ident.s[i] - '0');
@@ -375,8 +519,8 @@ Node *parse_term(Lexer *l, Proc *p) {
node->src_pos = l->pos;
lex_next(l);
}
- if (negate_after) {
- node = node_new(p, N_OP_NEG, node);
+ if (op_after != N_START) {
+ node = node_new(p, op_after, node_peephole(node, p, l));
}
return node_peephole(node, p, l);
}
generated by cgit v1.2.3 (git 2.46.0) at 2025-11-15 12:23:54 +0000