commit d7548fa5d7c6ab4adaff87619e9801d0bdb07b55
parent 58bd1de2647d8a7acd0e8edb4ec2bfb9f99799a6
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Wed, 15 Jul 2015 18:01:38 -0400
add rpo test and some liveness code
Diffstat:
6 files changed, 146 insertions(+), 14 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -0,0 +1,10 @@
+@start
+ jmp @foo
+@baz
+ jez 1, @end, @foo
+@bar
+ jmp @end
+@foo
+ jez 0, @bar, @baz
+@end
+ ret
