diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | main.c | 3 | ||||
| -rw-r--r-- | semantics.c | 67 | ||||
| -rw-r--r-- | semantics.h | 25 | ||||
| -rw-r--r-- | ssa.c | 101 | ||||
| -rw-r--r-- | ssa.h | 14 |
6 files changed, 155 insertions, 61 deletions
@@ -6,9 +6,9 @@ run: db: gdb cibic -cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o +cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o mips.o mkdir -p bin - gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o + gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o mips.o cp bin/cibic cibic lex.yy.o: lex.yy.c cibic.tab.c gcc -c lex.yy.c @@ -22,6 +22,8 @@ semantics.o: semantics.c semantics.h gcc -c semantics.c -g -Wall -Wextra -DCIBIC_DEBUG ssa.o: ssa.c ssa.h gcc -c ssa.c -g -Wall -Wextra -DCIBIC_DEBUG +mips.o: mips.c mips.h + gcc -c mips.c -g -Wall -Wextra -DCIBIC_DEBUG lex.yy.c: cibic.l flex cibic.l cibic.tab.c: cibic.y @@ -55,7 +55,8 @@ void print_sem() { void print_ssa() { cibic_init(); yyparse(); - ssa_generate(semantics_check(ast_root)); + semantics_check(ast_root); + ssa_generate(); } void print_help() { diff --git a/semantics.c b/semantics.c index 5af8761..9ef5f7f 100644 --- a/semantics.c +++ b/semantics.c @@ -273,8 +273,8 @@ CType_t ctype_create(char *name, int type, CNode *ast) { return ct; } -static int align_shift(int x) { - return x + ((4 - (x & 3)) & 3); +int align_shift(int x) { + return ((4 - (x & 3)) & 3); } int calc_size(CType_t type) { @@ -296,8 +296,11 @@ int calc_size(CType_t type) { if (!p) return -1; for (; p; p = p->next) { + /* add padding to align to word boundary */ + if (p->type->type != CCHAR) + size += align_shift(size); p->start = size; - size += align_shift(calc_size(p->type)); + size += calc_size(p->type); } } break; @@ -308,7 +311,7 @@ int calc_size(CType_t type) { if (!p) return -1; for (; p; p = p->next) { - int t = align_shift(calc_size(p->type)); + int t = calc_size(p->type); if (t > size) size = t; p->start = 0; } @@ -1809,7 +1812,10 @@ void ctype_print(CType_t ct) { ctype_print_(ct, 0); } void cvar_print(CVar_t cv) { cvar_print_(cv, 0); } void cdef_print(CDef_t cd) { cdef_print_(cd, 0); } -CScope_t semantics_check(CNode *p) { +CTList_t funcs; +CVList_t gvars; + +void semantics_check(CNode *p) { CScope_t scope = cscope_create(); basic_type_int = ctype_create("int", CINT, NULL); basic_type_char = ctype_create("char", CCHAR, NULL); @@ -1840,7 +1846,55 @@ CScope_t semantics_check(CNode *p) { default: assert(0); } } -/* cscope_debug_print(scope); + { + int i; + CTNode *p; + funcs = NULL; + gvars = NULL; + for (i = 0; i < MAX_TABLE_SIZE; i++) + for (p = scope->ids->head[i]; p; p = p->next) + { + CSymbol_t tp = (CSymbol_t)(p->val); + CType_t func = tp->rec.type; + if (tp->kind == CTYPE && + func->type == CFUNC && + func->rec.func.body) + { + CTList_t nf = NEW(CTList); + CVar_t p; + int size; + nf->type = func; + nf->next = funcs; + funcs = nf; + size = 0; + for (p = func->rec.func.params; p; p = p->next) + { + /* force to a word alignment */ + size += align_shift(size); + p->start = size; + size += calc_size(p->type); + } + func->rec.func.params_size = size; + size = 0; + for (p = func->rec.func.local; p; p = p->next) + { + /* force to a word alignment */ + size += align_shift(size); + p->start = size; + size += calc_size(p->type); + } + func->rec.func.local_size = size; + } + else if (tp->kind == CVAR) + { + CVList_t nv = NEW(CVList); + nv->var = tp->rec.var; + nv->next = gvars; + gvars = nv; + } + } + } + /* cscope_debug_print(scope); { CTNode *p; int i; @@ -1862,5 +1916,4 @@ CScope_t semantics_check(CNode *p) { } } cnode_debug_print(ast_root, 1); */ - return scope; } diff --git a/semantics.h b/semantics.h index 65d1b7e..4db33b6 100644 --- a/semantics.h +++ b/semantics.h @@ -13,8 +13,25 @@ typedef CSymbol *CSymbol_t; typedef struct CDef CDef; typedef CDef *CDef_t; +typedef struct CTList CTList; +typedef CTList *CTList_t; +struct CTList { + CType_t type; + CTList_t next; +}; + +typedef struct CVList CVList; +typedef CVList *CVList_t; +struct CVList { + CVar_t var; + CVList_t next; +}; + + typedef struct CBList *CBList_t; typedef struct COList *COList_t; +typedef struct CVList *CVList_t; + struct CVar { char *name; CVar_t next; /* next in the linked list */ @@ -57,6 +74,8 @@ struct CType { CVar_t local; CType_t ret; CNode *body; + int params_size; + int local_size; } func; /* for a function */ } rec; int size; /* memory footprint */ @@ -154,7 +173,7 @@ void cscope_debug_print(CScope_t cs); unsigned int bkdr_hash(const char *str); const char *ctable_cvar_print(void *var); -CScope_t semantics_check(CNode *ast); +void semantics_check(CNode *ast); enum DefState{ FORCE_ID, @@ -170,4 +189,8 @@ void block_exit(void); void def_enter(enum DefState kind); void def_exit(void); int calc_size(CType_t type); +int align_shift(int x); + +extern CTList_t funcs; +extern CVList_t gvars; #endif @@ -4,6 +4,7 @@ #include <assert.h> #include "ast.h" #include "ssa.h" +#include "mips.h" #define NEW(type) ((type *)malloc(sizeof(type))) #define DBLINK(from, to) ((from)->next = (to))->prev = (from) @@ -11,7 +12,12 @@ static CGraph cfg, dtree; static CBlock_t blks[MAX_BLOCK]; static int bcnt; /* block counter */ static int tcnt; /* temporary counter */ -static int gbbase; + +/* for code generation */ +int gbbase; +CBlock_t entry; +COList_t defs; +CType_t func; CBlock_t cblock_create(int inc) { CBlock_t cblk = NEW(CBlock); @@ -218,6 +224,11 @@ void cinst_print(CInst_t inst) { } else fprintf(stderr, "return"); break; + case ADDR: + copr_print(inst->dest); + fprintf(stderr, " = addr "); + copr_print(inst->src1); + break; default: { const char *op; @@ -289,23 +300,19 @@ void ssa_func_print(CBlock_t p) { for (; p; p = p->next) cblock_print(p); } -CBlock_t ssa_func(CType_t); -void ssa_generate(CScope_t scope) { - CTNode *p; - int i; - for (i = 0; i < MAX_TABLE_SIZE; i++) - for (p = scope->ids->head[i]; p; p = p->next) - { - CSymbol_t tp = (CSymbol_t)(p->val); - CType_t func = tp->rec.type; - if (tp->kind != CTYPE || - func->type != CFUNC || - !func->rec.func.body) continue; - fprintf(stderr, "%s:\n", tp->rec.type->name); - ssa_func_print(ssa_func(func)); - gbbase += bcnt; - bcnt = 0; - } +void ssa_func(CType_t); +void ssa_generate() { + CTList_t f; + for (f = funcs; f; f = f->next) + { + func = f->type; + fprintf(stderr, "%s:\n", func->name); + ssa_func(func); + ssa_func_print(entry); + mips_generate(); + gbbase += bcnt; + bcnt = 0; + } } COpr_t ssa_exp_(CNode *p, CBlock_t, CInst_t, CBlock_t); @@ -556,6 +563,26 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) { } } } + else if (op == '&' && !p->chd->next) + { + ssa_exp_(p->chd, cur, inst, succ); + if (inst->op == MOVE) + { + inst->op = ADDR; + inst->src1 = inst->dest; + inst->src2 = NULL; + } + else + { + inst->op = ADD; + inst->src1 = inst->dest; + } + inst->dest = NEW(COpr); + inst->dest->kind = TMP; + inst->dest->info.var = ctmp_create(p->ext.type); + cblock_append(cur, inst); + return inst->dest; + } else { int unary = 0; @@ -649,21 +676,12 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) { case OPT_GE: inst->op = GE; break; case '/': inst->op = DIV; break; case '%': inst->op = MOD; break; - case '&': - if (p->chd->next) - inst->op = AND; - else - { - rec = 0; - res = NEW(COpr); - res->kind = IMM; - res->info.imm = 0; - /* TODO: be filled in with correct address */ - } - break; case '*': inst->op = MUL; break; + case '&': + inst->op = AND; + break; case '+': if (p->chd->next) inst->op = ADD; @@ -1062,7 +1080,7 @@ int intersect(int b1, int b2) { return b1; } -void calc_dominant_frontier(CBlock_t entry) { +void calc_dominant_frontier() { int i; int ch = 1; ocnt = 0; @@ -1282,7 +1300,7 @@ void renaming_dfs(CBlock_t blk) { } } -void renaming_vars(CVList_t vars, CBlock_t entry) { +void renaming_vars(CVList_t vars) { CVList_t vp; for (vp = vars; vp; vp = vp->next) { @@ -1498,7 +1516,7 @@ void cinterv_union(COpr_t a, COpr_t b) { a->par = b; } -COList_t init_def(CBlock_t entry) { +COList_t init_def() { CBlock_t p; COList_t defs = NULL, def; for (p = entry; p; p = p->next) @@ -1554,16 +1572,16 @@ void print_intervals(COList_t defs) { } } -void register_alloc(CBlock_t entry) { - COList_t defs; +void register_alloc() { mark_insts(); build_intervals(); - defs = init_def(entry); + defs = init_def(); print_intervals(defs); } -CBlock_t ssa_func(CType_t func) { - CBlock_t entry = cblock_create(1), p; +void ssa_func(CType_t func) { + CBlock_t p; + entry = cblock_create(1); CPSet_t vs = cpset_create(), avs = cpset_create(); CVList_t vars = NULL, all_vars = NULL; int i; @@ -1601,7 +1619,7 @@ CBlock_t ssa_func(CType_t func) { } blks[p->id] = p; } - calc_dominant_frontier(entry); + calc_dominant_frontier(); { CPNode *p; for (i = 0; i < MAX_TABLE_SIZE; i++) @@ -1623,9 +1641,8 @@ CBlock_t ssa_func(CType_t func) { } } insert_phi(vars); - renaming_vars(all_vars, entry); - register_alloc(entry); + renaming_vars(all_vars); + register_alloc(); cpset_destroy(vs); cpset_destroy(avs); - return entry; } @@ -55,6 +55,7 @@ struct CInst { RET, /* return */ MOVE, LOAD, /* load from memory */ + ADDR, /* get address */ MUL, DIV, MOD, ADD, SUB, SHL, SHR, AND, XOR, OR, LOR, LAND, NEG, NOR, SEQ, @@ -93,13 +94,6 @@ struct CBList { CBList_t next; }; -typedef struct CVList CVList; -typedef CVList *CVList_t; -struct CVList { - CVar_t var; - CVList_t next; -}; - CBlock_t cblock_create(int inc); void cblock_append(CBlock_t cblk, CInst_t inst); void cblock_pappend(CBlock_t cblk, CPhi_t phi); @@ -134,5 +128,9 @@ typedef struct CInterv { CRange_t range; } CInterv; -void ssa_generate(CScope_t scope); +void ssa_generate(); +extern int gbbase; +extern CBlock_t entry; +extern COList_t defs; +extern CType_t func; #endif |