aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--semantics.c4
-rw-r--r--semantics.h2
-rw-r--r--ssa.c110
-rw-r--r--ssa.h33
4 files changed, 126 insertions, 23 deletions
diff --git a/semantics.c b/semantics.c
index 4545303..5af8761 100644
--- a/semantics.c
+++ b/semantics.c
@@ -126,8 +126,7 @@ void *ctable_lookup(CTable_t ct, const char *key) {
int ctable_insert(CTable_t ct, const char *key, void *val, int lvl) {
unsigned int hv = ct->hfunc(key) % MAX_TABLE_SIZE;
- CTNode *p = ct->head[hv];
- CTNode *np;
+ CTNode *p = ct->head[hv], *np;
for (; p && p->lvl == lvl; p = p->next)
if (!strcmp(p->key, key))
return 0; /* conflict */
@@ -261,6 +260,7 @@ CVar_t cvar_create(char *name, CType_t type, CNode *ast) {
cv->name = name;
cv->type = type;
cv->ast = ast;
+ cv->defsite = NULL;
return cv;
}
diff --git a/semantics.h b/semantics.h
index 0a555df..a6c4df7 100644
--- a/semantics.h
+++ b/semantics.h
@@ -13,12 +13,14 @@ typedef CSymbol *CSymbol_t;
typedef struct CDef CDef;
typedef CDef *CDef_t;
+typedef struct CBList *CBList_t;
struct CVar {
char *name;
CVar_t next; /* next in the linked list */
CType_t type;
int start;
CNode *ast;
+ CBList_t defsite;
};
CVar_t cvar_create(char *name, CType_t type, CNode *ast);
diff --git a/ssa.c b/ssa.c
index 489fb3e..7b659cf 100644
--- a/ssa.c
+++ b/ssa.c
@@ -15,10 +15,14 @@ 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;
+ CInst_t dum = NEW(CInst);
+ CPhi_t pdum = NEW(CPhi);
+ dum->prev = dum;
+ dum->next = dum;
+ pdum->prev = pdum;
+ pdum->next = pdum;
+ cblk->insts = dum;
+ cblk->phis = pdum;
cblk->next = NULL;
cblk->id = (bcnt++) + gbbase;
cblk->ref = 0;
@@ -31,6 +35,12 @@ void cblock_append(CBlock_t cblk, CInst_t inst) {
(inst->next = head)->prev = inst;
}
+void cblock_pappend(CBlock_t cblk, CPhi_t phi) {
+ CPhi_t head = cblk->phis;
+ (phi->prev = head->prev)->next = phi;
+ (phi->next = head)->prev = phi;
+}
+
void cblock_popback(CBlock_t cblk) {
CInst_t last = cblk->insts->prev;
last->next->prev = last->prev;
@@ -153,8 +163,12 @@ void cinst_print(CInst_t inst) {
copr_print(inst->src1);
break;
case RET:
- fprintf(stderr, "return ");
- copr_print(inst->src1);
+ if (inst->src1)
+ {
+ fprintf(stderr, "return ");
+ copr_print(inst->src1);
+ }
+ else fprintf(stderr, "return");
break;
default:
{
@@ -195,7 +209,7 @@ void cinst_print(CInst_t inst) {
void cblock_print(CBlock_t blk) {
CInst_t p, sp = blk->insts;
- if (blk->ref)
+ /*if (blk->ref)*/
fprintf(stderr, "_L%d:\n", blk->id);
for (p = sp->next; p != sp; p = p->next)
{
@@ -442,7 +456,7 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
else
{
int unary = 0;
- inst->op = -1;
+ inst->op = (unsigned)-1;
switch (op)
{
case ASS_MUL: inst->op = MUL; break;
@@ -458,7 +472,7 @@ COpr_t ssa_exp_(CNode *p, CBlock_t cur, CInst_t lval, CBlock_t succ) {
case OPT_INC: inst->op = ADD; unary = 1; break;
case OPT_DEC: inst->op = SUB; unary = 1; break;
}
- if (inst->op != -1)
+ if (inst->op != (unsigned)-1)
{
CInst_t tins = NEW(CInst);
ssa_exp_(p->chd, cur, tins, succ); /* as lval */
@@ -780,7 +794,10 @@ CBlock_t ssa_if(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
CBlock_t ssa_ret(CNode *p, CBlock_t cur) {
CInst_t inst = NEW(CInst);
inst->op = RET;
- inst->src1 = ssa_exp(p->chd, cur, 0);
+ if (p->chd->type != NOP)
+ inst->src1 = ssa_exp(p->chd, cur, 0);
+ else
+ inst->src1 = NULL;
cblock_append(cur, inst);
return cur;
}
@@ -846,9 +863,78 @@ CBlock_t ssa_comp(CNode *p, CBlock_t cur, CBlock_t loop_exit) {
return cur;
}
+CPSet_t cpset_create() {
+ CPSet_t res = NEW(CPSet);
+ memset(res->head, 0, sizeof res->head);
+ return res;
+}
+
+void 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;
+ np = NEW(CPNode);
+ np->key = key;
+ np->next = cps->head[hv];
+ cps->head[hv] = np;
+}
+
CBlock_t ssa_func(CType_t func) {
- CBlock_t start = cblock_create();
+ CBlock_t start = cblock_create(), p;
+ CPSet_t vars = cpset_create();
+ cfg_clear();
ssa_comp(func->rec.func.body, start, NULL);
+ for (p = start; p; p = p->next)
+ {
+ CInst_t head = p->insts, i;
+ for (i = head->next; i != head; i = i->next)
+ {
+ switch (i->op)
+ {
+ 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;
+ }
+ }
+ }
+ blks[p->id] = p;
+ }
+ {
+ int i;
+ CPNode *p;
+ for (i = 0; i < MAX_TABLE_SIZE; i++)
+ for (p = vars->head[i]; p; p = p->next)
+ {
+ CVar_t var = (CVar_t)p->key;
+ CBList_t t = var->defsite;
+ CBList_t def = NULL;
+ static int indef[MAX_BLOCK];
+ fprintf(stderr, "%s:", var->name);
+ 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 */
+ for (t = def; t; t = t->next)
+ fprintf(stderr, " %d", t->cblk->id);
+ fprintf(stderr, "\n");
+ }
+ }
return start;
}
-
diff --git a/ssa.h b/ssa.h
index 75d166d..bedf7c8 100644
--- a/ssa.h
+++ b/ssa.h
@@ -22,7 +22,6 @@ typedef struct CInst CInst;
typedef CInst *CInst_t;
struct CInst {
enum {
- MOVE,
BEQZ, /* conditional jump */
BNEZ,
GOTO, /* unconditional jump */
@@ -31,6 +30,7 @@ struct CInst {
PUSH, /* push to stack top */
CALL, /* call function */
RET, /* return */
+ MOVE,
MUL, DIV, MOD, ADD, SUB,
SHL, SHR, AND, XOR, OR,
LOR, LAND, NEG, NOR, SEQ,
@@ -40,17 +40,12 @@ struct CInst {
CInst_t next, prev;
};
-typedef struct COprList COprList;
-typedef COprList *COprList_t;
-struct COprList {
- COpr opr;
- COprList_t next;
-};
typedef struct CPhi CPhi;
typedef CPhi *CPhi_t;
struct CPhi {
- COpr dest;
- COprList_t params;
+ COpr_t dest;
+ COpr_t *oprs;
+ CPhi_t next, prev;
};
typedef struct CBlock CBlock;
@@ -63,8 +58,16 @@ struct CBlock {
int ref; /* if referenced by any gotos */
};
+typedef struct CBList CBList;
+typedef CBList *CBList_t;
+struct CBList {
+ CBlock_t cblk;
+ CBList_t next;
+};
+
CBlock_t cblock_create();
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);
int cblock_isempty(CBlock_t cblk);
@@ -76,5 +79,17 @@ typedef struct CGraph {
} *head[MAX_BLOCK], *rhead[MAX_BLOCK];
} CGraph;
+typedef struct CPNode CPNode;
+typedef struct CPSet {
+ struct CPNode {
+ long key;
+ CPNode *next;
+ } *head[MAX_TABLE_SIZE];
+} CPSet;
+typedef CPSet *CPSet_t;
+
+CPSet_t cpset_create();
+void cpset_insert(CPSet_t cps, long key);
+
void ssa_generate(CScope_t scope);
#endif
Powered by cgit, Themed by Ted Yin.