reg alloc almost done, can pass most of data

5 files changed, 177 insertions, 147 deletions

diff --git a/lib.s b/lib.s
index 6e219b0..8a42898 100644
--- a/lib.s
+++ b/lib.s
@@ -1,143 +1,113 @@
 _func_printf:
-	addiu $sp, $sp, -88
-	sw $31, 84($sp) #printf
+	addiu $sp, $sp, -64
+	sw $31, 60($sp) #printf
 # load fmt_0
+	lw $8, 64($sp)	#fmt
 # load arg_0
-# load len_0
 # load ch_0
+	lb $9, 12($sp)	#ch
 # load x_0
+	lw $10, 4($sp)	#x
+# load len_0
+	lw $11, 8($sp)	#len
 # t0 = addr fmt_0
-	addiu $2, $sp, 88
-	sw $2, 80($sp)	#t0
+	addiu $12, $sp, 64
 # arg_1 = t0 + 4
-	lw $2, 80($sp)	#t0
-	addiu $2, $2, 4
-	sw $2, 16($sp)	#arg
+	addiu $12, $12, 4
+	sw $12, 16($sp)	#arg
 # goto __L2
 	j __L2
 __L1:
 # t3 = ch_2 == 37
-	lb $2, 12($sp)	#ch
 	li $3, 37
-	seq $2, $2, $3
-	sw $2, 76($sp)	#t3
+	seq $13, $9, $3
 # if not (t3) goto __L20
-	lw $2, 76($sp)	#t3
-	beqz $2, __L20
+	beqz $13, __L20
 # fmt_4 = fmt_1 + 1
-	lw $2, 88($sp)	#fmt
-	addiu $2, $2, 1
-	sw $2, 88($sp)	#fmt
+	addiu $8, $8, 1
+	sw $8, 64($sp)	#fmt
 # ch_4 = fmt_4[0]
-	lw $2, 88($sp)	#fmt
-	lb $3, 0($2)
-	sb $3, 12($sp)	#ch
+	lb $9, 0($8)
+	sb $9, 12($sp)	#ch
 # t5 = ch_4 == 100
-	lb $2, 12($sp)	#ch
 	li $3, 100
-	seq $2, $2, $3
-	sw $2, 72($sp)	#t5
+	seq $13, $9, $3
 # if not (t5) goto __L6
-	lw $2, 72($sp)	#t5
-	beqz $2, __L6
+	beqz $13, __L6
 # t7 = arg_2[0]
-	lw $2, 16($sp)	#arg
-	lw $3, 0($2)
-	sw $3, 68($sp)	#t7
+	lw $13, 0($12)
 # push t7
-	lw $2, 68($sp)	#t7
-	sw $2, 0($sp) # push
+	sw $13, 0($sp) # push
 # t6 = call __print_int
 	jal _func___print_int
-	sw $2, 64($sp)	#t6
 # goto __L19
 	j __L19
 __L6:
 # t8 = ch_4 == 99
-	lb $2, 12($sp)	#ch
 	li $3, 99
-	seq $2, $2, $3
-	sw $2, 60($sp)	#t8
+	seq $13, $9, $3
 # if not (t8) goto __L8
-	lw $2, 60($sp)	#t8
-	beqz $2, __L8
+	beqz $13, __L8
 # t10 = arg_2[0]
-	lw $2, 16($sp)	#arg
-	lw $3, 0($2)
-	sb $3, 56($sp)	#t10
+	lw $13, 0($12)
 # push t10
-	lb $2, 56($sp)	#t10
-	sw $2, 0($sp) # push
+	sw $13, 0($sp) # push
 # t9 = call __print_char
 	jal _func___print_char
-	sw $2, 52($sp)	#t9
 # goto __L19
 	j __L19
 __L8:
 # t11 = ch_4 == 115
-	lb $2, 12($sp)	#ch
 	li $3, 115
-	seq $2, $2, $3
-	sw $2, 48($sp)	#t11
+	seq $13, $9, $3
 # if not (t11) goto __L10
-	lw $2, 48($sp)	#t11
-	beqz $2, __L10
+	beqz $13, __L10
 # t13 = arg_2[0]
-	lw $2, 16($sp)	#arg
-	lw $3, 0($2)
-	sw $3, 44($sp)	#t13
+	lw $13, 0($12)
 # push t13
-	lw $2, 44($sp)	#t13
-	sw $2, 0($sp) # push
+	sw $13, 0($sp) # push
 # t12 = call __print_string
 	jal _func___print_string
-	sw $2, 40($sp)	#t12
 # goto __L19
 	j __L19
 __L10:
 # x_4 = arg_2[0]
