From a7c4a9e74388579b6bb718e33e9944d23ea2eba7 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Tue, 13 Dec 2022 21:42:30 -0500 Subject: [PATCH] added string refcounting logic --- cerise/backend/ssa/codegen.c | 73 +++++++++++++++++++++++++++++++ cerise/inc/cerise.h | 7 ++- cerise/src/grammar.c | 85 ++++++++++-------------------------- cerise/src/ssa.c | 55 ++++++++++++++++++++++- cerise/src/type_checks.c | 8 +++- cerise/tests/A.m | 10 +++++ 6 files changed, 170 insertions(+), 68 deletions(-) diff --git a/cerise/backend/ssa/codegen.c b/cerise/backend/ssa/codegen.c index 8408d17..ba0df9b 100644 --- a/cerise/backend/ssa/codegen.c +++ b/cerise/backend/ssa/codegen.c @@ -117,6 +117,54 @@ void codegen_init(Parser* p) fout(p, "%%Int = type i64\n"); fout(p, "%%Real = type double\n"); fout(p, "%%String = type i8*\n"); + fout(p, "declare ptr @allocate(i64)\n"); + fout(p, "declare void @deallocate(ptr)\n"); + fout(p, + "%%obj.header.t = type { i64 }" + "\n" + "define private void @addref(ptr %%0) {\n" + " %%2 = icmp eq ptr %%0, null\n" + " br i1 %%2, label %%7, label %%3\n" + "3:\n" + " %%4 = getelementptr inbounds %%obj.header.t, ptr %%0, i64 -1\n" + " %%5 = load i64, ptr %%4, align 8\n" + " %%6 = add nsw i64 %%5, 1\n" + " store i64 %%6, ptr %%4, align 8\n" + " br label %%7\n" + "7:\n" + " ret void\n" + "}\n" + "\n" + "define private void @delref(ptr %%0) {\n" + " %%2 = icmp eq ptr %%0, null\n" + " br i1 %%2, label %%9, label %%3\n" + "3:\n" + " %%4 = getelementptr inbounds %%obj.header.t, ptr %%0, i64 -1\n" + " %%5 = load i64, ptr %%4, align 8\n" + " %%6 = add nsw i64 %%5, -1\n" + " store i64 %%6, ptr %%4, align 8\n" + " %%7 = icmp eq i64 %%6, 0\n" + " br i1 %%7, label %%8, label %%9\n" + "8:\n" + " tail call void @deallocate(ptr %%0) #4\n" + " br label %%9\n" + "9:\n" + " ret void\n" + "}\n" + "\n" + "define private void @retref(ptr %%0) {\n" + " %%2 = icmp eq ptr %%0, null\n" + " br i1 %%2, label %%7, label %%3\n" + "3:\n" + " %%4 = getelementptr inbounds %%obj.header.t, ptr %%0, i64 -1\n" + " %%5 = load i64, ptr %%4, align 8\n" + " %%6 = add nsw i64 %%5, -1\n" + " store i64 %%6, ptr %%4, align 8\n" + " br label %%7\n" + "7:\n" + " ret void\n" + "}\n" + ); } void codegen_symbol(Parser* p, Symbol* sym) @@ -479,6 +527,31 @@ void print_op(Parser* p, SsaNode* expr) fout(p, "\n"); break; + case MODE_REFOP: + fout(p, " "); + fout(p, "call void "); + if (expr->code == '+') + { + fout(p, "@addref(ptr"); + print_oparg(p, expr->left); + fout(p, ")"); + } + else if (expr->code == '-') + { + fout(p, "@delref(ptr"); + print_oparg(p, expr->left); + fout(p, ")"); + } + else if (expr->code == '$') + { + fout(p, "@strcreate(ptr"); + print_oparg(p, expr->left); + fout(p, ")"); + } + + fout(p, "\n"); + break; + case MODE_VAR: case MODE_CONST: default: diff --git a/cerise/inc/cerise.h b/cerise/inc/cerise.h index 784933f..f1d62fd 100644 --- a/cerise/inc/cerise.h +++ b/cerise/inc/cerise.h @@ -196,6 +196,7 @@ enum { MODE_UNOP = 4, MODE_BINOP = 5, MODE_MEMORY = 6, + MODE_REFOP = 7, }; typedef struct Symbol { @@ -333,12 +334,16 @@ SsaBlock* ssa_block(Parser* p); void ssa_block_add(SsaBlock* blk, SsaNode* stmt); SsaNode* ssa_if(Parser* p, SsaNode* cond, SsaBlock* br1, SsaBlock* br2); -SsaNode* ssa_return(Parser* p, SsaNode* expr); +SsaNode* ssa_return(Parser* p, SsaNode* expr, size_t scope); SsaNode* ssa_branch(Parser* p, SsaBlock* br); SsaNode* ssa_call(Parser* p, SsaNode* func); void ssa_call_add(Parser* p, SsaNode* call, SsaNode* arg); +void ssa_addref(Parser* p, SsaNode* str); +void ssa_delref(Parser* p, SsaNode* str); +void ssa_takeref(Parser* p, SsaNode* str); + /* Backend Code Generation and Base Type Definitions *****************************************************************************/ extern Type VoidType, BoolType, IntType, RealType, StringType; diff --git a/cerise/src/grammar.c b/cerise/src/grammar.c index e7be311..77da701 100644 --- a/cerise/src/grammar.c +++ b/cerise/src/grammar.c @@ -48,43 +48,6 @@ static Field* add_field(Parser* p, Type* type, char* name, bool export) return field; } -/* Builtin Operations - *****************************************************************************/ -/* - String Operations: - - * String strcreate(i8* s) - * void strrefinc(String s) - * void strrefdec(String s) - -*/ - -void create_builtin(Parser* p, size_t rtmodid, char* name, char* spec) -{ - (void)spec; - Symbol* sym = symbol_new(p, rtmodid, name, SYM_PROC, 0); - sym->module = rtmodid; - sym->type = symbol_newtype(p); - sym->type->form = FORM_PROC; -} - -SsaNode* call_builtin(Parser* p, char* name) -{ - size_t modid = symbol_getid(p, 0, "Runtime", SYM_MODULE); - size_t symid = symbol_getid(p, modid, name, SYM_PROC); - SsaNode* builtin = ssa_ident(p, symid); - return ssa_call(p, builtin); -} - -SsaNode* string_create(Parser* p) -{ - SsaNode* expr = ssa_string(p, peek(p)->text); - SsaNode* call = call_builtin(p, "StringCreate"); - ssa_call_add(p, call, expr); - codegen_const(p, expr); - return expr; -} - /* Grammar Definition *****************************************************************************/ static SsaNode* expression(Parser* p); @@ -153,12 +116,12 @@ static SsaNode* designator(Parser* p) // // case '^': // // expect(p, '^'); // // break; -// -// // case '(': -// // qualident(p); -// // expect(p, ')'); -// // break; -// + +// case '(': +// qualident(p); +// expect(p, ')'); +// break; + default: done = 1; break; @@ -194,7 +157,7 @@ static SsaNode* factor(Parser* p) break; case STRING: - expr = string_create(p); + expr = ssa_string(p, peek(p)->text); consume(p); break; @@ -568,7 +531,7 @@ static void const_decl(Parser* p) EXIT_RULE(); } -Symbol* proc_type(Parser* p) +Symbol* proc_type(Parser* p, size_t* scope) { expect(p, PROCEDURE); char* name = expect_text(p, IDENT); @@ -588,7 +551,7 @@ Symbol* proc_type(Parser* p) proc->type = proctype; /* start scope and parse argument list */ - size_t scope = symbol_openscope(p); + *scope = symbol_openscope(p); expect(p, '('); while (!matches(p, ')')) { @@ -597,7 +560,7 @@ Symbol* proc_type(Parser* p) Type* argtype = type(p); proc->nargs++; add_field(p, proctype, name, false)->type = argtype; - symbol_new(p, scope, name, SYM_VAR, false)->type = argtype; + symbol_new(p, *scope, name, SYM_VAR, false)->type = argtype; if (!matches(p, ')')) { expect(p, ','); @@ -608,7 +571,7 @@ Symbol* proc_type(Parser* p) return proc; } -void proc_body(Parser* p, Symbol* proc) +void proc_body(Parser* p, Symbol* proc, size_t scope) { expect(p, BEGIN); SsaBlock* block = ssa_block(p); @@ -621,11 +584,11 @@ void proc_body(Parser* p, Symbol* proc) SsaNode* retval = expression(p); check_type(p, proc->type->base, retval); expect(p, ';'); - ssa_return(p, retval); + ssa_return(p, retval, scope); } else { - ssa_return(p, NULL); + ssa_return(p, NULL, scope); } expect(p, END); codegen_symbol(p, proc); @@ -636,7 +599,8 @@ void proc_decl(Parser* p) { ENTER_RULE(); - Symbol* proc = proc_type(p); + size_t scope = 0; + Symbol* proc = proc_type(p, &scope); /* parse the private declarations */ if (accept(p, CONST)) @@ -668,9 +632,11 @@ void proc_decl(Parser* p) else { proc->forward = 0; - proc_body(p, proc); + proc_body(p, proc, scope); } + symbol_closescope(p, scope); + EXIT_RULE(); } @@ -731,7 +697,6 @@ static void module(Parser* p) proctype->form = FORM_PROC; proctype->base = &VoidType; sym->type = proctype; - codegen_symbol(p, sym); SsaBlock* block = ssa_block(p); p->curr_join = ssa_block(p); @@ -742,14 +707,14 @@ static void module(Parser* p) if (!matches(p, END)) { block->links[0] = statement_seq(p); - ssa_return(p, NULL); + ssa_return(p, NULL, 0); } else { block->links[0] = ssa_block(p); block->links[0]->links[0] = p->curr_join; p->curr_block = block->links[0]; - ssa_return(p, NULL); + ssa_return(p, NULL, 0); } expect(p, END); } @@ -758,9 +723,10 @@ static void module(Parser* p) block->links[0] = ssa_block(p); block->links[0]->links[0] = p->curr_join; p->curr_block = block->links[0]; - ssa_return(p, NULL); + ssa_return(p, NULL, 0); } ssa_join(p); + codegen_symbol(p, sym); codegen_block(p, block); if (!matches(p, END_FILE)) @@ -800,13 +766,6 @@ static void init_parser(Parser* p, char* path, bool genmain) symbol_new(p, 0, "Int", SYM_TYPE, 0)->type = &IntType; symbol_new(p, 0, "Real", SYM_TYPE, 0)->type = &RealType; symbol_new(p, 0, "String", SYM_TYPE, 0)->type = &StringType; - Symbol* rt = symbol_new(p, 0, "Runtime", SYM_MODULE, 0); - size_t rtmodid = rt - &p->syms[0]; - create_builtin(p, rtmodid, "StringCreate", "s"); -// Symbol* sym = symbol_new(p, rtmodid, "StringCreate", SYM_PROC, 0); -// sym->module = rtmodid; -// sym->type = symbol_newtype(p); -// sym->type->form = FORM_PROC; } static void compile_module(Parser* p, char* path, bool genmain) diff --git a/cerise/src/ssa.c b/cerise/src/ssa.c index ba588a1..7f77244 100644 --- a/cerise/src/ssa.c +++ b/cerise/src/ssa.c @@ -181,9 +181,11 @@ SsaNode* ssa_real(Parser* p, double val) SsaNode* ssa_string(Parser* p, char* val) { (void)p; + /* TODO: create a string refop here */ SsaNode* node = ssa_node(STRING, MODE_CONST); node->type = &StringType; SSA_VAL(node).s = val; + codegen_const(p, node); return node; } @@ -201,6 +203,7 @@ SsaNode* ssa_store(Parser* p, SsaNode* dest, SsaNode* value) { dest = load(p, dest); } + ssa_addref(p, value); // add ref count increment if necessary SsaNode* node = ssa_node(STORE, MODE_MEMORY); node->type = dest->type; @@ -209,7 +212,6 @@ SsaNode* ssa_store(Parser* p, SsaNode* dest, SsaNode* value) if (!symbol_getbyid(p, SSA_VAR(node).symid)->global) { -// SSA_VAR(node).symver = phi_add(p, SSA_VAR(node)); (void)phi_add(p, SSA_VAR(node)); } ssa_block_add(p->curr_block, node); @@ -299,8 +301,21 @@ SsaNode* ssa_if(Parser* p, SsaNode* cond, SsaBlock* br1, SsaBlock* br2) return node; } -SsaNode* ssa_return(Parser* p, SsaNode* expr) +SsaNode* ssa_return(Parser* p, SsaNode* expr, size_t scope) { + ssa_addref(p, expr); + + /* run destructors and close the scope */ + if (scope > 0) + { + printf("cleanup %s:\n", symbol_getbyid(p, scope-1)->name); + for (size_t i = scope; i < p->nsyms; i++) + { + ssa_delref(p, ssa_ident(p, i)); + printf(" %s\n", p->syms[i].name); + } + } + SsaNode* node = ssa_node(RETURN, MODE_CTRL); if (expr) { @@ -349,6 +364,7 @@ void ssa_call_add(Parser* p, SsaNode* call, SsaNode* arg) { SsaNode* arglist = call->right; loadmem(p, arg); + ssa_addref(p, arg); arglist->value.args.nv++; arglist->value.args.v = realloc(arglist->value.args.v, arglist->value.args.nv * sizeof(SsaNode*)); assert(arglist->value.args.v); @@ -580,3 +596,38 @@ static SsaNode* loadmem(Parser* p, SsaNode* node) } return node; } + +void ssa_addref(Parser* p, SsaNode* val) +{ + (void)p; + /* if it's a string type being assigned, increment the reference */ + if (val && val->type && val->type->form == FORM_STRING) + { + SsaNode* node = ssa_node('+', MODE_REFOP); + node->type = &VoidType; + node->left = val; + load(p, node); + } +} + +void ssa_delref(Parser* p, SsaNode* val) +{ + (void)p; + /* if it's a string type being assigned, increment the reference */ + if (val->type->form == FORM_STRING) + { + SsaNode* node = ssa_node('-', MODE_REFOP); + node->type = &VoidType; + node->left = val; + load(p, node); + } +} + +void ssa_takeref(Parser* p, SsaNode* val) +{ + (void)p; + SsaNode* node = ssa_node('^', MODE_REFOP); + node->type = &VoidType; + node->left = val; + load(p, node); +} diff --git a/cerise/src/type_checks.c b/cerise/src/type_checks.c index a5802da..0cff44f 100644 --- a/cerise/src/type_checks.c +++ b/cerise/src/type_checks.c @@ -98,12 +98,16 @@ void check_type(Parser* p, Type* type, SsaNode* a) { check_bool(p, a); } + else if (type->form == FORM_STRING) + { + check_string(p, a); + } // else if (a->type->form == FORM_ARRAY) // { // } else { - error(p, "unimplemented type check!"); + assert(!"unimplemented type check!"); } } @@ -131,7 +135,7 @@ void check_types(Parser* p, SsaNode* a, SsaNode* b) // } else { - error(p, "unimplemented type check!"); + assert(!"unimplemented type check!"); } } diff --git a/cerise/tests/A.m b/cerise/tests/A.m index 7ff8336..bc9076d 100644 --- a/cerise/tests/A.m +++ b/cerise/tests/A.m @@ -7,6 +7,7 @@ procedure Foo*() : Int forward procedure Bar*() : Int +var a : Int begin return Foo(); end @@ -15,3 +16,12 @@ procedure Foo*() : Int begin return 0; end + +procedure Baz*(a : String, b : String) : String +begin + return a; +end + +begin + Baz("abc", "def"); +end \ No newline at end of file -- 2.49.0