aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--semantics.h4
-rw-r--r--ssa.c342
-rw-r--r--ssa.h23
3 files changed, 299 insertions, 70 deletions
diff --git a/semantics.h b/semantics.h
index a6c4df7..65d1b7e 100644
--- a/semantics.h
+++ b/semantics.h
@@ -14,6 +14,7 @@ typedef struct CDef CDef;
typedef CDef *CDef_t;
typedef struct CBList *CBList_t;
+typedef struct COList *COList_t;
struct CVar {
char *name;
CVar_t next; /* next in the linked list */
@@ -21,6 +22,9 @@ struct CVar {
int start;
CNode *ast;
CBList_t defsite;
+ /* the following fields are used for renaming */
+ int cnt;
+ COList_t stack;
};
CVar_t cvar_create(char *name, CType_t type, CNode *ast);
diff --git a/ssa.c b/ssa.c
index ac316d4..be7e4f0 100644
--- a/ssa.c
+++ b/ssa.c
@@ -7,7 +7,7 @@
#define NEW(type) ((type *)malloc(sizeof(type)))
#define DBLINK(from, to) ((from)->next = (to))->prev = (from)
-static CGraph cfg;
+static CGraph cfg, dtree;
static CBlock_t blks[MAX_BLOCK];
static int bcnt; /* block counter */
static int tcnt; /* temporary counter */
@@ -94,8 +94,23 @@ void cfg_clear() {
}
}
+void dtree_clear() {
+ int i;
+ for (i = 0; i < MAX_BLOCK; i++)
+ {
+ CEdge *p, *np;
+ for (p = dtree.head[i]; p; p = np)
+ {
+ np = p->next;
+ free(p);
+ }
+ dtree.head[i] = NULL;
+ }
+}
+
void cfg_add_edge(CBlock_t from, CBlock_t to) {
int fid = from->id, tid = to->id;
+ printf("%d -> %d\n", from->id, to->id);
CEdge *e = NEW(CEdge), *re = NEW(CEdge);
e->to = to;
e->next = cfg.head[fid];
@@ -106,10 +121,20 @@ void cfg_add_edge(CBlock_t from, CBlock_t to) {
cfg.rhead[tid] = re;
}
+void dtree_add_edge(CBlock_t from, CBlock_t to) {
+ int id = from->id;
+ CEdge *e = NEW(CEdge);
+ e->to = to;
+ e->next = dtree.head[id];
+ dtree.head[id] = e;
+}
+
void copr_print(COpr_t opr) {
switch (opr->kind)
{
case VAR:
+ fprintf(stderr, "%s_%d", opr->info.var->name, opr->sub);
+ break;
case TMP: fprintf(stderr, "%s", opr->info.var->name);
break;
case IMM: fprintf(stderr, "%d", opr->info.imm);
@@ -217,14 +242,34 @@ void cinst_print(CInst_t inst) {
fprintf(stderr, "\n");
}
+void cphi_print(CPhi_t phi, CBlock_t blk) {
+ int i;
+ fprintf(stderr, "%s_%d = phi", phi->dest->info.var->name,
+ phi->dest->sub);
+ for (i = 0; i < blk->pred; i++)
+ fprintf(stderr, " %s_%d", phi->oprs[i]->info.var->name,
+ phi->oprs[i]->sub);
+ 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 + gbbase);
- for (p = sp->next; p != sp; p = p->next)
+ fprintf(stderr, "_L%d:\n", blk->id + gbbase);
{
- fprintf(stderr, "\t");
- cinst_print(p);
+ CPhi_t p, sp = blk->phis;
+ for (p = sp->next; p != sp; p = p->next)
+ {
+ fprintf(stderr, "\t");
+ cphi_print(p, blk);
+ }
+ }
+ {
+ CInst_t p, sp = blk->insts;
+ for (p = sp->next; p != sp; p = p->next)
+ {
+ fprintf(stderr, "\t");
+ cinst_print(p);
+ }
}
}
void ssa_func_print(CBlock_t p) {
@@ -308,6 +353,7 @@ COpr_t ssa_postfix(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
CInst_t ps = NULL, t;
base->op = CALL;
base->src1 = ssa_exp_(p->chd, cur, lval, succ);
+ base->src2 = NULL;
base->dest = NEW(COpr);
base->dest->kind = TMP;
base->dest->info.var = ctmp_create(rt);
@@ -316,6 +362,8 @@ COpr_t ssa_postfix(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
CInst_t pi = NEW(CInst);
pi->op = PUSH;
pi->src1 = ssa_exp_(arg, cur, lval, succ);
+ pi->src2 = NULL;
+ pi->dest = NULL;
pi->next = ps;
ps = pi;
}
@@ -391,6 +439,7 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
{
lval->op = MOVE;
lval->dest = res;
+ lval->src2 = NULL;
}
break;
case STR:
@@ -583,6 +632,7 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
{
inst->op = NEG;
inst->src1 = lhs;
+ inst->src2 = NULL;
}
break;
case '~':
@@ -663,17 +713,20 @@ CBlock_t ssa_while(CNode *p, CBlock_t cur) {
j_inst->op = GOTO;
+ j_inst->src1 = NULL;
+ j_inst->src2 = NULL;
j_inst->dest = NEW(COpr);
j_inst->dest->kind = IMM;
- j_inst->dest->info.imm = cond_blk->id;
+ j_inst->dest->info.imm = cond_blk->id + gbbase;
cond_blk->ref = 1;
cblock_append(cur, j_inst);
if_inst->op = BNEZ;
if_inst->src1 = ssa_exp(exp, cond_blk, 0);
+ if_inst->src2 = NULL;
if_inst->dest = NEW(COpr);
if_inst->dest->kind = IMM;
- if_inst->dest->info.imm = loop_blk->id;
+ if_inst->dest->info.imm = loop_blk->id + gbbase;
loop_blk->ref = 1;
cblock_append(cond_blk, if_inst);
@@ -706,17 +759,20 @@ CBlock_t ssa_for(CNode *p, CBlock_t cur) {
ssa_exp(exp3, loop_t, 1);
j_inst->op = GOTO;
+ j_inst->src1 = NULL;
+ j_inst->src2 = NULL;
j_inst->dest = NEW(COpr);
j_inst->dest->kind = IMM;
- j_inst->dest->info.imm = cond_blk->id;
+ j_inst->dest->info.imm = cond_blk->id + gbbase;
cond_blk->ref = 1;
cblock_append(cur, j_inst);
if_inst->op = BNEZ;
if_inst->src1 = ssa_exp(exp2, cond_blk, 0);
+ if_inst->src2 = NULL;
if_inst->dest = NEW(COpr);
if_inst->dest->kind = IMM;
- if_inst->dest->info.imm = loop_blk->id;
+ if_inst->dest->info.imm = loop_blk->id + gbbase;
loop_blk->ref = 1;
cblock_append(cond_blk, if_inst);
@@ -732,8 +788,7 @@ CBlock_t ssa_for(CNode *p, CBlock_t cur) {
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(1), then_t,
- next_blk,
+ CBlock_t then_blk, then_t, next_blk,
else_blk, else_t;
CInst_t if_inst = NEW(CInst);
COpr_t rt = ssa_exp(p->chd, cur, 0);
@@ -746,9 +801,10 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
else
return cur;
}
-
+ then_blk = cblock_create(1);
if_inst->op = BEQZ;
if_inst->src1 = rt; /* calculated cond */
+ if_inst->src2 = NULL;
if_inst->dest = NEW(COpr);
if_inst->dest->kind = IMM;
cblock_append(cur, if_inst);
@@ -760,11 +816,13 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
{
CInst_t j_inst = NEW(CInst);
j_inst->op = GOTO;
+ j_inst->src1 = NULL;
+ j_inst->src2 = NULL;
j_inst->dest = NEW(COpr);
j_inst->dest->kind = IMM;
else_blk = cblock_create(1);
- if_inst->dest->info.imm = else_blk->id;
+ if_inst->dest->info.imm = else_blk->id + gbbase;
else_blk->ref = 1;
DBLINK(then_t, else_blk);
else_t = ssa_stmt(body2, else_blk, loop_exit);
@@ -774,15 +832,15 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
{
next_blk = cblock_create(1);
DBLINK(else_t, next_blk);
+ cfg_add_edge(else_t, next_blk);
}
- j_inst->dest->info.imm = next_blk->id;
+ j_inst->dest->info.imm = next_blk->id + gbbase;
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
{
@@ -792,10 +850,10 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
{
next_blk = cblock_create(1);
DBLINK(then_t, next_blk);
+ cfg_add_edge(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;
+ if_inst->dest->info.imm = next_blk->id + gbbase;
next_blk->ref = 1;
}
return next_blk;
@@ -808,6 +866,8 @@ CBlock_t ssa_ret(CNode *p, CBlock_t cur) {
inst->src1 = ssa_exp(p->chd, cur, 0);
else
inst->src1 = NULL;
+ inst->src2 = NULL;
+ inst->dest = NULL;
cblock_append(cur, inst);
return cur;
}
@@ -816,9 +876,11 @@ CBlock_t ssa_break(CBlock_t cur, CBlock_t loop_exit) {
CInst_t inst = NEW(CInst);
assert(loop_exit);
inst->op = GOTO;
+ inst->src1 = NULL;
+ inst->src2 = NULL;
inst->dest = NEW(COpr);
inst->dest->kind = IMM;
- inst->dest->info.imm = loop_exit->id;
+ inst->dest->info.imm = loop_exit->id + gbbase;
loop_exit->ref = 1;
cblock_append(cur, inst);
cfg_add_edge(cur, loop_exit);
@@ -830,9 +892,11 @@ CBlock_t ssa_cont(CBlock_t cur, CBlock_t loop_exit) {
assert(loop_exit);
loop_exit = loop_exit->prev; /* loop cond */
inst->op = GOTO;
+ inst->src1 = NULL;
+ inst->src2 = NULL;
inst->dest = NEW(COpr);
inst->dest->kind = IMM;
- inst->dest->info.imm = loop_exit->id;
+ inst->dest->info.imm = loop_exit->id + gbbase;
loop_exit->ref = 1;
cblock_append(cur, inst);
cfg_add_edge(cur, loop_exit);
@@ -914,7 +978,7 @@ int cpset_belongs(CPSet_t cps, long key) {
}
int dom[MAX_BLOCK], ord[MAX_BLOCK], vis[MAX_BLOCK], par[MAX_BLOCK], ocnt;
-CPSet_t dfset[MAX_BLOCK];
+CPSet_t dfset[MAX_BLOCK], phi[MAX_BLOCK];
CBList_t df[MAX_BLOCK];
void dfs(CBlock_t u, int v) {
@@ -999,6 +1063,8 @@ void calc_dominant_frontier(CBlock_t entry) {
}
}
}
+ for (i = 1; i < bcnt; i++)
+ dtree_add_edge(blks[ord[dom[vis[i]]]], blks[i]);
for (i = 0; i < bcnt; i++)
{
CBList_t p = df[i];
@@ -1008,71 +1074,211 @@ void calc_dominant_frontier(CBlock_t entry) {
}
}
+void insert_phi(CVList_t vars) {
+ CVList_t vp;
+ int i;
+ for (i = 0; i < bcnt; i++)
+ {
+ if (phi[i]) cpset_destory(phi[i]);
+ phi[i] = cpset_create();
+ }
+ for (vp = vars; vp; vp = vp->next)
+ { /* for each variable */
+ CVar_t var = vp->var;
+ 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)
+ {
+ CBList_t p = NEW(CBList);
+ p->cblk = t->cblk;
+ p->next = def;
+ def = p;
+ }
+ 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 */
+ def = def->next;
+ for (i = df[n->cblk->id]; i; i = i->next)
+ {
+ CBlock_t y = i->cblk;
+ CPSet_t phiy = phi[y->id];
+ if (!cpset_belongs(phiy, (long)var))
+ {
+ CPhi_t phi = NEW(CPhi);
+ CBList_t ndef;
+ phi->dest = NEW(COpr);
+ phi->dest->info.var = var;
+ phi->oprs = (COpr_t *)malloc(sizeof(COpr_t) * y->pred);
+ cblock_pappend(y, phi);
+ cpset_insert(phiy, (long)var);
+ ndef = NEW(CBList);
+ ndef->cblk = y;
+ ndef->next = def;
+ def = ndef;
+ }
+ }
+ }
+ }
+
+}
+
+void renaming_dfs(CBlock_t blk) {
+ CInst_t ih = blk->insts, i;
+ CPhi_t ph = blk->phis, pi;
+ CEdge *e = cfg.head[blk->id];
+ COList_t defs = NULL, dn;
+ for (pi = ph->next; pi != ph; pi = pi->next)
+ {
+ COpr_t dest = pi->dest;
+ CVar_t var = dest->info.var;
+ COList_t n = NEW(COList), n2;
+ dest->sub = ++var->cnt;
+ dest->def = NULL; /* pi */
+ n->opr = dest;
+ n->next = var->stack;
+ var->stack = n;
+ n2 = NEW(COList);
+ n2->opr = dest;
+ n2->next = defs;
+ defs = n2;
+ }
+ for (i = ih->next; i != ih; i = i->next)
+ {
+ COpr_t dest = i->dest;
+ COpr_t *opr[2] = {&(i->src1), &(i->src2)};
+ int t;
+ for (t = 0; t < 2; t++)
+ {
+ COpr_t p = *(opr[t]);
+ if (!(p && p->kind == VAR)) continue;
+ free(p);
+ *(opr[t]) = p->info.var->stack->opr;
+ }
+ if (dest && dest->kind == VAR && i->op != WARR)
+ {
+ CVar_t var = dest->info.var;
+ COList_t n = NEW(COList), n2;
+ dest->sub = ++var->cnt;
+ dest->def = i;
+ n->opr = dest;
+ n->next = var->stack;
+ var->stack = n;
+ n2 = NEW(COList);
+ n2->opr = dest;
+ n2->next = defs;
+ defs = n2;
+ }
+ }
+ for (; e; e = e->next) /* for each successor */
+ {
+ CBlock_t y = e->to;
+ int j = 0;
+ CEdge *pre = cfg.rhead[y->id];
+ for (; pre->to != blk; pre = pre->next) j++;
+ ph = y->phis;
+ for (pi = ph->next; pi != ph; pi = pi->next)
+ pi->oprs[j] = pi->dest->info.var->stack->opr;
+ }
+ for (e = dtree.head[blk->id]; e; e = e->next)
+ renaming_dfs(e->to);
+ for (; defs; defs = dn)
+ {
+ CVar_t var = defs->opr->info.var;
+ COList_t nf = var->stack->next;
+ free(var->stack);
+ var->stack = nf;
+ dn = defs->next;
+ free(defs);
+ }
+}
+
+void renaming_vars(CVList_t vars, CBlock_t entry) {
+ CVList_t vp;
+ for (vp = vars; vp; vp = vp->next)
+ {
+ CVar_t var = vp->var;
+ COpr_t idef = NEW(COpr);
+ COList_t n = NEW(COList);
+ var->cnt = 0;
+ var->stack = n;
+ n->opr = idef;
+ n->next = NULL;
+ idef->def = NULL;
+ idef->sub = 0;
+ idef->kind = VAR;
+ idef->info.var = var;
+ }
+ renaming_dfs(entry);
+}
+
CBlock_t ssa_func(CType_t func) {
CBlock_t entry = cblock_create(1), p;
- CPSet_t vars = cpset_create();
+ CPSet_t vs = cpset_create(), avs = cpset_create();
+ CVList_t vars = NULL, all_vars = NULL;
+ int i;
cfg_clear();
+ dtree_clear();
ssa_comp(func->rec.func.body, entry, NULL);
for (p = entry; p; p = p->next)
{
CInst_t head = p->insts, i;
+ CEdge *e;
+ p->pred = 0;
+ for (e = cfg.rhead[p->id]; e; e = e->next)
+ p->pred++;
for (i = head->next; i != head; i = i->next)
{
- switch (i->op)
+ if (i->src1 && i->src1->kind == VAR)
+ cpset_insert(avs, (long)(i->src1->info.var));
+ if (i->src2 && i->src2->kind == VAR)
+ cpset_insert(avs, (long)(i->src2->info.var));
+ if (i->dest && i->dest->kind == VAR && i->op != WARR)
{
- case BEQZ: case BNEZ: case GOTO:
- case PUSH: case RET:
- case WARR:
- ; break;
- default:
- {
- CVar_t d = i->dest->info.var;
- CBList_t b = NEW(CBList);
- cpset_insert(vars, (long)d);
- b->next = d->defsite;
- b->cblk = p;
- d->defsite = b;
- }
+ CVar_t d = i->dest->info.var;
+ CBList_t b = NEW(CBList);
+ cpset_insert(vs, (long)d);
+ cpset_insert(avs, (long)d);
+ b->next = d->defsite;
+ b->cblk = p;
+ d->defsite = b;
}
}
blks[p->id] = p;
}
calc_dominant_frontier(entry);
{
- int i;
CPNode *p;
for (i = 0; i < MAX_TABLE_SIZE; i++)
- for (p = vars->head[i]; p; p = p->next)
- { /* for each variable */
- CVar_t var = (CVar_t)p->key;
- 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)
- {
- CBList_t p = NEW(CBList);
- p->cblk = t->cblk;
- p->next = def;
- def = p;
- }
- 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; /* remove some node n from def */
- def = def->next;
-
- }
+ {
+ for (p = vs->head[i]; p; p = p->next)
+ {
+ CVList_t n = NEW(CVList);
+ n->next = vars;
+ n->var = (CVar_t)p->key;
+ vars = n;
+ }
+ for (p = avs->head[i]; p; p = p->next)
+ {
+ CVList_t n = NEW(CVList);
+ n->next = all_vars;
+ n->var = (CVar_t)p->key;
+ all_vars = n;
}
- }
+ }
+ }
+ insert_phi(vars);
+ renaming_vars(all_vars, entry);
return entry;
}
diff --git a/ssa.h b/ssa.h
index bf49f0f..819428d 100644
--- a/ssa.h
+++ b/ssa.h
@@ -2,6 +2,10 @@
#define SSA_H
#include "const.h"
#include "semantics.h"
+
+typedef struct CInst CInst;
+typedef CInst *CInst_t;
+
typedef struct COpr COpr;
typedef COpr *COpr_t;
struct COpr {
@@ -16,10 +20,17 @@ struct COpr {
int imm;
char *str;
} info;
+ int sub;
+ CInst_t def;
+};
+
+typedef struct COList COList;
+typedef COList *COList_t;
+struct COList {
+ COpr_t opr;
+ COList_t next;
};
-typedef struct CInst CInst;
-typedef CInst *CInst_t;
struct CInst {
enum {
BEQZ, /* conditional jump */
@@ -56,6 +67,7 @@ struct CBlock {
CBlock_t next, prev;
int id;
int ref; /* if referenced by any gotos */
+ int pred; /* the number of predecessors */
};
typedef struct CBList CBList;
@@ -65,6 +77,13 @@ struct CBList {
CBList_t next;
};
+typedef struct CVList CVList;
+typedef CVList *CVList_t;
+struct CVList {
+ CVar_t var;
+ CVList_t next;
+};
+
CBlock_t cblock_create(int inc);
void cblock_append(CBlock_t cblk, CInst_t inst);
void cblock_pappend(CBlock_t cblk, CPhi_t phi);