diff options
| -rw-r--r-- | lisc/Makefile | 2 | ||||
| -rw-r--r-- | lisc/lisc.h | 4 | ||||
| -rw-r--r-- | lisc/rega.c | 211 |
3 files changed, 216 insertions, 1 deletions
diff --git a/lisc/Makefile b/lisc/Makefile index bab0059..b208eea 100644 --- a/lisc/Makefile +++ b/lisc/Makefile @@ -1,5 +1,5 @@ BIN = lisc -OBJ = main.o parse.o ssa.o live.o isel.o spill.o +OBJ = main.o parse.o ssa.o live.o isel.o spill.o rega.o CFLAGS = -Wall -Wextra -std=c11 -g -pedantic diff --git a/lisc/lisc.h b/lisc/lisc.h index ac5714a..95660cf 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -153,6 +153,7 @@ struct Sym { uint ndef, nuse; uint cost; uint spill; + int hint; }; struct Fn { @@ -191,3 +192,6 @@ void isel(Fn *); int bcnt(Bits *); void fillcost(Fn *); void spill(Fn *); + +/* rega.c */ +void rega(Fn *); diff --git a/lisc/rega.c b/lisc/rega.c new file mode 100644 index 0000000..deafe40 --- /dev/null +++ b/lisc/rega.c @@ -0,0 +1,211 @@ +#include "lisc.h" + + +typedef struct RMap RMap; +struct RMap { + int t[NReg]; + int r[NReg]; + Bits bt; + Bits br; + int n; +}; + +extern Ins insb[NIns], *curi; +static Sym *sym; /* symbol table in use */ +static Blk *elist; /* edge list created by edge() */ +static int ne; /* length of elist */ + +static int +rfind(RMap *m, int t) +{ + int i; + + for (i=0; i<m->n; i++) + if (m->t[i] == t) + return m->r[i]; + return -1; +} + +static void +radd(RMap *m, int t, int r) +{ + assert(m->n <= NReg); + assert(sym[t].type == STmp && "invalid allocation"); + assert(!BGET(m->bt, t) && "temp has mapping"); + assert(!BGET(m->br, r) && "reg already allocated"); + BSET(m->bt, t); + BSET(m->br, r); + m->t[m->n] = t; + m->r[m->n] = r; + m->n++; +} + +static void +ralloc(RMap *m, int t) +{ + int r; + + assert(m->n <= NReg || "oops, too few regs"); + r = sym[t].hint; + if (r == -1 || BGET(m->br, r)) + for (r=RAX; r<NReg; r++) + if (!BGET(m->br, r)) + break; + radd(m, t, r); +} + +static int +rfree(RMap *m, int t) +{ + int i, r; + + if (!BGET(m->bt, t)) + return 0; + for (i=0; m->t[i] != t; i++) + assert(i+1 < NReg); + r = m->r[i]; + BCLR(m->bt, t); + BCLR(m->br, r); + m->n--; + memmove(&m->t[i], &m->t[i+1], (m->n-i) * sizeof(int)); + memmove(&m->r[i], &m->r[i+1], (m->n-i) * sizeof(int)); + return r; +} + +static int +isreg(Ref r) +{ + return rtype(r) == RSym && sym[r.val].type == SReg; +} + +static Ins * +pmgen(Blk *b, Ins *i) +{ + diag("not implemented"); + return 0; +} + +/* register allocation + * depends on rpo, cost, (and obviously spill) + */ +void +rega(Fn *fn) +{ + int n, t, u, r; + Blk *b, *b1; + Ins *i; + RMap *end, *beg, cur; + + sym = fn->sym; + /* 1. gross hinting setup */ + for (b=fn->start; b; b=b->link) { + for (i=b->ins; i-b->ins < b->nins; i++) { + if (i->op == OCopy + && rtype(i->arg[0]) == RSym + && !req(i->to, R)) { + t = i->arg[0].val; + u = i->to.val; + if (sym[t].type == SReg) + sym[u].hint = t; + if (sym[u].type == SReg) + sym[t].hint = u; + } + } + } + + /* 2. assign registers backwards */ + end = alloc(fn->ntmp * sizeof end[0]); + beg = alloc(fn->ntmp * sizeof beg[0]); + for (n=fn->nblk-1; n>=0; n--) { + b = fn->rpo[n]; + b1 = b->s1; + cur.n = 0; + cur.bt = (Bits){{0}}; + cur.br = (Bits){{0}}; + if (!b1 || b->s2->loop > b1->loop) + b1 = b->s2; + /* try to reuse the register + * assignment of the most frequent + * successor + */ + for (t=Tmp0; t<fn->ntmp; t++) + if (BGET(b->out, t)) + if ((r = rfind(&beg[b1->id], t)) != -1) + radd(&cur, t, r); + for (t=Tmp0; t<fn->ntmp; t++) + if (!BGET(cur.bt, t)) + ralloc(&cur, t); + /* process instructions */ + if (rtype(b->jmp.arg) == RSym) + ralloc(&cur, b->jmp.arg.val); + for (i=&b->ins[b->nins]; i!=b->ins;) { + i--; + if (i->op == OCopy /* par. moves are special */ + && (isreg(i->arg[0]) || isreg(i->to))) { + i = pmgen(b, i); + continue; + } + if (!req(i->to, R)) + r = rfree(&cur, i->to.val); + if (rtype(i->arg[0]) == RSym) { + /* <arch> + * on Intel, we attempt to + * use the same register + * for the return and the + * first argument + */ + t = i->arg[0].val; + if (sym[t].hint == -1) + sym[t].hint = r; + ralloc(&cur, t); + } + if (rtype(i->arg[1]) == RSym) { + /* <arch> + * on Intel, we have to + * make sure we avoid the + * situation + * eax = sub ebx, eax + */ + if (!opdesc[i->op].commut && r!=-1) + BSET(cur.br, r); + t = i->arg[1].val; + ralloc(&cur, t); + if (!opdesc[i->op].commut && r!=-1) + BCLR(cur.br, r); + } + } + } + + /* 3. compose glue code */ + free(end); + free(beg); +} + + + + + + +static Blk * +edge(Blk *b, Blk **ps, Ins *ins, int nins) +{ + Blk *b1, *s; + Ins *ib; + + /* we could try to merge in blocks, + * but what the hell... + */ + s = *ps; + b1 = blocka(); + b1->link = elist; + elist = b1; + ne++; + sprintf(b1->name, "%s_%s", b->name, s->name); + ib = alloc(nins * sizeof(Ins)); + memcpy(ib, ins, nins * sizeof(Ins)); + b1->ins = ib; + b1->nins = nins; + b1->jmp.type = JJmp; + b1->s1 = s; + return *ps = b1; +} |