ref: c910735b4604acd14bffe223d8fc378b9d6f417b
parent: d79caf7c58ab47c0c36345c3249fea2c7a3d363e
author: Ori Bernstein <[email protected]>
date: Wed Jun 13 19:15:48 EDT 2012
Calculate uses/defs. Maybe.
Currently stubbed in and untested.
--- a/8/Makefile
+++ b/8/Makefile
@@ -1,6 +1,7 @@
BIN=8m
OBJ=isel.o \
main.o \
+ ra.o \
reduce.o \
regalloc.o \
--- a/8/asm.h
+++ b/8/asm.h
@@ -1,4 +1,4 @@
-#define MaxArg 4
+#define Maxarg 4
typedef struct Insn Insn;
typedef struct Loc Loc;
@@ -8,7 +8,7 @@
typedef struct Asmbb Asmbb;
typedef enum {-#define Insn(val, fmt, attr) val,
+#define Insn(val, fmt, use, def) val,
#include "insns.def"
#undef Insn
} AsmOp;
@@ -51,7 +51,7 @@
union {char *lbl;
struct {- long pseudo;
+ long id;
Reg colour;
} reg;
long lit;
@@ -69,8 +69,8 @@
struct Insn {AsmOp op;
- Loc *args[MaxArg];
- int narg;
+ Loc *args[Maxarg];
+ size_t nargs;
};
struct Func {@@ -89,8 +89,8 @@
Insn **il;
size_t ni;
- Bitset *in;
- Bitset *out;
+ Bitset *use;
+ Bitset *def;
Bitset *livein;
Bitset *liveout;
};
@@ -129,6 +129,9 @@
void iprintf(FILE *fd, Insn *insn);
/* register allocation */
+void regalloc(Isel *s);
+size_t uses(Insn *i, long *uses);
+size_t defs(Insn *i, long *defs);
extern const char *regnames[];
extern const Mode regmodes[];
--- a/8/insns.def
+++ b/8/insns.def
@@ -6,7 +6,7 @@
%m - A memory location.
%l - A location (either register or memory)
%x - Any value.
- %[0-9]*t - Mode of an operand. The optional number
+ %[1-9]*t - Mode of an operand. The optional number
preceeding it is the operand desired for
the mode.
%v - a value (ie, immediate integer or label)
@@ -13,52 +13,54 @@
Currently, there aren't any attrs, because none were needed yet.
Eventually, they'll probably include flag setting and so on.
- */
+ For technical reasons, the indexing on use and def statments is 1-based,
+ instead of 0-based. (0 is the sentinel value).
+*/
/* Note, the mov instruction is specified in an overly general manner. */
-Insn(Inone, "BAD_INSN", 0)
-Insn(Imov, "\tmov%t %x,%x\n", 0)
-Insn(Imovz, "\tmovz%0t%1t %x,%x\n", 0)
-Insn(Imovs, "\tmovs%0t%1t %x,%x\n", 0)
-Insn(Ilea, "\tlea%t %x,%x\n", 0)
+Insn(Inone, "BAD_INSN", Use(), Def())
+Insn(Imov, "\tmov%t %x,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Imovz, "\tmovz%1t%2t %x,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Imovs, "\tmovs%1t%2t %x,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Ilea, "\tlea%t %x,%x\n", Use(.l={1,2}), Def(.l={2}))-Insn(Iadd, "\tadd%t %r,%x\n", 0)
-Insn(Isub, "\tsub%t %r,%x\n", 0)
-Insn(Imul, "\tmul%t %r\n", 0)
-Insn(Idiv, "\tdiv%t %r\n", 0)
-Insn(Ineg, "\tneg%t %r\n", 0)
-Insn(Iand, "\tand%t %r,%x\n", 0)
-Insn(Ior, "\tor%t %r,%x\n", 0)
-Insn(Ixor, "\txor%t %r,%x\n", 0)
-Insn(Inot, "\tnot%t %x\n", 0)
-Insn(Ishl, "\tsal%1t %r,%x\n", 0)
-Insn(Isar, "\tshr%1t %r,%x\n", 0)
-Insn(Ishr, "\tshr%1t %r,%x\n", 0)
+Insn(Iadd, "\tadd%t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Isub, "\tsub%t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Imul, "\tmul%t %r\n", Use(.l={1},.r={Reax}), Def(.r={Reax,Redx}))+Insn(Idiv, "\tdiv%t %r\n", Use(.l={1},.r={Reax,Redx}), Def(.l={Reax,Redx}))+Insn(Ineg, "\tneg%t %r\n", Use(.l={1}), Def(.l={1}))+Insn(Iand, "\tand%t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Ior, "\tor%t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Ixor, "\txor%t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Inot, "\tnot%t %x\n", Use(.l={1}), Def(.l={1}))+Insn(Ishl, "\tsal%2t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Isar, "\tshr%2t %r,%x\n", Use(.l={1,2}), Def(.l={2}))+Insn(Ishr, "\tshr%2t %r,%x\n", Use(.l={1,2}), Def(.l={2}))-Insn(Itest, "\ttest%t %r,%r\n", 0)
-Insn(Icmp, "\tcmp%t %r,%r\n", 0)
+Insn(Itest, "\ttest%t %r,%r\n", Use(.l={1,2}), Def(.l={2}))+Insn(Icmp, "\tcmp%t %r,%r\n", Use(.l={1,2}), Def(.l={2}))-Insn(Ipush, "\tpush%t %r\n", 0)
-Insn(Ipop, "\tpop%t %r\n", 0)
+Insn(Ipush, "\tpush%t %r\n", Use(.l={1}), Def())+Insn(Ipop, "\tpop%t %r\n", Use(.l={1}), Def())/* branch instructions */
-Insn(Isetz, "\tsetz %v\n", 0)
-Insn(Isetnz, "\tsetnz %v\n", 0)
-Insn(Isetlt, "\tsetlt %v\n", 0)
-Insn(Isetle, "\tsetle %v\n", 0)
-Insn(Isetgt, "\tsetgt %v\n", 0)
-Insn(Isetge, "\tsetge %v\n", 0)
+Insn(Isetz, "\tsetz %v\n", Use(), Def(.l={2}))+Insn(Isetnz, "\tsetnz %v\n", Use(), Def(.l={2}))+Insn(Isetlt, "\tsetlt %v\n", Use(), Def(.l={2}))+Insn(Isetle, "\tsetle %v\n", Use(), Def(.l={2}))+Insn(Isetgt, "\tsetgt %v\n", Use(), Def(.l={2}))+Insn(Isetge, "\tsetge %v\n", Use(), Def(.l={2}))/* branch instructions */
-Insn(Icall, "\tcall %v\n", 0)
-Insn(Ijmp, "\tjmp %v\n", 0)
-Insn(Ijz, "\tjz %v\n", 0)
-Insn(Ijnz, "\tjnz %v\n", 0)
-Insn(Ijl, "\tjl %v\n", 0)
-Insn(Ijle, "\tjle %v\n", 0)
-Insn(Ijg, "\tjg %v\n", 0)
-Insn(Ijge, "\tjge %v\n", 0)
-Insn(Iret, "\tret\n", 0)
+Insn(Icall, "\tcall %v\n", Use(.l={2}), Def())+Insn(Ijmp, "\tjmp %v\n", Use(.l={2}), Def())+Insn(Ijz, "\tjz %v\n", Use(.l={2}), Def())+Insn(Ijnz, "\tjnz %v\n", Use(.l={2}), Def())+Insn(Ijl, "\tjl %v\n", Use(.l={2}), Def())+Insn(Ijle, "\tjle %v\n", Use(.l={2}), Def())+Insn(Ijg, "\tjg %v\n", Use(.l={2}), Def())+Insn(Ijge, "\tjge %v\n", Use(.l={2}), Def())+Insn(Iret, "\tret\n", Use(), Def())
/* not really an insn... */
-Insn(Ilbl, "%v:\n", 0)
+Insn(Ilbl, "%v:\n", Use(), Def())
--- a/8/isel.c
+++ b/8/isel.c
@@ -16,7 +16,7 @@
/* string tables */
char *insnfmts[] = {-#define Insn(val, fmt, attr) fmt,
+#define Insn(val, fmt, use, def) fmt,
#include "insns.def"
#undef Insn
};
@@ -126,9 +126,7 @@
i->op = op;
while ((l = va_arg(ap, Loc*)) != NULL)
i->args[n++] = l;
- if (op == Imov)
- assert(i->args[1] != NULL);
- i->narg = n;
+ i->nargs = n;
return i;
}
@@ -554,7 +552,7 @@
break;
case Locreg:
if (l->reg.colour == Rnone)
- fprintf(fd, "%%P.%ld", l->reg.pseudo);
+ fprintf(fd, "%%P.%ld", l->reg.id);
else
fprintf(fd, "%s", regnames[l->reg.colour]);
break;
--- a/8/ra.c
+++ b/8/ra.c
@@ -11,22 +11,137 @@
#include <unistd.h>
#include "parse.h"
+#include "opt.h"
#include "asm.h"
-struct Asmbb {- int id;
- char **lbls;
- size_t nlbls;
- Insn **insns;
- size_t ninsns;
- Bitset *livein;
- Bitset *liveout;
+typedef struct Usage Usage;
+struct Usage {+ int l[Maxarg + 1];
+ int r[Maxarg + 1];
};
-void adduses(Insn *i, Bitset *bs)
+Usage usetab[] = {+#define Use(...) {__VA_ARGS__}+#define Insn(i, fmt, use, def) use,
+#include "insns.def"
+#undef Insn
+#undef Use
+};
+
+Usage deftab[] = {+#define Def(...) {__VA_ARGS__}+#define Insn(i, fmt, use, def) def,
+#include "insns.def"
+#undef Insn
+#undef Def
+};
+
+size_t uses(Insn *insn, long *u)
{+ size_t i, j;
+ int k;
+ Loc *m;
+
+ j = 0;
+ /* Add all the registers used and defined. Duplicates
+ * in this list are fine, since they're being added to
+ * a set anyways */
+ for (i = 0; i < Maxarg; i++) {+ if (!usetab[insn->op].l[i])
+ break;
+ k = usetab[insn->op].l[i];
+ if (insn->args[k]->type == Locreg)
+ u[j++] = insn->args[k]->reg.id;
+ }
+ /* some insns don't reflect their defs in the args.
+ * These are explictly listed in the insn description */
+ for (i = 0; i < Maxarg; i++) {+ if (!usetab[insn->op].r[i])
+ break;
+ /* not a leak; physical registers get memoized */
+ u[j++] = locphysreg(usetab[insn->op].r[i])->reg.id;
+ }
+ /* If the registers are in an address calculation,
+ * they're used no matter what. */
+ for (i = 0; i < insn->nargs; i++) {+ m = insn->args[i];
+ if (m->type != Locmem && m->type != Locmeml)
+ break;
+ u[j++] = m->mem.base->reg.id;
+ if (m->mem.idx)
+ u[j++] = m->mem.idx->reg.id;
+ }
+ return j;
}
-void subdefs(Insn *i, Bitset *bs)
+size_t defs(Insn *insn, long *d)
{+ size_t i, j;
+ int k;
+
+ /* Add all the registers dsed and defined. Ddplicates
+ * in this list are fine, since they're being added to
+ * a set anyways */
+ for (i = 0; i < Maxarg; i++) {+ if (!deftab[insn->op].l[i])
+ break;
+ k = deftab[insn->op].l[i];
+ if (insn->args[k]->type == Locreg)
+ d[j++] = insn->args[k]->reg.id;
+ }
+ /* some insns don't reflect their defs in the args.
+ * These are explictly listed in the insn description */
+ for (i = 0; i < Maxarg; i++) {+ if (!deftab[insn->op].r[i])
+ break;
+ /* not a leak; physical registers get memoized */
+ d[j++] = locphysreg(deftab[insn->op].r[i])->reg.id;
+ }
+ return j;
+}
+
+void bbliveness(Asmbb *bb)
+{+ /* up to 2 registers per memloc, so
+ * 2*Maxarg is the maximum number of
+ * uses or defs we can see */
+ long u[2*Maxarg], d[2*Maxarg];
+ size_t nu, nd;
+ size_t i, j;
+
+ bb->use = bsclear(bb->use);
+ bb->def = bsclear(bb->def);
+ for (i = 0; i < bb->ni; i++) {+ nu = uses(bb->il[i], u);
+ nd = uses(bb->il[i], d);
+ for (j = 0; j < nu; j++)
+ if (!bshas(bb->def, u[j]))
+ bsput(bb->use, u[j]);
+ for (j = 0; j < nd; j++)
+ bsput(bb->def, d[j]);
+ }
+}
+
+void liveness(Isel *s)
+{+ Cfg *cfg;
+ ssize_t i;
+ int changed;
+
+ cfg = s->cfg;
+ cfg = cfg; /* shut up GCC for now */
+ for (i = s->nbb - 1; i >= 0; i--)
+ bbliveness(s->bb[i]);
+
+ changed = 1;
+ while (changed) {+ for (i = s->nbb - 1; i >= 0; i--) {+ }
+ changed = 0;
+ }
+}
+
+void regalloc(Isel *s)
+{+ liveness(s);
}
--- a/8/regalloc.c
+++ b/8/regalloc.c
@@ -73,12 +73,12 @@
Loc *locreg(Mode m)
{Loc *l;
- static long nextpseudo = 0;
+ static long nextid = 0;
l = zalloc(sizeof(Loc));
l->type = Locreg;
l->mode = m;
- l->reg.pseudo = nextpseudo++;
+ l->reg.id = nextid++;
return l;
}
--- a/parse/bitset.c
+++ b/parse/bitset.c
@@ -44,6 +44,17 @@
return bs;
}
+Bitset *bsclear(Bitset *bs)
+{+ size_t i;
+
+ if (!bs)
+ return mkbs();
+ for (i = 0; i < bs->nchunks; i++)
+ bs->chunks[i] = 0;
+ return bs;
+}
+
size_t bscount(Bitset *bs)
{size_t i, j, n;
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -225,6 +225,7 @@
/* data structures */
Bitset *mkbs(void);
Bitset *dupbs(Bitset *bs);
+Bitset *bsclear(Bitset *bs);
void delbs(Bitset *bs);
void bsput(Bitset *bs, uint elt);
void bsdel(Bitset *bs, uint elt);