commit 246a48ba94b92e6c1e02964d46269e0903b7a723
parent 1477dffe32ae769c15ee49e77c5f0856bd0f56ea
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Wed, 5 Aug 2015 11:37:10 -0400
start work on comparisons
There are two things I overlooked so far.
1. Binary instructions like cmp that do not have a result
in registers need the size suffix sometimes, for example
when comparing a spill location with a constant.
2. The register allocator needs to be adapted to support the
comparison instruction: it is not possible to compare two
spill locations without using a register.
Diffstat:
6 files changed, 109 insertions(+), 22 deletions(-)
diff --git a/lisc/emit.c b/lisc/emit.c
@@ -40,6 +40,36 @@ static char *rtoa[] = {
[R15D] = "r15d",
};
+static char *rbtoa[] = {
+ [RXX] = "OH GOD!",
+
+
+ [RAX] = "al",
+ [RCX] = "cl",
+ [RDX] = "dl",
+ [RSI] = "sil",
+ [RDI] = "dil",
+ [R8] = "r8b",
+ [R9] = "r9b",
+ [R10] = "r10b",
+ [R11] = "r11b",
+
+ [RBX] = "bl",
+ [R12] = "r12b",
+ [R13] = "r13b",
+ [R14] = "r14b",
+ [R15] = "r15b",
+
+ [RBP] = "bpl",
+ [RSP] = "spl",
+
+};
+
+static char *ctoa[NCmp] = {
+ [Ceq] = "e",
+ [Csle] = "le",
+};
+
static void
eref(Ref r, Fn *fn, FILE *f)
{
@@ -87,7 +117,7 @@ eop(char *op, Ref a, Ref b, Fn *fn, FILE *f)
static void
eins(Ins i, Fn *fn, FILE *f)
{
- static char *opi[] = {
+ static char *otoa[OLast] = {
[OAdd] = "add",
[OSub] = "sub",
};
@@ -103,7 +133,7 @@ eins(Ins i, Fn *fn, FILE *f)
}
if (!req(i.to, i.arg[0]))
eop("mov", i.arg[0], i.to, fn, f);
- eop(opi[i.op], i.arg[1], i.to, fn, f);
+ eop(otoa[i.op], i.arg[1], i.to, fn, f);
break;
case OStore:
i.to = i.arg[1];
@@ -127,9 +157,19 @@ eins(Ins i, Fn *fn, FILE *f)
case OXDiv:
eop("idiv", i.arg[0], R, fn, f);
break;
+ case OXCmp:
+ eop("cmp", i.arg[0], i.arg[1], fn, f);
+ break;
case ONop:
break;
default:
+ if (OXSet <= i.op && i.op <= OXSet1) {
+ eop("mov $0,", i.to, R, fn, f);
+ fprintf(f, "\tset%s %%%s\n",
+ ctoa[i.op-OXSet],
+ rbtoa[BASE(i.to.val)]);
+ break;
+ }
diag("emit: unhandled instruction (3)");
}
}
diff --git a/lisc/isel.c b/lisc/isel.c
@@ -40,15 +40,16 @@ newtmp(int type, Fn *fn)
}
static void
-sel(Ins *i, Fn *fn)
+sel(Ins i, Fn *fn)
{
Ref r0, r1, ra, rd;
- int t;
+ int t, ty, c;
- switch (i->op) {
+ switch (i.op) {
case ODiv:
case ORem:
- switch (fn->tmp[i->to.val].type) {
+ ty = fn->tmp[i.to.val].type;
+ switch (ty) {
default:
diag("isel: invalid division");
case TWord:
@@ -60,35 +61,42 @@ sel(Ins *i, Fn *fn)
rd = REG(RDX);
break;
}
- r0 = i->op == ODiv ? ra : rd;
- r1 = i->op == ODiv ? rd : ra;
- emit(OCopy, i->to, r0, R);
+ r0 = i.op == ODiv ? ra : rd;
+ r1 = i.op == ODiv ? rd : ra;
+ emit(OCopy, i.to, r0, R);
emit(OCopy, R, r1, R);
- if (rtype(i->arg[1]) == RCon) {
+ if (rtype(i.arg[1]) == RCon) {
/* immediates not allowed for
* divisions in x86
*/
- t = newtmp(fn->tmp[i->to.val].type, fn);
+ t = newtmp(ty, fn);
r0 = TMP(t);
} else
- r0 = i->arg[1];
+ r0 = i.arg[1];
emit(OXDiv, R, r0, R);
emit(OSign, rd, ra, R);
- emit(OCopy, ra, i->arg[0], R);
- if (rtype(i->arg[1]) == RCon)
- emit(OCopy, r0, i->arg[1], R);
+ emit(OCopy, ra, i.arg[0], R);
+ if (rtype(i.arg[1]) == RCon)
+ emit(OCopy, r0, i.arg[1], R);
break;
case OAdd:
case OSub:
case OCopy:
- emit(i->op, i->to, i->arg[0], i->arg[1]);
+ emit(i.op, i.to, i.arg[0], i.arg[1]);
break;
default:
+ if (OCmp <= i.op && i.op <= OCmp1) {
+ c = i.op - OCmp;
+ emit(OXSet+c, i.to, R, R);
+ emit(OXCmp, R, i.arg[0], i.arg[1]);
+ break;
+ }
diag("isel: non-exhaustive implementation");
}
}
/* instruction selection
+ * requires use counts (as given by parsing)
*/
void
isel(Fn *fn)
@@ -100,7 +108,7 @@ isel(Fn *fn)
for (b=fn->start; b; b=b->link) {
curi = &insb[NIns];
for (i=&b->ins[b->nins]; i!=b->ins;) {
- sel(--i, fn);
+ sel(*--i, fn);
}
nins = &insb[NIns] - curi;
free(b->ins);
diff --git a/lisc/lisc.h b/lisc/lisc.h
@@ -106,12 +106,20 @@ static inline int rtype(Ref r)
{ return req(r, R) ? -1 : r.type; }
enum {
- OXXX = 0,
+ Ceq,
+ Csle,
+ NCmp,
+};
+
+enum {
+ OXXX,
/* public instruction */
OAdd,
OSub,
ODiv,
ORem,
+ OCmp,
+ OCmp1 = OCmp + NCmp-1,
OStore,
OLoad,
/* reserved instructions */
@@ -120,6 +128,9 @@ enum {
OSwap,
OSign,
OXDiv,
+ OXCmp,
+ OXSet,
+ OXSet1 = OXSet + NCmp-1,
OLast
};
diff --git a/lisc/parse.c b/lisc/parse.c
@@ -23,6 +23,12 @@ OpDesc opdesc[OLast] = {
[OSwap] = { "swap", 2, T },
[OSign] = { "sign", 1, U },
[OXDiv] = { "xdiv", 1, U },
+ [OXCmp] = { "xcmp", 2, U },
+
+ [OCmp+Ceq] = { "ceq", 2, U },
+ [OCmp+Csle] = { "csle", 2, U },
+ [OXSet+Ceq] = { "xsete", 0, U },
+ [OXSet+Csle] = { "xsetle", 0, U },
};
typedef enum {
@@ -40,6 +46,8 @@ typedef enum {
TSub,
TDiv,
TRem,
+ TCeq,
+ TCsle,
TPhi,
TJmp,
TJez,
@@ -123,6 +131,8 @@ lex()
{ "sub", TSub },
{ "div", TDiv },
{ "rem", TRem },
+ { "ceq", TCeq },
+ { "csle", TCsle },
{ "phi", TPhi },
{ "jmp", TJmp },
{ "jez", TJez },
@@ -242,7 +252,7 @@ blocka()
}
static Ref
-tmpref(char *v)
+tmpref(char *v, int use)
{
int t;
@@ -252,6 +262,8 @@ tmpref(char *v)
if (ntmp++ >= NTmp)
err("too many temporaries");
strcpy(tmp[t].name, v);
+ tmp[t].ndef += !use;
+ tmp[t].nuse += use;
return TMP(t);
}
@@ -263,7 +275,7 @@ parseref()
switch (next()) {
case TTmp:
- return tmpref(tokval.str);
+ return tmpref(tokval.str, 1);
case TNum:
c = (Con){.type = CNum, .val = tokval.num};
strcpy(c.label, "");
@@ -400,7 +412,7 @@ parseline(PState ps)
closeblk();
return PLbl;
}
- r = tmpref(tokval.str);
+ r = tmpref(tokval.str, 0);
expect(TEq);
switch (next()) {
case TW:
@@ -428,6 +440,12 @@ parseline(PState ps)
case TRem:
op = ORem;
break;
+ case TCeq:
+ op = OCmp+Ceq;
+ break;
+ case TCsle:
+ op = OCmp+Csle;
+ break;
case TPhi:
if (ps != PPhi)
err("unexpected phi instruction");
diff --git a/lisc/spill.c b/lisc/spill.c
@@ -38,7 +38,7 @@ tmpuse(Ref r, int use, int loop, Fn *fn)
return;
t = &fn->tmp[r.val];
t->nuse += use;
- t->ndef += 1 - use;
+ t->ndef += !use;
t->cost += loop;
}
diff --git a/lisc/test/cup.ssa b/lisc/test/cup.ssa
@@ -0,0 +1,10 @@
+# counts up
+
+@start
+@loop
+ %n0 =w phi @start -1988, @loop %n1
+ %n1 =w add 1, %n0
+ %cmp =w csle %n1, 1000
+ jez %cmp, @end, @loop
+@end
+ ret
