#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;
}