diff options
Diffstat (limited to 'lisc')
| -rw-r--r-- | lisc/Makefile | 2 | ||||
| -rw-r--r-- | lisc/emit.c | 20 | ||||
| -rw-r--r-- | lisc/isel.c | 9 | ||||
| -rw-r--r-- | lisc/lisc.h | 16 | ||||
| -rw-r--r-- | lisc/live.c | 42 | ||||
| -rw-r--r-- | lisc/parse.c | 20 | ||||
| -rw-r--r-- | lisc/rega.c | 83 | ||||
| -rw-r--r-- | lisc/spill.c | 47 |
8 files changed, 97 insertions, 142 deletions
diff --git a/lisc/Makefile b/lisc/Makefile index 444485c..799ec93 100644 --- a/lisc/Makefile +++ b/lisc/Makefile @@ -1,7 +1,7 @@ BIN = lisc OBJ = parse.o ssa.o live.o isel.o spill.o rega.o emit.o main.o -CFLAGS = -Wall -Wextra -std=c11 -g -pedantic +CFLAGS = -Wall -Wextra -std=c99 -g -pedantic $(BIN): $(OBJ) $(CC) $(LDFLAGS) $(OBJ) -o $@ diff --git a/lisc/emit.c b/lisc/emit.c index a08ad52..76ce82c 100644 --- a/lisc/emit.c +++ b/lisc/emit.c @@ -75,7 +75,10 @@ static void eref(Ref r, Fn *fn, FILE *f) { switch (rtype(r)) { - case RReg: + default: + diag("emitref: invalid reference"); + case RTmp: + assert(r.val < Tmp0); fprintf(f, "%%%s", rtoa(r.val)); break; case RSlot: @@ -85,8 +88,6 @@ eref(Ref r, Fn *fn, FILE *f) fprintf(f, "$"); econ(&fn->con[r.val], f); break; - default: - diag("emitref: invalid reference"); } } @@ -102,7 +103,7 @@ emem(Ref r, Fn *fn, FILE *f) case RCon: econ(&fn->con[r.val], f); break; - case RReg: + case RTmp: assert(r.val < EAX); fprintf(f, "("); eref(r, fn, f); @@ -178,7 +179,8 @@ eins(Ins i, Fn *fn, FILE *f) case OStores: case OStoreb: fprintf(f, "\tmov%s ", stoa[i.op - OStorel]); - if (rtype(i.arg[0]) == RReg) { + if (rtype(i.arg[0]) == RTmp) { + assert(i.arg[0].val < Tmp0); reg = RBASE(i.arg[0].val); fprintf(f, "%%%s", rsub[reg][i.op - OStorel]); } else @@ -203,17 +205,17 @@ eins(Ins i, Fn *fn, FILE *f) fprintf(f, "\n"); break; case OAlloc: - eop("sub", i.arg[0], REG(RSP), fn, f); + eop("sub", i.arg[0], TMP(RSP), fn, f); if (!req(i.to, R)) - eop("mov", REG(RSP), i.to, fn ,f); + eop("mov", TMP(RSP), i.to, fn ,f); break; case OSwap: eop("xchg", i.arg[0], i.arg[1], fn, f); break; case OSign: - if (req(i.to, REG(RDX)) && req(i.arg[0], REG(RAX))) + if (req(i.to, TMP(RDX)) && req(i.arg[0], TMP(RAX))) fprintf(f, "\tcqto\n"); - else if (req(i.to, REG(EDX)) && req(i.arg[0], REG(EAX))) + else if (req(i.to, TMP(EDX)) && req(i.arg[0], TMP(EAX))) fprintf(f, "\tcltd\n"); else diag("emit: unhandled instruction (2)"); diff --git a/lisc/isel.c b/lisc/isel.c index 5b83081..a9e3ee2 100644 --- a/lisc/isel.c +++ b/lisc/isel.c @@ -122,12 +122,12 @@ sel(Ins i, Fn *fn) default: diag("isel: invalid division"); case TWord: - ra = REG(EAX); - rd = REG(EDX); + ra = TMP(EAX); + rd = TMP(EDX); break; case TLong: - ra = REG(RAX); - rd = REG(RDX); + ra = TMP(RAX); + rd = TMP(RDX); break; } r0 = i.op == ODiv ? ra : rd; @@ -230,6 +230,7 @@ flagi(Ins *i0, Ins *i) return 0; case OAdd: /* flag-setting */ case OSub: + case OAnd: return i; case OCopy: /* flag-transparent */ case OStorel: diff --git a/lisc/lisc.h b/lisc/lisc.h index abf9c1f..3ae5c56 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -18,7 +18,7 @@ typedef struct Fn Fn; typedef enum { U, F, T } B3; -enum { +enum Reg { RXX, RAX, /* caller-save */ @@ -56,8 +56,9 @@ enum { R14D, R15D, - // NReg = R15 - RAX + 1 - NReg = 3 /* for test purposes */ + Tmp0, /* first non-reg temporary */ + + NReg = RDX - RAX + 1 }; #define RWORD(r) (r + (EAX-RAX)) @@ -90,7 +91,6 @@ enum { RTmp, RCon, RSlot, - RReg, NRef = (1<<14) - 1 }; @@ -99,14 +99,13 @@ enum { #define CON(x) (Ref){RCon, x} #define CON_Z CON(0) /* reserved zero constant */ #define SLOT(x) (Ref){RSlot, x} -#define REG(x) (Ref){RReg, x} static inline int req(Ref a, Ref b) { return a.type == b.type && a.val == b.val; } static inline int rtype(Ref r) { return req(r, R) ? -1 : r.type; } -enum { +enum Cmp { Ceq, Csle, Cslt, @@ -118,7 +117,7 @@ enum { #define COP(c) (c==Ceq||c==Cne ? c : NCmp-1 - c) -enum { +enum Op { OXXX, /* public instructions */ @@ -154,7 +153,7 @@ enum { NOp }; -enum { +enum Jmp { JXXX, JRet, JJmp, @@ -211,6 +210,7 @@ struct Tmp { TUndef, TWord, TLong, + TReg, } type; char name[NString]; uint ndef, nuse; diff --git a/lisc/live.c b/lisc/live.c index aec7701..64fcf6a 100644 --- a/lisc/live.c +++ b/lisc/live.c @@ -1,24 +1,14 @@ #include "lisc.h" static void -bset(Ref r, Blk *b, Bits *rb, int *nlv) +bset(Ref r, Blk *b, int *nlv) { - Bits *bs; - - switch (rtype(r)) { - case RTmp: - bs = &b->in; - BSET(b->gen, r.val); - break; - case RReg: - bs = rb; - break; - default: + if (rtype(r) != RTmp) return; - } - if (!BGET(*bs, r.val)) { + BSET(b->gen, r.val); + if (!BGET(b->in, r.val)) { ++*nlv; - BSET(*bs, r.val); + BSET(b->in, r.val); } } @@ -33,7 +23,7 @@ filllive(Fn *f) Phi *p; int z, n, chg, nlv; uint a; - Bits tb, rb; + Bits tb; assert(f->ntmp <= NBit*BITS); for (b=f->start; b; b=b->link) { @@ -56,28 +46,18 @@ Again: chg |= memcmp(&b->out, &tb, sizeof(Bits)); b->in = b->out; - rb = (Bits){{0}}; nlv = bcnt(&b->in); - bset(b->jmp.arg, b, &rb, &nlv); + bset(b->jmp.arg, b, &nlv); b->nlive = nlv; for (i=&b->ins[b->nins]; i!=b->ins;) { i--; - switch (rtype(i->to)) { - default: - diag("live: unhandled destination"); - case RTmp: + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); nlv -= BGET(b->in, i->to.val); BCLR(b->in, i->to.val); - break; - case RReg: - nlv -= BGET(rb, i->to.val); - BCLR(rb, i->to.val); - break; - case -1: - break; } - bset(i->arg[0], b, &rb, &nlv); - bset(i->arg[1], b, &rb, &nlv); + bset(i->arg[0], b, &nlv); + bset(i->arg[1], b, &nlv); if (nlv > b->nlive) b->nlive = nlv; } diff --git a/lisc/parse.c b/lisc/parse.c index fc35800..5a06911 100644 --- a/lisc/parse.c +++ b/lisc/parse.c @@ -257,7 +257,7 @@ tmpref(char *v, int use) { int t; - for (t=0; t<ntmp; t++) + for (t=Tmp0; t<ntmp; t++) if (strcmp(v, tmp[t].name) == 0) goto Found; if (ntmp++ >= NTmp) @@ -496,9 +496,12 @@ parsefn(FILE *f) for (i=0; i<NBlk; i++) bmap[i] = 0; for (i=0; i<NTmp; i++) - tmp[i] = (Tmp){.name = ""}; - ntmp = 1; /* first tmp is invalid */ - ncon = 1; /* first con in 0 */ + if (i < Tmp0) + tmp[i] = (Tmp){.type = TReg}; + else + tmp[i] = (Tmp){.name = ""}; + ntmp = Tmp0; + ncon = 1; /* first constant must be 0 */ curi = insb; curb = 0; lnum = 1; @@ -531,11 +534,15 @@ printref(Ref r, Fn *fn, FILE *f) [TUndef] = "?", [TWord] = "w", [TLong] = "l", + [TReg] = "", }; switch (r.type) { case RTmp: - fprintf(f, "%%%s", fn->tmp[r.val].name); + if (r.val < Tmp0) + fprintf(f, "R%d", r.val); + else + fprintf(f, "%%%s", fn->tmp[r.val].name); return ttoa[fn->tmp[r.val].type]; case RCon: switch (fn->con[r.val].type) { @@ -554,9 +561,6 @@ printref(Ref r, Fn *fn, FILE *f) case RSlot: fprintf(f, "$%d", r.val); break; - case RReg: - fprintf(f, "R%d", r.val); - break; } return ""; } diff --git a/lisc/rega.c b/lisc/rega.c index ea26417..5aae3b6 100644 --- a/lisc/rega.c +++ b/lisc/rega.c @@ -31,13 +31,14 @@ rfind(RMap *m, int t) static Ref reg(int r, int t) { + assert(r < Tmp0); switch (tmp[t].type) { default: - assert(!"invalid temporary"); + diag("rega: invalid temporary"); case TWord: - return REG(RWORD(r)); + return TMP(RWORD(r)); case TLong: - return REG(r); + return TMP(r); } } @@ -75,6 +76,10 @@ ralloc(RMap *m, int t) static int x; int n, r; + if (t < Tmp0) { + BSET(m->br, t); + return TMP(t); + } if (BGET(m->bt, t)) { r = rfind(m, t); assert(r != -1); @@ -100,6 +105,12 @@ rfree(RMap *m, int t) { int i, r; + if (t < Tmp0) { + t = RBASE(t); + assert(BGET(m->br, t)); + BCLR(m->br, t); + return t; + } if (!BGET(m->bt, t)) return -1; for (i=0; m->t[i] != t; i++) @@ -194,6 +205,12 @@ pmgen() free(status); } +static int +isreg(Ref r) +{ + return rtype(r) == RTmp && r.val < Tmp0; +} + static Ins * dopm(Blk *b, Ins *i, RMap *m) { @@ -203,7 +220,7 @@ dopm(Blk *b, Ins *i, RMap *m) npm = 0; i1 = i+1; - if (rtype(i->to) == RReg) + if (isreg(i->to)) for (;; i--) { r = RBASE(i->to.val); rt = i->arg[0]; @@ -215,13 +232,12 @@ dopm(Blk *b, Ins *i, RMap *m) pmadd(rt, i->to); if (i==b->ins || (i-1)->op!=OCopy - || rtype((i-1)->to) != RReg) + || isreg((i-1)->to)) break; } - else if (rtype(i->arg[0]) == RReg) + else if (isreg(i->arg[0])) for (;; i--) { r = RBASE(i->arg[0].val); - assert(req(i->to, R) || i->to.type == RTmp); if (req(i->to, R)) { if (BGET(m->br, r)) { for (n=0; m->r[n] != r; n++) @@ -239,7 +255,7 @@ dopm(Blk *b, Ins *i, RMap *m) BSET(m->br, r); if (i==b->ins || (i-1)->op!=OCopy - || rtype((i-1)->arg[0]) != RReg) + || isreg((i-1)->arg[0])) break; } else @@ -273,21 +289,19 @@ rega(Fn *fn) Ref src, dst; tmp = fn->tmp; - end = alloc(fn->ntmp * sizeof end[0]); - beg = alloc(fn->ntmp * sizeof beg[0]); + end = alloc(fn->nblk * sizeof end[0]); + beg = alloc(fn->nblk * sizeof beg[0]); /* 1. gross hinting setup */ - for (t=0; t<fn->ntmp; t++) + for (t=Tmp0; t<fn->ntmp; t++) tmp[t].hint = -1; for (b=fn->start; b; b=b->link) for (i=b->ins; i-b->ins < b->nins; i++) { if (i->op != OCopy) continue; - if (rtype(i->arg[0]) == RTmp - && rtype(i->to) == RReg) + if (rtype(i->arg[0]) == RTmp && isreg(i->to)) tmp[i->arg[0].val].hint = RBASE(i->to.val); - if (rtype(i->to) == RTmp - && rtype(i->arg[0]) == RReg) + if (rtype(i->to) == RTmp && isreg(i->arg[0])) tmp[i->to.val].hint = RBASE(i->arg[0].val); } @@ -309,48 +323,38 @@ rega(Fn *fn) * successor */ if (b1 != b) - for (t=0; t<fn->ntmp; t++) + 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 (x=0; x<2; x++) - for (t=0; t<fn->ntmp; t++) + for (t=Tmp0; t<fn->ntmp; t++) if (x==1 || tmp[t].hint!=-1) if (BGET(b->out, t)) if (!BGET(cur.bt, t)) ralloc(&cur, t); /* process instructions */ end[n] = cur; - assert(rtype(b->jmp.arg) != RReg); if (rtype(b->jmp.arg) == RTmp) b->jmp.arg = ralloc(&cur, b->jmp.arg.val); for (i=&b->ins[b->nins]; i!=b->ins;) { i--; if (i->op == OCopy /* par. moves are special */ - && (rtype(i->arg[0]) == RReg || rtype(i->to) == RReg)) { + && (isreg(i->arg[0]) || isreg(i->to))) { i = dopm(b, i, &cur); continue; } - switch (rtype(i->to)) { - default: - assert(!"unhandled destination"); - case RTmp: + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); r = rfree(&cur, i->to.val); if (r == -1) { *i = (Ins){ONop, R, {R, R}}; continue; } - i->to = reg(r, i->to.val); - break; - case RReg: - r = RBASE(i->to.val); - assert(BGET(cur.br, r)); - BCLR(cur.br, r); - break; - case -1:; + if (i->to.val >= Tmp0) + i->to = reg(r, i->to.val); } - switch (rtype(i->arg[0])) { - case RTmp: + if (rtype(i->arg[0]) == RTmp) { /* <arch> * on Intel, we attempt to * use the same register @@ -361,19 +365,10 @@ rega(Fn *fn) if (tmp[t].hint == -1 && r) tmp[t].hint = r; i->arg[0] = ralloc(&cur, t); - break; - case RReg: - BSET(cur.br, RBASE(i->arg[0].val)); - break; } - switch (rtype(i->arg[1])) { - case RTmp: + if (rtype(i->arg[1]) == RTmp) { t = i->arg[1].val; i->arg[1] = ralloc(&cur, t); - break; - case RReg: - BSET(cur.br, RBASE(i->arg[1].val)); - break; } } b->in = cur.bt; @@ -413,7 +408,7 @@ rega(Fn *fn) src = rref(&end[b->id], src.val); pmadd(src, dst); } - for (t=0; t<fn->ntmp; t++) + for (t=Tmp0; t<fn->ntmp; t++) if (BGET(s->in, t)) { src = rref(&end[b->id], t); dst = rref(&beg[s->id], t); diff --git a/lisc/spill.c b/lisc/spill.c index 6554316..ad461f0 100644 --- a/lisc/spill.c +++ b/lisc/spill.c @@ -34,7 +34,7 @@ tmpuse(Ref r, int use, int loop, Fn *fn) { Tmp *t; - if (rtype(r) != RTmp) + if (rtype(r) != RTmp || r.val < Tmp0) return; t = &fn->tmp[r.val]; t->nuse += use; @@ -77,7 +77,7 @@ fillcost(Fn *fn) } } for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) { - t->cost = 0; + t->cost = t-fn->tmp < Tmp0 ? 1e6 : 0; t->nuse = 0; t->ndef = 0; } @@ -104,7 +104,7 @@ fillcost(Fn *fn) } if (debug['S']) { fprintf(stderr, "\n> Spill costs:\n"); - for (n=0; n<fn->ntmp; n++) + for (n=Tmp0; n<fn->ntmp; n++) fprintf(stderr, "\t%-10s %d\n", fn->tmp[n].name, fn->tmp[n].cost); @@ -145,8 +145,6 @@ static Bits *f; /* temps to prioritize in registers (for tcmp1) */ static Tmp *tmp; /* current temporaries (for tcmpX) */ static int ntmp; /* current # of temps (for limit) */ static uint ns; /* current # of spill slots */ -static int nreg; /* # of registers available */ -static Bits br; /* live registers */ static int tcmp0(const void *pa, const void *pb) @@ -168,6 +166,8 @@ slot(int t) { int s; + if (t < Tmp0) + diag("spill: cannot spill register"); s = tmp[t].spill; if (!s) { s = ++ns; @@ -237,24 +237,11 @@ setloc(Ref *pr, Bits *v, Bits *w) { int t; - /* <arch> - * here we assume that the - * machine can always support - * instructions of the kind - * reg = op slot, slot - * if not, we need to add - * 't' to 'w' before calling - * limit - */ - if (rtype(*pr) == RReg) { - nreg -= !BGET(br, pr->val); - BSET(br, pr->val); - } if (rtype(*pr) != RTmp) return 0; t = pr->val; BSET(*v, t); - if (limit(v, nreg, w) == t) + if (limit(v, NReg, w) == t) /* if t was spilled by limit, * it was not live so we don't * have to reload it */ @@ -300,7 +287,6 @@ spill(Fn *fn) for (n=fn->nblk-1; n>=0; n--) { /* invariant: m>n => in,out of m updated */ b = fn->rpo[n]; - assert(bcnt(&br) == 0); /* 1. find temporaries in registers at * the end of the block (put them in v) */ @@ -345,32 +331,19 @@ spill(Fn *fn) assert(bcnt(&v) <= NReg); /* 2. process the block instructions */ - nreg = NReg; curi = &insb[NIns]; for (i=&b->ins[b->nins]; i!=b->ins;) { - assert(bcnt(&v) <= nreg); + assert(bcnt(&v) <= NReg); i--; s = 0; - switch (rtype(i->to)) { - default: - diag("spill: unhandled destination"); - case RTmp: + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); j = i->to.val; if (BGET(v, j)) BCLR(v, j); else - limit(&v, nreg-1, &w); + limit(&v, NReg-1, &w); s = tmp[j].spill; - break; - case RReg: - j = i->to.val; - if (BGET(br, j)) { - BCLR(br, j); - nreg++; - } else - limit(&v, nreg-1, &w); - break; - case -1:; } w = (Bits){{0}}; j = opdesc[i->op].nmem; |