resolve interval building issues in loops

7 files changed, 370 insertions, 97 deletions

diff --git a/ast.c b/ast.c
index b2c6676..959addf 100644
--- a/ast.c
+++ b/ast.c
@@ -401,7 +401,7 @@ char *cnode_debug_type_repr(CNode *ast) {
         }
         head += sprintf(head, "(%d:%d)", ast->loc.row, ast->loc.col);
         if (ast->ext.type)
-        sprintf(head, "->(var:%lx type:%lx ic:%d cv:%d off:%d)",
+        sprintf(head, "->(var:%lx type:%lx ic:%d cv:%ld off:%d)",
                 (size_t)ast->ext.var, (size_t)ast->ext.type,
                 ast->ext.is_const, ast->ext.const_val, ast->ext.offset);
     }
diff --git a/ast.h b/ast.h
index 0979aa0..6679a6b 100644
--- a/ast.h
+++ b/ast.h
@@ -49,7 +49,7 @@ typedef struct CNode {
         CType_t type;
         CVar_t var;
         CVList_t autos;
-        int const_val;
+        long const_val;
         int is_const;
         int offset; /* offset from var */
     } ext;
diff --git a/mips.c b/mips.c
index abb86ab..fd41e67 100644
--- a/mips.c
+++ b/mips.c
@@ -7,6 +7,7 @@
 
 int reg_v0 = 2;
 int reg_v1 = 3;
