diff options
Diffstat (limited to 'ssa.c')
| -rw-r--r-- | ssa.c | 371 |
1 files changed, 371 insertions, 0 deletions
@@ -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; +} + |