From b5415099835e85e8ab9b51c121dffd4a2db605ff Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Fri, 11 Feb 2022 20:52:06 -0500 Subject: [PATCH] typedefs, globals, and function defs working for llvm ir --- cerise/backend/ssa/codegen.c | 237 ++++++++++++++++++++++++++++++----- cerise/build.sh | 3 +- cerise/inc/cerise.h | 3 - cerise/opcodes.c | 34 +++++ cerise/src/grammar.c | 2 +- cerise/src/ssa.c | 164 ------------------------ 6 files changed, 240 insertions(+), 203 deletions(-) create mode 100644 cerise/opcodes.c diff --git a/cerise/backend/ssa/codegen.c b/cerise/backend/ssa/codegen.c index 571eaf6..5056505 100644 --- a/cerise/backend/ssa/codegen.c +++ b/cerise/backend/ssa/codegen.c @@ -26,25 +26,7 @@ Type StringType = { .size = -1 }; -static char* strmcat(char* first, ...) { - va_list args; - /* calculate the length of the final string */ - size_t len = strlen(first); - va_start(args, first); - for (char* s = NULL; (s = va_arg(args, char*));) - len += strlen(s); - va_end(args); - /* allocate the final string and copy the args into it */ - char *str = malloc(len+1), *curr = str; - while (first && *first) *(curr++) = *(first++); - va_start(args, first); - for (char* s = NULL; (s = va_arg(args, char*));) - while (s && *s) *(curr++) = *(s++); - va_end(args); - /* null terminate and return */ - *curr = '\0'; - return str; -} +void emit_type(Type* type); void declare_record_type(Type* type) { @@ -60,11 +42,11 @@ void declare_record_type(Type* type) } /* ok print the top level typedef */ - int len = snprintf(NULL, 0, "%%struct.%p", (void*)type); + int len = snprintf(NULL, 0, "struct.%p", (void*)type); type->name = calloc(1, len+1); - (void)snprintf(type->name, len+1, "%%struct.%p", (void*)type); + (void)snprintf(type->name, len+1, "struct.%p", (void*)type); - printf("%s = type { ", type->name); + printf("%%%s = type { ", type->name); for (Field* f = type->fields; f; f = f->next) { emit_type(f->type); @@ -85,11 +67,14 @@ void emit_type(Type* type) case FORM_BOOL: printf("%%Bool"); break; case FORM_INT: printf("%%Int"); break; case FORM_REAL: printf("%%Real"); break; - case FORM_VOID: printf("%%Void"); break; + case FORM_VOID: printf("void"); break; case FORM_STRING: printf("%%String"); break; case FORM_ARRAY: - printf("[]"); + printf("[%d x ", type->size); + emit_type(type->base); + printf("]"); + break; case FORM_RECORD: @@ -109,7 +94,6 @@ void codegen_init(Parser* p) printf("%%Bool = type i1\n"); printf("%%Int = type i64\n"); printf("%%Real = type double\n"); - printf("%%Void = type void\n"); printf("%%String = type { i64, i8* }\n"); } @@ -118,11 +102,22 @@ void codegen_symbol(Parser* p, Symbol* sym) (void)p; if (sym->class == SYM_VAR) { - printf("@%s = %s global ", - sym->name, - (sym->export ? "dso_local" : "internal")); + printf("@%s = global ", sym->name); emit_type(sym->type); - printf(" 0\n"); + + if (sym->type->form == FORM_ARRAY || sym->type->form == FORM_RECORD) + { + printf(" zeroinitializer\n"); + } + else if (sym->type->form == FORM_REAL) + { + printf(" 0.0\n"); + } + else + { + printf(" 0\n"); + } + puts(""); } else if (sym->class == SYM_TYPE) { @@ -130,17 +125,191 @@ void codegen_symbol(Parser* p, Symbol* sym) { declare_record_type(sym->type); } - printf("%c%s = type \n", (sym->global ? '@' : '%'), sym->name); + printf("%%%s = type ", sym->name); + emit_type(sym->type); + puts("\n"); } else if (sym->class == SYM_PROC) { - printf("define %c%s\n", (sym->global ? '@' : '%'), sym->name); + printf("define "); + emit_type(sym->type->base); + printf(" @%s(", sym->name); + for (Field* f = sym->type->fields; f; f = f->next) + { + emit_type(f->type); + printf(" %%%s.0", f->name); + if (f->next) + { + printf(", "); + } + } + printf(")\n"); } - puts(""); } -void codegen_block(Parser* p, SsaBlock* block) +static void topsort(Bitset* set, SsaBlock** sorted, SsaBlock* block) +{ + if (block && !bitset_has(set, block->id)) + { + /* mark it visited and visit children */ + bitset_add(set, block->id); + topsort(set, sorted, block->links[1]); + topsort(set, sorted, block->links[0]); + + /* push block to the sorted list */ + block->next = *sorted; + *sorted = block; + } +} + +static void print_ident(Parser* p, SsaVar* var) +{ + Symbol* s = symbol_getbyid(p, var->symid); + printf("%s.%lu", s->name, var->symver); +} + +static void print_dest(Parser* p, SsaNode* node) +{ + if (node->mode != MODE_CONTROL) + { + print_ident(p, &(node->dest)); + printf(" = "); + } +} + +static void print_opcode(SsaNode* node) +{ + int op = node->code; + if (op < 256) + { + printf(" %c ", op); + } + else if (op == RETURN) + { + printf(" return "); + } + else if (op == IF) + { + printf("if "); + } + else if (op == EQ) + { + printf(" == "); + } + else if (op == NEQ) + { + printf(" != "); + } + else if (op == LTEQ) + { + printf(" <= "); + } + else if (op == GTEQ) + { + printf(" >= "); + } + else + { + printf("%d\n", op); + } +} + +void print_op(Parser* p, SsaNode* expr) { (void)p; - (void)block; + switch(expr->code) + { + case IDENT: + print_ident(p, &(expr->left.var)); + break; + + case BOOL: + printf("(Bool)%d", ssa_asbool(expr)); + break; + + case INT: + printf("(Int)%lld", ssa_asint(expr)); + break; + + case REAL: + printf("(Real)%f", ssa_asreal(expr)); + break; + + case IF: + printf("if "); + print_ident(p, &(expr->dest)); + printf(" then block%lu else block%lu", expr->left.block->id, expr->right.block->id); + break; + + case RETURN: + printf("return "); + print_ident(p, &(expr->dest)); + break; + + default: + if (expr->mode == MODE_VAR) + { + print_ident(p, &(expr->left.var)); + } + else if (expr->mode == MODE_UNOP) + { + print_opcode(expr); + print_ident(p, &(expr->left.var)); + } + else if (expr->mode == MODE_BINOP) + { + print_ident(p, &(expr->left.var)); + print_opcode(expr); + print_ident(p, &(expr->right.var)); + } + else + { + printf("??? M:%d C:%d\n", expr->mode, expr->code); + } + break; + } +} + + +void codegen_block(Parser* p, SsaBlock* block) +{ + /* perform a topological sort of the nodes */ + SsaBlock* sorted = NULL; + Bitset* set = bitset_new(p->blockid); + topsort(set, &sorted, block); + + /* now let's print the plantuml representation */ + printf("{\n"); + for (SsaBlock* curr = sorted; curr; curr = curr->next) + { + printf("L%lu:\n", curr->id); + /* print the phis */ + for (SsaPhi* phi = curr->phis; phi; phi = phi->next) + { + Symbol* s = symbol_getbyid(p, phi->symid); + printf(" %%%s.%lu = phi ", s->name, phi->latest_ver); + emit_type(s->type); + printf(" "); + for (SsaPhiVar* var = phi->vars; var; var = var->next) + { + printf("[%%%s.%lu, %%L%lu]", s->name, var->version, var->block); + if (var->next) + { + printf(", "); + } + } + puts(""); + } + + /* print the instructions */ + for (SsaNode* node = curr->head; node; node = node->next) + { + printf(" "); + print_dest(p, node); + print_op(p, node); + puts(""); + } + } + printf("}\n"); + puts(""); } diff --git a/cerise/build.sh b/cerise/build.sh index b8bd72c..f4ad61d 100755 --- a/cerise/build.sh +++ b/cerise/build.sh @@ -11,7 +11,8 @@ grep -rh TODO src/*.* backend/*/*.* | sed -E -e 's/ *\/\/ *//' -e 's/ *\/\* *(.* $CCCMD -D CERISE_TESTS -o cerisec-test src/*.c backend/test/*.c \ && $CCCMD -o cerisec src/*.c "backend/ssa"/*.c \ && ./cerisec-test \ -&& ./cerisec tests/Module.m +&& (./cerisec tests/Module.m | tee test.l) \ +&& llc test.l rm -f Module diff --git a/cerise/inc/cerise.h b/cerise/inc/cerise.h index 4d664bc..511d549 100644 --- a/cerise/inc/cerise.h +++ b/cerise/inc/cerise.h @@ -285,9 +285,6 @@ SsaNode* ssa_return(Parser* p, SsaNode* expr); SsaNode* ssa_call(SsaNode* func); void ssa_call_add(SsaBlock* call, SsaNode* arg); -void ssa_print(Parser* p, SsaNode* expr); -void ssa_print_asm(Parser* p, SsaBlock* block); - /* Backend Code Generation and Base Type Definitions *****************************************************************************/ extern Type VoidType, BoolType, IntType, RealType, StringType; diff --git a/cerise/opcodes.c b/cerise/opcodes.c new file mode 100644 index 0000000..2326719 --- /dev/null +++ b/cerise/opcodes.c @@ -0,0 +1,34 @@ +#include + +bool cmp1(int a, int b) { return a < b; } +bool cmp2(int a, int b) { return a > b; } +bool cmp3(int a, int b) { return a <= b; } +bool cmp4(int a, int b) { return a >= b; } +bool cmp5(int a, int b) { return a == b; } +bool cmp6(int a, int b) { return a != b; } + +bool fcmp1(double a, double b) { return a < b; } +bool fcmp2(double a, double b) { return a > b; } +bool fcmp3(double a, double b) { return a <= b; } +bool fcmp4(double a, double b) { return a >= b; } +bool fcmp5(double a, double b) { return a == b; } +bool fcmp6(double a, double b) { return a != b; } + +int op1(int a, int b) { return a + b; } +int op2(int a, int b) { return a - b; } +int op3(int a, int b) { return a * b; } +int op4(int a, int b) { return a / b; } +int op5(int a, int b) { return a % b; } +int op6(int a) { return -a; } + +double fop1(double a, double b) { return a + b; } +double fop2(double a, double b) { return a - b; } +double fop3(double a, double b) { return a * b; } +double fop4(double a, double b) { return a / b; } +double fop5(double a, double b) { return a % b; } +double fop6(double a) { return -a; } + +bool bop1(bool a, bool b) { return a && b; } +bool bop2(bool a, bool b) { return a || b; } +bool bop3(bool a) { return !a; } + diff --git a/cerise/src/grammar.c b/cerise/src/grammar.c index 8b015b0..8ee12e4 100644 --- a/cerise/src/grammar.c +++ b/cerise/src/grammar.c @@ -537,7 +537,6 @@ void proc_decl(Parser* p) Type* proctype = symbol_newtype(p); proctype->form = FORM_PROC; proc->type = proctype; - codegen_symbol(p, proc); /* start scope and parse argument list */ size_t scope = symbol_openscope(p); @@ -557,6 +556,7 @@ void proc_decl(Parser* p) } expect(p, ')'); proctype->base = (accept(p, ':') ? type(p) : &VoidType); + codegen_symbol(p, proc); /* parse the private declarations */ if (accept(p, CONST)) diff --git a/cerise/src/ssa.c b/cerise/src/ssa.c index 699bf0e..ff85c45 100644 --- a/cerise/src/ssa.c +++ b/cerise/src/ssa.c @@ -456,167 +456,3 @@ static SsaNode* load(Parser* p, SsaNode* node) } return node; } - -static void print_ident(Parser* p, SsaVar* var) -{ - Symbol* s = symbol_getbyid(p, var->symid); - printf("%s.%lu", s->name, var->symver); -} - -static void print_dest(Parser* p, SsaNode* node) -{ - if (node->mode != MODE_CONTROL) - { - print_ident(p, &(node->dest)); - printf(" = "); - } -} - -static void print_opcode(SsaNode* node) -{ - int op = node->code; - if (op < 256) - { - printf(" %c ", op); - } - else if (op == RETURN) - { - printf(" return "); - } - else if (op == IF) - { - printf("if "); - } - else if (op == EQ) - { - printf(" == "); - } - else if (op == NEQ) - { - printf(" != "); - } - else if (op == LTEQ) - { - printf(" <= "); - } - else if (op == GTEQ) - { - printf(" >= "); - } - else - { - printf("%d\n", op); - } -} - -void ssa_print(Parser* p, SsaNode* expr) -{ - (void)p; - switch(expr->code) - { - case IDENT: - print_ident(p, &(expr->left.var)); - break; - - case BOOL: - printf("(Bool)%d", ssa_asbool(expr)); - break; - - case INT: - printf("(Int)%lld", ssa_asint(expr)); - break; - - case REAL: - printf("(Real)%f", ssa_asreal(expr)); - break; - - case IF: - printf("if "); - print_ident(p, &(expr->dest)); - printf(" then block%lu else block%lu", expr->left.block->id, expr->right.block->id); - break; - - case RETURN: - printf("return "); - print_ident(p, &(expr->dest)); - break; - - default: - if (expr->mode == MODE_VAR) - { - print_ident(p, &(expr->left.var)); - } - else if (expr->mode == MODE_UNOP) - { - print_opcode(expr); - print_ident(p, &(expr->left.var)); - } - else if (expr->mode == MODE_BINOP) - { - print_ident(p, &(expr->left.var)); - print_opcode(expr); - print_ident(p, &(expr->right.var)); - } - else - { - printf("??? M:%d C:%d\n", expr->mode, expr->code); - } - break; - } -} - -static void topsort(Bitset* set, SsaBlock** sorted, SsaBlock* block) -{ - if (block && !bitset_has(set, block->id)) - { - /* mark it visited and visit children */ - bitset_add(set, block->id); - topsort(set, sorted, block->links[1]); - topsort(set, sorted, block->links[0]); - - /* push block to the sorted list */ - block->next = *sorted; - *sorted = block; - } -} - -void ssa_print_asm(Parser* p, SsaBlock* block) -{ - /* perform a topological sort of the nodes */ - SsaBlock* sorted = NULL; - Bitset* set = bitset_new(p->blockid); - topsort(set, &sorted, block); - - /* now let's print the plantuml representation */ - printf("@startasm\n"); - for (SsaBlock* curr = sorted; curr; curr = curr->next) - { - printf("block%lu:\n", curr->id); - - /* print the phis */ - for (SsaPhi* phi = curr->phis; phi; phi = phi->next) - { - Symbol* s = symbol_getbyid(p, phi->symid); - printf(" %s.%lu = phi(", s->name, phi->latest_ver); - for (SsaPhiVar* var = phi->vars; var; var = var->next) - { - printf("%s.%lu", s->name, var->version); - if (var->next) - { - printf(", "); - } - } - puts(")"); - } - - /* print the instructions */ - for (SsaNode* node = curr->head; node; node = node->next) - { - printf(" "); - print_dest(p, node); - ssa_print(p, node); - puts(""); - } - } - printf("@endasm\n\n"); -} -- 2.49.0