+COpr_t status[32];
 
 void mips_prologue() {
     CVList_t v;
@@ -25,10 +26,10 @@ void mips_prologue() {
             switch (initr->ext.type->type)
             {
                 case CINT:
-                    printf("\t.word %d\n", initr->ext.const_val);
+                    printf("\t.word %ld\n", initr->ext.const_val);
                     break;
                 case CCHAR:
-                    printf("\t.byte %d\n", initr->ext.const_val);
+                    printf("\t.byte %ld\n", initr->ext.const_val);
                     break;
                 case CPTR:
                     {
@@ -62,7 +63,7 @@ void mips_prologue() {
 }
 
 void mips_load(int reg, COpr_t opr) {
-    CVar_t var = cinterv_repr(opr)->info.var;
+    CVar_t var = opr->spill->info.var;
     CType_t type = opr->type;
     if (type->type == CSTRUCT ||
         type->type == CUNION ||
@@ -84,7 +85,7 @@ void mips_load(int reg, COpr_t opr) {
 }
 
 void mips_store(int reg, COpr_t opr) {
-    CVar_t var = cinterv_repr(opr)->info.var;
+    CVar_t var = opr->spill->info.var;
     CType_t type = opr->type;
     const char *l = type->type == CCHAR ? "sb" : "sw";
     /* TODO: struct */
@@ -110,7 +111,7 @@ int mips_to_reg(COpr_t opr, int reg0) {
         printf("\tla $%d, _func_%s\n", reg0, opr->info.str);
         return reg0;
     }
-    if (opr->reg != -1) return cinterv_repr(opr)->reg;
+    if (opr->reg != -1) return opr->reg;
     mips_load(reg0, opr);
     return reg0;
 }
@@ -128,7 +129,8 @@ void mips_space_alloc() {
     for (d = defs; d; d = d->next)
     {
         COpr_t opr = d->opr;
-        if (opr->kind == TMP && opr->par == opr)
+        assert(opr->par == opr);
+        if (opr->kind == TMP)
         {
             int t = opr->type->type;
             tmp_size += align_shift(tmp_size);
@@ -192,7 +194,8 @@ void mips_space_alloc() {
     for (d = defs; d; d = d->next)
     {
         COpr_t opr = d->opr;
-        if (opr->kind == TMP && opr->par == opr)
+        assert(opr->par == opr);
+        if (opr->kind == TMP)
             opr->info.var->start += prev;
     }
     prev += tmp_size;
@@ -261,7 +264,7 @@ void mips_generate() {
             switch (i->op)
             {
                 case LOAD:
-                    if (i->dest->reg != -1)
+                    if (i->dest->kind == VAR && i->dest->reg > 0)
                         mips_load(i->dest->reg, i->dest);
                     break;
                 case MOVE:
@@ -269,7 +272,7 @@ void mips_generate() {
                         /* TODO: struct */
                         int rs = mips_to_reg(i->src1, reg_v0);
                         int rd = i->dest->reg;
-                        if (rd != -1)
+                        if (rd > 0)
                             printf("\tmove $%d $%d\n", rd, rs);
                         else
                             rd = rs;
@@ -378,15 +381,20 @@ void mips_generate() {
                     {
                         int rd = i->dest->reg;
                         if (i->src1->kind == IMMF)
-                            printf("\tjal _func_%s\n", i->src1->info.str);
+                            printf("\tjal %s%s\n", 
+                                    strcmp(i->src1->info.str, "main") ? "_func_" : "",
+                                    i->src1->info.str);
                         else
                             printf("\tjalr $%d\n", mips_to_reg(i->src1, reg_v0));
-                        if (rd != -1) 
-                            printf("\tmove $%d, $%d\n", rd, reg_v0);
-                        else
-                            rd = reg_v0;
-                        if (i->dest->reg == -1 || i->dest->kind == VAR)
-                            mips_store(reg_v0, i->dest);
+                        if (rd != -2)
+                        {
+                            if (rd != -1) 
+                                printf("\tmove $%d, $%d\n", rd, reg_v0);
+                            else
+                                rd = reg_v0;
+                            if (i->dest->reg == -1 || i->dest->kind == VAR)
+                                mips_store(reg_v0, i->dest);
+                        }
                     }
                     break;
                 case RET:
@@ -411,7 +419,7 @@ void mips_generate() {
                             printf("\tla $%d, %s\n", rd, i->src1->info.str);
                         else
                         {
-                            CVar_t var = i->src1->info.var;
+                            CVar_t var = i->src1->spill->info.var;
                             if (var->global)
                                 printf("\tla $%d, _%s\n", rd, var->name);
                             else
diff --git a/semantics.c b/semantics.c
index 75ee872..501d6eb 100644
--- a/semantics.c
+++ b/semantics.c
@@ -271,6 +271,7 @@ CVar_t cvar_create(char *name, CType_t type, CNode *ast) {
     cv->initr = NULL;
     cv->defsite = NULL;
     cv->global = 0;
+    cv->weight = 0;
     return cv;
 }
 
@@ -803,7 +804,7 @@ ExpType exp_check_arith(ExpType op1, ExpType op2, CNode *p, char kind) {
     res.type = basic_type_int;
     if ((p->ext.is_const = lch->ext.is_const && rch->ext.is_const))
     {
-        int l = lch->ext.const_val,
+        long l = lch->ext.const_val,
             r = rch->ext.const_val,
             *a = &(p->ext.const_val);
         switch (kind)
@@ -830,7 +831,7 @@ ExpType exp_check_bitwise(ExpType op1, ExpType op2, CNode *p, char kind) {
     res.type = basic_type_int;
     if ((p->ext.is_const = lch->ext.is_const && rch->ext.is_const))
     {
-        int l = lch->ext.const_val,
+        long l = lch->ext.const_val,
             r = rch->ext.const_val,
             *a = &(p->ext.const_val);
         switch (kind)
@@ -888,7 +889,7 @@ ExpType exp_check_add(ExpType op1, ExpType op2, CNode *p, char kind) {
     }
     if ((p->ext.is_const = lch->ext.is_const && rch->ext.is_const))
     {
-        int r = rch->ext.const_val,
+        long r = rch->ext.const_val,
             *a = &(p->ext.const_val);
         if (t1 == CARR)
         {
@@ -1001,7 +1002,7 @@ ExpType exp_check_logical(ExpType op1, ExpType op2, CNode *p, char kind) {
 
     if ((p->ext.is_const = lch->ext.is_const && rch->ext.is_const))
     {
-        int l = lch->ext.const_val,
+        long l = lch->ext.const_val,
             r = rch->ext.const_val,
             *a = &(p->ext.const_val);
         switch (kind)
@@ -1052,7 +1053,7 @@ ExpType exp_check_equality(ExpType op1, ExpType op2, CNode *p, int kind) {
     res.type = basic_type_int;
     if ((p->ext.is_const = lch->ext.is_const && rch->ext.is_const))
     {
-        int l = lch->ext.const_val,
+        long l = lch->ext.const_val,
             r = rch->ext.const_val,
             *a = &(p->ext.const_val);
         switch (kind)
diff --git a/semantics.h b/semantics.h
index 039e551..855efb1 100644
--- a/semantics.h
+++ b/semantics.h
@@ -50,6 +50,7 @@ struct CVar {
     int global;
     /* the following fields are used for renaming */
     int cnt;
+    int weight;
     COList_t stack;
 };
 
diff --git a/ssa.c b/ssa.c
index e1dfd83..adf8722 100644
--- a/ssa.c
+++ b/ssa.c
@@ -10,14 +10,15 @@
 
 static CGraph cfg, dtree;
 static CBlock_t blks[MAX_BLOCK];
+static COList_t raw_defs;
 static int bcnt;        /* block counter */
 static int tcnt;        /* temporary counter */
 
 /* for code generation */
 int gbbase;
 CBlock_t entry;
-COList_t defs;
 CType_t func;
+COList_t defs;
 
 COpr_t copr_create() {
     COpr_t opr = NEW(COpr);
@@ -141,7 +142,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); */
+    fprintf(stderr, "%d -> %d\n", from->id, to->id);
     CEdge *e = NEW(CEdge), *re = NEW(CEdge);
     e->to = to;
     e->next = cfg.head[fid];
@@ -1369,16 +1370,22 @@ int cpset_belongs(CPSet_t cps, long key) {
 }
 
 int dom[MAX_BLOCK], ord[MAX_BLOCK], vis[MAX_BLOCK], par[MAX_BLOCK], ocnt;
+int loop_tail[MAX_BLOCK];
 CPSet_t dfset[MAX_BLOCK], phi[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);
+    {
+        CBlock_t v = e->to;
+        if (vis[v->id] == -1)
+            dfs(v, u->id);
+        else if (vis[v->id] == 0)
+            loop_tail[v->id] = u->id;
+    }
     vis[u->id] = ocnt;
     ord[ocnt++] = u->id;
 }
@@ -1396,6 +1403,7 @@ void calc_dominant_frontier() {
     ocnt = 0;
     memset(vis, -1, sizeof vis);
     memset(dom, -1, sizeof dom);
+    memset(loop_tail, -1, sizeof loop_tail);
     dfs(entry, -1);
     dom[vis[entry->id]] = vis[entry->id];
     while (ch)
@@ -1531,7 +1539,7 @@ void renaming_dfs(CBlock_t blk) {
     CInst_t ih = blk->insts, i;
     CPhi_t ph = blk->phis, pi;
     CEdge *e = cfg.head[blk->id];
-    COList_t defs = NULL, dn;
+    COList_t defl = NULL, dn;
     for (pi = ph->next; pi != ph; pi = pi->next)
     {
         COpr_t dest = pi->dest;
@@ -1545,8 +1553,8 @@ void renaming_dfs(CBlock_t blk) {
         var->stack = n;
         n2 = NEW(COList);
         n2->opr = dest;
-        n2->next = defs;
-        defs = n2;
+        n2->next = defl;
+        defl = n2;
     }
     for (i = ih->next; i != ih; i = i->next)
     {
@@ -1562,7 +1570,8 @@ void renaming_dfs(CBlock_t blk) {
             p = *(opr[t]);
             if (!(p && (p->kind == VAR || p->kind == TMP))) continue;
             /* free(p); */  /* memory leak */
-            (*(opr[t]) = p->info.var->stack->opr)->type = p->type;
+            (*opr[t] = p->info.var->stack->opr)->type = p->type;
+            (*opr[t])->info.var->weight++;
         }
         if (dest)
         {
@@ -1582,8 +1591,8 @@ void renaming_dfs(CBlock_t blk) {
                     var->stack = n;
                     n2 = NEW(COList);
                     n2->opr = dest;
-                    n2->next = defs;
-                    defs = n2;
+                    n2->next = defl;
+                    defl = n2;
                 }
             }
         }
@@ -1604,14 +1613,14 @@ void renaming_dfs(CBlock_t blk) {
     }
     for (e = dtree.head[blk->id]; e; e = e->next)
         renaming_dfs(e->to);
-    for (; defs; defs = dn)
+    for (; defl; defl = dn)
     {
-        CVar_t var = defs->opr->info.var;
+        CVar_t var = defl->opr->info.var;
         COList_t nf = var->stack->next;
         free(var->stack);
         var->stack = nf;
-        dn = defs->next;
-        free(defs);
+        dn = defl->next;
+        free(defl);
     }
 }
 
@@ -1657,28 +1666,98 @@ void mark_insts() {
 CPSet_t liveset[MAX_BLOCK];
 COList_t live[MAX_BLOCK];
 
+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;)
+    {
+        if (a && (!b || (a->l < b->l || (a->l == b->l && a->r < b->r))))
+        {
+            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
+            {
+                assert(tail->r < b->l);
+                tail->next = b;
+                tail = b;
+            }
+            b = b->next;
+        }
+    }
+    tail->next = NULL;
+    return res.next;
+}
+
+void add_range_(COpr_t opr, int begin, int end) {
+    CRange_t range;
+    range = NEW(CRange);
+    range->l = begin;
+    range->r = end;
+    range->next = NULL;
+    opr->range = crange_merge(opr->range, range);
+}
+
 void add_range(COpr_t opr, CBlock_t blk, int end) {
     int dfid = opr->def->id;
     int begin;
-    CRange_t range, prev = opr->range;
     if (blk->first <= dfid && dfid <= blk->last)
         begin = dfid;
     else
         begin = blk->first;
-    if (prev && prev->l == end)
-        prev->l = begin;
-    else if (begin != end)
+    add_range_(opr, begin, end);
+}
+/*
+int low[MAX_BLOCK], dfn[MAX_BLOCK], dcnt;
+int loop_tail[MAX_BLOCK];
+*/
+
+/*
+void find_loop_tail(CBlock_t u) {
+    CEdge *e;
+    low[u->id] = bcnt;
+    dfn[u->id] = dcnt++;
+    for (e = cfg.head[u->id]; e; e = e->next)
     {
-        range = NEW(CRange);
-        range->l = begin;
-        range->r = end;
-        range->next = prev;
-        opr->range = range;
+        CBlock_t v = e->to;
+        if (dfn[v->id] == -1)
+        {
+            find_loop_tail(v);
+            if (low[v->id] < dfn[u->id] && low[v->id] < low[u->id])
+            {
+                low[u->id] = low[v->id];
+                loop_tail[u->id] = loop_tail[v->id];
+            }
+        }
+        else if (dfn[v->id] < dfn[u->id] && dfn[v->id] < low[u->id])
+        {
+            low[u->id] = dfn[v->id];
+            loop_tail[u->id] = u->id;
+        }
     }
 }
+*/
 
 void build_intervals() {
     int i;
+    /*
+    dcnt = 0;
+    memset(dfn, -1, sizeof dfn);
+    find_loop_tail(entry);
+    */
     for (i = 0; i < bcnt; i++)
         liveset[i] = cpset_create();
     for (i = 0; i < bcnt; i++)
@@ -1766,6 +1845,18 @@ void build_intervals() {
             for (i = ph->prev; i != ph; i = i->prev)
                 cpset_erase(curlive, (long)i->dest);
         }
+        if (loop_tail[id] != -1)
+        {
+            COList_t p;
+            for (p = live[id]; p; p = p->next) 
+                if (cpset_belongs(curlive, (long)p->opr))
+                {
+                    int j;
+                    for (j = loop_tail[id]; j != id; j = par[j])
+                        add_range_(p->opr, blks[j]->first, blks[j]->last + 1);
+                    add_range_(p->opr, b->first, b->last + 1);
+                }
+        }
     }
     for (i = 0; i < bcnt; i++)
     {
@@ -1784,42 +1875,6 @@ 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;)
-    {
-        if (a && (!b || a->l < b->l))
-        {
-            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
-            {
-                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);
@@ -1836,7 +1891,7 @@ void cinterv_union(COpr_t a, COpr_t b) {
 void init_def() {
     CBlock_t p;
     COList_t def;
-    defs = NULL;
+    raw_defs = NULL;
     for (p = entry; p; p = p->next)
     {
         CInst_t i, ih = p->insts;
@@ -1846,15 +1901,15 @@ void init_def() {
             {
                 def = NEW(COList);
                 def->opr = i->dest;
-                def->next = defs;
-                defs = def;
+                def->next = raw_defs;
+                raw_defs = def;
             }
         for (pi = ph->next; pi != ph; pi = pi->next)
         {
             def = NEW(COList);
             def->opr = pi->dest;
-            def->next = defs;
-            defs = def;
+            def->next = raw_defs;
+            raw_defs = def;
         }
     }
     for (p = entry; p; p = p->next)
@@ -1871,7 +1926,7 @@ void init_def() {
 
 void print_intervals() {
     COList_t d;
-    for (d = defs; d; d = d->next)
+    for (d = raw_defs; d; d = d->next)
     {
         COpr_t opr = d->opr,
                repr = cinterv_repr(opr);
@@ -1888,17 +1943,218 @@ void print_intervals() {
     }
 }
 
+#define MAX_AVAIL_REGS 10
+const int avail_regs[MAX_AVAIL_REGS] = {8, 9, 10, 11, 12, 13, 14, 15, 24, 25};
+
+void colist_remove(COList_t node) {
+    node->prev->next = node->next;
+    node->next->prev = node->prev;
+}
+
+void colist_add(COList_t head, COList_t p) {
+    (p->next = head->next)->prev = p;
+    (p->prev = head)->next = p;
+}
+
+int overlap_with_beg(COpr_t i, int beg) {
+    CRange_t r;
+    for (r = i->range; r->l <= beg; r = r->next)
+        if (r->r > beg) return 1;
+    return 0;
+}
+
+int overlap_with_interv(COpr_t i, COpr_t cur) {
+    CRange_t pi, pc;
+    for (pi = i->range, pc = cur->range; pi && pc;)
+    {
+        if (pi->r <= pc->l) pi = pi->next;
+        else if (pc->r <= pi->l) pc = pc->next;
+        else return 1;
+    }
+    return 0;
+}
+
+int copr_comp(const void *a, const void *b) {
+    return (*(COpr_t *)a)->range->l - (*(COpr_t *)b)->range->l;
+}
+
 void register_alloc() {
-    mark_insts();
-    build_intervals();
-    init_def();
-    /* FIXME: all vars are spilled */
+    static int freg[32], f[32];
+    int dn = 0, i;
+    COList_t p;
+    COpr_t *unhandled;
+    COList_t active = NEW(COList),
+             inactive = NEW(COList);
+    active->next = active->prev = active;
+    inactive->next = inactive->prev = inactive;
+    memset(freg, -1, sizeof freg);
+    for (i = 0; i < MAX_AVAIL_REGS; i++)
+        freg[avail_regs[i]] = 1; /* available */
+    for (p = raw_defs; p; p = p->next)
+    {
+        COpr_t opr = p->opr;
+        opr->reg = -2;
+        if (opr->par != opr) continue;
+        if (cinterv_repr(opr)->range)
+        {
+            opr->reg = -1;
+            dn++;
+        }
+    }
+    unhandled = (COpr_t *)malloc(dn * sizeof(COpr_t));
+    i = 0;
+    for (p = raw_defs; p; p = p->next)
+        if (p->opr->reg == -1)
+            unhandled[i++] = p->opr;
+    for (i = 0; i < dn; i++)
     {
-        COList_t p;
-        for (p = defs; p; p = p->next)
-            p->opr->reg = -1;
+        COpr_t opr = unhandled[i];
+        CRange_t r;
+        /*
+        if (opr->kind == VAR && opr->range->next)
+        {
+            free(opr->range);
+            opr->range = opr->range->next;
+        }*/   /* discard uncessary load */
+        for (r = opr->range; r->next; r = r->next);
+        opr->begin = opr->range->l;
+        opr->end = r->r;
+        copr_print(stderr, opr);
+        fprintf(stderr, " (key: %d begin: %d, end: %d, weight: %d)\n",
+                opr->range->l, opr->begin, opr->end, opr->info.var->weight);
     }
+    qsort(unhandled, dn, sizeof(COpr_t), copr_comp);
     print_intervals();
+    /* preparation done */
+    for (i = 0; i < dn; i++)
+    {
+        COList_t c = NEW(COList);
+        COpr_t cur;
+        COList_t np;
+        int reg, t;
+        cur = c->opr = unhandled[i];
+        /* for each interval in active */
+        for (p = active->next; p != active; p = np)
+        {
+            COpr_t i = p->opr;
+            np = p->next;
+            if (i->end <= cur->begin) /* if i ends before cur.beg */
+            {
+                colist_remove(p);
+                free(p);            /* move i to handled */
+                freg[i->reg] = 1;   /* add i.reg to free */
+            }
+            else if (!overlap_with_beg(i, cur->begin))
+            {
+                colist_remove(p); 
+                colist_add(inactive, p); /* move i to inactive */
+                freg[i->reg] = 1;        /* add i.reg to free */
+            }
+        }
+        /* for each interval i in inactive */
+        for (p = inactive->next; p != inactive; p = np)
+        {
+            COpr_t i = p->opr;
+            np = p->next;
+            if (i->end <= cur->begin)   /* if i ends before cur.beg */
+            {
+                colist_remove(p);
+                free(p);                /* move i to handled */
+            }
+            else if (overlap_with_beg(i, cur->begin))
+            {
+                colist_remove(p);
+                colist_add(active, p);  /* move i to active */
+                freg[i->reg] = 0;       /* remove i.reg from free */
+            }
+        }
+        memmove(f, freg, sizeof f);
+        /* for each interval i in inactive that overlaps cur do
+         * f <- f - {i.reg} */
+        for (p = inactive->next; p != inactive; p = p->next)
+            if (overlap_with_interv(p->opr, cur))
+                f[p->opr->reg] = 0;
+        reg = -1;
+        for (t = 0; t < 32; t++)
+            if (f[t] > 0) { reg = t; break; }
+        if (reg == -1) /* if f = {} */
+        { /* assign mem loc */
+            static int w[32];
+            int min = 0x7fffffff;
+            memset(w, 0, sizeof w);
+            for (p = active->next; p != active; p = p->next)
+                if (overlap_with_interv(p->opr, cur))
+                    w[p->opr->reg] += p->opr->info.var->weight;
+            for (p = inactive->next; p != inactive; p = p->next)
+                if (overlap_with_interv(p->opr, cur))
+                    w[p->opr->reg] += p->opr->info.var->weight;
+            for (t = 0; t < 32; t++)
+                if (f[t] != -1 && w[t] < min) min = t, reg = t;
+            if (cur->info.var->weight < w[reg])
+            {
+                cur->reg = -1;      /* assign a memory location to cur */
+                free(c);            /* and move cur to handled */
+            }
+            else
+            {
+                /* move all active or inactive intervals to which r was assigned to handled
+                 * assign memory locations to them */
+                for (p = active->next; p != active; p = np)
+                {
+                    np = p->next;
+                    if (p->opr->reg == reg)
+                    {
+                        p->opr->reg = -1;
+                        colist_remove(p);
+                        free(p);
+                    }
+                }
+                for (p = inactive->next; p != inactive; p = np)
+                {
+                    np = p->next;
+                    if (p->opr->reg == reg)
+                    {
+                        p->opr->reg = -1;
+                        colist_remove(p);
+                        free(p);
+                    }
+                }
+                cur->reg = reg;
+                colist_add(active, c); /* move cur to active */
+            }
+        }
+        else
+        {
+            cur->reg = reg; /* cur.reg <- any register in f */
+            freg[reg] = 0;  /* free <- free - {cur.reg} */
+            colist_add(active, c); /* move cur to active */
+        }
+    }
+    for (i = 0; i < dn; i++)
+    {
+        COpr_t opr = unhandled[i];
+        copr_print(stderr, opr);
+        fprintf(stderr, " (begin: %d, end: %d, weight: %d, reg: %d)\n",
+                opr->begin, opr->end, opr->info.var->weight, opr->reg);
+    }
+    for (p = raw_defs; p; p = p->next)
+    {
+        COpr_t opr = p->opr;
+        if (cinterv_repr(opr)->range)
+        {
+            opr->spill = cinterv_repr(opr);
+            opr->reg = opr->spill->reg;
+        }
+    }
+    defs = NULL;
+    for (i = 0; i < dn; i++)
+    {
+        COList_t p = NEW(COList);
+        p->opr = unhandled[i];
+        p->next = defs;
+        defs = p;
+    }
+    free(unhandled);
 }
 
 void const_propagation() {
@@ -2066,5 +2322,8 @@ void ssa_func(CType_t func) {
     insert_phi(vars);
     renaming_vars(all_oprs);
     const_propagation();
+    mark_insts();
+    build_intervals();
+    init_def();
     register_alloc();
 }
diff --git a/ssa.h b/ssa.h
index 722545d..3699b9d 100644
--- a/ssa.h
+++ b/ssa.h
@@ -34,20 +34,24 @@ struct COpr {
     int dep;
     int mod;
     int reg;        /* -1 for spilled, -2 for discarded */
+    int begin, end; /* for reg allocation */
     CType_t type;
     CInst_t def;
     CRange_t range;
     COpr_t par;     /* union-find */
     COpr_t cval;
+    COpr_t spill;   /* check this reference if spilled */
 };
 
 typedef struct COList COList;
 typedef COList *COList_t;
 struct COList {
     COpr_t opr;
-    COList_t next;
+    COList_t next, prev;
 };
 
+void colist_remove(COList_t node);
+
 struct CInst {
     enum {
         BEQZ,   /* conditional jump */