...

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