diff options
| -rw-r--r-- | main.c | 36 | ||||
| -rw-r--r-- | mips.c | 8 | ||||
| -rw-r--r-- | mips.h | 2 | ||||
| -rw-r--r-- | semantics.c | 144 | ||||
| -rw-r--r-- | semantics.h | 17 | ||||
| -rw-r--r-- | ssa.c | 178 | ||||
| -rw-r--r-- | ssa.h | 17 |
7 files changed, 191 insertions, 211 deletions
@@ -3,8 +3,9 @@ #include <stdlib.h> #include "cibic.tab.h" #include "ast.h" -#include "ssa.h" #include "semantics.h" +#include "ssa.h" +#include "mips.h" extern char linebuff[]; extern char *lptr; @@ -48,8 +49,7 @@ void print_ast() { void print_sem() { cibic_init(); yyparse(); - semantics_check(ast_root); -/* cnode_debug_print(ast_root, 1); */ + semantics_check(ast_root, 0); } void lib_generate() { @@ -66,8 +66,16 @@ void lib_generate() { void print_ssa() { cibic_init(); yyparse(); - semantics_check(ast_root); - ssa_generate(); + semantics_check(ast_root, 1); + ssa_generate(0); +} + +void compile() { + cibic_init(); + yyparse(); + semantics_check(ast_root, 1); + ssa_generate(1); + mips_generate(); lib_generate(); } @@ -80,14 +88,17 @@ void print_help() { "Usage: [options] filename\n" "Options:\n" "\t --ast \t\t Print AST Construction\n" + "\t --sem \t\t Print Semantic Information\n" + "\t --ssa \t\t Print Single Static Assignment\n" "\t --help \t Show this info\n" ); } static struct option lopts[] = { { "ast", no_argument, 0, 'a'}, - { "help", no_argument, 0, 'h'}, { "sem", no_argument, 0, 'm'}, + { "ssa", no_argument, 0, 's'}, + { "help", no_argument, 0, 'h'}, {0, 0, 0, 0} }; @@ -95,8 +106,9 @@ enum { PRINT_AST, PRINT_HELP, PRINT_SEM, - PRINT_SSA -} mode = PRINT_SSA; + PRINT_SSA, + COMPILE +} mode = COMPILE; int main(int argc, char **argv) { int option_index = 0; @@ -109,8 +121,9 @@ int main(int argc, char **argv) { { case 0: break; case 'a': mode = PRINT_AST; break; - case 'h': print_help(); return 0; + case 's': mode = PRINT_SSA; break; case 'm': mode = PRINT_SEM; break; + case 'h': print_help(); return 0; } } if (optind == argc - 1) @@ -136,9 +149,10 @@ int main(int argc, char **argv) { switch (mode) { case PRINT_AST: print_ast(); break; - case PRINT_HELP: print_help(); break; case PRINT_SEM: print_sem(); break; - default: print_ssa(); + case PRINT_SSA: print_ssa(); break; + case PRINT_HELP: print_help(); break; + case COMPILE: compile(); break; } return 0; } @@ -315,7 +315,7 @@ void mips_func_end(void) { printf("\tjr $31\n"); } -void mips_generate(void) { +void mips_func(void) { CBlock_t p; CType_t rt; func = func_ir->func; @@ -731,3 +731,9 @@ void mips_generate(void) { } mips_func_end(); } + +void mips_generate(void) { + mips_prologue(); + for (; func_ir; func_ir = func_ir->next) + mips_func(); +} @@ -1,5 +1,7 @@ #ifndef MIPS_C #define MIPS_C + void mips_prologue(void); void mips_generate(void); + #endif diff --git a/semantics.c b/semantics.c index d8fe289..f8fffcc 100644 --- a/semantics.c +++ b/semantics.c @@ -4,6 +4,7 @@ #include <stdio.h> #include "semantics.h" #include "ast.h" + #define NEW(type) ((type *)malloc(sizeof(type))) #define CHECK_TYPE(p, _type) assert(p->type == _type) #define ERROR(x) do { error_print x; } while (0) @@ -94,7 +95,6 @@ const char *csymbol_getname(CSymbol_t sym) { return NULL; } -#ifdef CIBIC_DEBUG CTable_t ctable_create(Hashfunc_t hfunc, Printfunc_t pfunc) { CTable_t ct = NEW(CTable); memset(ct->head, 0, sizeof(CTNode*) * MAX_TABLE_SIZE); @@ -102,14 +102,7 @@ CTable_t ctable_create(Hashfunc_t hfunc, Printfunc_t pfunc) { ct->pfunc = pfunc; return ct; } -#else -CTable_t ctable_create(Hashfunc_t hfunc) { - CTable_t ct = NEW(CTable); - memset(ct->head, 0, sizeof(CTNode*) * MAX_TABLE_SIZE); - ct->hfunc = hfunc; - return ct; -} -#endif + void ctable_destory(CTable_t ct) { int i; for (i = 0; i < MAX_TABLE_SIZE; i++) @@ -1129,7 +1122,8 @@ ExpType exp_check_postfix(CNode *p, CScope_t scope) { if (!(t1 == CSTRUCT || t1 == CUNION)) ERROR((p, "request for the member in something not a structure or union")); { - calc_size(op1.type); + if (calc_size(op1.type) == -1) + ERROR((op1.type->ast, "invalid use of undefined type '%s'", op1.type->name)); CVar_t fv = ctable_lookup(op1.type->rec.st.fields, post->chd->rec.strval); if (!fv) @@ -1735,7 +1729,7 @@ const char *csymbol_print(void *csym) { return buff; } -void ctype_print_(CType_t, int lvl); +void ctype_print_(CType_t, int, CPSet_t); void print_tabs(int tnum) { while (tnum--) fprintf(stderr, " "); } void ctype_pre_(CType_t type, int lvl) { int t= type->type; @@ -1746,21 +1740,21 @@ void ctype_pre_(CType_t type, int lvl) { } } -void cvar_print_(CVar_t cv, int lvl) { +void cvar_print_(CVar_t cv, int lvl, CPSet_t visited) { fprintf(stderr, "[var@%lx:%s :: ", (size_t)cv, cv->name); ctype_pre_(cv->type, ++lvl); - ctype_print_(cv->type, lvl); + ctype_print_(cv->type, lvl, visited); fprintf(stderr, "]"); } -void cdef_print_(CDef_t cd, int lvl) { +void cdef_print_(CDef_t cd, int lvl, CPSet_t visited) { fprintf(stderr, "[def@%lx:%s :: ", (size_t)cd, cd->name); ctype_pre_(cd->type, ++lvl); - ctype_print_(cd->type, lvl); + ctype_print_(cd->type, lvl, visited); fprintf(stderr, "]"); } -void ctype_print_(CType_t ct, int lvl) { +void ctype_print_(CType_t ct, int lvl, CPSet_t visited) { switch (ct->type) { case CINT: @@ -1776,10 +1770,16 @@ void ctype_print_(CType_t ct, int lvl) { int i; CTNode *fn; lvl++; - fprintf(stderr, "[%s@%lx:{name:%s}{size:%d}", + fprintf(stderr, "[%s@%lx:{name:%s}", ct->type == CSTRUCT ? "struct" : "union", - (size_t)ct, ct->name, ct->size); - + (size_t)ct, ct->name); + if (cpset_belongs(visited, (long)ct)) + { + fprintf(stderr, "]\n"); + return; + } + cpset_insert(visited, (long)ct); + fprintf(stderr, "{size:%d}", ct->size); fprintf(stderr, "{fields:"); if (f) { @@ -1790,7 +1790,7 @@ void ctype_print_(CType_t ct, int lvl) { { fprintf(stderr, "%s", first ? (first = 0, "") : ",\n"); print_tabs(lvl); - cvar_print_((CVar_t)fn->val, lvl); + cvar_print_((CVar_t)fn->val, lvl, visited); } } fprintf(stderr, "}]"); @@ -1802,7 +1802,7 @@ void ctype_print_(CType_t ct, int lvl) { fprintf(stderr, "[arr:{len:%d}{size:%d}]->", ct->rec.arr.len, ct->size); ctype_pre_(type, ++lvl); - ctype_print_(type, lvl); + ctype_print_(type, lvl, visited); } break; case CPTR: @@ -1810,7 +1810,7 @@ void ctype_print_(CType_t ct, int lvl) { CType_t type = ct->rec.ref; fprintf(stderr, "[ptr]->"); ctype_pre_(type, ++lvl); - ctype_print_(type, lvl); + ctype_print_(type, lvl, visited); } break; case CFUNC: @@ -1828,7 +1828,7 @@ void ctype_print_(CType_t ct, int lvl) { for (p = ct->rec.func.params; p; p = p->next) { print_tabs(lvl + 1); - cvar_print_(p, lvl + 1); + cvar_print_(p, lvl + 1, visited); if (p->next) fprintf(stderr, ",\n"); } } @@ -1842,23 +1842,37 @@ void ctype_print_(CType_t ct, int lvl) { for (p = ct->rec.func.local; p; p = p->next) { print_tabs(lvl + 1); - cvar_print_(p, lvl + 1); + cvar_print_(p, lvl + 1, visited); if (p->next) fprintf(stderr, ",\n"); } } fprintf(stderr, "}]->"); ctype_pre_(type, lvl); - ctype_print_(type, lvl); + ctype_print_(type, lvl, visited); } break; } } -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); } +void ctype_print(CType_t ct) { + CPSet_t visited = cpset_create(); + ctype_print_(ct, 0, visited); + cpset_destroy(visited); +} + +void cvar_print(CVar_t cv) { + CPSet_t visited = cpset_create(); + cvar_print_(cv, 0, visited); + cpset_destroy(visited); +} -void semantics_check(CNode *p) { +void cdef_print(CDef_t cd) { + CPSet_t visited = cpset_create(); + cdef_print_(cd, 0, visited); + cpset_destroy(visited); +} + +void semantics_check(CNode *p, int quiet) { CScope_t scope = cscope_create(); basic_type_int = ctype_create("int", CINT, NULL); basic_type_char = ctype_create("char", CCHAR, NULL); @@ -1953,26 +1967,84 @@ void semantics_check(CNode *p) { } } } - /* cscope_debug_print(scope); + if (!quiet) { CTNode *p; int i; + cscope_debug_print(scope); 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); switch (tp->kind) { - case CVAR: - if (calc_size(tp->rec.var->type) == -1) - ERROR((tp->rec.var->ast, "storage size of ‘a’ isn’t known")); - cvar_print(tp->rec.var); - break; + case CVAR: cvar_print(tp->rec.var); break; case CTYPE: ctype_print(tp->rec.type); break; case CDEF: cdef_print(tp->rec.def); break; } fprintf(stderr, "\n\n"); } + cnode_debug_print(ast_root, 1); + } +} + + +CPSet_t cpset_create(void) { + CPSet_t res = NEW(CPSet); + memset(res->head, 0, sizeof res->head); + return res; +} + +void cpset_destroy(CPSet_t cps) { + int i; + for (i = 0; i < MAX_TABLE_SIZE; i++) + { + CPNode *p, *np; + for (p = cps->head[i]; p; p = np) + { + np = p->next; + free(p); + } } - cnode_debug_print(ast_root, 1); */ + free(cps); +} + +int cpset_insert(CPSet_t cps, long key) { + unsigned int hv = key % MAX_TABLE_SIZE; + CPNode *p = cps->head[hv], *np; + for (; p; p = p->next) + if (p->key == key) + return 0; + np = NEW(CPNode); + np->key = key; + np->next = cps->head[hv]; + cps->head[hv] = np; + return 1; +} + +void cpset_erase(CPSet_t cps, long key) { + unsigned int hv = key % MAX_TABLE_SIZE; + int flag = 0; + CPNode *p = cps->head[hv], *pp = NULL; + for (; p; pp = p, p = p->next) + if (p->key == key) + { + flag = 1; + break; + } + if (!flag) return; + if (pp) + pp->next = p->next; + else + cps->head[hv] = p->next; + free(p); +} + +int cpset_belongs(CPSet_t cps, long key) { + unsigned int hv = key % MAX_TABLE_SIZE; + CPNode *p = cps->head[hv]; + for (; p; p = p->next) + if (p->key == key) + return 1; + return 0; } diff --git a/semantics.h b/semantics.h index a7712b6..c710304 100644 --- a/semantics.h +++ b/semantics.h @@ -185,7 +185,7 @@ void cscope_debug_print(CScope_t cs); unsigned int bkdr_hash(const char *str); const char *ctable_cvar_print(void *var); -void semantics_check(CNode *ast); +void semantics_check(CNode *ast, int quiet); enum DefState{ FORCE_ID, @@ -193,6 +193,21 @@ enum DefState{ NONE }; +typedef struct CPNode CPNode; +typedef struct CPSet { + struct CPNode { + long key; + CPNode *next; + } *head[MAX_TABLE_SIZE]; +} CPSet; +typedef CPSet *CPSet_t; + +CPSet_t cpset_create(void); +int cpset_insert(CPSet_t cps, long key); +int cpset_belongs(CPSet_t cps, long key); +void cpset_erase(CPSet_t cps, long key); +void cpset_destroy(CPSet_t cps); + int is_identifier(const char *name); void push(char *name); void cibic_init(void); @@ -14,6 +14,7 @@ static COList_t raw_defs; /* defintion of all vars and tmps */ static int bcnt; /* block counter */ static int tcnt; /* temporary counter */ +static int quiet; static int gbbase; static CBlock_t entry; static COList_t defs; /* all defintions that have actual effects */ @@ -143,7 +144,9 @@ void dtree_clear(void) { void cfg_add_edge(CBlock_t from, CBlock_t to) { int fid = from->id, tid = to->id; +#ifdef CIBIC_DEBUG fprintf(stderr, "%d -> %d\n", from->id, to->id); +#endif CEdge *e = NEW(CEdge), *re = NEW(CEdge); e->to = to; e->next = cfg.head[fid]; @@ -155,7 +158,9 @@ void cfg_add_edge(CBlock_t from, CBlock_t to) { } void dtree_add_edge(CBlock_t from, CBlock_t to) { +#ifdef CIBIC_DEBUG fprintf(stderr, "%d d-> %d\n", from->id, to->id); +#endif int id = from->id; CEdge *e = NEW(CEdge); e->to = to; @@ -299,7 +304,6 @@ void cphi_print(CPhi_t phi, CBlock_t blk) { } void cblock_print(CBlock_t blk) { - /*if (blk->ref)*/ fprintf(stderr, "_L%d:\n", blk->id + gbbase); { CPhi_t p, sp = blk->phis; @@ -323,9 +327,10 @@ void ssa_func_print(CBlock_t p) { cblock_print(p); } void ssa_func(CType_t); -void ssa_generate(void) { +void ssa_generate(int quiet) { CTList_t f; - CFuncIR_t cf, cf_list = NULL; + CFuncIR_t cf; + func_ir = NULL; for (f = funcs; f; f = f->next) { cf = NEW(CFuncIR); @@ -333,18 +338,18 @@ void ssa_generate(void) { cf->gbbase = gbbase; cf->defs = defs; cf->entry = entry; - cf->next = cf_list; - cf_list = cf; - fprintf(stderr, "%s:\n", cf->func->name); - ssa_func_print(entry); + cf->next = func_ir; + func_ir = cf; gbbase += bcnt; bcnt = 0; } - mips_prologue(); - for (cf = cf_list; cf; cf = cf->next) + if (!quiet) { - func_ir = cf; - mips_generate(); + for (cf = func_ir; cf; cf = cf->next) + { + fprintf(stderr, "%s:\n", cf->func->name); + ssa_func_print(cf->entry); + } } } @@ -1381,66 +1386,6 @@ CBlock_t ssa_comp(CNode *p, CBlock_t cur, CBlock_t loop_exit) { return cur; } -CPSet_t cpset_create(void) { - CPSet_t res = NEW(CPSet); - memset(res->head, 0, sizeof res->head); - return res; -} - -void cpset_destroy(CPSet_t cps) { - int i; - for (i = 0; i < MAX_TABLE_SIZE; i++) - { - CPNode *p, *np; - for (p = cps->head[i]; p; p = np) - { - np = p->next; - free(p); - } - } - free(cps); -} - -int cpset_insert(CPSet_t cps, long key) { - unsigned int hv = key % MAX_TABLE_SIZE; - CPNode *p = cps->head[hv], *np; - for (; p; p = p->next) - if (p->key == key) - return 0; - np = NEW(CPNode); - np->key = key; - np->next = cps->head[hv]; - cps->head[hv] = np; - return 1; -} - -void cpset_erase(CPSet_t cps, long key) { - unsigned int hv = key % MAX_TABLE_SIZE; - int flag = 0; - CPNode *p = cps->head[hv], *pp = NULL; - for (; p; pp = p, p = p->next) - if (p->key == key) - { - flag = 1; - break; - } - if (!flag) return; - if (pp) - pp->next = p->next; - else - cps->head[hv] = p->next; - free(p); -} - -int cpset_belongs(CPSet_t cps, long key) { - unsigned int hv = key % MAX_TABLE_SIZE; - CPNode *p = cps->head[hv]; - for (; p; p = p->next) - if (p->key == key) - return 1; - return 0; -} - int dom[MAX_BLOCK], ord[MAX_BLOCK], vis[MAX_BLOCK], par[MAX_BLOCK], ocnt; int loop_tail[MAX_BLOCK]; CPSet_t dfset[MAX_BLOCK], phi[MAX_BLOCK]; @@ -1539,9 +1484,6 @@ void insert_phi(CVList_t vars) { CBList_t t = var->defsite; CBList_t def = NULL; static int indef[MAX_BLOCK]; -#ifdef CIBIC_DEBUG - fprintf(stderr, "%s:", var->name); -#endif for (t = var->defsite; t; t = t->next) if (++indef[t->cblk->id] == 1) { @@ -1552,11 +1494,6 @@ void insert_phi(CVList_t vars) { } for (t = var->defsite; t; t = t->next) indef[t->cblk->id] = 0; /* clear */ -#ifdef CIBIC_DEBUG - for (t = def; t; t = t->next) - fprintf(stderr, " %d", t->cblk->id); - fprintf(stderr, "\n"); -#endif while (def) /* while def not empty */ { CBList_t n = def, i; /* remove some node n from def */ @@ -1913,11 +1850,13 @@ COpr_t cinterv_repr(COpr_t opr) { void cinterv_union(COpr_t a, COpr_t b) { a = cinterv_repr(a); b = cinterv_repr(b); +#ifdef CIBIC_DEBUG fprintf(stderr, "merging "); copr_print(stderr, a); fprintf(stderr, " "); copr_print(stderr, b); fprintf(stderr, "\n"); +#endif if (a == b) return; b->range = crange_merge(b->range, a->range); a->par = b; @@ -1974,25 +1913,6 @@ void init_def(void) { } } -void print_intervals(void) { - COList_t d; - for (d = raw_defs; d; d = d->next) - { - COpr_t opr = d->opr, - repr = cinterv_repr(opr); - CRange_t p; - copr_print(stderr, opr); - fprintf(stderr, ": "); - if (repr == opr) - { - for (p = opr->range; p; p = p->next) - fprintf(stderr, "[%d, %d)", p->l, p->r); - } - else copr_print(stderr, repr); - fprintf(stderr, "\n"); - } -} - void colist_remove(COList_t node) { node->prev->next = node->next; node->next->prev = node->prev; @@ -2073,21 +1993,11 @@ void register_alloc(void) { { COpr_t opr = unhandled[i]; CRange_t r; - /* - if (opr->kind == VAR && opr->range->next) - { - free(opr->range); - opr->range = opr->range->next; - }*/ /* discard uncessary load */ for (r = opr->range; r->next; r = r->next); opr->begin = opr->range->l; opr->end = r->r; - copr_print(stderr, opr); - fprintf(stderr, " (key: %d begin: %d, end: %d, weight: %d)\n", - opr->range->l, opr->begin, opr->end, opr->info.var->weight); } qsort(unhandled, dn, sizeof(COpr_t), copr_comp); - print_intervals(); /* preparation done */ for (i = 0; i < dn; i++) { @@ -2198,13 +2108,6 @@ void register_alloc(void) { colist_add(active, c); /* move cur to active */ } } - for (i = 0; i < dn; i++) - { - COpr_t opr = unhandled[i]; - copr_print(stderr, opr); - fprintf(stderr, " (begin: %d, end: %d, weight: %d, reg: %d)\n", - opr->begin, opr->end, opr->info.var->weight, opr->reg); - } for (p = raw_defs; p; p = p->next) { COpr_t opr = p->opr; @@ -2220,6 +2123,19 @@ void register_alloc(void) { p->next = defs; defs = p; } + if (!quiet) + { + for (i = 0; i < dn; i++) + { + COpr_t opr = unhandled[i]; + CRange_t p; + copr_print(stderr, opr); + for (p = opr->range; p; p = p->next) + fprintf(stderr, ": [%d, %d)", p->l, p->r); + fprintf(stderr, " (begin: %d, end: %d, weight: %d, reg: %d)\n", + opr->begin, opr->end, opr->info.var->weight, opr->reg); + } + } free(unhandled); } @@ -2295,10 +2211,8 @@ void const_propagation(void) { { c = copr_create(); c->kind = IMM; - /* free(i->src1); free(i->src2); - */ i->op = MOVE; i->src1 = c; c->info.imm = immd; @@ -2336,6 +2250,7 @@ void strength_reduction(void) { if (bp != buff) \ { \ CInst_t print = cinst_create(); \ + CSList_t cstr = NEW(CSList); \ print->op = CALL; \ print->dest = copr_create(); \ print->dest->kind = TMP; \ @@ -2343,7 +2258,6 @@ void strength_reduction(void) { print->dest->type = i->dest->type; \ print->src1 = copr_create(); \ print->src1->kind = IMMF; \ - CSList_t cstr = NEW(CSList); \ *bp = '\0'; \ print->src1->kind = IMMF; \ cstr->str = strdup(buff); \ @@ -2417,14 +2331,6 @@ void strength_reduction(void) { call_cnt++; break; case CALL: - /* - if (i->src1->kind == IMMF && - call_cnt == 1 && - !strcmp(i->src1->info.str, "printf")) - { - i->src1->info.str = "__print_string"; - } - */ if (i->src1->kind == IMMF && !strcmp(i->src1->info.str, "printf")) { @@ -2667,22 +2573,6 @@ void subexp_elimination_(CBlock_t b, CExpMap_t cem) { case SHL: case SHR: case AND: case XOR: case OR: case NOR: case EQ: case NE: case LT: case GT: case LE: case GE: case NEG: - /* - if (i->dest->kind == VAR) - { - CInst_t t = cinst_create(); - *t = *i; - t->dest = copr_create(); - t->dest->kind = TMP; - t->dest->info.var = ctmp_create(); - (t->next = i->next)->prev = t; - (t->prev = i)->next = t; - t->dest->def = t; - t->dest->type = i->dest->type; - cexpmap_insert(cem, t); - } - else - */ if (i->dest->kind == TMP) cexpmap_insert(cem, i); break; default: ; @@ -2696,9 +2586,6 @@ void subexp_elimination_(CBlock_t b, CExpMap_t cem) { void subexp_elimination(void) { CExpMap_t cem = cexpmap_create(); -/* int i; - for (i = bcnt - 1; i >= 0; i--) - */ subexp_elimination_(entry, cem); cexpmap_destroy(cem); } @@ -2753,7 +2640,6 @@ void ssa_func(CType_t func) { } \ } while (0) - CBlock_t p; entry = cblock_create(1); CPSet_t vs = cpset_create(), avs = cpset_create(); @@ -122,21 +122,6 @@ typedef struct CGraph { } *head[MAX_BLOCK], *rhead[MAX_BLOCK]; } CGraph; -typedef struct CPNode CPNode; -typedef struct CPSet { - struct CPNode { - long key; - CPNode *next; - } *head[MAX_TABLE_SIZE]; -} CPSet; -typedef CPSet *CPSet_t; - -CPSet_t cpset_create(void); -int cpset_insert(CPSet_t cps, long key); -int cpset_belongs(CPSet_t cps, long key); -void cpset_destroy(CPSet_t cps); - - typedef struct CInterv { COpr_t opr; CRange_t range; @@ -169,7 +154,7 @@ struct CFuncIR { CFuncIR_t next; }; -void ssa_generate(void); +void ssa_generate(int quiet); COpr_t cinterv_repr(COpr_t opr); void cinst_print(FILE *stream, CInst_t inst); int overlap_with_beg(COpr_t i, int beg); |