From 86c55937170b83c21a9cd1dc3e5be94b2ee4bf2e Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Wed, 14 Jul 2021 10:41:59 -0400 Subject: [PATCH] Got If statements and procedure definitions working. AST creation now self optimizes by performing constant folding, block coalescing and dead code removal during creation. This will result in less work for the optimizer. --- cerise/inc/cerise.h | 7 +- cerise/src/ast.c | 99 +++++++++++++++++----- cerise/src/grammar.c | 177 +++++++++++++++++---------------------- cerise/src/type_checks.c | 24 ++++++ cerise/tests/Module.m | 17 +++- 5 files changed, 195 insertions(+), 129 deletions(-) diff --git a/cerise/inc/cerise.h b/cerise/inc/cerise.h index 059aeb7..779737f 100644 --- a/cerise/inc/cerise.h +++ b/cerise/inc/cerise.h @@ -181,6 +181,7 @@ void check_num(Parser* p, AstNode* a); void check_nums(Parser* p, AstNode* a, AstNode* b); void check_bool(Parser* p, AstNode* a); void check_bools(Parser* p, AstNode* a, AstNode* b); +void check_type(Parser* p, Type* type, AstNode* a); void check_types(Parser* p, AstNode* a, AstNode* b); // src/grammar.c @@ -199,9 +200,9 @@ AstNode* ast_bool(bool val); AstNode* ast_int(long long val); AstNode* ast_real(double val); -bool ast_asbool(Parser* p, AstNode* node); -long long ast_asint(Parser* p, AstNode* node); -double ast_asreal(Parser* p, AstNode* node); +bool ast_asbool(AstNode* node); +long long ast_asint(AstNode* node); +double ast_asreal(AstNode* node); AstNode* ast_binop(int op, AstNode* left, AstNode* right); AstNode* ast_unop(int op, AstNode* operand); diff --git a/cerise/src/ast.c b/cerise/src/ast.c index ea5d876..f9a3163 100644 --- a/cerise/src/ast.c +++ b/cerise/src/ast.c @@ -2,9 +2,9 @@ /* Optimizations to Perform: - * Constant folding - (Constant expression evaluation) - * Dead code elimination - (when building conditional and loop nodes) - * Block coalescing (see above) + * (Done) Constant folding - (Constant expression evaluation) + * (Done) Dead code elimination - (when building conditional and loop nodes) + * (Done) Block coalescing (see above) * https://en.wikipedia.org/wiki/Bounds-checking_elimination * https://en.wikipedia.org/wiki/Compile-time_function_execution @@ -111,21 +111,21 @@ AstNode* ast_real(double val) return (AstNode*)node; } -bool ast_asbool(Parser* p, AstNode* node) +bool ast_asbool(AstNode* node) { - check_bool(p, node); + assert(node->hdr.type->form == FORM_BOOL); return (bool)(((AstValue*)node)->val.i); } -long long ast_asint(Parser* p, AstNode* node) +long long ast_asint(AstNode* node) { - check_int(p, node); + assert(node->hdr.type->form == FORM_INT); return ((AstValue*)node)->val.i; } -double ast_asreal(Parser* p, AstNode* node) +double ast_asreal(AstNode* node) { - check_real(p, node); + assert(node->hdr.type->form == FORM_REAL); return ((AstValue*)node)->val.f; } @@ -237,7 +237,21 @@ AstNode* ast_binop(int op, AstNode* left, AstNode* right) } else { - ret = ast_new(op, left->hdr.type, left, right, NULL); + switch (op) + { + case EQ: + case NEQ: + case '<': + case LTEQ: + case '>': + case GTEQ: + ret = ast_new(op, &BoolType, left, right, NULL); + break; + + default: + ret = ast_new(op, left->hdr.type, left, right, NULL); + break; + } } return ret; } @@ -332,7 +346,7 @@ AstNode* ast_fieldref(Parser* p, AstNode* record, char* fname) AstNode* ast_index(Parser* p, AstNode* array, AstNode* index) { - if (ast_isconst(index) && ast_asint(p, index) >= array->hdr.type->size) + if (ast_isconst(index) && ast_asint(index) >= array->hdr.type->size) { error(p, "constant array index out of bounds"); } @@ -344,18 +358,33 @@ AstNode* ast_block(void) return ast_new(BEGIN, &VoidType, NULL, NULL, NULL); } +static void append(AstNode* node, AstNode* first, AstNode* last) +{ + if (!node->links[0]) + { + node->links[0] = first; + node->links[1] = last; + } + else + { + node->links[1]->hdr.next = first; + node->links[1] = last; + } +} + void ast_block_add(AstNode* blk, AstNode* stmt) { assert(blk->hdr.code == BEGIN); - if (!blk->links[0]) + /* if we recieve a BEGIN block, we faltten it into the block by + appending all its statemtents */ + if (stmt->hdr.code == BEGIN) { - blk->links[0] = stmt; - blk->links[1] = stmt; + append(blk, stmt->links[0], stmt->links[1]); } + /* otherwise just append the statement to the block */ else { - blk->links[1]->hdr.next = stmt; - blk->links[1] = stmt; + append(blk, stmt, stmt); } } @@ -366,13 +395,21 @@ AstNode* ast_call(AstNode* func) void ast_call_add(AstNode* func, AstNode* arg) { - /* TODO: append to linked list */ - (void)func, (void)arg; + append(func, arg, arg); } AstNode* ast_if(AstNode* cond, AstNode* br1, AstNode* br2) { - return ast_new(IF, &VoidType, cond, br1, br2); + AstNode* ret; + if (ast_isconst(cond)) + { + ret = (ast_asbool(cond) ? br1 : br2); + } + else + { + ret = ast_new(IF, &VoidType, cond, br1, br2); + } + return ret; } AstNode* ast_return(AstNode* expr) @@ -400,6 +437,14 @@ static void print_opcode(AstNode* node) { printf("(%c\n", op); } + else if (op == RETURN) + { + printf("(return\n"); + } + else if (op == IF) + { + printf("(if\n"); + } else { printf("(%d\n", op); @@ -448,10 +493,24 @@ static void print(Parser* p, AstNode* node, int indent) { print(p, curr, indent+1); } - printf(")"); + print_indent(indent, ")"); } break; + case IF: + { + printf("(if\n"); + print(p, node->links[0], indent+1); + print(p, node->links[1], indent+1); + if (node->links[2]) + { + print(p, node->links[2], indent+1); + } + print_indent(indent, ")"); + } + break; + + default: if (node->links[1]) { diff --git a/cerise/src/grammar.c b/cerise/src/grammar.c index 63ba7f1..de79f23 100644 --- a/cerise/src/grammar.c +++ b/cerise/src/grammar.c @@ -329,7 +329,8 @@ static Type* type(Parser* p) { error(p, "non-constant array size"); } - long long length = ast_asint(p, lnode); + check_int(p, lnode); + long long length = ast_asint(lnode); expect(p, OF); Type* base = type(p); ret = calloc(1, sizeof(Type)); @@ -408,29 +409,6 @@ static AstNode* statement_seq(Parser* p) } ast_block_add(block, ast_if(cond, blk1, blk2)); expect(p, END); - -// codegen_if(p, item); -// expect(p, THEN); -// statement_seq(p, &(Item){0}); -// int elsifs = 0; -// while (accept(p, ELSIF)) -// { -// elsifs++; -// codegen_else(p, item); -// expression(p, item); -// check_bool(p, item); -// codegen_if(p, item); -// expect(p, THEN); -// statement_seq(p, &(Item){0}); -// } -// if (accept(p, ELSE)) -// { -// codegen_else(p, item); -// statement_seq(p, &(Item){0}); -// } -// codegen_endif(p, elsifs, item); -// expect(p, END); -// ast_block_add(block, ast_binop('=', left, right)); } else /* assignments/expressions */ { @@ -506,80 +484,75 @@ static void const_decl(Parser* p) EXIT_RULE(); } -//RULE(proc_decl, Item* item) -//{ -// ENTER_RULE(); -// expect(p, PROCEDURE); -// char* name = expect_text(p, IDENT); -// bool export = accept(p, '*'); -// Symbol* proc = symbol_new(p, 0, name, SYM_PROC, export); -// Type* proctype = calloc(1, sizeof(Type)); -// proctype->form = FORM_PROC; -// proc->type = proctype; -// size_t scope = symbol_openscope(p); -// -// /* construct the proc type */ -// expect(p, '('); -// while (!matches(p, ')')) -// { -// char* name = expect_text(p, IDENT); -// expect(p, ':'); -// type(p, item); -// proc->nargs++; -// add_field(p, proctype, name, false)->type = item->type; -// symbol_new(p, scope, name, SYM_VAR, export)->type = item->type; -// if (!matches(p, ')')) -// { -// expect(p, ','); -// } -// } -// expect(p, ')'); -// if (accept(p, ':')) -// { -// type(p, item); -// proctype->base = item->type; -// } -// -// codegen_startproc(p, proc); -// -// /* parse the declarations */ -// if (accept(p, CONST)) -// { -// const_decl(p, item); -// } -// -// if (accept(p, TYPE)) -// { -// type_decl(p, item); -// } -// -// if (accept(p, VAR)) -// { -// var_decl(p, item); -// } -// -// /* parse the body of the procedure */ -// expect(p, BEGIN); -// if (!matches(p, RETURN) && !matches(p, END)) -// { -// statement_seq(p, item); -// } -// if (accept(p, RETURN)) -// { -// expression(p, item); -// codegen_return(p, item); -// expect(p, ';'); -// } -// else -// { -// codegen_return(p, NULL); -// } -// expect(p, END); -// -// codegen_endproc(p); -// symbol_closescope(p, scope); -// EXIT_RULE(); -//} +void proc_decl(Parser* p) +{ + ENTER_RULE(); + + expect(p, PROCEDURE); + char* name = expect_text(p, IDENT); + bool export = accept(p, '*'); + Symbol* proc = symbol_new(p, 0, name, SYM_PROC, export); + Type* proctype = calloc(1, sizeof(Type)); + proctype->form = FORM_PROC; + proc->type = proctype; + + /* start scope and parse argument list */ + size_t scope = symbol_openscope(p); + expect(p, '('); + while (!matches(p, ')')) + { + char* name = expect_text(p, IDENT); + expect(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; + if (!matches(p, ')')) + { + expect(p, ','); + } + } + expect(p, ')'); + proctype->base = (accept(p, ':') ? type(p) : &VoidType); + + /* parse the private declarations */ + if (accept(p, CONST)) + { + const_decl(p); + } + + if (accept(p, TYPE)) + { + type_decl(p); + } + + if (accept(p, VAR)) + { + var_decl(p); + } + + /* parse the body of the procedure */ + expect(p, BEGIN); + proc->value = ast_block(); + if (!matches(p, RETURN) && !matches(p, END)) + { + ast_block_add(proc->value, statement_seq(p)); + } + if (proctype->base != &VoidType) + { + expect(p, RETURN); + AstNode* retval = expression(p); + check_type(p, proctype->base, retval); + ast_block_add(proc->value, ast_return(retval)); + expect(p, ';'); + } + expect(p, END); + symbol_closescope(p, scope); + + ast_print(p, proc->value); + + EXIT_RULE(); +} static void import_list(Parser* p) { @@ -641,10 +614,10 @@ static void module(Parser* p) var_decl(p); } -// while (matches(p, PROCEDURE)) -// { -// proc_decl(p); -// } + while (matches(p, PROCEDURE)) + { + proc_decl(p); + } if (accept(p, BEGIN)) { diff --git a/cerise/src/type_checks.c b/cerise/src/type_checks.c index ff98dda..38c7b63 100644 --- a/cerise/src/type_checks.c +++ b/cerise/src/type_checks.c @@ -70,6 +70,29 @@ void check_bools(Parser* p, AstNode* a, AstNode* b) check_bool(p, b); } +void check_type(Parser* p, Type* type, AstNode* a) +{ + if (type->form == FORM_REAL) + { + check_real(p, a); + } + else if (type->form == FORM_INT) + { + check_int(p, a); + } + else if (type->form == FORM_BOOL) + { + check_bool(p, a); + } +// else if (a->hdr.type->form == FORM_ARRAY) +// { +// } + else + { + error(p, "unimplemented type check!"); + } +} + void check_types(Parser* p, AstNode* a, AstNode* b) { // printf("%d %d\n", a->hdr.type->form, b->hdr.type->form); @@ -93,3 +116,4 @@ void check_types(Parser* p, AstNode* a, AstNode* b) error(p, "unimplemented type check!"); } } + diff --git a/cerise/tests/Module.m b/cerise/tests/Module.m index 15c976a..64187f5 100644 --- a/cerise/tests/Module.m +++ b/cerise/tests/Module.m @@ -54,10 +54,19 @@ var # return z1; #end -#procedure Bar(a : Int) : Int -#begin -# return a; -#end +procedure Bar(a : Int) : Int +begin + return a; +end + +procedure Baz(a : Int) +begin + if (1 > 2) then + 42; + else + 24; + end +end begin # h[1].i = 42; -- 2.49.0