-	lw $2, 16($sp)	#arg
-	lw $3, 0($2)
-	sw $3, 4($sp)	#x
+	lw $10, 0($12)
+	sw $10, 4($sp)	#x
 # t15 = x_4 == 0
-	lw $2, 4($sp)	#x
 	li $3, 0
-	seq $2, $2, $3
-	sw $2, 36($sp)	#t15
+	seq $11, $10, $3
 # if not (t15) goto __L12
-	lw $2, 36($sp)	#t15
-	beqz $2, __L12
+	beqz $11, __L12
 # len_11 = 1
 	li $2, 1
-	sw $2, 8($sp)	#len
+	move $11 $2
+	sw $11, 8($sp)	#len
 # goto __L15
 	j __L15
 __L12:
 # len_8 = 0
 	li $2, 0
-	sw $2, 8($sp)	#len
+	move $11 $2
+	sw $11, 8($sp)	#len
 # goto __L14
 	j __L14
 __L13:
 # x_7 = x_6 / 10
-	lw $2, 4($sp)	#x
 	li $3, 10
-	divu $2, $2, $3
-	sw $2, 4($sp)	#x
+	divu $10, $10, $3
+	sw $10, 4($sp)	#x
 # len_10 = len_9 + 1
-	lw $2, 8($sp)	#len
-	addiu $2, $2, 1
-	sw $2, 8($sp)	#len
+	addiu $11, $11, 1
+	sw $11, 8($sp)	#len
 __L14:
 # if (x_6) goto __L13
-	lw $2, 4($sp)	#x
-	bnez $2, __L13
+	bnez $10, __L13
 __L15:
 # len_5 = 4 - len_4
 	li $2, 4
-	lw $3, 8($sp)	#len
-	subu $2, $2, $3
-	sw $2, 8($sp)	#len
+	subu $11, $2, $11
+	sw $11, 8($sp)	#len
 # goto __L17
 	j __L17
 __L16:
@@ -146,60 +116,46 @@ __L16:
 	sw $2, 0($sp) # push
 # t17 = call __print_char
 	jal _func___print_char
-	sw $2, 32($sp)	#t17
 # len_7 = len_6 - 1
-	lw $2, 8($sp)	#len
 	li $3, 1
-	subu $2, $2, $3
-	sw $2, 8($sp)	#len
+	subu $11, $11, $3
+	sw $11, 8($sp)	#len
 __L17:
 # if (len_6) goto __L16
-	lw $2, 8($sp)	#len
-	bnez $2, __L16
+	bnez $11, __L16
 # t19 = arg_2[0]
-	lw $2, 16($sp)	#arg
-	lw $3, 0($2)
-	sw $3, 28($sp)	#t19
+	lw $13, 0($12)
 # push t19
-	lw $2, 28($sp)	#t19
-	sw $2, 0($sp) # push
+	sw $13, 0($sp) # push
 # t18 = call __print_int
 	jal _func___print_int
-	sw $2, 24($sp)	#t18
 # fmt_6 = fmt_4 + 2
-	lw $2, 88($sp)	#fmt
-	addiu $2, $2, 2
-	sw $2, 88($sp)	#fmt
+	addiu $8, $8, 2
+	sw $8, 64($sp)	#fmt
 __L19:
 # arg_4 = arg_2 + 4
-	lw $2, 16($sp)	#arg
-	addiu $2, $2, 4
-	sw $2, 16($sp)	#arg
+	addiu $12, $12, 4
+	sw $12, 16($sp)	#arg
 # goto __L21
 	j __L21
 __L20:
 # push ch_2
-	lb $2, 12($sp)	#ch
-	sw $2, 0($sp) # push
+	sw $9, 0($sp) # push
 # t20 = call __print_char
 	jal _func___print_char
-	sw $2, 20($sp)	#t20
 __L21:
 # fmt_3 = fmt_2 + 1
-	lw $2, 88($sp)	#fmt
-	addiu $2, $2, 1
-	sw $2, 88($sp)	#fmt
+	addiu $8, $8, 1
+	sw $8, 64($sp)	#fmt
 __L2:
 # ch_2 = fmt_1[0]
-	lw $2, 88($sp)	#fmt
-	lb $3, 0($2)
-	sb $3, 12($sp)	#ch
+	lb $9, 0($8)
+	sb $9, 12($sp)	#ch
 # if (ch_2) goto __L1
-	lb $2, 12($sp)	#ch
-	bnez $2, __L1
+	bnez $9, __L1
 _ret_printf:
