aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--dom.c2
-rw-r--r--ssa.c200
-rw-r--r--ssa.h3
3 files changed, 172 insertions, 33 deletions
diff --git a/dom.c b/dom.c
index 7fbd948..c6eaa97 100644
--- a/dom.c
+++ b/dom.c
@@ -105,7 +105,7 @@ int main() {
for (; e; e = e->next)
{
int p = e->to;
- if (p == new_idom) continue;
+ if (vis[p] == new_idom) continue;
if (dom[vis[p]] != -1)
new_idom = intersect(vis[p], new_idom);
}
diff --git a/ssa.c b/ssa.c
index 7b659cf..ac316d4 100644
--- a/ssa.c
+++ b/ssa.c
@@ -13,7 +13,7 @@ static int bcnt; /* block counter */
static int tcnt; /* temporary counter */
static int gbbase;
-CBlock_t cblock_create() {
+CBlock_t cblock_create(int inc) {
CBlock_t cblk = NEW(CBlock);
CInst_t dum = NEW(CInst);
CPhi_t pdum = NEW(CPhi);
@@ -24,7 +24,8 @@ CBlock_t cblock_create() {
cblk->insts = dum;
cblk->phis = pdum;
cblk->next = NULL;
- cblk->id = (bcnt++) + gbbase;
+ if (inc)
+ cblk->id = bcnt++;
cblk->ref = 0;
return cblk;
}
@@ -76,24 +77,33 @@ void ctmp_destroy(CVar_t type) {
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)
{
- CEdge *p, *np;
- for (p = cfg.head[i]; p; p = np)
- {
- np = p->next;
- free(p);
- }
- cfg.head[i] = NULL;
+ np = p->next;
+ free(p);
}
+ cfg.head[i] = NULL;
+ for (p = cfg.rhead[i]; p; p = np)
+ {
+ np = p->next;
+ free(p);
+ }
+ cfg.rhead[i] = NULL;
+ }
}
void cfg_add_edge(CBlock_t from, CBlock_t to) {
- int id = from->id;
- CEdge *e = NEW(CEdge);
+ int fid = from->id, tid = to->id;
+ CEdge *e = NEW(CEdge), *re = NEW(CEdge);
e->to = to;
- e->next = cfg.head[id];
- cfg.head[id] = e;
+ e->next = cfg.head[fid];
+ cfg.head[fid] = e;
+
+ re->to = from;
+ re->next = cfg.rhead[tid];
+ cfg.rhead[tid] = re;
}
void copr_print(COpr_t opr) {
@@ -210,7 +220,7 @@ void cinst_print(CInst_t inst) {
void cblock_print(CBlock_t blk) {
CInst_t p, sp = blk->insts;
/*if (blk->ref)*/
- fprintf(stderr, "_L%d:\n", blk->id);
+ fprintf(stderr, "_L%d:\n", blk->id + gbbase);
for (p = sp->next; p != sp; p = p->next)
{
fprintf(stderr, "\t");
@@ -611,7 +621,7 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
}
COpr_t ssa_exp(CNode *p, CBlock_t cur, int discard_last) {
- CBlock_t succ = cblock_create();
+ CBlock_t succ = cblock_create(0);
COpr_t res = ssa_exp_(p, cur, NULL, succ);
CInst_t last;
{
@@ -639,9 +649,9 @@ COpr_t ssa_exp(CNode *p, CBlock_t cur, int discard_last) {
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 = cblock_create(),
- next_blk = cblock_create();
+ CBlock_t loop_blk = cblock_create(1), loop_t,
+ cond_blk = cblock_create(1),
+ next_blk = cblock_create(1);
CInst_t j_inst = NEW(CInst),
if_inst = NEW(CInst);
@@ -680,9 +690,9 @@ 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 = cblock_create(),
- next_blk = cblock_create();
+ CBlock_t loop_blk = cblock_create(1), loop_t,
+ cond_blk = cblock_create(1),
+ next_blk = cblock_create(1);
CInst_t j_inst = NEW(CInst),
if_inst = NEW(CInst);
@@ -722,7 +732,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(), then_t,
+ CBlock_t then_blk = cblock_create(1), then_t,
next_blk,
else_blk, else_t;
CInst_t if_inst = NEW(CInst);
@@ -753,7 +763,7 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
j_inst->dest = NEW(COpr);
j_inst->dest->kind = IMM;
- else_blk = cblock_create();
+ else_blk = cblock_create(1);
if_inst->dest->info.imm = else_blk->id;
else_blk->ref = 1;
DBLINK(then_t, else_blk);
@@ -762,7 +772,7 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
next_blk = else_t;
else
{
- next_blk = cblock_create();
+ next_blk = cblock_create(1);
DBLINK(else_t, next_blk);
}
@@ -780,7 +790,7 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
next_blk = then_t;
else
{
- next_blk = cblock_create();
+ next_blk = cblock_create(1);
DBLINK(then_t, next_blk);
}
cfg_add_edge(cur, next_blk);
@@ -869,6 +879,19 @@ CPSet_t cpset_create() {
return res;
}
+void cpset_destory(CPSet_t cps) {
+ int i;
+ for (i = 0; i < MAX_TABLE_SIZE; i++)
+ {
+ CPNode *p, *np;
+ for (p = cps->head[i]; p; p = np)
+ {
+ np = p->next;
+ free(p);
+ }
+ }
+}
+
void cpset_insert(CPSet_t cps, long key) {
unsigned int hv = key % MAX_TABLE_SIZE;
CPNode *p = cps->head[hv], *np;
@@ -881,12 +904,116 @@ void cpset_insert(CPSet_t cps, long key) {
cps->head[hv] = np;
}
+int cpset_belongs(CPSet_t cps, long key) {
+ unsigned int hv = key % MAX_TABLE_SIZE;
+ CPNode *p = cps->head[hv];
+ for (; p; p = p->next)
+ if (p->key == key)
+ return 1;
+ return 0;
+}
+
+int dom[MAX_BLOCK], ord[MAX_BLOCK], vis[MAX_BLOCK], par[MAX_BLOCK], ocnt;
+CPSet_t dfset[MAX_BLOCK];
+CBList_t df[MAX_BLOCK];
+
+void dfs(CBlock_t u, int v) {
+ CEdge *e;
+ if (vis[u->id] != -1) return;
+ par[u->id] = v;
+ vis[u->id] = 0;
+ for (e = cfg.head[u->id]; e; e = e->next)
+ dfs(e->to, u->id);
+ vis[u->id] = ocnt;
+ ord[ocnt++] = u->id;
+}
+
+int intersect(int b1, int b2) {
+ while (b1 != b2)
+ if (b1 < b2) b1 = dom[b1];
+ else b2 = dom[b2];
+ return b1;
+}
+
+void calc_dominant_frontier(CBlock_t entry) {
+ int i;
+ int ch = 1;
+ ocnt = 0;
+ memset(vis, -1, sizeof vis);
+ memset(dom, -1, sizeof dom);
+ dfs(entry, -1);
+ dom[vis[entry->id]] = vis[entry->id];
+ while (ch)
+ {
+ int i;
+ ch = 0;
+ for (i = bcnt - 2; i >= 0; i--)
+ {
+ int id = ord[i];
+ CEdge *e = cfg.rhead[id];
+ int new_idom = vis[par[id]];
+ for (; e; e = e->next)
+ {
+ int p = e->to->id;
+ if (vis[p] == new_idom) continue;
+ if (dom[vis[p]] != -1)
+ new_idom = intersect(vis[p], new_idom);
+ }
+ if (dom[i] != new_idom)
+ {
+ ch = 1;
+ dom[i] = new_idom;
+ }
+ }
+ }
+ for (i = 0; i < bcnt; i++)
+ {
+ CBList_t p, np;
+ for (p = df[i]; p; p = np)
+ {
+ free(p);
+ np = p->next;
+ }
+ df[i] = NULL;
+ if (dfset[i]) cpset_destory(dfset[i]);
+ dfset[i] = cpset_create();
+ }
+ for (i = 0; i < bcnt; i++)
+ if (cfg.rhead[i] && cfg.rhead[i]->next)
+ {
+ CEdge *p = cfg.rhead[i];
+ for (; p; p = p->next)
+ {
+ int runner = p->to->id;
+ while (vis[runner] != dom[vis[i]])
+ {
+ if (!cpset_belongs(dfset[runner], i))
+ {
+ CBList_t np = NEW(CBList);
+ np->cblk = blks[i];
+ np->next = df[runner];
+ cpset_insert(dfset[runner], i);
+ df[runner] = np;
+ }
+ runner = ord[dom[vis[runner]]];
+ }
+ }
+ }
+ for (i = 0; i < bcnt; i++)
+ {
+ CBList_t p = df[i];
+ printf("%d: ", i);
+ for (; p; p = p->next)
+ printf("%d ", p->cblk->id); puts("");
+ }
+}
+
CBlock_t ssa_func(CType_t func) {
- CBlock_t start = cblock_create(), p;
+ CBlock_t entry = cblock_create(1), p;
CPSet_t vars = cpset_create();
cfg_clear();
- ssa_comp(func->rec.func.body, start, NULL);
- for (p = start; p; p = p->next)
+ ssa_comp(func->rec.func.body, entry, NULL);
+ for (p = entry; p; p = p->next)
{
CInst_t head = p->insts, i;
for (i = head->next; i != head; i = i->next)
@@ -910,17 +1037,20 @@ CBlock_t ssa_func(CType_t func) {
}
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)
{
@@ -931,10 +1061,18 @@ CBlock_t ssa_func(CType_t func) {
}
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;
+
+ }
}
}
- return start;
+ return entry;
}
diff --git a/ssa.h b/ssa.h
index bedf7c8..bf49f0f 100644
--- a/ssa.h
+++ b/ssa.h
@@ -65,7 +65,7 @@ struct CBList {
CBList_t next;
};
-CBlock_t cblock_create();
+CBlock_t cblock_create(int inc);
void cblock_append(CBlock_t cblk, CInst_t inst);
void cblock_pappend(CBlock_t cblk, CPhi_t phi);
CInst_t cblock_getback(CBlock_t cblk);
@@ -90,6 +90,7 @@ typedef CPSet *CPSet_t;
CPSet_t cpset_create();
void cpset_insert(CPSet_t cps, long key);
+int cpset_belongs(CPSet_t cps, long key);
void ssa_generate(CScope_t scope);
#endif