commit 5fc8104e00187335411e35ec951bef53562c8fcd
parent 78bf28f56e7dcdd89efba5c69bd90ed858658162
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Thu, 13 Aug 2015 16:10:54 -0400
major lifting: get rid of RReg
I've been septic since I introduced it, this commit
proves that it costs more than it helps. I've also fixed
a bad bug in rega() where I alloc'ed the wrong size for
internal arrays. Enums now have names so I can use them
to cast in gdb to get the name corresponding to a constant.
Diffstat:
8 files changed, 97 insertions(+), 142 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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;