-	lw $31, 84($sp)
-	addiu $sp, $sp, 88
+	lw $31, 60($sp)
+	addiu $sp, $sp, 64
 	jr $31
 _func___print_int:
     lw $a0, 0($sp)
diff --git a/mips.c b/mips.c
index fd41e67..4e1c26e 100644
--- a/mips.c
+++ b/mips.c
@@ -7,7 +7,8 @@
 
 int reg_v0 = 2;
 int reg_v1 = 3;
-COpr_t status[32];
+static int save_pos[32];
+static int used_reg[32]; 
 
 void mips_prologue() {
     CVList_t v;
@@ -111,7 +112,11 @@ 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 opr->reg;
+    if (opr->reg != -1) 
+    {
+        used_reg[opr->reg] = 1;
+        return opr->reg;
+    }
     mips_load(reg0, opr);
     return reg0;
 }
@@ -123,6 +128,7 @@ void mips_space_alloc() {
     int tmp_size = 0;
     int offset = 0;
     int prev = 0;
+    int save_size = MAX_AVAIL_REGS * INT_SIZE;
     CBlock_t p;
     COList_t d;
     CVar_t v;
@@ -130,7 +136,7 @@ void mips_space_alloc() {
     {
         COpr_t opr = d->opr;
         assert(opr->par == opr);
-        if (opr->kind == TMP)
+        if (opr->kind == TMP && opr->reg == -1)
         {
             int t = opr->type->type;
             tmp_size += align_shift(tmp_size);
@@ -190,12 +196,18 @@ void mips_space_alloc() {
         v->start += prev;
     prev += local_size;
     prev += align_shift(prev);
+    {
+        int i;
+        for (i = 0; i < MAX_AVAIL_REGS; i++)
+            save_pos[avail_regs[i]] = prev + i * INT_SIZE;
+    }
+    prev += save_size;
     /* adjust offset for spilled temporaries */
     for (d = defs; d; d = d->next)
     {
         COpr_t opr = d->opr;
         assert(opr->par == opr);
-        if (opr->kind == TMP)
+        if (opr->kind == TMP && opr->reg == -1)
             opr->info.var->start += prev;
     }
     prev += tmp_size;
@@ -245,6 +257,10 @@ void mips_func_end() {
 
 void mips_generate() {
     CBlock_t p;
+    int i;
+    memset(used_reg, 0, sizeof used_reg);
+    for (i = 0; i < MAX_AVAIL_REGS; i++)
+        used_reg[avail_regs[i]] = 1;
     mips_space_alloc();
     if (strcmp(func->name, "main"))
         printf("_func_%s:\n",func->name);
@@ -259,6 +275,8 @@ void mips_generate() {
         for (i = ih->next; i != ih; i = i->next)
         {
             int flag = 1, swap;
+            if (i->dest && i->dest->reg == -2 && i->dest->kind == TMP && i->op != CALL)
+                continue;
             printf("# ");
             cinst_print(stdout, i);
             switch (i->op)
@@ -273,7 +291,11 @@ void mips_generate() {
                         int rs = mips_to_reg(i->src1, reg_v0);
                         int rd = i->dest->reg;
                         if (rd > 0)
+                        {
+                            used_reg[rd] = 1;
+                            assert(rd);
                             printf("\tmove $%d $%d\n", rd, rs);
+                        }
                         else
                             rd = rs;
                         if (i->dest->reg == -1 || i->dest->kind == VAR)
@@ -311,35 +333,25 @@ void mips_generate() {
                             int index = i->src2->info.imm;
                             rd = i->dest->reg;
                             if (rd == -1) rd = reg_v1;
-                            /*
-                            if (type->type == CSTRUCT || type->type == CUNION)
+                            else 
                             {
-                                if (IN_IMM(index))
-                                    printf("\taddiu $%d, $%d, %d\n", rd, arr, index);
-                                else
-                                {
-                                    printf("\tli $%d, %d\n", reg_v1, index);
-                                    printf("\taddu $%d, $%d, $%d\n", rd, arr, reg_v1);
-                                }
+                                used_reg[rd] = 1;
+                                assert(rd);
                             }
-                            else
-                            */
-                                printf("\t%s $%d, %d($%d)\n", l, rd, index, arr);
+                            printf("\t%s $%d, %d($%d)\n", l, rd, index, arr);
                         }
                         else
                         {
                             int index = mips_to_reg(i->src2, reg_v1);
                             rd = i->dest->reg;
-                            if (rd == -1) rd = reg_v0;
-                            /*
-                            if (type->type == CSTRUCT || type->type == CUNION)
-                                printf("\taddu $%d, $%d, $%d\n", rd, arr, index);
-                            else
-                            */
+                            if (rd < 0) rd = reg_v0;
+                            else 
                             {
-                                printf("\taddu $%d, $%d, $%d\n", index, arr, index);
-                                printf("\t%s $%d, 0($%d)\n", l, rd, index);
+                                used_reg[rd] = 1;
+                                assert(rd);
                             }
+                            printf("\taddu $%d, $%d, $%d\n", reg_v1, arr, index);
+                            printf("\t%s $%d, 0($%d)\n", l, rd, reg_v1);
                         }
                         if (i->dest->reg == -1 || i->dest->kind == VAR)
                             mips_store(rd, i->dest);
@@ -364,9 +376,9 @@ void mips_generate() {
                         else
                         {
                             int index = mips_to_reg(i->src2, reg_v1);
-                            printf("\taddu $%d, $%d, $%d\n", index, arr, index);
+                            printf("\taddu $%d, $%d, $%d\n", reg_v1, arr, index);
                             rs = mips_to_reg(i->src1, reg_v0);
-                            printf("\t%s $%d, 0($%d)\n", s, rs, index);
+                            printf("\t%s $%d, 0($%d)\n", s, rs, reg_v1);
                         }
                     }
                     break;
@@ -379,17 +391,47 @@ void mips_generate() {
                     break;
                 case CALL:
                     {
+                        COList_t p;
                         int rd = i->dest->reg;
+                        int j;
+                        memset(used_reg, 0, sizeof used_reg);
+                        for (p = defs; p; p = p->next)
+                        {
+                            COpr_t opr = p->opr;
+                            if (opr->reg != -1 && 
+                                (opr->kind == TMP || !opr->info.var->global) &&
+                                overlap_with_beg(opr, i->id))
+                                used_reg[opr->reg] = 1;
+                        }
+                        for (j = 0; j < 32; j++)
+                            if (used_reg[j])
+                                printf("\tsw $%d, %d($sp) # save reg\n", j, save_pos[j]);
                         if (i->src1->kind == IMMF)
                             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));
+                        for (j = 0; j < 32; j++)
+                            if (used_reg[j])
+                                printf("\tlw $%d, %d($sp) # load reg\n", j, save_pos[j]);
+                        for (p = defs; p; p = p->next)
+                        {
+                            COpr_t opr = p->opr;
+                            if (opr->reg != -1 &&
+                                opr->kind == VAR &&
+                                opr->info.var->global &&
+                                overlap_with_beg(opr, i->id))
+                                mips_load(opr->reg, opr);
+                        }
                         if (rd != -2)
                         {
                             if (rd != -1) 
+                            {
+                                used_reg[rd] = 1;
+                            assert(rd);
                                 printf("\tmove $%d, $%d\n", rd, reg_v0);
+                            }
                             else
                                 rd = reg_v0;
                             if (i->dest->reg == -1 || i->dest->kind == VAR)
@@ -402,7 +444,15 @@ void mips_generate() {
                         if (i->src1)
                         {
                             if (i->src1->reg != -1)
-                                printf("\tmove $%d, $%d\n", reg_v0, mips_to_reg(i->src1, reg_v1));
+                            {
+                                if (i->src1->kind == IMM)
+                                    printf("\tli$%d, %d\n", reg_v0, i->src1->info.imm);
+                                else
+                                {
+                                    used_reg[i->src1->reg] = 1;
+                                    printf("\tmove $%d, $%d\n", reg_v0, mips_to_reg(i->src1, reg_v1));
+                                }
+                            }
                             else
                                 mips_to_reg(i->src1, reg_v0);
                         }
@@ -414,7 +464,12 @@ void mips_generate() {
                         assert(i->src1->kind == VAR ||
                                 i->src1->kind == IMMF);
                         int rd = i->dest->reg;
-                        if (rd == -1) rd = reg_v0;
+                        if (rd < 0) rd = reg_v0;
+                        else 
+                        {
+                            assert(rd);
+                            used_reg[rd] = 1;
+                        }
                         if (i->src1->kind == IMMF)
                             printf("\tla $%d, %s\n", rd, i->src1->info.str);
                         else
@@ -459,7 +514,12 @@ void mips_generate() {
             {
                 int rs, rt;
                 int rd = i->dest->reg;
-                if (rd == -1) rd = reg_v0;
+                if (rd < 0) rd = reg_v0;
+                else 
+                {
+                    used_reg[rd] = 1;
+                    assert(rd);
+                }
                 if (swap)
                 {
                     COpr_t t;
@@ -499,7 +559,12 @@ void mips_generate() {
             {
                 int rs = mips_to_reg(i->src1, reg_v0);
                 int rd = i->dest->reg;
-                if (rd == -1) rd = reg_v0;
+                if (rd < 0) rd = reg_v0;
+                else 
+                {
+                    used_reg[rd] = 1;
+                    assert(rd);
+                }
                 printf("\tnegu $%d, $%d\n", rd, rs);
                 if (i->dest->reg == -1 || i->dest->kind == VAR)
                     mips_store(rd, i->dest);
diff --git a/printf.c b/printf.c
index 7c9cf3a..488c0d5 100644
--- a/printf.c
+++ b/printf.c
@@ -29,4 +29,3 @@ int printf(char *fmt) {
         fmt++;
     }
 }
-
diff --git a/ssa.c b/ssa.c
index adf8722..d69c959 100644
--- a/ssa.c
+++ b/ssa.c
@@ -1377,13 +1377,13 @@ CBList_t df[MAX_BLOCK];
 void dfs(CBlock_t u, int v) {
     CEdge *e;
     par[u->id] = v;
-    vis[u->id] = 0;
+    vis[u->id] = -2;
     for (e = cfg.head[u->id]; e; e = e->next)
     {
         CBlock_t v = e->to;
         if (vis[v->id] == -1)
             dfs(v, u->id);
-        else if (vis[v->id] == 0)
+        else if (vis[v->id] == -2)
             loop_tail[v->id] = u->id;
     }
     vis[u->id] = ocnt;
@@ -1676,7 +1676,10 @@ CRange_t crange_merge(CRange_t a, CRange_t 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;
+            {
+                if (a->r > tail->r)
+                    tail->r = a->r;
+            }
             else
             {
                 assert(tail->r < a->l);
@@ -1688,7 +1691,10 @@ CRange_t crange_merge(CRange_t a, CRange_t b) {
         else
         {
             if (tail->r >= b->l)
-                tail->r = b->r;
+            {
+                if (b->r > tail->r)
+                    tail->r = b->r;
+            }
             else
             {
                 assert(tail->r < b->l);
@@ -1851,10 +1857,13 @@ void build_intervals() {
             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);
+                    */
+                    add_range_(p->opr, b->first, blks[loop_tail[id]]->last + 1);
                 }
         }
     }
@@ -1943,9 +1952,6 @@ 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;
@@ -1958,7 +1964,7 @@ void colist_add(COList_t head, COList_t p) {
 
 int overlap_with_beg(COpr_t i, int beg) {
     CRange_t r;
-    for (r = i->range; r->l <= beg; r = r->next)
+    for (r = i->range; r && r->l <= beg; r = r->next)
         if (r->r > beg) return 1;
     return 0;
 }
@@ -1978,6 +1984,9 @@ int copr_comp(const void *a, const void *b) {
     return (*(COpr_t *)a)->range->l - (*(COpr_t *)b)->range->l;
 }
 
+const int avail_regs[] = {8, 9, 10, 11, 12, 13, 14, 15, 24, 25};
+const int MAX_AVAIL_REGS = sizeof(avail_regs) / sizeof(avail_regs[0]);
+
 void register_alloc() {
     static int freg[32], f[32];
     int dn = 0, i;
@@ -2090,7 +2099,7 @@ void register_alloc() {
                     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])
+            if (reg == -1 || cur->info.var->weight < w[reg])
             {
                 cur->reg = -1;      /* assign a memory location to cur */
                 free(c);            /* and move cur to handled */
@@ -2140,11 +2149,9 @@ void register_alloc() {
     for (p = raw_defs; p; p = p->next)
     {
         COpr_t opr = p->opr;
+        opr->spill = cinterv_repr(opr);
         if (cinterv_repr(opr)->range)
-        {
-            opr->spill = cinterv_repr(opr);
             opr->reg = opr->spill->reg;
-        }
     }
     defs = NULL;
     for (i = 0; i < dn; i++)
diff --git a/ssa.h b/ssa.h
index 3699b9d..77010a4 100644
--- a/ssa.h
+++ b/ssa.h
@@ -143,8 +143,11 @@ typedef struct CInterv {
 void ssa_generate(void);
 COpr_t cinterv_repr(COpr_t opr);
 void cinst_print(FILE *stream, CInst_t inst);
+int overlap_with_beg(COpr_t i, int beg);
 extern int gbbase;
 extern CBlock_t entry;
 extern COList_t defs;
 extern CType_t func;
+extern const int avail_regs[];
+extern const int MAX_AVAIL_REGS;
 #endif