ref: 6a7f16a2b8e1be9639a79726d8195fc6cfae27f1
parent: c910735b4604acd14bffe223d8fc378b9d6f417b
author: Ori Bernstein <[email protected]>
date: Wed Jun 13 20:12:35 EDT 2012
Move towards generating flow graphs properly.
--- a/8/asm.h
+++ b/8/asm.h
@@ -89,6 +89,8 @@
Insn **il;
size_t ni;
+ Bitset *pred;
+ Bitset *succ;
Bitset *use;
Bitset *def;
Bitset *livein;
--- a/8/insns.def
+++ b/8/insns.def
@@ -52,14 +52,14 @@
Insn(Isetge, "\tsetge %v\n", Use(), Def(.l={2}))/* branch instructions */
-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(Icall, "\tcall %v\n", Use(.l={1}), Def())+Insn(Ijmp, "\tjmp %v\n", Use(.l={1}), Def())+Insn(Ijz, "\tjz %v\n", Use(.l={1}), Def())+Insn(Ijnz, "\tjnz %v\n", Use(.l={1}), Def())+Insn(Ijl, "\tjl %v\n", Use(.l={1}), Def())+Insn(Ijle, "\tjle %v\n", Use(.l={1}), Def())+Insn(Ijg, "\tjg %v\n", Use(.l={1}), Def())+Insn(Ijge, "\tjge %v\n", Use(.l={1}), Def())Insn(Iret, "\tret\n", Use(), Def())
/* not really an insn... */
--- a/8/isel.c
+++ b/8/isel.c
@@ -616,7 +616,7 @@
modeidx = 0;
default:
if (isdigit(*p))
- modeidx = strtol(p, &p, 10);
+ modeidx = strtol(p, &p, 10) - 1;
if (*p == 't')
fputc(modenames[insn->args[modeidx]->mode], fd);
@@ -692,9 +692,17 @@
iprintf(fd, s->bb[j]->il[i]);
}
-static Asmbb *mkasmbb()
+static Asmbb *mkasmbb(Bb *bb)
{- return zalloc(sizeof(Asmbb));
+ Asmbb *as;
+
+ as = zalloc(sizeof(Asmbb));
+ as->id = bb->id;
+ as->pred = bsdup(bb->pred);
+ as->succ = bsdup(bb->succ);
+ as->lbls = memdup(bb->lbls, bb->nlbls*sizeof(char*));
+ as->nlbls = bb->nlbls;
+ return as;
}
/* genasm requires all nodes in 'nl' to map cleanly to operations that are
@@ -710,23 +718,21 @@
is.ret = fn->ret;
is.cfg = fn->cfg;
- is.bb = zalloc(fn->cfg->nbb * sizeof(Asmbb*));
+ for (i = 0; i < fn->cfg->nbb; i++)
+ lappend(&is.bb, &is.nbb, mkasmbb(fn->cfg->bb[i]));
- lappend(&is.bb, &is.nbb, mkasmbb());
- is.curbb = is.bb[is.nbb - 1];
+ is.curbb = is.bb[0];
prologue(&is, fn->stksz);
-
for (j = 0; j < fn->cfg->nbb; j++) {- lappend(&is.bb, &is.nbb, mkasmbb());
- is.curbb = is.bb[is.nbb - 1];
+ is.curbb = is.bb[j + 1];
for (i = 0; i < fn->cfg->bb[j]->nnl; i++) {isel(&is, fn->cfg->bb[j]->nl[i]);
}
}
- lappend(&is.bb, &is.nbb, mkasmbb());
is.curbb = is.bb[is.nbb - 1];
epilogue(&is);
+ regalloc(&is);
if (debug)
writeasm(fn, &is, stdout);
--- a/8/ra.c
+++ b/8/ra.c
@@ -49,7 +49,8 @@
for (i = 0; i < Maxarg; i++) {if (!usetab[insn->op].l[i])
break;
- k = usetab[insn->op].l[i];
+ k = usetab[insn->op].l[i] - 1;
+ /* non-registers are handled later */
if (insn->args[k]->type == Locreg)
u[j++] = insn->args[k]->reg.id;
}
@@ -85,7 +86,7 @@
for (i = 0; i < Maxarg; i++) {if (!deftab[insn->op].l[i])
break;
- k = deftab[insn->op].l[i];
+ k = deftab[insn->op].l[i] - 1;
if (insn->args[k]->type == Locreg)
d[j++] = insn->args[k]->reg.id;
}
@@ -124,20 +125,39 @@
void liveness(Isel *s)
{- Cfg *cfg;
- ssize_t i;
+ Bitset *old;
+ Asmbb **bb;
+ size_t nbb;
+ size_t i, j;
int changed;
- cfg = s->cfg;
- cfg = cfg; /* shut up GCC for now */
- for (i = s->nbb - 1; i >= 0; i--)
+ bb = s->bb;
+ nbb = s->nbb;
+ for (i = 0; i < nbb; i++) {bbliveness(s->bb[i]);
+ bb[i]->livein = bsclear(bb[i]->livein);
+ bb[i]->liveout = bsclear(bb[i]->liveout);
+ }
changed = 1;
while (changed) {- for (i = s->nbb - 1; i >= 0; i--) {- }
changed = 0;
+ for (i = 0; i < nbb; i--) {+ old = bsdup(bb[i]->liveout);
+ /* liveout[b] = U(s in succ) livein[s] */
+ for (j = 0; j < bsmax(bb[i]->succ); j++) {+ if (!bshas(bb[i]->succ, j))
+ continue;
+ bsunion(bb[i]->liveout, bb[j]->livein);
+ }
+ /* livein[b] = use[b] U (out[b] \ def[b]) */
+ bb[i]->livein = bsclear(bb[i]->livein);
+ bsunion(bb[i]->livein, bb[i]->liveout);
+ bsdiff(bb[i]->liveout, bb[i]->def);
+ bsunion(bb[i]->liveout, bb[i]->use);
+ if (!changed)
+ changed = !bseq(old, bb[i]->liveout);
+ }
}
}
--- a/opt/cfg.c
+++ b/opt/cfg.c
@@ -21,8 +21,8 @@
bb = zalloc(sizeof(Bb));
bb->id = nextbbid++;
- bb->in = mkbs();
- bb->out = mkbs();
+ bb->pred = mkbs();
+ bb->succ = mkbs();
lappend(&cfg->bb, &cfg->nbb, bb);
return bb;
}
@@ -101,15 +101,15 @@
targ = htget(cfg->lblmap, a->lbl.name);
if (!targ)
die("No bb with label %s", a->lbl.name);- bsput(bb->out, targ->id);
- bsput(targ->in, bb->id);
+ bsput(bb->succ, targ->id);
+ bsput(targ->pred, bb->id);
}
if (b) {targ = htget(cfg->lblmap, b->lbl.name);
if (!targ)
die("No bb with label %s", b->lbl.name);- bsput(bb->out, targ->id);
- bsput(targ->in, bb->id);
+ bsput(bb->succ, targ->id);
+ bsput(targ->pred, bb->id);
}
}
return cfg;
@@ -134,8 +134,8 @@
/* in edges */
fprintf(fd, "In: ");
sep = "";
- for (i = 0; i < bsmax(bb->in); i++) {- if (bshas(bb->in, i)) {+ for (i = 0; i < bsmax(bb->pred); i++) {+ if (bshas(bb->pred, i)) {fprintf(fd, "%s%zd", sep, i);
sep = ",";
}
@@ -145,8 +145,8 @@
/* out edges */
fprintf(fd, "Out: ");
sep = "";
- for (i = 0; i < bsmax(bb->out); i++) {- if (bshas(bb->out, i)) {+ for (i = 0; i < bsmax(bb->succ); i++) {+ if (bshas(bb->succ, i)) {fprintf(fd, "%s%zd", sep, i);
sep = ",";
}
--- a/opt/opt.h
+++ b/opt/opt.h
@@ -19,8 +19,8 @@
size_t nlbls;
Node **nl;
size_t nnl;
- Bitset *in;
- Bitset *out;
+ Bitset *pred;
+ Bitset *succ;
};
/* Takes a reduced block, and returns a flow graph. */
--- a/parse/bitset.c
+++ b/parse/bitset.c
@@ -33,7 +33,7 @@
return bs;
}
-Bitset *dupbs(Bitset *a)
+Bitset *bsdup(Bitset *a)
{Bitset *bs;
@@ -131,6 +131,17 @@
eqsz(a, b);
for (i = 0; i < a->nchunks; i++)
a->chunks[i] &= ~b->chunks[i];
+}
+
+int bseq(Bitset *a, Bitset *b)
+{+ size_t i;
+
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ if (a->chunks[i] != b->chunks[i])
+ return 0;
+ return 1;
}
int bsissubset(Bitset *set, Bitset *sub)
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -155,9 +155,9 @@
if (a->cstrs && b->cstrs)
bsunion(b->cstrs, a->cstrs);
else if (a->cstrs)
- b->cstrs = dupbs(a->cstrs);
+ b->cstrs = bsdup(a->cstrs);
else if (b->cstrs)
- a->cstrs = dupbs(b->cstrs);
+ a->cstrs = bsdup(b->cstrs);
} else {if (!cstrcheck(a, b))
fatal(ctx->line, "%s incompatible with %s near %s", tystr(a), tystr(b), ctxstr(ctx));
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -224,7 +224,7 @@
/* data structures */
Bitset *mkbs(void);
-Bitset *dupbs(Bitset *bs);
+Bitset *bsdup(Bitset *bs);
Bitset *bsclear(Bitset *bs);
void delbs(Bitset *bs);
void bsput(Bitset *bs, uint elt);
@@ -233,6 +233,7 @@
void bsintersect(Bitset *a, Bitset *b);
void bsdiff(Bitset *a, Bitset *b);
int bshas(Bitset *bs, uint elt);
+int bseq(Bitset *a, Bitset *b);
int bsissubset(Bitset *set, Bitset *sub);
size_t bscount(Bitset *bs);
size_t bsmax(Bitset *bs);