From 7a0e78225a62ce613672b05c9ce1e42ac6419b2c Mon Sep 17 00:00:00 2001 From: Teddy Date: Sun, 27 Apr 2014 17:53:08 +0800 Subject: ... --- ast.c | 5 +- ast.h | 2 +- main.c | 8 +- semantics.c | 26 ++-- semantics.h | 11 +- ssa.c | 414 ++++++++++++++++++++++++++++++++++++++++++------------------ ssa.h | 1 + test_all.sh | 2 +- 8 files changed, 323 insertions(+), 146 deletions(-) diff --git a/ast.c b/ast.c index 866588f..b2c6676 100644 --- a/ast.c +++ b/ast.c @@ -33,7 +33,6 @@ CNode *cnode_create_nop() { CNode *nop = NEW_CNODE; nop->type = NOP; nop->next = nop->chd = NULL; - nop->ext.type = NULL; return nop; } @@ -44,6 +43,7 @@ CNode *cnode_create_general(int type, int subtype, int pnum, va_list ap) { exp->rec.subtype = subtype; exp->next = exp->chd = NULL; exp->ext.type = NULL; + exp->ext.offset = 0; for (i = 0; i < pnum; i++) { CNode *subexp = va_arg(ap, CNode*); @@ -72,6 +72,7 @@ CNode *cnode_create_identifier(char *val) { exp->chd = exp->next = NULL; exp->rec.strval = val; exp->ext.type = NULL; + exp->ext.offset = 0; return exp; } @@ -402,7 +403,7 @@ char *cnode_debug_type_repr(CNode *ast) { if (ast->ext.type) sprintf(head, "->(var:%lx type:%lx ic:%d cv:%d off:%d)", (size_t)ast->ext.var, (size_t)ast->ext.type, - ast->ext.is_const, ast->ext.const_val, ast->ext.offest); + ast->ext.is_const, ast->ext.const_val, ast->ext.offset); } return buffer; } diff --git a/ast.h b/ast.h index e63dd0a..81f6f7e 100644 --- a/ast.h +++ b/ast.h @@ -50,7 +50,7 @@ typedef struct CNode { CVar_t var; int const_val; int is_const; - int offest; /* offest from var */ + int offset; /* offset from var */ } ext; struct CNode *chd, *next; /* For error reporting */ diff --git a/main.c b/main.c index e0b06a7..08655f0 100644 --- a/main.c +++ b/main.c @@ -74,14 +74,16 @@ void print_help() { static struct option lopts[] = { { "ast", no_argument, 0, 'a'}, { "help", no_argument, 0, 'h'}, + { "sem", no_argument, 0, 'm'}, {0, 0, 0, 0} }; enum { PRINT_AST, PRINT_HELP, - PRINT_SEM -} mode = PRINT_SEM; + PRINT_SEM, + PRINT_SSA +} mode = PRINT_SSA; int main(int argc, char **argv) { int option_index = 0; @@ -95,6 +97,7 @@ int main(int argc, char **argv) { case 0: break; case 'a': mode = PRINT_AST; break; case 'h': print_help(); return 0; + case 'm': mode = PRINT_SEM; break; } } if (optind == argc - 1) @@ -121,6 +124,7 @@ int main(int argc, char **argv) { { case PRINT_AST: print_ast(); break; case PRINT_HELP: print_help(); break; + case PRINT_SEM: print_sem(); break; default: print_ssa(); } return 0; diff --git a/semantics.c b/semantics.c index c29ae04..065dfc2 100644 --- a/semantics.c +++ b/semantics.c @@ -256,7 +256,7 @@ unsigned int bkdr_hash(const char *str) { return hv; } -CVar_t cvar_create(const char *name, CType_t type, CNode *ast) { +CVar_t cvar_create(char *name, CType_t type, CNode *ast) { CVar_t cv = NEW(CVar); cv->name = name; cv->type = type; @@ -264,7 +264,7 @@ CVar_t cvar_create(const char *name, CType_t type, CNode *ast) { return cv; } -CType_t ctype_create(const char *name, int type, CNode *ast) { +CType_t ctype_create(char *name, int type, CNode *ast) { CType_t ct = NEW(CType); ct->name = name; ct->type = type; @@ -296,8 +296,8 @@ int calc_size(CType_t type) { if (!p) return -1; for (; p; p = p->next) { - size += align_shift(calc_size(p->type)); p->start = size; + size += align_shift(calc_size(p->type)); } } break; @@ -745,6 +745,7 @@ CVar_t semantics_decl(CNode *p, CScope_t scope) { ExpType exp_check_aseq(ExpType lhs, ExpType rhs, CNode *ast) { exp_check_aseq_(lhs.type, rhs.type, ast); + lhs.lval = 0; return lhs; } @@ -875,7 +876,7 @@ ExpType exp_check_add(ExpType op1, ExpType op2, CNode *p, char kind) { *a = &(p->ext.const_val); if (t1 == CARR) { - int l = p->chd->ext.offest; + int l = p->chd->ext.offset; CType_t type; p->ext.var = p->chd->ext.var; if (t1 == CPTR) type = op1.type->rec.ref; @@ -883,8 +884,8 @@ ExpType exp_check_add(ExpType op1, ExpType op2, CNode *p, char kind) { r *= calc_size(type); switch (kind) { - case '+': p->ext.offest = l + r; break; - case '-': p->ext.offest = l - r; break; + case '+': p->ext.offset = l + r; break; + case '-': p->ext.offset = l - r; break; } } else @@ -967,6 +968,7 @@ ExpType exp_check_inc(ExpType op1, CNode *p) { ERROR((p, "wrong type argument to increment/decrement")); if (!op1.lval) ERROR((p, "lvalue required as increment/decrement operand")); + op1.lval = 0; return op1; } @@ -1081,7 +1083,7 @@ ExpType exp_check_postfix(CNode *p, CScope_t scope) { if ((p->ext.is_const = p->chd->ext.is_const && \ post->chd->ext.is_const)) { - p->ext.offest = p->chd->ext.offest + \ + p->ext.offset = p->chd->ext.offset + \ calc_size(op1.type) * post->chd->ext.const_val; p->ext.var = p->chd->ext.var; } @@ -1122,7 +1124,7 @@ ExpType exp_check_postfix(CNode *p, CScope_t scope) { if (!fv) ERROR((p, "struct/union has no member named '%s'", post->chd->rec.strval)); p->ext.var = NULL; - p->ext.offest = fv->start; + p->ext.offset = fv->start; op1.type = fv->type; } break; @@ -1135,17 +1137,19 @@ ExpType exp_check_postfix(CNode *p, CScope_t scope) { ERROR((p, "request for the member in something not a structure or union")); if (!tref->rec.st.fields) ERROR((p, "dereferencing pointer to incomplete type")); + calc_size(tref); CVar_t fv = ctable_lookup(tref->rec.st.fields, post->chd->rec.strval); if (!fv) ERROR((p, "struct/union has no member named '%s'", post->chd->rec.strval)); p->ext.var = fv; + p->ext.offset = fv->start; op1.type = fv->type; op1.lval = 1; } break; case OPT_INC: case OPT_DEC: - exp_check_inc(op1, p); + op1 = exp_check_inc(op1, p); break; default: assert(0); } @@ -1515,7 +1519,7 @@ CType_t semantics_func(CNode *p, CScope_t scope) { return func; } -CType_t make_builtin_func(const char *name, CType_t rt) { +CType_t make_builtin_func(char *name, CType_t rt) { CType_t func = ctype_create(name, CFUNC, NULL); func->rec.func.params = NULL; func->rec.func.body = NULL; @@ -1552,7 +1556,7 @@ int is_identifier(const char *name) { return lu->kind == CVAR; } -void push(const char *name) { +void push(char *name) { if (typedef_stack && typedef_stack->kind == IN_TYPEDEF) cscope_push_type(typedef_scope, ctype_create(name, 0, NULL), NS_ID); else diff --git a/semantics.h b/semantics.h index d0b681a..0a555df 100644 --- a/semantics.h +++ b/semantics.h @@ -14,14 +14,14 @@ typedef struct CDef CDef; typedef CDef *CDef_t; struct CVar { - const char *name; + char *name; CVar_t next; /* next in the linked list */ CType_t type; int start; CNode *ast; }; -CVar_t cvar_create(const char *name, CType_t type, CNode *ast); +CVar_t cvar_create(char *name, CType_t type, CNode *ast); void cvar_print(CVar_t cv); struct CType { @@ -35,7 +35,7 @@ struct CType { CPTR, CFUNC } type; - const char *name; + char *name; union { struct { CTable_t fields; /* for a struct or union */ @@ -57,7 +57,7 @@ struct CType { CNode *ast; }; -CType_t ctype_create(const char *name, int type, CNode *ast); +CType_t ctype_create(char *name, int type, CNode *ast); void ctype_debug_print(CType_t ct); typedef unsigned int (*Hashfunc_t) (const char *); @@ -157,10 +157,11 @@ enum DefState{ }; int is_identifier(const char *name); -void push(const char *name); +void push(char *name); void cibic_init(void); void block_enter(void); void block_exit(void); void def_enter(enum DefState kind); void def_exit(void); +int calc_size(CType_t type); #endif diff --git a/ssa.c b/ssa.c index 39133f7..4ec90f6 100644 --- a/ssa.c +++ b/ssa.c @@ -30,6 +30,12 @@ void cblock_append(CBlock_t cblk, CInst_t inst) { (inst->next = head)->prev = inst; } +void cblock_popback(CBlock_t cblk) { + CInst_t last = cblk->insts->prev; + last->next->prev = last->prev; + last->prev->next = last->next; +} + CInst_t cblock_getback(CBlock_t cblk) { return cblk->insts->prev; } @@ -44,6 +50,11 @@ CVar_t ctmp_create(CType_t type) { return cvar_create(strdup(buff), type, NULL); } +void ctmp_destroy(CVar_t type) { + free(type->name); /* allocated dynamically */ + free(type); +} + void cfg_clear() { int i; for (i = 0; i < MAX_BLOCK; i++) @@ -110,6 +121,18 @@ void cinst_print(CInst_t inst) { copr_print(&inst->src2); fprintf(stderr, "]"); break; + case NEG: + copr_print(&inst->dest); + fprintf(stderr, " = -"); + copr_print(&inst->src1); + break; + case WARR: + copr_print(&inst->dest); + fprintf(stderr, "["); + copr_print(&inst->src2); + fprintf(stderr, "] = "); + copr_print(&inst->src1); + break; default: { const char *op; @@ -168,7 +191,66 @@ void ssa_generate(CScope_t scope) { } } -COpr ssa_exp(CNode *p, CBlock_t cur) { +COpr ssa_exp_(CNode *p, CBlock_t, CInst_t); +COpr ssa_postfix(CNode *p, CBlock_t cur, CInst_t lval) { + CNode *post = p->chd->next; + CType_t rt = p->ext.type; + CInst_t base = NEW(CInst); + switch (post->rec.subtype) + { + case POSTFIX_ARR: + { + CInst_t off = NEW(CInst); + off->dest.kind = TMP; + off->dest.info.var = ctmp_create(post->chd->ext.type); + off->op = MUL; + off->src1 = ssa_exp_(post->chd, cur, 0); + off->src2.kind = IMM; + off->src2.info.imm = calc_size(rt); + cblock_append(cur, off); + + base->dest.kind = TMP; + base->dest.info.var = ctmp_create(rt); + base->src1 = ssa_exp_(p->chd, cur, 0); + base->src2 = off->dest; + base->op = rt->type == CARR ? ADD : ARR; + } + break; + case POSTFIX_DOT: + { + base->dest.kind = TMP; + base->dest.info.var = ctmp_create(rt); + base->op = (rt->type == CSTRUCT || rt->type == CUNION) ? ADD : ARR; + base->src1 = ssa_exp_(p->chd, cur, 0); + base->src2.kind = IMM; + base->src2.info.imm = p->ext.offset; + } + break; + case POSTFIX_PTR: + { + base->dest.kind = TMP; + base->dest.info.var = ctmp_create(rt); + base->op = (rt->type == CSTRUCT || rt->type == CUNION) ? ADD : ARR; + base->src1 = ssa_exp_(p->chd, cur, 0); + base->src2.kind = IMM; + base->src2.info.imm = p->ext.offset; + } + break; + } + + if (lval) + { + lval->op = WARR; + lval->dest = base->src1; + lval->src2 = base->src2; + free(base); + return lval->dest; + } + cblock_append(cur, base); + return base->dest; +} + +COpr ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval) { COpr res; CInst_t inst = NEW(CInst); switch (p->type) @@ -177,6 +259,11 @@ COpr ssa_exp(CNode *p, CBlock_t cur) { case ID: res.kind = VAR; res.info.var = p->ext.var; + if (lval) + { + lval->op = MOVE; + lval->dest = res; + } break; default: @@ -189,141 +276,220 @@ COpr ssa_exp(CNode *p, CBlock_t cur) { { int op = p->rec.subtype; int rec = 1, auto_dest = 1; - COpr lhs = ssa_exp(p->chd, cur), rhs; - if (p->chd->next) - rhs = ssa_exp(p->chd->next, cur); - inst->src1 = lhs; - inst->src2 = rhs; - switch (op) + if (op == '=') { - case OPT_OR: inst->op = LOR; break; - case OPT_AND: inst->op = LAND; break; - case OPT_SHL: inst->op = SHL; break; - case OPT_SHR: inst->op = SHR; break; - case '|': inst->op = OR; break; - case '^': inst->op = XOR; break; - case OPT_EQ: inst->op = EQ; break; - case OPT_NE: inst->op = NE; break; - case '<': inst->op = LT; break; - case '>': inst->op = GT; break; - case OPT_LE: inst->op = LE; break; - 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.kind = IMM; - res.info.imm = 0; - /* TODO: be filled in with correct address */ - } - break; - case '*': - if (p->chd->next) - inst->op = MUL; - else - { - inst->op = ARR; - inst->src1 = lhs; - inst->src2.kind = IMM; - inst->src2.info.imm = 0; - } - break; - case '+': - if (p->chd->next) - inst->op = ADD; - else res = lhs; - break; - case '-': - if (p->chd->next) - inst->op = SUB; - else - { - inst->op = NEG; - inst->src1 = lhs; - } - break; - case '~': - inst->op = NOR; - inst->src1 = lhs; - inst->src2.kind = IMM; - inst->src2.info.imm = 0; - break; - case '!': - inst->op = SEQ; - inst->src1 = lhs; - inst->src2.kind = IMM; - inst->src2.info.imm = 0; - break; - case OPT_INC: - auto_dest = 0; - inst->op = ADD; - inst->dest = lhs; - inst->src1 = lhs; - inst->src2.kind = IMM; - inst->src2.info.imm = 1; - break; - case OPT_DEC: - auto_dest = 0; - inst->op = SUB; - inst->dest = lhs; - inst->src1 = lhs; - inst->src2.kind = IMM; - inst->src2.info.imm = 1; - break; - default: - auto_dest = 0; - if (op == '=') - { - if (rhs.kind == VAR) - { - inst->op = MOVE; - inst->dest = lhs; - inst->src1 = rhs; - cblock_append(cur, inst); - } - else - { - inst = cblock_getback(cur); - inst->dest = lhs; - } - res = inst->dest; - break; - } - inst->dest = lhs; - switch (op) - { - case ASS_MUL: inst->op = MUL; break; - case ASS_DIV: inst->op = DIV; break; - case ASS_MOD: inst->op = MOD; break; - case ASS_ADD: inst->op = ADD; break; - case ASS_SUB: inst->op = SUB; break; - case ASS_SHL: inst->op = SHL; break; - case ASS_SHR: inst->op = SHR; break; - case ASS_AND: inst->op = AND; break; - case ASS_XOR: inst->op = XOR; break; - case ASS_OR: inst->op = OR; break; - } + inst->src1 = ssa_exp_(p->chd->next, cur, NULL); + ssa_exp_(p->chd, cur, inst); + cblock_append(cur, inst); + if (inst->op == MOVE) + return inst->dest; + else + { + CInst_t tins = NEW(CInst); + tins->op = ARR; + tins->src1 = inst->dest; /* base */ + tins->src2 = inst->src2; /* displacement */ + tins->dest.kind = TMP; + tins->dest.info.var = ctmp_create(p->ext.type); + cblock_append(cur, tins); + return tins->dest; + } } - if (rec) + else if (op == '*' && !p->chd->next) { - if (auto_dest) { - inst->dest.kind = TMP; - inst->dest.info.var = ctmp_create(p->ext.type); + if (lval) + { + lval->op = WARR; + lval->dest = ssa_exp_(p->chd, cur, NULL); + lval->src2.kind = IMM; + lval->src2.info.imm = 0; + return lval->dest; + } + else + { + inst->op = ARR; + inst->src1 = ssa_exp_(p->chd, cur, NULL); + inst->src2.kind = IMM; + inst->src2.info.imm = 0; + inst->dest.kind = TMP; + inst->dest.info.var = ctmp_create(p->ext.type); + cblock_append(cur, inst); + return inst->dest; + } } - cblock_append(cur, inst); - res = inst->dest; + } + else + { + + inst->op = -1; + switch (op) + { + case ASS_MUL: inst->op = MUL; break; + case ASS_DIV: inst->op = DIV; break; + case ASS_MOD: inst->op = MOD; break; + case ASS_ADD: inst->op = ADD; break; + case ASS_SUB: inst->op = SUB; break; + case ASS_SHL: inst->op = SHL; break; + case ASS_SHR: inst->op = SHR; break; + case ASS_AND: inst->op = AND; break; + case ASS_XOR: inst->op = XOR; break; + case ASS_OR: inst->op = OR; break; + } + if (inst->op != -1) + { + CInst_t tins = NEW(CInst); + ssa_exp_(p->chd, cur, tins); /* as lval */ + inst->src1 = ssa_exp_(p->chd, cur, NULL); /* as rval */ + inst->src2 = ssa_exp_(p->chd->next, cur, NULL); + if (tins->op == MOVE) + { + inst->dest = tins->dest; + cblock_append(cur, inst); + free(tins); + return inst->dest; + } + else + { + CInst_t tins2 = NEW(CInst); + inst->dest.kind = TMP; + inst->dest.info.var = ctmp_create(p->ext.type); + tins->src1 = inst->dest; + tins2->op = ARR; + tins2->src1 = tins->dest; /* base */ + tins2->src2 = tins->src2; /* displacement */ + tins2->dest.kind = TMP; + tins2->dest.info.var = ctmp_create(p->ext.type); + cblock_append(cur, inst); + cblock_append(cur, tins); + cblock_append(cur, tins2); + return tins2->dest; + } + } + } + + switch (op) + { + case EXP_CAST: + free(inst); + return ssa_exp_(p->chd->next, cur, lval); + case EXP_POSTFIX: + free(inst); + return ssa_postfix(p, cur, lval); + /* KW_SIZEOF is eliminated during semantic checking */ + default: + { + COpr lhs = ssa_exp_(p->chd, cur, lval), rhs; + if (p->chd->next) + rhs = ssa_exp_(p->chd->next, cur, lval); + + inst->src1 = lhs; + inst->src2 = rhs; + switch (op) + { + case OPT_OR: inst->op = LOR; break; + case OPT_AND: inst->op = LAND; break; + case OPT_SHL: inst->op = SHL; break; + case OPT_SHR: inst->op = SHR; break; + case '|': inst->op = OR; break; + case '^': inst->op = XOR; break; + case OPT_EQ: inst->op = EQ; break; + case OPT_NE: inst->op = NE; break; + case '<': inst->op = LT; break; + case '>': inst->op = GT; break; + case OPT_LE: inst->op = LE; break; + 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.kind = IMM; + res.info.imm = 0; + /* TODO: be filled in with correct address */ + } + break; + case '*': + inst->op = MUL; + break; + case '+': + if (p->chd->next) + inst->op = ADD; + else res = lhs; + break; + case '-': + if (p->chd->next) + inst->op = SUB; + else + { + inst->op = NEG; + inst->src1 = lhs; + } + break; + case '~': + inst->op = NOR; + inst->src1 = lhs; + inst->src2.kind = IMM; + inst->src2.info.imm = 0; + break; + case '!': + inst->op = SEQ; + inst->src1 = lhs; + inst->src2.kind = IMM; + inst->src2.info.imm = 0; + break; + case OPT_INC: + auto_dest = 0; + inst->op = ADD; + inst->dest = lhs; + inst->src1 = lhs; + inst->src2.kind = IMM; + inst->src2.info.imm = 1; + break; + case OPT_DEC: + auto_dest = 0; + inst->op = SUB; + inst->dest = lhs; + inst->src1 = lhs; + inst->src2.kind = IMM; + inst->src2.info.imm = 1; + break; + default: + auto_dest = 0; + } + if (rec) + { + if (auto_dest) + { + inst->dest.kind = TMP; + inst->dest.info.var = ctmp_create(p->ext.type); + } + cblock_append(cur, inst); + res = inst->dest; + } + } } } } return res; } +COpr ssa_exp(CNode *p, CBlock_t cur) { + COpr res = ssa_exp_(p, cur, NULL); + CInst_t last = cblock_getback(cur); + if (last->dest.kind == TMP) /* temporary not used */ + { + ctmp_destroy(last->dest.info.var); + free(last); + cblock_popback(cur); + } + return res; +} + CBlock_t ssa_stmt(CNode *, CBlock_t, CBlock_t); CBlock_t ssa_while(CNode *p, CBlock_t cur) { CNode *exp = p->chd; diff --git a/ssa.h b/ssa.h index e9ff81e..d2cba0b 100644 --- a/ssa.h +++ b/ssa.h @@ -23,6 +23,7 @@ struct CInst { BNEZ, GOTO, /* unconditional jump */ ARR, /* displacement */ + WARR, MUL, DIV, MOD, ADD, SUB, SHL, SHR, AND, XOR, OR, LOR, LAND, NEG, NOR, SEQ, EQ, NE, LT, GT, LE, GE } op; COpr dest, src1, src2; diff --git a/test_all.sh b/test_all.sh index 03ff5d0..4dda78e 100755 --- a/test_all.sh +++ b/test_all.sh @@ -8,7 +8,7 @@ for file in $dir do gcc $file -o /dev/null &> /dev/null gcc_ret="$?" - ./cibic $file &> /dev/null + ./cibic --sem $file &> /dev/null ret=$? if [ $ret -ne $gcc_ret ]; then echo "Failed on $file" -- cgit v1.2.3-70-g09d2