diff options
| -rw-r--r-- | lisc/rega.c | 168 |
1 files changed, 128 insertions, 40 deletions
diff --git a/lisc/rega.c b/lisc/rega.c index deafe40..874ba2f 100644 --- a/lisc/rega.c +++ b/lisc/rega.c @@ -11,9 +11,11 @@ struct RMap { }; 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 Sym *sym; /* symbol table in use */ +static struct { + Ref src, dst; +} *pm; /* parallel move constructed */ +static int cpm, npm; /* capacity and size of pm */ static int rfind(RMap *m, int t) @@ -26,6 +28,20 @@ rfind(RMap *m, int t) return -1; } +static Ref +rref(RMap *m, int t) +{ + int r, s; + + r = rfind(m, t); + if (r == -1) { + s = sym[t].spill; + assert(s && "should have spilled"); + return SLOT(s); + } else + return SYM(r); +} + static void radd(RMap *m, int t, int r) { @@ -40,7 +56,7 @@ radd(RMap *m, int t, int r) m->n++; } -static void +static int ralloc(RMap *m, int t) { int r; @@ -52,6 +68,7 @@ ralloc(RMap *m, int t) if (!BGET(m->br, r)) break; radd(m, t, r); + return t; } static int @@ -72,14 +89,66 @@ rfree(RMap *m, int t) return r; } -static int +static inline int isreg(Ref r) { return rtype(r) == RSym && sym[r.val].type == SReg; } +static void +pmadd(Ref src, Ref dst) +{ + if (npm == cpm) { + cpm *= 2; + pm = realloc(pm, cpm * sizeof pm[0]); + if (!pm) + diag("pmadd: out of memory"); + } + pm[npm].src = src; + pm[npm].dst = dst; + npm++; +} + +enum PMStat { ToMove, Moving, Moved }; + +static void +pmrec(enum PMStat *status, int i) +{ + int j; + + if (req(pm[i].src, pm[i].dst)) + return; + status[i] = Moving; + for (j=0; j<npm; j++) { + if (req(pm[j].src, pm[i].dst)) + switch (status[j]) { + case ToMove: + pmrec(status, j); + break; + case Moving: + case Moved: + break; + } + } + status[i] = Moved; +} + +static void +pmgen() +{ + int i; + enum PMStat *status; + + status = alloc(npm * sizeof status[0]); + assert(!npm || status[npm-1] == ToMove); + curi = insb; + for (i=0; i<npm; i++) + pmrec(status, i); + free(status); +} + static Ins * -pmgen(Blk *b, Ins *i) +dopm(Blk *b, Ins *i) { diag("not implemented"); return 0; @@ -91,10 +160,13 @@ pmgen(Blk *b, Ins *i) void rega(Fn *fn) { - int n, t, u, r; - Blk *b, *b1; + int n, t, u, r, z; + Blk *b, *b1, *s, ***ps, *blist; Ins *i; RMap *end, *beg, cur; + Phi *p; + uint a; + Bits v; sym = fn->sym; /* 1. gross hinting setup */ @@ -136,13 +208,14 @@ rega(Fn *fn) if (!BGET(cur.bt, t)) ralloc(&cur, t); /* process instructions */ + end[n] = cur; 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); + i = dopm(b, i); continue; } if (!req(i->to, R)) @@ -157,7 +230,7 @@ rega(Fn *fn) t = i->arg[0].val; if (sym[t].hint == -1) sym[t].hint = r; - ralloc(&cur, t); + i->arg[0] = SYM(ralloc(&cur, t)); } if (rtype(i->arg[1]) == RSym) { /* <arch> @@ -169,43 +242,58 @@ rega(Fn *fn) if (!opdesc[i->op].commut && r!=-1) BSET(cur.br, r); t = i->arg[1].val; - ralloc(&cur, t); + i->arg[1] = SYM(ralloc(&cur, t)); if (!opdesc[i->op].commut && r!=-1) BCLR(cur.br, r); } } + beg[n] = cur; } /* 3. compose glue code */ + blist = 0; + for (b=fn->start;; b=b->link) { + ps = (Blk**[3]){&b->s1, &b->s2, (Blk*[1]){0}}; + for (; (s=**ps); ps++) { + v = b->out; + for (z=0; z<BITS; z++) + v.t[z] |= s->in.t[z]; + for (p=s->phi; p; p=p->link) { + for (a=0; p->blk[a]!=b; a++) + assert(a+1 < p->narg); + if (rtype(p->arg[a]) == RSym) + BSET(v, p->arg[a].val); + } + npm = 0; + for (t=Tmp0; t<fn->ntmp; t++) + if (BGET(v, t)) + pmadd( + rref(&end[b->id], t), + rref(&beg[s->id], t) + ); + pmgen(); + /* todo, moving this out of + * here would make sense */ + n = curi-insb; + b1 = blocka(); + b1->link = blist; + blist = b1; + fn->nblk++; + sprintf(b1->name, "%s_%s", b->name, s->name); + i = alloc(n * sizeof(Ins)); + memcpy(i, insb, n * sizeof(Ins)); + b1->ins = i; + b1->nins = n; + b1->jmp.type = JJmp; + b1->s1 = s; + **ps = b1; + } + if (!b->link) { + b->link = blist; + break; + } + } + 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; -} |