diff options
| -rw-r--r-- | lisc/Makefile | 2 | ||||
| -rw-r--r-- | lisc/copy.c | 158 | ||||
| -rw-r--r-- | lisc/lisc.h | 9 | ||||
| -rw-r--r-- | lisc/main.c | 6 |
4 files changed, 171 insertions, 4 deletions
diff --git a/lisc/Makefile b/lisc/Makefile index 389e376..6db1153 100644 --- a/lisc/Makefile +++ b/lisc/Makefile @@ -1,5 +1,5 @@ BIN = lisc -OBJ = main.o util.o parse.o ssa.o live.o isel.o spill.o rega.o emit.o +OBJ = main.o util.o parse.o ssa.o copy.o live.o isel.o spill.o rega.o emit.o CFLAGS = -Wall -Wextra -std=c99 -g -pedantic diff --git a/lisc/copy.c b/lisc/copy.c new file mode 100644 index 0000000..9367e8d --- /dev/null +++ b/lisc/copy.c @@ -0,0 +1,158 @@ +#include "lisc.h" + +typedef struct RList RList; +struct RList { + int t; + RList *l; +}; + +static Ref +copyof(Ref r, Ref *cp) +{ + if (rtype(r) == RTmp) + return cp[r.val]; + else + return r; +} + +static void +update(Ref r, Ref rcp, Ref *cp, RList **w) +{ + RList *l; + + if (!req(cp[r.val], rcp)) { + cp[r.val] = rcp; + l = emalloc(sizeof *l); + l->t = r.val; + l->l = *w; + *w = l; + } +} + +static void +visitphi(Phi *p, Ref *cp, RList **w) +{ + uint a; + Ref r, r1; + + r = R; + for (a=0; a<p->narg; a++) { + r1 = copyof(p->arg[a], cp); + if (req(r1, R)) + continue; + if (req(r, R) || req(r, r1)) + r = r1; + else { + r = p->to; + break; + } + } + assert(!req(r, R)); + update(p->to, r, cp, w); +} + +static void +visitins(Ins *i, Ref *cp, RList **w) +{ + Ref r; + + if (i->op != OCopy) { + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + update(i->to, i->to, cp, w); + } + } else { + assert(rtype(i->to) == RTmp); + r = copyof(i->arg[0], cp); + update(i->to, r, cp, w); + } +} + +void +copy(Fn *fn) +{ + Blk *b; + Ref *cp, r; + RList *w, *w1; + Use *u, *u1; + Ins *i; + Phi *p, **pp; + uint a; + int t; + + w = 0; + cp = emalloc(fn->ntmp * sizeof cp[0]); + for (b=fn->start; b; b=b->link) { + for (p=b->phi; p; p=p->link) + visitphi(p, cp, &w); + for (i=b->ins; i!=&b->ins[b->nins]; i++) + visitins(i, cp, &w); + } + while ((w1=w)) { + t = w->t; + w = w->l; + free(w1); + u = fn->tmp[t].use; + u1 = u + fn->tmp[t].nuse; + for (; u<u1; u++) + switch (u->type) { + default: + diag("copy: invalid use"); + case UPhi: + visitphi(u->u.phi, cp, &w); + break; + case UIns: + visitins(u->u.ins, cp, &w); + break; + case UJmp: + break; + } + } + for (b=fn->start; b; b=b->link) { + for (pp=&b->phi; (p=*pp); pp=&p->link) { + Again: + r = cp[p->to.val]; + if (!req(r, p->to)) { + *pp = p->link; + p = *pp; + goto Again; + } + for (a=0; a<p->narg; a++) + if (rtype(p->arg[a]) == RTmp) { + r = cp[p->arg[a].val]; + assert(!req(r, R)); + p->arg[a] = r; + } + } + for (i=b->ins; i!=&b->ins[b->nins]; i++) { + r = cp[i->to.val]; + if (!req(r, i->to)) { + *i = (Ins){.op = ONop}; + continue; + } + for (a=0; a<2; a++) + if (rtype(i->arg[a]) == RTmp) { + r = cp[i->arg[a].val]; + assert(!req(r, R)); + i->arg[a] = r; + } + } + if (rtype(b->jmp.arg) == RTmp) { + r = cp[b->jmp.arg.val]; + assert(!req(r, R)); + b->jmp.arg = r; + } + } + if (debug['C']) { + fprintf(stderr, "\n> Copy information:"); + for (t=Tmp0; t<fn->ntmp; t++) + if (!req(cp[t], TMP(t))) { + fprintf(stderr, "\n%10s copy of ", + fn->tmp[t].name); + printref(cp[t], fn, stderr); + } + fprintf(stderr, "\n\n> After copy elimination:\n"); + printfn(fn, stderr); + } + free(cp); +} diff --git a/lisc/lisc.h b/lisc/lisc.h index 3643e48..fcce670 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -257,8 +257,8 @@ struct Use { } type; int bid; union { - int ins; - Ref phi; + Ins *ins; + Phi *phi; } u; }; @@ -371,6 +371,7 @@ void addcon(Con *, Con *); extern OpDesc opdesc[NOp]; void parse(FILE *, void (Dat *), void (Fn *)); void printfn(Fn *, FILE *); +void printref(Ref, Fn *, FILE *); /* ssa.c */ void filluse(Fn *); @@ -378,10 +379,14 @@ void fillpreds(Fn *); void fillrpo(Fn *); void ssa(Fn *); +/* copy.c */ +void copy(Fn *); + /* live.c */ Bits liveon(Blk *, Blk *); void filllive(Fn *); + /* isel.c */ extern int rsave[NRSave]; extern int rclob[NRClob]; diff --git a/lisc/main.c b/lisc/main.c index e91d65e..90f8b37 100644 --- a/lisc/main.c +++ b/lisc/main.c @@ -3,9 +3,11 @@ char debug['Z'+1] = { ['P'] = 0, /* parsing */ - ['C'] = 0, /* call lowering */ + ['A'] = 0, /* abi lowering */ ['I'] = 0, /* instruction selection */ ['L'] = 0, /* liveness */ + ['N'] = 0, /* ssa construction */ + ['C'] = 0, /* copy elimination */ ['S'] = 0, /* spilling */ ['R'] = 0, /* reg. allocation */ }; @@ -52,6 +54,8 @@ func(Fn *fn) filluse(fn); ssa(fn); filluse(fn); + copy(fn); + filluse(fn); isel(fn); filllive(fn); fillcost(fn); |