From 08def1ad5a24fb38276ebf28e8b9b32b29a56000 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Fri, 9 Jul 2021 15:14:15 -0400 Subject: [PATCH] unary constant operations are working --- cerise/backend/ssa/codegen.c | 4 + cerise/backend/test/codegen.c | 4 + cerise/inc/cerise.h | 17 +++-- cerise/src/ast.c | 135 +++++++++++++++++++++++++++++----- cerise/src/const_ops.c | 34 --------- cerise/src/grammar.c | 19 ++--- 6 files changed, 146 insertions(+), 67 deletions(-) diff --git a/cerise/backend/ssa/codegen.c b/cerise/backend/ssa/codegen.c index 056efd7..f8b6d77 100644 --- a/cerise/backend/ssa/codegen.c +++ b/cerise/backend/ssa/codegen.c @@ -2,6 +2,10 @@ #include #include +Type VoidType = { + .form = FORM_VOID, +}; + Type BoolType = { .form = FORM_BOOL, .size = sizeof(bool) diff --git a/cerise/backend/test/codegen.c b/cerise/backend/test/codegen.c index c57491a..7fb8a23 100644 --- a/cerise/backend/test/codegen.c +++ b/cerise/backend/test/codegen.c @@ -2,6 +2,10 @@ #include #include +Type VoidType = { + .form = FORM_VOID, +}; + Type BoolType = { .form = FORM_BOOL, .size = sizeof(bool) diff --git a/cerise/inc/cerise.h b/cerise/inc/cerise.h index def3378..80ad248 100644 --- a/cerise/inc/cerise.h +++ b/cerise/inc/cerise.h @@ -91,7 +91,7 @@ typedef struct Field { typedef struct Type { enum { FORM_BOOL, FORM_INT, FORM_REAL, FORM_ARRAY, FORM_STRING, - FORM_RECORD, FORM_PROC, + FORM_RECORD, FORM_PROC, FORM_VOID, FORM_COUNT } form; struct Field* fields; @@ -105,6 +105,8 @@ typedef union { char* s; } Operand; +struct AstNode; + typedef struct Symbol { enum{ SYM_SCOPE, SYM_CONST, SYM_VAR, SYM_TYPE, SYM_PROC, SYM_FIELD @@ -112,8 +114,8 @@ typedef struct Symbol { char* name; Type* type; struct Symbol* desc; + struct AstNode* value; long nargs; - Operand imm; int export : 1; int global : 1; } Symbol; @@ -207,7 +209,7 @@ long size_of(Type* type); /* Backend Code Generation *****************************************************************************/ -extern Type BoolType, IntType, RealType, StringType; +extern Type VoidType, BoolType, IntType, RealType, StringType; void codegen_startmod(Parser* p); void codegen_endmod(Parser* p); @@ -234,7 +236,11 @@ void codegen_field(Parser* p, Item* record, char* name); /* Abstract Syntax Tree Definition *****************************************************************************/ -struct AstNode; +//enum AstMode { +// AST_CONST = 0, +// AST_EXPR, +// AST_CTRL, +//}; typedef struct { int code : 28; @@ -257,8 +263,7 @@ typedef struct { } val; } AstValue; -AstNode* ast_new(int type, AstNode* l0, AstNode* l1, AstNode* l2); -AstNode* ast_ident(long long index); +AstNode* ast_ident(Parser* p, long long index); AstNode* ast_bool(bool val); AstNode* ast_int(long long val); AstNode* ast_real(double val); diff --git a/cerise/src/ast.c b/cerise/src/ast.c index 40e7735..52ea2ea 100644 --- a/cerise/src/ast.c +++ b/cerise/src/ast.c @@ -2,48 +2,103 @@ /* Optimizations to Perform: -* Constant folding - (Constant expression evaluation) -* Dead code elimination -* Block coalescing -* + * Constant folding - (Constant expression evaluation) + * Dead code elimination - (when building conditional and loop nodes) + * Block coalescing (see above) + + * https://en.wikipedia.org/wiki/Bounds-checking_elimination + * https://en.wikipedia.org/wiki/Compile-time_function_execution + * https://en.wikipedia.org/wiki/Common_subexpression_elimination + * https://en.wikipedia.org/wiki/Copy_propagation + * https://en.wikipedia.org/wiki/Dead_code_elimination + * https://en.wikipedia.org/wiki/Dead_store + * https://en.wikipedia.org/wiki/Induction_variable + * https://en.wikipedia.org/wiki/Inline_expansion + * https://en.wikipedia.org/wiki/Interprocedural_optimization + * https://en.wikipedia.org/wiki/Jump_threading + * https://en.wikipedia.org/wiki/Loop_inversion + * https://en.wikipedia.org/wiki/Loop-invariant_code_motion + * https://en.wikipedia.org/wiki/Redundant_code + * https://en.wikipedia.org/wiki/Value_numbering */ +static bool is_const(AstNode* node) +{ + bool ret; + switch (node->hdr.code) + { + case BOOL: + case INT: + case REAL: + case IDENT: + ret = true; + break; + + default: + ret = false; + break; + } + return ret; +} + +static bool both_const(AstNode* left, AstNode* right) +{ + return is_const(left) && is_const(right); +} -AstNode* ast_new(int type, AstNode* l0, AstNode* l1, AstNode* l2) +static AstNode* ast_new(int code, Type* type, AstNode* l0, AstNode* l1, AstNode* l2) { AstNode* node = calloc(1, sizeof(AstNode)); - node->hdr.code = type; + node->hdr.code = code; + node->hdr.type = type; node->links[0] = l0; node->links[1] = l1; node->links[2] = l2; return node; } -AstNode* ast_ident(long long index) +static AstNode* ast_clone(AstNode* parent) { - AstValue* node = (AstValue*)ast_new(IDENT, NULL, NULL, NULL); - node->val.i = index; + AstNode* node = calloc(1, sizeof(AstNode)); + *node = *parent; + return node; +} + +AstNode* ast_ident(Parser* p, long long index) +{ + Symbol* sym = symbol_getbyid(p, (size_t)index); + AstNode* node; + if (sym && sym->class == SYM_CONST) + { + assert(sym->value != NULL); + node = ast_clone(sym->value); + } + else + { + node = ast_new(IDENT, sym->type, NULL, NULL, NULL); + ((AstValue*)node)->val.i = index; + } return (AstNode*)node; } AstNode* ast_bool(bool val) { - AstValue* node = (AstValue*)ast_new(BOOL, NULL, NULL, NULL); + AstValue* node = (AstValue*)ast_new(BOOL, &BoolType, NULL, NULL, NULL); node->val.i = val; return (AstNode*)node; } AstNode* ast_int(long long val) { - AstValue* node = (AstValue*)ast_new(INT, NULL, NULL, NULL); + AstValue* node = (AstValue*)ast_new(INT, &IntType, NULL, NULL, NULL); node->val.i = val; return (AstNode*)node; } AstNode* ast_real(double val) { - AstValue* node = (AstValue*)ast_new(REAL, NULL, NULL, NULL); + AstValue* node = (AstValue*)ast_new(REAL, &RealType, NULL, NULL, NULL); node->val.f = val; return (AstNode*)node; } @@ -52,18 +107,58 @@ AstNode* ast_binop(int op, AstNode* left, AstNode* right) { assert(left); assert(right); - return ast_new(op, left, right, NULL); + return ast_new(op, left->hdr.type, left, right, NULL); } AstNode* ast_unop(int op, AstNode* operand) { assert(operand); - return ast_new(op, operand, NULL, NULL); + AstNode* ret = NULL; + if (is_const(operand)) + { + AstValue* a = (AstValue*)operand; + if (a->hdr.type->form == FORM_INT) + { + switch (op) + { + case '+': a->val.i = +a->val.i; break; + case '-': a->val.i = -a->val.i; break; + default: assert(!"not a valid op"); break; + } + } + else if (a->hdr.type->form == FORM_REAL) + { + switch (op) + { + case '+': a->val.f = +a->val.f; break; + case '-': a->val.f = -a->val.f; break; + default: assert(!"not a valid op"); break; + } + } + else if (a->hdr.type->form == FORM_BOOL) + { + switch (op) + { + case NOT: a->val.i = !a->val.i; break; + default: assert(!"not a valid op"); break; + } + } + else + { + assert(!"not a valid form"); + } + ret = (AstNode*)a; + } + else + { + ret = ast_new(op, operand->hdr.type, operand, NULL, NULL); + } + return ret; } AstNode* ast_block(void) { - return ast_new(BEGIN, NULL, NULL, NULL); + return ast_new(BEGIN, &VoidType, NULL, NULL, NULL); } void ast_block_add(AstNode* func) @@ -74,7 +169,7 @@ void ast_block_add(AstNode* func) AstNode* ast_call(AstNode* func) { - return ast_new(CALL, func, NULL, NULL); + return ast_new(CALL, func->hdr.type, func, NULL, NULL); } void ast_call_add(AstNode* func) @@ -85,12 +180,12 @@ void ast_call_add(AstNode* func) AstNode* ast_if(AstNode* cond, AstNode* br1, AstNode* br2) { - return ast_new(IF, cond, br1, br2); + return ast_new(IF, &VoidType, cond, br1, br2); } AstNode* ast_return(AstNode* expr) { - return ast_new(RETURN, expr, NULL, NULL); + return ast_new(RETURN, &VoidType, expr, NULL, NULL); } void ast_print(AstNode* node) @@ -110,6 +205,10 @@ void ast_print(AstNode* node) printf("R:%f", ((AstValue*)node)->val.f); break; + case IDENT: + printf("S:%lld", ((AstValue*)node)->val.i); + break; + default: if (node->links[1]) { diff --git a/cerise/src/const_ops.c b/cerise/src/const_ops.c index 532f8f3..79bbeae 100644 --- a/cerise/src/const_ops.c +++ b/cerise/src/const_ops.c @@ -106,37 +106,3 @@ // } //} // -//void const_unop(Parser* p, int op, Item* a) -//{ -// (void)p; -// if (a->type->form == FORM_INT) -// { -// switch (op) -// { -// case '+': a->imm.i = +a->imm.i; break; -// case '-': a->imm.i = -a->imm.i; break; -// default: assert(!"not a valid op"); break; -// } -// } -// else if (a->type->form == FORM_REAL) -// { -// switch (op) -// { -// case '+': a->imm.f = +a->imm.f; break; -// case '-': a->imm.f = -a->imm.f; break; -// default: assert(!"not a valid op"); break; -// } -// } -// else if (a->type->form == FORM_BOOL) -// { -// switch (op) -// { -// case NOT: a->imm.i = !a->imm.i; break; -// default: assert(!"not a valid op"); break; -// } -// } -// else -// { -// assert(!"not a valid form"); -// } -//} diff --git a/cerise/src/grammar.c b/cerise/src/grammar.c index 21ea4dd..790dfbf 100644 --- a/cerise/src/grammar.c +++ b/cerise/src/grammar.c @@ -58,10 +58,8 @@ static AstNode* qualident(Parser* p) { ENTER_RULE(); - AstNode* expr = ast_ident(0); char* name = expect_text(p, IDENT); - (void)name; /* TODO: get real index of variable */ -// ir_load(p, name); + AstNode* expr = ast_ident(p, symbol_getid(p, name, -1)); // if (accept(p, '.')) // { @@ -131,6 +129,7 @@ static AstNode* designator(Parser* p) // } EXIT_RULE(); + assert(expr != NULL); return expr; } @@ -219,6 +218,7 @@ static AstNode* factor(Parser* p) } EXIT_RULE(); + assert(expr != NULL); return expr; } @@ -255,6 +255,7 @@ static AstNode* term(Parser* p) // } EXIT_RULE(); + assert(expr != NULL); return expr; } @@ -293,9 +294,9 @@ static AstNode* simple_expr(Parser* p) // codegen_binop(p, op, item, &right); // } - return expr; - EXIT_RULE(); + assert(expr != NULL); + return expr; } static AstNode* expression(Parser* p) @@ -315,9 +316,9 @@ static AstNode* expression(Parser* p) // codegen_binop(p, op, item, &right); // } - return expr; - EXIT_RULE(); + assert(expr != NULL); + return expr; } //RULE(type, Item* item) @@ -495,8 +496,8 @@ static void const_decl(Parser* p) export = accept(p, '*'); sym = symbol_new(p, 0, name, SYM_CONST, export); expect(p, '='); - AstNode* expr = expression(p); - ast_print(expr); + sym->value = expression(p); + ast_print(sym->value); puts(""); (void)sym; /* TODO: put const value into symbol table */ // ir_getconst(p, sym); -- 2.49.0