aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--TODO.rst2
-rw-r--r--ssa.c201
-rw-r--r--ssa.h19
3 files changed, 200 insertions, 22 deletions
diff --git a/TODO.rst b/TODO.rst
index dd231f4..cb314da 100644
--- a/TODO.rst
+++ b/TODO.rst
@@ -18,6 +18,8 @@ TODO
- calculate type memory footprint at proper time
- function to 'pointer to function' conversion (according the std 6.3.2/4) (done)
- vague var table management (done)
+ - incorrect address reference `&`
+ - const function name
- Not Implemented:
diff --git a/ssa.c b/ssa.c
index 93b291f..1faa6b0 100644
--- a/ssa.c
+++ b/ssa.c
@@ -116,7 +116,7 @@ void dtree_clear() {
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);
+/* printf("%d -> %d\n", from->id, to->id); */
CEdge *e = NEW(CEdge), *re = NEW(CEdge);
e->to = to;
e->next = cfg.head[fid];
@@ -277,7 +277,7 @@ void cblock_print(CBlock_t blk) {
CInst_t p, sp = blk->insts;
for (p = sp->next; p != sp; p = p->next)
{
- fprintf(stderr, "\t");
+ fprintf(stderr, "%02d\t", p->id);
cinst_print(p);
}
}
@@ -967,7 +967,7 @@ CPSet_t cpset_create() {
return res;
}
-void cpset_destory(CPSet_t cps) {
+void cpset_destroy(CPSet_t cps) {
int i;
for (i = 0; i < MAX_TABLE_SIZE; i++)
{
@@ -980,16 +980,35 @@ void cpset_destory(CPSet_t cps) {
}
}
-void cpset_insert(CPSet_t cps, long key) {
+int cpset_insert(CPSet_t cps, long key) {
unsigned int hv = key % MAX_TABLE_SIZE;
CPNode *p = cps->head[hv], *np;
for (; p; p = p->next)
if (p->key == key)
- return;
+ return 0;
np = NEW(CPNode);
np->key = key;
np->next = cps->head[hv];
cps->head[hv] = np;
+ return 1;
+}
+
+void cpset_erase(CPSet_t cps, long key) {
+ unsigned int hv = key % MAX_TABLE_SIZE;
+ int flag = 0;
+ CPNode *p = cps->head[hv], *pp = NULL;
+ for (; p; pp = p, p = p->next)
+ if (p->key == key)
+ {
+ flag = 1;
+ break;
+ }
+ if (!flag) return;
+ if (pp)
+ pp->next = p->next;
+ else
+ cps->head[hv] = p->next;
+ free(p);
}
int cpset_belongs(CPSet_t cps, long key) {
@@ -1063,7 +1082,7 @@ void calc_dominant_frontier(CBlock_t entry) {
np = p->next;
}
df[i] = NULL;
- if (dfset[i]) cpset_destory(dfset[i]);
+ if (dfset[i]) cpset_destroy(dfset[i]);
dfset[i] = cpset_create();
}
for (i = 0; i < bcnt; i++)
@@ -1103,7 +1122,7 @@ void insert_phi(CVList_t vars) {
int i;
for (i = 0; i < bcnt; i++)
{
- if (phi[i]) cpset_destory(phi[i]);
+ if (phi[i]) cpset_destroy(phi[i]);
phi[i] = cpset_create();
}
for (vp = vars; vp; vp = vp->next)
@@ -1112,9 +1131,11 @@ void insert_phi(CVList_t vars) {
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)
{
@@ -1125,11 +1146,13 @@ void insert_phi(CVList_t vars) {
}
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 */
@@ -1170,6 +1193,7 @@ void renaming_dfs(CBlock_t blk) {
COList_t n = NEW(COList), n2;
dest->sub = var->cnt++;
dest->def = ih->next; /* the first inst */
+ dest->range = NULL;
n->opr = dest;
n->next = var->stack;
var->stack = n;
@@ -1190,23 +1214,32 @@ void renaming_dfs(CBlock_t blk) {
/* free(p); */ /* memory leak */
*(opr[t]) = p->info.var->stack->opr;
}
- if (dest && dest->kind == VAR)
+ if (dest)
{
- if (i->op == WARR)
- i->dest = dest->info.var->stack->opr;
- else
+ if (dest->kind == VAR)
+ {
+ if (i->op == WARR)
+ i->dest = dest->info.var->stack->opr;
+ else
+ {
+ CVar_t var = dest->info.var;
+ COList_t n = NEW(COList), n2;
+ dest->sub = var->cnt++;
+ dest->def = i;
+ dest->range = NULL;
+ n->opr = dest;
+ n->next = var->stack;
+ var->stack = n;
+ n2 = NEW(COList);
+ n2->opr = dest;
+ n2->next = defs;
+ defs = n2;
+ }
+ }
+ else if (dest->kind == TMP)
{
- 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;
+ dest->range = NULL;
}
}
}
@@ -1262,6 +1295,129 @@ void renaming_vars(CVList_t vars, CBlock_t entry) {
renaming_dfs(entry);
}
+void mark_insts() {
+ int i, icnt = 0;
+ for (i = bcnt - 1; i >= 0; i--)
+ {
+ CBlock_t b = blks[ord[i]];
+ CInst_t ih = b->insts, ii;
+ CPhi_t ph = b->phis, pi;
+ for (ii = ih->next; ii != ih; ii = ii->next)
+ ii->id = icnt++;
+ for (pi = ph->next; pi != ph; pi = pi->next)
+ icnt++;
+ b->first = ih->next->id;
+ b->last = ih->prev->id;
+ }
+}
+
+CPSet_t liveset[MAX_BLOCK];
+COList_t live[MAX_BLOCK];
+
+void add_range(COpr_t opr, CBlock_t blk, int end) {
+ int dfid = opr->def->id;
+ CRange_t range = NEW(CRange);
+ if (blk->first <= dfid && dfid <= blk->last)
+ range->l = dfid;
+ else
+ range->l = blk->first;
+ range->r = end;
+ range->next = opr->range;
+ opr->range = range;
+}
+
+void build_intervals() {
+ int i;
+ for (i = 0; i < bcnt; i++)
+ {
+ COList_t p = live[i], np;
+ for (; p; p = np)
+ {
+ np = p->next;
+ free(p);
+ }
+ live[i] = NULL;
+ if (liveset[i]) cpset_destroy(liveset[i]);
+ liveset[i] = cpset_create();
+ }
+ for (i = 0; i < bcnt; i++)
+ {
+ int id = ord[i];
+ CBlock_t b = blks[id];
+ CEdge *e = cfg.head[id];
+ CPSet_t curlive = liveset[id];
+ for (; e; e = e->next)
+ {
+ int sid = e->to->id;
+ COList_t p = live[sid];
+ for (; p; p = p->next)
+ if (cpset_belongs(liveset[sid], (long)p->opr) &&
+ cpset_insert(curlive, (long)p->opr))
+ {
+ COList_t np = NEW(COList);
+ np->opr = p->opr;
+ np->next = live[id];
+ live[id] = np;
+ }
+ }
+ {
+ COList_t p;
+ for (p = live[id]; p; p = p->next)
+ add_range(p->opr, b, b->last + 1);
+ }
+ {
+ CInst_t ih = b->insts, i;
+ for (i = ih->prev; i != ih; i = i->prev)
+ {
+ int t;
+ COpr_t oprs[2] = {i->src1, i->src2};
+ if (i->dest &&
+ (i->dest->kind == VAR ||
+ i->dest->kind == TMP) && i->op != WARR) /* def */
+ cpset_erase(curlive, (long)i->dest);
+ for (t = 0; t < 2; t++)
+ {
+ COpr_t opr = oprs[t];
+ if (opr &&
+ (opr->kind == VAR ||
+ opr->kind == TMP) && !cpset_belongs(curlive, (long)opr))
+ {
+ COList_t np = NEW(COList);
+ np->opr = oprs[t];
+ np->next = live[id];
+ live[id] = np;
+ cpset_insert(curlive, (long)oprs[t]);
+ add_range(oprs[t], b, i->id);
+ }
+ }
+ }
+ }
+ }
+}
+
+void register_alloc(CBlock_t entry) {
+ mark_insts();
+ build_intervals();
+ {
+ CBlock_t p;
+ for (p = entry; p; p = p->next)
+ {
+ CInst_t i, ih = p->insts;
+ for (i = ih->next; i != ih; i = i->next)
+ if (i->dest &&
+ (i->dest->kind == VAR || i->dest->kind == TMP) && i->op != WARR)
+ {
+ CRange_t p;
+ copr_print(i->dest);
+ fprintf(stderr, ": ");
+ for (p = i->dest->range; p; p = p->next)
+ fprintf(stderr, "[%d, %d)", p->l, p->r);
+ fprintf(stderr, "\n");
+ }
+ }
+ }
+}
+
CBlock_t ssa_func(CType_t func) {
CBlock_t entry = cblock_create(1), p;
CPSet_t vs = cpset_create(), avs = cpset_create();
@@ -1324,5 +1480,8 @@ CBlock_t ssa_func(CType_t func) {
}
insert_phi(vars);
renaming_vars(all_vars, entry);
+ register_alloc(entry);
+ cpset_destroy(vs);
+ cpset_destroy(avs);
return entry;
}
diff --git a/ssa.h b/ssa.h
index 2f985aa..348893b 100644
--- a/ssa.h
+++ b/ssa.h
@@ -6,6 +6,13 @@
typedef struct CInst CInst;
typedef CInst *CInst_t;
+typedef struct CRange CRange;
+typedef struct CRange *CRange_t;
+struct CRange {
+ int l, r; /* [l, r) */
+ CRange_t next;
+};
+
typedef struct COpr COpr;
typedef COpr *COpr_t;
struct COpr {
@@ -22,6 +29,7 @@ struct COpr {
} info;
int sub;
CInst_t def;
+ CRange_t range;
};
typedef struct COList COList;
@@ -50,6 +58,7 @@ struct CInst {
} op;
COpr_t dest, src1, src2;
CInst_t next, prev;
+ int id;
};
typedef struct CPhi CPhi;
@@ -69,6 +78,7 @@ struct CBlock {
int id;
int ref; /* if referenced by any gotos */
int pred; /* the number of predecessors */
+ int first, last;
};
typedef struct CBList CBList;
@@ -109,8 +119,15 @@ typedef struct CPSet {
typedef CPSet *CPSet_t;
CPSet_t cpset_create();
-void cpset_insert(CPSet_t cps, long key);
+int cpset_insert(CPSet_t cps, long key);
int cpset_belongs(CPSet_t cps, long key);
+void cpset_destroy(CPSet_t cps);
+
+
+typedef struct CInterv {
+ COpr_t opr;
+ CRange_t range;
+} CInterv;
void ssa_generate(CScope_t scope);
#endif