interval merging

3 files changed, 133 insertions, 37 deletions

diff --git a/TODO.rst b/TODO.rst
index cb314da..07acc89 100644
--- a/TODO.rst
+++ b/TODO.rst
@@ -19,7 +19,8 @@ TODO
   - 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 
+  - const function name (done)
+  - remove the redundant edge from blocks that break a loop
 
 - Not Implemented:
 
diff --git a/ssa.c b/ssa.c
index f38bf63..28970c0 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];
@@ -128,6 +128,7 @@ void cfg_add_edge(CBlock_t from, CBlock_t to) {
 }
 
 void dtree_add_edge(CBlock_t from, CBlock_t to) {
+/*    printf("%d d-> %d\n", from->id, to->id); */
     int id = from->id;
     CEdge *e = NEW(CEdge);
     e->to = to;
@@ -1150,11 +1151,9 @@ 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)
             {
@@ -1165,13 +1164,11 @@ 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 */
@@ -1321,12 +1318,17 @@ void mark_insts() {
         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;
+        if (cblock_isempty(b))
+            b->first = b->last = icnt++;
+        else
+        {
+            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;
+        }
     }
 }
 
@@ -1412,7 +1414,12 @@ void build_intervals() {
                 if (i->dest &&
                     (i->dest->kind == VAR ||
                      i->dest->kind == TMP) && i->op != WARR) /* def */
+                {
+                    i->is_def = 1;
                     cpset_erase(curlive, (long)i->dest);
+                }
+                else
+                    i->is_def = 0;
                 for (t = 0; t < 2; t++)
                 {
                     COpr_t opr = oprs[t];
@@ -1438,37 +1445,121 @@ void build_intervals() {
     }
 }
 
-void register_alloc(CBlock_t entry) {
-    mark_insts();
-    build_intervals();
+COpr_t cinterv_repr(COpr_t opr) {
+    return opr->par == opr ? opr : (opr->par = cinterv_repr(opr->par));
+}
+
+CRange_t crange_merge(CRange_t a, CRange_t b) {
+    CRange res;
+    CRange_t tail = &res;
+    res.next = NULL;
+    res.r = -1;
+    for (; a || b;)
     {
-        CBlock_t p;
-        for (p = entry; p; p = p->next)
+        if (a && (!b || a->l < b->l))
         {
-            CInst_t i, ih = p->insts;
-            CPhi_t pi, ph = p->phis;
-            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");
-                }
-            for (pi = ph->next; pi != ph; pi = pi->next)
+            if (tail->r == a->l)
+                tail->r = a->r;
+            else
+            {
+                assert(tail->r < a->l);
+                tail->next = a;
+                tail = a;
+            }
+            a = a->next;
+        }
+        else
+        {
+            if (tail->r == b->l)
+                tail->r = b->r;
+            else
             {
-                CRange_t p;
-                copr_print(pi->dest);
-                fprintf(stderr, ": ");
-                for (p = pi->dest->range; p; p = p->next)
-                    fprintf(stderr, "[%d, %d)", p->l, p->r);
-                fprintf(stderr, "\n");
+                assert(tail->r < b->l);
+                tail->next = b;
+                tail = b;
             }
+            b = b->next;
         }
     }
+    tail->next = NULL;
+    return res.next;
+}
+
+void cinterv_union(COpr_t a, COpr_t b) {
+    a = cinterv_repr(a);
+    b = cinterv_repr(b);
+    fprintf(stderr, "merging ");
+    copr_print(a);
+    fprintf(stderr, " ");
+    copr_print(b);
+    fprintf(stderr, "\n");
+    if (a == b) return;
+    b->range = crange_merge(b->range, a->range);
+    a->par = b;
+}
+
+COList_t init_def(CBlock_t entry) {
+    CBlock_t p;
+    COList_t defs = NULL, def;
+    for (p = entry; p; p = p->next)
+    {
+        CInst_t i, ih = p->insts;
+        CPhi_t pi, ph = p->phis;
+        for (i = ih->next; i != ih; i = i->next)
+            if (i->is_def)
+            {
+                i->dest->par = i->dest;
+                def = NEW(COList);
+                def->opr = i->dest;
+                def->next = defs;
+                defs = def;
+            }
+        for (pi = ph->next; pi != ph; pi = pi->next)
+        {
+            pi->dest->par = pi->dest;
+            def = NEW(COList);
+            def->opr = pi->dest;
+            def->next = defs;
+            defs = def;
+        }
+    }
+    for (p = entry; p; p = p->next)
+    {
+        CPhi_t pi, ph = p->phis;
+        for (pi = ph->next; pi != ph; pi = pi->next)
+        {
+            int i;
+            for (i = 0; i < p->pred; i++)
+                cinterv_union(pi->dest, pi->oprs[i]);
+        }
+    }
+    return defs;
+}
+
+void print_intervals(COList_t defs) {
+    for (; defs; defs = defs->next)
+    {
+        COpr_t opr = defs->opr,
+               repr = cinterv_repr(opr);
+        CRange_t p;
+        copr_print(opr);
+        fprintf(stderr, ": ");
+        if (repr == opr)
+        {
+            for (p = opr->range; p; p = p->next)
+                fprintf(stderr, "[%d, %d)", p->l, p->r);
+        }
+        else copr_print(repr);
+        fprintf(stderr, "\n");
+    }
+}
+
+void register_alloc(CBlock_t entry) {
+    COList_t defs;
+    mark_insts();
+    build_intervals();
+    defs = init_def(entry);
+    print_intervals(defs);
 }
 
 CBlock_t ssa_func(CType_t func) {
diff --git a/ssa.h b/ssa.h
index 4e745d2..67ce3a4 100644
--- a/ssa.h
+++ b/ssa.h
@@ -28,9 +28,12 @@ struct COpr {
         int imm;
         char *str;
     } info;
+
     int sub;
     CInst_t def;
     CRange_t range;
+    int reg;        /* -1 for spilled */
+    COpr_t par;     /* union-find */
 };
 
 typedef struct COList COList;
@@ -60,6 +63,7 @@ struct CInst {
     COpr_t dest, src1, src2;
     CInst_t next, prev;
     int id;
+    int is_def;
 };
 
 typedef struct CPhi CPhi;