From 8ef3cac508d203cec57d911cbe61019364a11807 Mon Sep 17 00:00:00 2001 From: Teddy Date: Sun, 4 May 2014 08:07:13 +0800 Subject: reg alloc almost done, can pass most of data --- lib.s | 164 +++++++++++++++++++++++---------------------------------------- mips.c | 125 ++++++++++++++++++++++++++++++++++++------------ printf.c | 1 - ssa.c | 31 +++++++----- ssa.h | 3 ++ 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 -- cgit v1.2.3