diff options
| -rw-r--r-- | lisc/Makefile | 2 | ||||
| -rw-r--r-- | lisc/lisc.h | 40 | ||||
| -rw-r--r-- | lisc/live.c | 59 | ||||
| -rw-r--r-- | lisc/parse.c | 48 | ||||
| -rw-r--r-- | lisc/ssa.c | 1 | ||||
| -rw-r--r-- | lisc/test/rpo.ssa | 10 |
6 files changed, 146 insertions, 14 deletions
diff --git a/lisc/Makefile b/lisc/Makefile index 381452d..fcf91a5 100644 --- a/lisc/Makefile +++ b/lisc/Makefile @@ -1,5 +1,5 @@ BIN = lisc -OBJ = parse.o ssa.o +OBJ = parse.o ssa.o live.o CFLAGS = -Wall -Wextra -std=c99 -g diff --git a/lisc/lisc.h b/lisc/lisc.h index 2f6ada4..0ed9411 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -1,41 +1,56 @@ #include <assert.h> #include <stdio.h> #include <stdlib.h> +#include <string.h> typedef unsigned int uint; typedef unsigned short ushort; typedef unsigned char uchar; +typedef unsigned long long ullong; enum { NReg = 32, Tmp0 = NReg+1, + NString = 32, NPred = 15, NBlk = 128, NIns = 256, + + BITS = 4, + NBit = 8 * sizeof(ullong), }; +typedef struct Bits Bits; +typedef struct Ref Ref; typedef struct OpDesc OpDesc; typedef struct Ins Ins; typedef struct Phi Phi; typedef struct Blk Blk; typedef struct Sym Sym; typedef struct Fn Fn; -typedef struct Ref Ref; + +struct Bits { + ullong t[BITS]; +}; + +#define BGET(b, n) (1&((b).t[n/NBit]>>(n%NBit))) +#define BSET(b, n) ((b).t[n/NBit] |= (ullong)1<<(n%NBit)) +#define BCLR(b, n) ((b).t[n/NBit] &= ~((ullong)1<<(n%NBit))) struct Ref { ushort type:1; ushort val:15; }; +#define R (Ref){0, 0} // Invalid reference + static inline int req(Ref a, Ref b) { return a.type == b.type && a.val == b.val; } -#define R (Ref){0, 0} // Invalid reference - enum { RSym = 0, RConst = 1, @@ -46,7 +61,7 @@ enum { #define CONST(x) (Ref){RConst, x} enum { - OXXX, + OXXX = 0, OAdd, OSub, ODiv, @@ -58,12 +73,6 @@ enum { OLast }; -struct OpDesc { - int arity; - int commut:1; - char *name; -}; - enum { JXXX, JRet, @@ -71,6 +80,12 @@ enum { JJez, }; +struct OpDesc { + int arity; + int commut:1; + char *name; +}; + struct Ins { short op; Ref to; @@ -99,6 +114,7 @@ struct Blk { Blk **pred; uint npred; + Bits in, out; char name[NString]; int id; }; @@ -124,7 +140,6 @@ struct Fn { /* parse.c */ extern OpDesc opdesc[]; - void *alloc(size_t); Fn *parsefn(FILE *); void printfn(Fn *, FILE *); @@ -133,3 +148,6 @@ void printfn(Fn *, FILE *); void fillpreds(Fn *); void fillrpo(Fn *); void ssafix(Fn *, int); + +/* live.c */ +void filllive(Fn *); diff --git a/lisc/live.c b/lisc/live.c new file mode 100644 index 0000000..82acae9 --- /dev/null +++ b/lisc/live.c @@ -0,0 +1,59 @@ +#include "lisc.h" + +/* liveness analysis + * requires rpo computation + */ +void +filllive(Fn *f) +{ + Blk *b; + Ins *i; + Phi *p; + int z, n, chg; + Bits *kill, *use, *k, *u, bt; + + assert(f->ntmp <= NBit*BITS); + kill = alloc(f->ntmp * sizeof kill[0]); + use = alloc(f->ntmp * sizeof use[0]); + for (b=f->start; b; b=b->link) { + k = &kill[b->id]; + u = &use[b->id]; + for (p=b->phi; p; p=p->link) + BSET(*k, p->to.val); + for (i=b->ins; i-b->ins < b->nins; i++) { + if (!req(i->to, R)) + BSET(*k, i->to.val); + if (!req(i->arg[0], R)) + BSET(*u, i->arg[0].val); + if (!req(i->arg[1], R)) + BSET(*u, i->arg[1].val); + } + if (!req(b->jmp.arg, R)) + BSET(*u, b->jmp.arg.val); + for (z=0; z<BITS; z++) + u->t[z] &= ~k->t[z]; + memset(&b->in, 0, sizeof(Bits)); + memset(&b->out, 0, sizeof(Bits)); + } +Again: + chg = 0; + for (n=f->nblk-1; n>=0; n--) { + b = f->rpo[n]; + bt = b->out; + if (b->s1) + for (z=0; z<BITS; z++) + b->out.t[z] |= b->s1->in.t[z]; + if (b->s2) + for (z=0; z<BITS; z++) + b->out.t[z] |= b->s2->in.t[z]; + chg |= memcmp(&b->out, &bt, sizeof(Bits)) != 0; + k = &kill[n]; + u = &use[n]; + for (z=0; z<BITS; z++) + b->in.t[z] = (b->out.t[z]|u->t[z]) & ~k->t[z]; + } + if (chg) + goto Again; + free(kill); + free(use); +} diff --git a/lisc/parse.c b/lisc/parse.c index 3c00144..d8e2095 100644 --- a/lisc/parse.c +++ b/lisc/parse.c @@ -534,11 +534,21 @@ printfn(Fn *fn, FILE *f) } +static void +dumprset(Bits *b, Fn *fn) +{ + int t; + + for (t=Tmp0; t<fn->ntmp; t++) + if (BSET(*b, t)) + fprintf(stderr, " %s", fn->sym[t].name); + fprintf(stderr, "\n"); +} + int main(int ac, char *av[]) { int opt; - int tx, ntmp; Fn *fn; fn = parsefn(stdin); @@ -548,7 +558,9 @@ main(int ac, char *av[]) opt = av[1][1]; switch (opt) { - case 'f': + case 'f': { + int tx, ntmp; + fprintf(stderr, "[test ssafix:"); fillpreds(fn); for (ntmp=fn->ntmp, tx=Tmp0; tx<ntmp; tx++) { @@ -558,6 +570,38 @@ main(int ac, char *av[]) fprintf(stderr, "]\n"); break; } + case 'r': { + int n; + + fprintf(stderr, "[test rpo]\n"); + fillrpo(fn); + assert(fn->rpo[0] == fn->start); + for (n=0;; n++) + if (n == fn->nblk-1) { + fn->rpo[n]->link = 0; + break; + } else + fn->rpo[n]->link = fn->rpo[n+1]; + break; + } + case 'l': { + Blk *b; + + fprintf(stderr, "[test liveness]\n"); + fillrpo(fn); + filllive(fn); + for (b=fn->start; b; b=b->link) { + fprintf(stderr, "> Block %s\n", b->name); + fprintf(stderr, "\tlive in :"); + dumprset(&b->in, fn); + fprintf(stderr, "\tlive out:"); + dumprset(&b->out, fn); + } + break; + } + default: + break; + } printfn(fn, stdout); return 0; diff --git a/lisc/ssa.c b/lisc/ssa.c index c08d6b1..c4710f6 100644 --- a/lisc/ssa.c +++ b/lisc/ssa.c @@ -46,6 +46,7 @@ rporec(Blk *b, int x) { if (b->id >= 0) return x; + b->id = 1; if (b->s1) x = rporec(b->s1, x); if (b->s2) diff --git a/lisc/test/rpo.ssa b/lisc/test/rpo.ssa new file mode 100644 index 0000000..44d0056 --- /dev/null +++ b/lisc/test/rpo.ssa @@ -0,0 +1,10 @@ +@start + jmp @foo +@baz + jez 1, @end, @foo +@bar + jmp @end +@foo + jez 0, @bar, @baz +@end + ret |