diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | const.h | 2 | ||||
| -rw-r--r-- | main.c | 9 | ||||
| -rw-r--r-- | semantics.c | 5 | ||||
| -rw-r--r-- | semantics.h | 2 | ||||
| -rw-r--r-- | ssa.c | 371 | ||||
| -rw-r--r-- | ssa.h | 53 |
7 files changed, 441 insertions, 7 deletions
@@ -6,9 +6,9 @@ run: db: gdb cibic -cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o +cibic: lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o mkdir -p bin - gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o + gcc -o bin/cibic lex.yy.o cibic.tab.o ast.o main.o semantics.o ssa.o cp bin/cibic cibic lex.yy.o: lex.yy.c cibic.tab.c gcc -c lex.yy.c @@ -20,6 +20,8 @@ ast.o: ast.c ast.h gcc -c ast.c -g -Wall -Wextra -DCIBIC_DEBUG 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 lex.yy.c: cibic.l flex cibic.l cibic.tab.c: cibic.y @@ -22,7 +22,7 @@ enum { NS_ID, NS_TAG }; - +#define MAX_BLOCK 1024 #define MAX_CHDN 1024 #define MAX_DEBUG_PRINT_BUFF 1024 #define MAX_DEBUG_PRINT_LVL 1024 @@ -3,6 +3,7 @@ #include <stdlib.h> #include "cibic.tab.h" #include "ast.h" +#include "ssa.h" #include "semantics.h" extern char linebuff[]; @@ -51,6 +52,12 @@ void print_sem() { /* cnode_debug_print(ast_root, 1); */ } +void print_ssa() { + cibic_init(); + yyparse(); + ssa_generate(semantics_check(ast_root)); +} + void print_help() { fprintf(stderr, "CBIC: C Implemented Bare and Ingenuous Compiler\n\n" @@ -114,7 +121,7 @@ int main(int argc, char **argv) { { case PRINT_AST: print_ast(); break; case PRINT_HELP: print_help(); break; - default: print_sem(); + default: print_ssa(); } return 0; } diff --git a/semantics.c b/semantics.c index 6bf6925..5a6419c 100644 --- a/semantics.c +++ b/semantics.c @@ -1169,10 +1169,10 @@ ExpType semantics_exp(CNode *p, CScope_t scope) { else { p->ext.type = lu->rec.type; - p->ext.var = NULL; res.type = p->ext.type; res.lval = res.type->type == CFUNC; POINTER_CONV(res.type, p); + p->ext.var = cvar_create(p->ext.type->name, res.type, NULL); } p->ext.is_const = res.type->type == CARR || res.type->type == CFUNC; @@ -1763,7 +1763,7 @@ 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 semantics_check(CNode *p) { +CScope_t 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); @@ -1816,4 +1816,5 @@ void semantics_check(CNode *p) { } } cnode_debug_print(ast_root, 1); + return scope; } diff --git a/semantics.h b/semantics.h index ca97633..d0b681a 100644 --- a/semantics.h +++ b/semantics.h @@ -148,7 +148,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); +CScope_t semantics_check(CNode *ast); enum DefState{ FORCE_ID, @@ -0,0 +1,371 @@ +#include <stdlib.h> +#include <stdio.h> +#include "ast.h" +#include "ssa.h" +#define NEW(type) ((type *)malloc(sizeof(type))) +#define DBLINK(from, to) ((from)->next = (to))->prev = (from) + +static CGraph cfg; +static CBlock_t blks[MAX_BLOCK]; +static int bcnt; /* block counter */ +static int tcnt; /* temporary counter */ +static int gbbase; + +CBlock_t cblock_create() { + CBlock_t cblk = NEW(CBlock); + CInst_t dummy = NEW(CInst); + dummy->prev = dummy; + dummy->next = dummy; + cblk->insts = dummy; + cblk->next = NULL; + cblk->id = (bcnt++) + gbbase; + cblk->ref = 0; + return cblk; +} + +void cblock_append(CBlock_t cblk, CInst_t inst) { + CInst_t head = cblk->insts; + (inst->prev = head->prev)->next = inst; + (inst->next = head)->prev = inst; +} + +CInst_t cblock_getback(CBlock_t cblk) { + return cblk->insts->prev; +} + +int cblock_isempty(CBlock_t cblk) { + return cblk->insts->prev == cblk->insts; +} + +void cfg_clear() { + int i; + for (i = 0; i < MAX_BLOCK; i++) + if (cfg.head[i]) + { + CEdge *p, *np; + for (p = cfg.head[i]; p; p = np) + { + np = p->next; + free(p); + } + cfg.head[i] = NULL; + } +} + +void cfg_add_edge(CBlock_t from, CBlock_t to) { + int id = from->id; + CEdge *e = NEW(CEdge); + e->to = to; + e->next = cfg.head[id]; + cfg.head[id] = e; +} + +void copr_print(COpr *opr) { + switch (opr->kind) + { + case VAR: + case TMP: fprintf(stderr, "%s", opr->info.var->name); + break; + case IMM: fprintf(stderr, "%d", opr->info.imm); + break; + } +} + +void cinst_print(CInst_t inst) { + switch (inst->op) + { + case MOVE: + copr_print(&inst->dest); + fprintf(stderr, " = "); + copr_print(&inst->src1); + break; + case BEQZ: + fprintf(stderr, "if not ("); + copr_print(&inst->src1); + fprintf(stderr, ") goto _L"); + copr_print(&inst->dest); + break; + case GOTO: + fprintf(stderr, "goto _L"); + copr_print(&inst->dest); + break; + case ADD: + copr_print(&inst->dest); + fprintf(stderr, " = "); + copr_print(&inst->src1); + fprintf(stderr, " + "); + copr_print(&inst->src2); + break; + } + fprintf(stderr, "\n"); +} + +void cblock_print(CBlock_t blk) { + CInst_t p, sp = blk->insts; + if (blk->ref) + fprintf(stderr, "_L%d:\n", blk->id); + for (p = sp->next; p != sp; p = p->next) + { + fprintf(stderr, "\t"); + cinst_print(p); + } +} +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)); + } +} + +COpr ssa_exp(CNode *p, CBlock_t cur) { + COpr res; + CInst_t inst = NEW(CInst); + switch (p->type) + { + case NOP: ; break; + case ID: + res.kind = VAR; + res.info.var = p->ext.var; + break; + default: + if (p->ext.is_const) + { + res.kind = IMM; + res.info.imm = p->ext.const_val; + } + else + { + COpr lhs = ssa_exp(p->chd, cur), rhs; + if (p->chd->next) + rhs = ssa_exp(p->chd->next, cur); + switch (p->rec.subtype) + { + case '=' : + inst->op = MOVE; + inst->dest = lhs; + inst->src1 = rhs; + break; + case ASS_ADD: + inst->op = ADD; + inst->dest = lhs; + inst->src1 = lhs; + inst->src2 = rhs; + break; + /* + case ASS_MUL: + case ASS_DIV: + case ASS_MOD: + case ASS_ADD: + case ASS_SUB: + case ASS_SHL: + case ASS_SHR: + case ASS_AND: + case ASS_XOR: + case ASS_OR: + */ + } + cblock_append(cur, inst); + res = inst->dest; + } + } + return res; +} + +CBlock_t ssa_stmt(CNode *, CBlock_t, CBlock_t); +CBlock_t ssa_while(CNode *p, CBlock_t cur) { + CNode *exp = p->chd; + CBlock_t loop_blk = cblock_create(), loop_t, + cond_blk, + next_blk = cblock_create(); + CInst_t j_inst = NEW(CInst), + if_inst = NEW(CInst); + + loop_t = ssa_stmt(exp->next, loop_blk, next_blk); + + cond_blk = cblock_create(); + DBLINK(loop_t, cond_blk); + cfg_add_edge(loop_t, cond_blk); + + ssa_exp(exp, cond_blk); + + j_inst->op = GOTO; + j_inst->dest.kind = IMM; + j_inst->dest.info.imm = cond_blk->id; + cond_blk->ref = 1; + cblock_append(cur, j_inst); + + if_inst->op = BEQZ; + if_inst->src1 = cblock_getback(cond_blk)->dest; + if_inst->dest.kind = IMM; + if_inst->dest.info.imm = loop_blk->id; + loop_blk->ref = 1; + cblock_append(cond_blk, if_inst); + + cfg_add_edge(cur, cond_blk); + cfg_add_edge(cond_blk, loop_blk); + cfg_add_edge(cond_blk, next_blk); + + DBLINK(cur, loop_blk); + DBLINK(cond_blk, next_blk); +} + +CBlock_t ssa_for(CNode *p, CBlock_t cur) { + CNode *exp1 = p->chd, + *exp2 = exp1->next, + *exp3 = exp2->next; + CBlock_t loop_blk = cblock_create(), loop_t, + cond_blk, + next_blk = cblock_create(); + CInst_t j_inst = NEW(CInst), + if_inst = NEW(CInst); + + loop_t = ssa_stmt(exp3->next, loop_blk, next_blk); + + cond_blk = cblock_create(); + DBLINK(loop_t, cond_blk); + cfg_add_edge(loop_t, cond_blk); + + ssa_exp(exp1, cur); + ssa_exp(exp2, cond_blk); + ssa_exp(exp3, loop_t); + + j_inst->op = GOTO; + j_inst->dest.kind = IMM; + j_inst->dest.info.imm = cond_blk->id; + cond_blk->ref = 1; + cblock_append(cur, j_inst); + + if_inst->op = BEQZ; + if_inst->src1 = cblock_getback(cond_blk)->dest; + if_inst->dest.kind = IMM; + if_inst->dest.info.imm = loop_blk->id; + loop_blk->ref = 1; + cblock_append(cond_blk, if_inst); + + cfg_add_edge(cur, cond_blk); + cfg_add_edge(cond_blk, loop_blk); + cfg_add_edge(cond_blk, next_blk); + + DBLINK(cur, loop_blk); + DBLINK(cond_blk, next_blk); + + return next_blk; +} + +CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) { + CNode *body1 = p->chd->next, + *body2 = body1->next; + CBlock_t then_blk = cblock_create(), then_t, + next_blk, + else_blk, else_t; + CInst_t if_inst = NEW(CInst); + ssa_exp(p->chd, cur); + if_inst->op = BEQZ; + if_inst->src1 = cblock_getback(cur)->dest; /* calculated cond */ + if_inst->dest.kind = IMM; + cblock_append(cur, if_inst); + + cfg_add_edge(cur, then_blk); + DBLINK(cur, then_blk); + then_t = ssa_stmt(body1, then_blk, loop_exit); + if (body2->type != NOP) + { + CInst_t j_inst = NEW(CInst); + j_inst->op = GOTO; + j_inst->dest.kind = IMM; + + else_blk = cblock_create(); + if_inst->dest.info.imm = else_blk->id; + else_blk->ref = 1; + DBLINK(then_t, else_blk); + else_t = ssa_stmt(body2, else_blk, loop_exit); + if (cblock_isempty(else_t)) + next_blk = else_t; + else + { + next_blk = cblock_create(); + DBLINK(else_t, next_blk); + } + + j_inst->dest.info.imm = next_blk->id; + next_blk->ref = 1; + cblock_append(then_t, j_inst); + + cfg_add_edge(cur, else_blk); + cfg_add_edge(then_t, next_blk); + cfg_add_edge(else_t, next_blk); + } + else + { + if (cblock_isempty(then_t)) + next_blk = then_t; + else + { + next_blk = cblock_create(); + DBLINK(then_t, next_blk); + } + cfg_add_edge(cur, next_blk); + cfg_add_edge(then_t, next_blk); + if_inst->dest.info.imm = next_blk->id; + next_blk->ref = 1; + } + return next_blk; +} + +CBlock_t ssa_comp(CNode *, CBlock_t, CBlock_t loop_exit); +CBlock_t ssa_stmt(CNode *p, CBlock_t cur, CBlock_t loop_exit) { + switch (p->rec.subtype) + { + case STMT_EXP: + ssa_exp(p->chd, cur); + break; + case STMT_COMP: + cur = ssa_comp(p, cur, loop_exit); + break; + case STMT_IF: + return ssa_if(p, cur, loop_exit); + case STMT_FOR: + return ssa_for(p, cur); + case STMT_WHILE: + return ssa_while(p, cur); +/* return ssa_while(p, cur);*/ + /* + case STMT_CONT: + return ssa_cont(p, cur, loop_exit); + case STMT_BREAK: + return ssa_break(p, cur, loop_exit); + case STMT_RET: + return ssa_return(p, cur, loop_exit); + */ + } + return cur; +} + +CBlock_t ssa_comp(CNode *p, CBlock_t cur, CBlock_t loop_exit) { + CNode *stmts = p->chd->next, *i; + if (stmts->chd->type != NOP) + for (i = stmts->chd; i; i = i->next) + cur = ssa_stmt(i, cur, loop_exit); + return cur; +} + +CBlock_t ssa_func(CType_t func) { + CBlock_t start = cblock_create(); + ssa_comp(func->rec.func.body, start, NULL); + return start; +} + @@ -0,0 +1,53 @@ +#ifndef SSA_H +#define SSA_H +#include "const.h" +#include "semantics.h" +typedef struct COpr { + enum { + VAR, + TMP, + IMM + } kind; + union { + CVar_t var; + int imm; + } info; +} COpr; + +typedef struct CInst CInst; +typedef CInst *CInst_t; +struct CInst { + enum { + MOVE, + BEQZ, /* conditional jump */ + GOTO, /* unconditional jump */ + ADD + } op; + COpr dest, src1, src2; + CInst_t next, prev; +}; + +typedef struct CBlock CBlock; +typedef CBlock *CBlock_t; +struct CBlock { + CInst_t insts; /* instructions */ + CBlock_t next, prev; + int id; + int ref; /* if referenced by any gotos */ +}; + +CBlock_t cblock_create(); +void cblock_append(CBlock_t cblk, CInst_t inst); +CInst_t cblock_getback(CBlock_t cblk); +int cblock_isempty(CBlock_t cblk); + +typedef struct CEdge CEdge; +typedef struct CGraph { + struct CEdge { + CBlock *to; + CEdge *next; + } *head[MAX_BLOCK], *rhead[MAX_BLOCK]; +} CGraph; + +void ssa_generate(CScope_t scope); +#endif |