From 2981a267f406fb03142f149a0f0e6608917cd123 Mon Sep 17 00:00:00 2001 From: Quentin Carbonneaux Date: Fri, 24 Jul 2015 09:31:48 -0400 Subject: add slot addressing and some more spilling --- lisc/lisc.h | 14 ++--- lisc/parse.c | 12 ++++- lisc/spill.c | 165 +++++++++++++++++++++++++++++++++++++---------------------- 3 files changed, 121 insertions(+), 70 deletions(-) diff --git a/lisc/lisc.h b/lisc/lisc.h index d639289..d116012 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -33,7 +33,7 @@ enum { R14, R15, // NReg = R15 - RAX + 1 - NReg = 4 /* for test purposes */ + NReg = 3 /* for test purposes */ }; enum { @@ -57,19 +57,21 @@ struct Bits { #define BCLR(b, n) ((b).t[n/NBit] &= ~(1ll<<(n%NBit))) struct Ref { - uint16_t type:1; - uint16_t val:15; + uint16_t type:2; + uint16_t val:14; }; enum { - RSym = 0, - RConst = 1, - NRef = (1<<15) - 1 + RSym, + RConst, + RSlot, + NRef = (1<<14) - 1 }; #define R (Ref){0, 0} #define SYM(x) (Ref){RSym, x} #define CONST(x) (Ref){RConst, x} +#define SLOT(x) (Ref){RSlot, x} static inline int req(Ref a, Ref b) { return a.type == b.type && a.val == b.val; } diff --git a/lisc/parse.c b/lisc/parse.c index 4e43f84..75882e8 100644 --- a/lisc/parse.c +++ b/lisc/parse.c @@ -16,6 +16,8 @@ OpDesc opdesc[OLast] = { [OSub] = { 2, 0, "sub" }, [ODiv] = { 2, 0, "div" }, [ORem] = { 2, 0, "mod" }, + [OStore] = { 2, 0, "store" }, + [OLoad] = { 1, 0, "load" }, [OCopy] = { 1, 0, "copy" }, }; @@ -484,6 +486,9 @@ printref(Ref r, Fn *fn, FILE *f) case RConst: fprintf(f, "%d", r.val); break; + case RSlot: + fprintf(f, "$%d", r.val); + break; } } @@ -514,9 +519,12 @@ printfn(Fn *fn, FILE *f) } for (i=b->ins; i-b->ins < b->nins; i++) { fprintf(f, "\t"); - printref(i->to, fn, f); + if (!req(i->to, R)) { + printref(i->to, fn, f); + fprintf(f, " = "); + } assert(opdesc[i->op].name); - fprintf(f, " = %s", opdesc[i->op].name); + fprintf(f, "%s", opdesc[i->op].name); n = opdesc[i->op].arity; if (n > 0) { fprintf(f, " "); diff --git a/lisc/spill.c b/lisc/spill.c index 26a6631..df8a1a3 100644 --- a/lisc/spill.c +++ b/lisc/spill.c @@ -167,6 +167,27 @@ tcmp1(const void *pa, const void *pb) return c ? c : tcmp0(pa, pb); } +static Ref +slot(int t) +{ + int s; + + s = sym[t].spill; + if (!s) { + s = 1 + ns++; + sym[t].spill = s; + } + return SLOT(s); +} + +static void +emit(short op, Ref to, Ref arg0, Ref arg1) +{ + if (curi == insb) + diag("emit (spill.c): out of memory"); + *--curi = (Ins){op, to, {arg0, arg1}}; +} + static Bits limit(Bits *b, int k, Bits *fst) { @@ -183,11 +204,9 @@ limit(Bits *b, int k, Bits *fst) maxt = nt; } i = 0; - for (t=0/*Tmp0*/; tto = SYM(t0); - curi->op = OLoad; - s = tspill(t[--l]); - curi->arg[0] = CONST(s); - } - t[l] = t0; - for (p=&t[l]; p>t; p--) - if (sym[*p].cost > sym[p[-1]].cost) { - *p = p[-1]; - p[-1] = t0; - } else - assert(p[-1]!=t0); - /* break; */ - return l+1; -} - /* spill code insertion * requires spill costs, rpo, liveness * @@ -258,12 +241,12 @@ void spill(Fn *fn) { Blk *b, *s1, *s2, *hd; - int n, z, l, *t; + int n, z, l; Bits v, w; Ins *i; - int j; + int j, s; + Phi *p; - t = 1 + (int[NReg+1]){0}; ns = 0; sym = fn->sym; ntmp = fn->ntmp; @@ -275,6 +258,7 @@ spill(Fn *fn) /* 1. find temporaries in registers at * the end of the block (put them in v) */ + curi = 0; s1 = b->s1; s2 = b->s2; v = (Bits){{0}}; @@ -311,33 +295,90 @@ spill(Fn *fn) assert(bcnt(&w) <= NReg); v = limit(&v, NReg, &w); } - assert(bcnt(&v) <= NReg); - if (rtype(b->jmp.arg) == RSym - && !BGET(v, b->jmp.arg.val) - && bcnt(&v) == NReg) - v = limit(&v, NReg-1, 0); b->out = v; + assert(bcnt(&v) <= NReg); /* 2. process the block instructions */ - l = 0; - for (j=0; jntmp; j++) - if (BGET(v, j)) - tnew(j, t, l++); - if (rtype(b->jmp.arg) == RSym - && !BGET(v, b->jmp.arg.val)) { + if (rtype(b->jmp.arg) == RSym) { j = b->jmp.arg.val; - tnew(j, t, l++); + if (!BGET(v, j) && l==NReg) { + v = limit(&v, l-1, 0); + b->out = v; + } BSET(v, j); } - curi = &insb[NIns]; for (i=&b->ins[b->nins]; i!=b->ins;) { - assert(l<=NReg); - assert(l==bcnt(&v)); + assert(bcnt(&v) <= NReg); i--; + /* + * here we assume that the + * machine can always support + * instructions of the kind + * reg = op slot, slot + * if not, we need to use the + * last argument of 'limit' + */ if (!req(i->to, R)) { - assert(rtype(i->to) == RSym); + assert(rtype(i->to)==RSym); + j = i->to.val; + if (BSET(v, j)) + BCLR(v, j); + else + v = limit(&v, NReg-1, &w); + s = sym[j].spill; + } else + s = 0; + w = (Bits){{0}}; + if (rtype(i->arg[1]) == RSym) { + j = i->arg[1].val; + if (!req(i->to, R) + && opdesc[i->op].commut == 0) { + /* + */ + BSET(w, i->to.val); + BSET(v, i->to.val); + BSET(v, j); + v = limit(&v, NReg, &w); + if (curi->op == OLoad) + if (curi->to.val == j) + curi++; + if (!BGET(v, j)) + i->arg[1] = slot(j); + BCLR(v, i->to.val); + BCLR(w, i->to.val); + } else { + BSET(v, j); + v = limit(&v, NReg, 0); + if (!BGET(v, j)) + i->arg[1] = slot(j); + } + if (BGET(v, j)) + BSET(w, j); } + if (rtype(i->arg[0]) == RSym) { + j = i->arg[0].val; + BSET(v, j); + v = limit(&v, NReg, &w); + if (curi->op == OLoad) + if (curi->to.val == j) + curi++; + if (!BGET(v, j)) + i->arg[0] = slot(j); + else + BSET(w, j); + } + if (s) + emit(OStore, R, i->to, SLOT(s)); + emit(i->op, i->to, i->arg[0], i->arg[1]); } + free(b->ins); + b->nins = &insb[NIns] - curi; + b->ins = alloc(b->nins * sizeof(Ins)); + memcpy(b->ins, curi, b->nins * sizeof(Ins)); + + for (p=b->phi; p; p=p->link) + BCLR(v, p->to.val); + b->in = v; } } -- cgit 1.4.1