commit 8d2d674466c14738418fb6579126569f53d6f86a
parent cf307002d9cb87238d1c09b2bd795a057ae064d7
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Sat, 1 Aug 2015 21:05:18 -0400
start change of representation for registers
Diffstat:
6 files changed, 82 insertions(+), 90 deletions(-)
diff --git a/lisc/Makefile b/lisc/Makefile
@@ -1,5 +1,5 @@
BIN = lisc
-OBJ = main.o parse.o ssa.o live.o isel.o spill.o rega.o emit.o
+OBJ = main.o parse.o ssa.o live.o # isel.o spill.o rega.o emit.o
CFLAGS = -Wall -Wextra -std=c11 -g -pedantic
diff --git a/lisc/lisc.h b/lisc/lisc.h
@@ -19,7 +19,9 @@ typedef struct Fn Fn;
typedef enum { U, F, T } B3;
enum {
- RAX = 1, /* caller-save */
+ RXX,
+
+ RAX, /* caller-save */
RCX,
RDX,
RSI,
@@ -43,8 +45,6 @@ enum {
};
enum {
- Tmp0 = 33,
-
NString = 32,
NPred = 15,
NBlk = 128,
@@ -71,6 +71,7 @@ enum {
RSym,
RCons,
RSlot,
+ RReg,
NRef = (1<<14) - 1
};
@@ -78,6 +79,7 @@ enum {
#define SYM(x) (Ref){RSym, x}
#define CONS(x) (Ref){RCons, x}
#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; }
@@ -158,11 +160,6 @@ struct Blk {
};
struct Sym {
- enum {
- SUndef,
- SReg,
- STmp,
- } type;
char name[NString];
int class;
uint ndef, nuse;
@@ -185,7 +182,7 @@ struct Fn {
Blk *start;
Sym *sym;
Cons *cons;
- int ntmp;
+ int nsym;
int nblk;
Blk **rpo;
uint nspill;
diff --git a/lisc/live.c b/lisc/live.c
@@ -1,12 +1,24 @@
#include "lisc.h"
static void
-bset(Ref r, Blk *b, int *nlv)
+bset(Ref r, Blk *b, Bits *rb, int *nlv)
{
- if (rtype(r) == RSym && !BGET(b->in, r.val)) {
- ++*nlv;
- BSET(b->in, r.val);
+ Bits *bs;
+
+ switch (rtype(r)) {
+ case RSym:
+ bs = &b->in;
BSET(b->gen, r.val);
+ break;
+ case RReg:
+ bs = rb;
+ break;
+ default:
+ diag("live: unhandled reference");
+ }
+ if (!BGET(*bs, r.val)) {
+ ++*nlv;
+ BSET(*bs, r.val);
}
}
@@ -21,9 +33,9 @@ filllive(Fn *f)
Phi *p;
int z, n, chg, nlv;
uint a;
- Bits tb;
+ Bits tb, rb;
- assert(f->ntmp <= NBit*BITS);
+ assert(f->nsym <= NBit*BITS);
for (b=f->start; b; b=b->link) {
b->in = (Bits){{0}};
b->out = (Bits){{0}};
@@ -44,17 +56,25 @@ Again:
chg |= memcmp(&b->out, &tb, sizeof(Bits));
b->in = b->out;
+ rb = (Bits){{0}};
nlv = bcnt(&b->in);
- bset(b->jmp.arg, b, &nlv);
+ bset(b->jmp.arg, b, &rb, &nlv);
b->nlive = nlv;
for (i=&b->ins[b->nins]; i!=b->ins;) {
i--;
- if (!req(i->to, R)) {
+ switch (rtype(i->to)) {
+ case RSym:
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);
+ default:
+ diag("live: unhandled destination");
}
- bset(i->arg[0], b, &nlv);
- bset(i->arg[1], b, &nlv);
+ bset(i->arg[0], b, &rb, &nlv);
+ bset(i->arg[1], b, &rb, &nlv);
if (nlv > b->nlive)
b->nlive = nlv;
}
diff --git a/lisc/main.c b/lisc/main.c
@@ -33,13 +33,13 @@ main(int ac, char *av[])
switch (opt) {
case 'f': {
- int tx, ntmp;
+ int s, nsym;
fprintf(stderr, "[Testing SSA Reconstruction:");
fillpreds(fn);
- for (ntmp=fn->ntmp, tx=Tmp0; tx<ntmp; tx++) {
- fprintf(stderr, " %s", fn->sym[tx].name);
- ssafix(fn, tx);
+ for (nsym=fn->nsym, s=0; s<nsym; s++) {
+ fprintf(stderr, " %s", fn->sym[s].name);
+ ssafix(fn, s);
}
fprintf(stderr, "]\n");
break;
diff --git a/lisc/parse.c b/lisc/parse.c
@@ -68,26 +68,9 @@ static struct {
} tokval;
static int lnum;
-static Sym sym[NSym] = {
- [RAX] = { .type = SReg, .name = "rax" },
- [RCX] = { .type = SReg, .name = "rcx" },
- [RDX] = { .type = SReg, .name = "rdx" },
- [RBX] = { .type = SReg, .name = "rbx" },
- [RSP] = { .type = SReg, .name = "rsp" },
- [RBP] = { .type = SReg, .name = "rbp" },
- [RSI] = { .type = SReg, .name = "rsi" },
- [RDI] = { .type = SReg, .name = "rdi" },
- [R8 ] = { .type = SReg, .name = "r8" },
- [R9 ] = { .type = SReg, .name = "r9" },
- [R10] = { .type = SReg, .name = "r10" },
- [R11] = { .type = SReg, .name = "r11" },
- [R12] = { .type = SReg, .name = "r12" },
- [R13] = { .type = SReg, .name = "r13" },
- [R14] = { .type = SReg, .name = "r14" },
- [R15] = { .type = SReg, .name = "r15" },
-};
+static Sym sym[NSym];
static Cons cons[NCons];
-static int ntmp;
+static int nsym;
static int ncons;
static Phi **plink;
static Blk *bmap[NBlk+1];
@@ -261,17 +244,15 @@ blocka()
static Ref
varref(char *v)
{
- int t;
+ int s;
- for (t=Tmp0; t<ntmp; t++)
- if (sym[t].type == STmp)
- if (strcmp(v, sym[t].name) == 0)
- return SYM(t);
- if (ntmp++ >= NSym)
+ for (s=0; s<nsym; s++)
+ if (strcmp(v, sym[s].name) == 0)
+ return SYM(s);
+ if (nsym++ >= NSym)
err("too many symbols");
- sym[t].type = STmp;
- strcpy(sym[t].name, v);
- return SYM(t);
+ strcpy(sym[s].name, v);
+ return SYM(s);
}
static Ref
@@ -509,9 +490,9 @@ parsefn(FILE *f)
inf = f;
for (i=0; i<NBlk; i++)
bmap[i] = 0;
- for (i=Tmp0; i<NSym; i++)
- sym[i] = (Sym){.type = SUndef};
- ntmp = Tmp0;
+ for (i=0; i<NSym; i++)
+ sym[i] = (Sym){.name = ""};
+ nsym = 0;
ncons = 0;
curi = insb;
curb = 0;
@@ -527,11 +508,11 @@ parsefn(FILE *f)
err("empty file");
if (curb->jmp.type == JXXX)
err("last block misses jump");
- fn->sym = alloc(ntmp * sizeof sym[0]);
- memcpy(fn->sym, sym, ntmp * sizeof sym[0]);
+ fn->sym = alloc(nsym * sizeof sym[0]);
+ memcpy(fn->sym, sym, nsym * sizeof sym[0]);
fn->cons = alloc(ncons * sizeof cons[0]);
memcpy(fn->cons, cons, ncons * sizeof cons[0]);
- fn->ntmp = ntmp;
+ fn->nsym = nsym;
fn->nblk = nblk;
fn->rpo = 0;
return fn;
@@ -548,17 +529,8 @@ printref(Ref r, Fn *fn, FILE *f)
switch (r.type) {
case RSym:
- switch (fn->sym[r.val].type) {
- case STmp:
- fprintf(f, "%%%s", fn->sym[r.val].name);
- return ctoa[fn->sym[r.val].class];
- case SReg:
- fprintf(f, "%s", fn->sym[r.val].name);
- break;
- case SUndef:
- diag("printref: invalid symbol");
- }
- break;
+ fprintf(f, "%%%s", fn->sym[r.val].name);
+ return ctoa[fn->sym[r.val].class];
case RCons:
switch (fn->cons[r.val].type) {
case CAddr:
@@ -576,6 +548,9 @@ printref(Ref r, Fn *fn, FILE *f)
case RSlot:
fprintf(f, "$%d", r.val);
break;
+ case RReg:
+ fprintf(f, "???");
+ break;
}
return "";
}
diff --git a/lisc/ssa.c b/lisc/ssa.c
@@ -102,7 +102,7 @@ static Ref
topdef(Blk *b, Fn *f)
{
uint i;
- int t1;
+ int s1;
Ref r;
Phi *p;
@@ -115,8 +115,8 @@ topdef(Blk *b, Fn *f)
return r;
}
/* add a phi node */
- t1 = f->ntmp++;
- r = SYM(t1);
+ s1 = f->nsym++;
+ r = SYM(s1);
top[b->id] = r;
p = alloc(sizeof *p);
p->link = b->phi;
@@ -137,7 +137,7 @@ void
ssafix(Fn *f, int t)
{
uint n;
- int t0, t1;
+ int s0, s1;
Ref rt;
Blk *b;
Phi *p;
@@ -146,31 +146,31 @@ ssafix(Fn *f, int t)
top = alloc(f->nblk * sizeof top[0]);
bot = alloc(f->nblk * sizeof bot[0]);
rt = SYM(t);
- t0 = f->ntmp;
+ s0 = f->nsym;
for (b=f->start; b; b=b->link) {
- t1 = 0;
+ s1 = 0;
/* rename defs and some in-blocks uses */
for (p=b->phi; p; p=p->link)
if (req(p->to, rt)) {
- t1 = f->ntmp++;
- p->to = SYM(t1);
+ s1 = f->nsym++;
+ p->to = SYM(s1);
}
for (i=b->ins; i-b->ins < b->nins; i++) {
- if (t1) {
+ if (s1) {
if (req(i->arg[0], rt))
- i->arg[0] = SYM(t1);
+ i->arg[0] = SYM(s1);
if (req(i->arg[1], rt))
- i->arg[1] = SYM(t1);
+ i->arg[1] = SYM(s1);
}
if (req(i->to, rt)) {
- t1 = f->ntmp++;
- i->to = SYM(t1);
+ s1 = f->nsym++;
+ i->to = SYM(s1);
}
}
- if (t1 && req(b->jmp.arg, rt))
- b->jmp.arg = SYM(t1);
+ if (s1 && req(b->jmp.arg, rt))
+ b->jmp.arg = SYM(s1);
top[b->id] = R;
- bot[b->id] = t1 ? SYM(t1) : R;
+ bot[b->id] = s1 ? SYM(s1) : R;
}
for (b=f->start; b; b=b->link) {
for (p=b->phi; p; p=p->link)
@@ -187,13 +187,13 @@ ssafix(Fn *f, int t)
b->jmp.arg = topdef(b, f);
}
/* add new symbols */
- f->sym = realloc(f->sym, f->ntmp * sizeof f->sym[0]);
+ f->sym = realloc(f->sym, f->nsym * sizeof f->sym[0]);
if (!f->sym)
diag("ssafix: out of memory");
- for (t1=t0; t0<f->ntmp; t0++) {
- f->sym[t0] = f->sym[t];
- snprintf(f->sym[t0].name, NString, "%s%d",
- f->sym[t].name, t0-t1);
+ for (s1=s0; s0<f->nsym; s0++) {
+ f->sym[s0] = f->sym[t];
+ snprintf(f->sym[s0].name, NString, "%s%d",
+ f->sym[t].name, s0-s1);
}
free(top);
free(bot);
