diff options
Diffstat (limited to 'lcc/src/gen.c')
| -rwxr-xr-x | lcc/src/gen.c | 830 |
1 files changed, 830 insertions, 0 deletions
diff --git a/lcc/src/gen.c b/lcc/src/gen.c new file mode 100755 index 0000000..ab8506a --- /dev/null +++ b/lcc/src/gen.c @@ -0,0 +1,830 @@ +#include "c.h"
+
+
+#define readsreg(p) \
+ (generic((p)->op)==INDIR && (p)->kids[0]->op==VREG+P)
+#define setsrc(d) ((d) && (d)->x.regnode && \
+ (d)->x.regnode->set == src->x.regnode->set && \
+ (d)->x.regnode->mask&src->x.regnode->mask)
+
+#define relink(a, b) ((b)->x.prev = (a), (a)->x.next = (b))
+
+static Symbol askfixedreg(Symbol);
+static Symbol askreg(Symbol, unsigned*);
+static void blkunroll(int, int, int, int, int, int, int[]);
+static void docall(Node);
+static void dumpcover(Node, int, int);
+static void dumpregs(char *, char *, char *);
+static void dumprule(int);
+static void dumptree(Node);
+static unsigned emitasm(Node, int);
+static void genreload(Node, Symbol, int);
+static void genspill(Symbol, Node, Symbol);
+static Symbol getreg(Symbol, unsigned*, Node);
+static int getrule(Node, int);
+static void linearize(Node, Node);
+static int moveself(Node);
+static void prelabel(Node);
+static Node* prune(Node, Node*);
+static void putreg(Symbol);
+static void ralloc(Node);
+static void reduce(Node, int);
+static int reprune(Node*, int, int, Node);
+static int requate(Node);
+static Node reuse(Node, int);
+static void rewrite(Node);
+static Symbol spillee(Symbol, unsigned mask[], Node);
+static void spillr(Symbol, Node);
+static int uses(Node, Regnode);
+
+int offset;
+
+int maxoffset;
+
+int framesize;
+int argoffset;
+
+int maxargoffset;
+
+int dalign, salign;
+int bflag = 0; /* omit */
+int dflag = 0;
+
+int swap;
+
+unsigned (*emitter)(Node, int) = emitasm;
+static char NeedsReg[] = {
+ 0, /* unused */
+ 1, /* CNST */
+ 0, 0, /* ARG ASGN */
+ 1, /* INDIR */
+ 0, 0, 1, 1, /* - - CVF CVI */
+ 1, 0, 1, 1, /* CVP - CVU NEG */
+ 1, /* CALL */
+ 1, /* LOAD */
+ 0, /* RET */
+ 1, 1, 1, /* ADDRG ADDRF ADDRL */
+ 1, 1, 1, 1, 1, /* ADD SUB LSH MOD RSH */
+ 1, 1, 1, 1, /* BAND BCOM BOR BXOR */
+ 1, 1, /* DIV MUL */
+ 0, 0, 0, 0, 0, 0, /* EQ GE GT LE LT NE */
+ 0, 0 /* JUMP LABEL */
+};
+Node head;
+
+unsigned freemask[2];
+unsigned usedmask[2];
+unsigned tmask[2];
+unsigned vmask[2];
+Symbol mkreg(char *fmt, int n, int mask, int set) {
+ Symbol p;
+
+ NEW0(p, PERM);
+ p->name = p->x.name = stringf(fmt, n);
+ NEW0(p->x.regnode, PERM);
+ p->x.regnode->number = n;
+ p->x.regnode->mask = mask<<n;
+ p->x.regnode->set = set;
+ return p;
+}
+Symbol mkwildcard(Symbol *syms) {
+ Symbol p;
+
+ NEW0(p, PERM);
+ p->name = p->x.name = "wildcard";
+ p->x.wildcard = syms;
+ return p;
+}
+void mkauto(Symbol p) {
+ assert(p->sclass == AUTO);
+ offset = roundup(offset + p->type->size, p->type->align);
+ p->x.offset = -offset;
+ p->x.name = stringd(-offset);
+}
+void blockbeg(Env *e) {
+ e->offset = offset;
+ e->freemask[IREG] = freemask[IREG];
+ e->freemask[FREG] = freemask[FREG];
+}
+void blockend(Env *e) {
+ if (offset > maxoffset)
+ maxoffset = offset;
+ offset = e->offset;
+ freemask[IREG] = e->freemask[IREG];
+ freemask[FREG] = e->freemask[FREG];
+}
+int mkactual(int align, int size) {
+ int n = roundup(argoffset, align);
+
+ argoffset = n + size;
+ return n;
+}
+static void docall(Node p) {
+ p->syms[1] = p->syms[0];
+ p->syms[0] = intconst(argoffset);
+ if (argoffset > maxargoffset)
+ maxargoffset = argoffset;
+ argoffset = 0;
+}
+void blkcopy(int dreg, int doff, int sreg, int soff, int size, int tmp[]) {
+ assert(size >= 0);
+ if (size == 0)
+ return;
+ else if (size <= 2)
+ blkunroll(size, dreg, doff, sreg, soff, size, tmp);
+ else if (size == 3) {
+ blkunroll(2, dreg, doff, sreg, soff, 2, tmp);
+ blkunroll(1, dreg, doff+2, sreg, soff+2, 1, tmp);
+ }
+ else if (size <= 16) {
+ blkunroll(4, dreg, doff, sreg, soff, size&~3, tmp);
+ blkcopy(dreg, doff+(size&~3),
+ sreg, soff+(size&~3), size&3, tmp);
+ }
+ else
+ (*IR->x.blkloop)(dreg, doff, sreg, soff, size, tmp);
+}
+static void blkunroll(int k, int dreg, int doff, int sreg, int soff, int size, int tmp[]) {
+ int i;
+
+ assert(IR->x.max_unaligned_load);
+ if (k > IR->x.max_unaligned_load
+ && (k > salign || k > dalign))
+ k = IR->x.max_unaligned_load;
+ for (i = 0; i+k < size; i += 2*k) {
+ (*IR->x.blkfetch)(k, soff+i, sreg, tmp[0]);
+ (*IR->x.blkfetch)(k, soff+i+k, sreg, tmp[1]);
+ (*IR->x.blkstore)(k, doff+i, dreg, tmp[0]);
+ (*IR->x.blkstore)(k, doff+i+k, dreg, tmp[1]);
+ }
+ if (i < size) {
+ (*IR->x.blkfetch)(k, i+soff, sreg, tmp[0]);
+ (*IR->x.blkstore)(k, i+doff, dreg, tmp[0]);
+ }
+}
+void parseflags(int argc, char *argv[]) {
+ int i;
+
+ for (i = 0; i < argc; i++)
+ if (strcmp(argv[i], "-d") == 0)
+ dflag = 1;
+ else if (strcmp(argv[i], "-b") == 0) /* omit */
+ bflag = 1; /* omit */
+}
+static int getrule(Node p, int nt) {
+ int rulenum;
+
+ assert(p);
+ rulenum = (*IR->x._rule)(p->x.state, nt);
+ if (!rulenum) {
+ fprint(stderr, "(%x->op=%s at %w is corrupt.)\n", p, opname(p->op), &src);
+ assert(0);
+ }
+ return rulenum;
+}
+static void reduce(Node p, int nt) {
+ int rulenum, i;
+ short *nts;
+ Node kids[10];
+
+ p = reuse(p, nt);
+ rulenum = getrule(p, nt);
+ nts = IR->x._nts[rulenum];
+ (*IR->x._kids)(p, rulenum, kids);
+ for (i = 0; nts[i]; i++)
+ reduce(kids[i], nts[i]);
+ if (IR->x._isinstruction[rulenum]) {
+ assert(p->x.inst == 0 || p->x.inst == nt);
+ p->x.inst = nt;
+ if (p->syms[RX] && p->syms[RX]->temporary) {
+ debug(fprint(stderr, "(using %s)\n", p->syms[RX]->name));
+ p->syms[RX]->x.usecount++;
+ }
+ }
+}
+static Node reuse(Node p, int nt) {
+ struct _state {
+ short cost[1];
+ };
+ Symbol r = p->syms[RX];
+
+ if (generic(p->op) == INDIR && p->kids[0]->op == VREG+P
+ && r->u.t.cse && p->x.mayrecalc
+ && ((struct _state*)r->u.t.cse->x.state)->cost[nt] == 0)
+ return r->u.t.cse;
+ else
+ return p;
+}
+
+int mayrecalc(Node p) {
+ int op;
+
+ assert(p && p->syms[RX]);
+ if (p->syms[RX]->u.t.cse == NULL)
+ return 0;
+ op = generic(p->syms[RX]->u.t.cse->op);
+ if (op == CNST || op == ADDRF || op == ADDRG || op == ADDRL) {
+ p->x.mayrecalc = 1;
+ return 1;
+ } else
+ return 0;
+}
+static Node *prune(Node p, Node pp[]) {
+ if (p == NULL)
+ return pp;
+ p->x.kids[0] = p->x.kids[1] = p->x.kids[2] = NULL;
+ if (p->x.inst == 0)
+ return prune(p->kids[1], prune(p->kids[0], pp));
+ else if (p->syms[RX] && p->syms[RX]->temporary
+ && p->syms[RX]->x.usecount < 2) {
+ p->x.inst = 0;
+ debug(fprint(stderr, "(clobbering %s)\n", p->syms[RX]->name));
+ return prune(p->kids[1], prune(p->kids[0], pp));
+ }
+ else {
+ prune(p->kids[1], prune(p->kids[0], &p->x.kids[0]));
+ *pp = p;
+ return pp + 1;
+ }
+}
+
+#define ck(i) return (i) ? 0 : LBURG_MAX
+
+int range(Node p, int lo, int hi) {
+ Symbol s = p->syms[0];
+
+ switch (specific(p->op)) {
+ case ADDRF+P:
+ case ADDRL+P: ck(s->x.offset >= lo && s->x.offset <= hi);
+ case CNST+I: ck(s->u.c.v.i >= lo && s->u.c.v.i <= hi);
+ case CNST+U: ck(s->u.c.v.u >= lo && s->u.c.v.u <= hi);
+ case CNST+P: ck(s->u.c.v.p == 0 && lo <= 0 && hi >= 0);
+ }
+ return LBURG_MAX;
+}
+static void dumptree(Node p) {
+ if (p->op == VREG+P && p->syms[0]) {
+ fprint(stderr, "VREGP(%s)", p->syms[0]->name);
+ return;
+ } else if (generic(p->op) == LOAD) {
+ fprint(stderr, "LOAD(");
+ dumptree(p->kids[0]);
+ fprint(stderr, ")");
+ return;
+ }
+ fprint(stderr, "%s(", opname(p->op));
+ switch (generic(p->op)) {
+ case CNST: case LABEL:
+ case ADDRG: case ADDRF: case ADDRL:
+ if (p->syms[0])
+ fprint(stderr, "%s", p->syms[0]->name);
+ break;
+ case RET:
+ if (p->kids[0])
+ dumptree(p->kids[0]);
+ break;
+ case CVF: case CVI: case CVP: case CVU: case JUMP:
+ case ARG: case BCOM: case NEG: case INDIR:
+ dumptree(p->kids[0]);
+ break;
+ case CALL:
+ if (optype(p->op) != B) {
+ dumptree(p->kids[0]);
+ break;
+ }
+ /* else fall thru */
+ case EQ: case NE: case GT: case GE: case LE: case LT:
+ case ASGN: case BOR: case BAND: case BXOR: case RSH: case LSH:
+ case ADD: case SUB: case DIV: case MUL: case MOD:
+ dumptree(p->kids[0]);
+ fprint(stderr, ", ");
+ dumptree(p->kids[1]);
+ break;
+ default: assert(0);
+ }
+ fprint(stderr, ")");
+}
+static void dumpcover(Node p, int nt, int in) {
+ int rulenum, i;
+ short *nts;
+ Node kids[10];
+
+ p = reuse(p, nt);
+ rulenum = getrule(p, nt);
+ nts = IR->x._nts[rulenum];
+ fprint(stderr, "dumpcover(%x) = ", p);
+ for (i = 0; i < in; i++)
+ fprint(stderr, " ");
+ dumprule(rulenum);
+ (*IR->x._kids)(p, rulenum, kids);
+ for (i = 0; nts[i]; i++)
+ dumpcover(kids[i], nts[i], in+1);
+}
+
+static void dumprule(int rulenum) {
+ assert(rulenum);
+ fprint(stderr, "%s / %s", IR->x._string[rulenum],
+ IR->x._templates[rulenum]);
+ if (!IR->x._isinstruction[rulenum])
+ fprint(stderr, "\n");
+}
+static unsigned emitasm(Node p, int nt) {
+ int rulenum;
+ short *nts;
+ char *fmt;
+ Node kids[10];
+
+ p = reuse(p, nt);
+ rulenum = getrule(p, nt);
+ nts = IR->x._nts[rulenum];
+ fmt = IR->x._templates[rulenum];
+ assert(fmt);
+ if (IR->x._isinstruction[rulenum] && p->x.emitted)
+ print("%s", p->syms[RX]->x.name);
+ else if (*fmt == '#')
+ (*IR->x.emit2)(p);
+ else {
+ if (*fmt == '?') {
+ fmt++;
+ assert(p->kids[0]);
+ if (p->syms[RX] == p->x.kids[0]->syms[RX])
+ while (*fmt++ != '\n')
+ ;
+ }
+ for ((*IR->x._kids)(p, rulenum, kids); *fmt; fmt++)
+ if (*fmt != '%')
+ (void)putchar(*fmt);
+ else if (*++fmt == 'F')
+ print("%d", framesize);
+ else if (*fmt >= '0' && *fmt <= '9')
+ emitasm(kids[*fmt - '0'], nts[*fmt - '0']);
+ else if (*fmt >= 'a' && *fmt < 'a' + NELEMS(p->syms))
+ fputs(p->syms[*fmt - 'a']->x.name, stdout);
+ else
+ (void)putchar(*fmt);
+ }
+ return 0;
+}
+void emit(Node p) {
+ for (; p; p = p->x.next) {
+ assert(p->x.registered);
+ if (p->x.equatable && requate(p) || moveself(p))
+ ;
+ else
+ (*emitter)(p, p->x.inst);
+ p->x.emitted = 1;
+ }
+}
+static int moveself(Node p) {
+ return p->x.copy
+ && p->syms[RX]->x.name == p->x.kids[0]->syms[RX]->x.name;
+}
+int move(Node p) {
+ p->x.copy = 1;
+ return 1;
+}
+static int requate(Node q) {
+ Symbol src = q->x.kids[0]->syms[RX];
+ Symbol tmp = q->syms[RX];
+ Node p;
+ int n = 0;
+
+ debug(fprint(stderr, "(requate(%x): tmp=%s src=%s)\n", q, tmp->x.name, src->x.name));
+ for (p = q->x.next; p; p = p->x.next)
+ if (p->x.copy && p->syms[RX] == src
+ && p->x.kids[0]->syms[RX] == tmp)
+ debug(fprint(stderr, "(requate arm 0 at %x)\n", p)),
+ p->syms[RX] = tmp;
+ else if (setsrc(p->syms[RX]) && !moveself(p) && !readsreg(p))
+ return 0;
+ else if (p->x.spills)
+ return 0;
+ else if (generic(p->op) == CALL && p->x.next)
+ return 0;
+ else if (p->op == LABEL+V && p->x.next)
+ return 0;
+ else if (p->syms[RX] == tmp && readsreg(p))
+ debug(fprint(stderr, "(requate arm 5 at %x)\n", p)),
+ n++;
+ else if (p->syms[RX] == tmp)
+ break;
+ debug(fprint(stderr, "(requate arm 7 at %x)\n", p));
+ assert(n > 0);
+ for (p = q->x.next; p; p = p->x.next)
+ if (p->syms[RX] == tmp && readsreg(p)) {
+ p->syms[RX] = src;
+ if (--n <= 0)
+ break;
+ }
+ return 1;
+}
+static void prelabel(Node p) {
+ if (p == NULL)
+ return;
+ prelabel(p->kids[0]);
+ prelabel(p->kids[1]);
+ if (NeedsReg[opindex(p->op)])
+ setreg(p, (*IR->x.rmap)(opkind(p->op)));
+ switch (generic(p->op)) {
+ case ADDRF: case ADDRL:
+ if (p->syms[0]->sclass == REGISTER)
+ p->op = VREG+P;
+ break;
+ case INDIR:
+ if (p->kids[0]->op == VREG+P)
+ setreg(p, p->kids[0]->syms[0]);
+ break;
+ case ASGN:
+ if (p->kids[0]->op == VREG+P)
+ rtarget(p, 1, p->kids[0]->syms[0]);
+ break;
+ case CVI: case CVU: case CVP:
+ if (optype(p->op) != F
+ && opsize(p->op) <= p->syms[0]->u.c.v.i)
+ p->op = LOAD + opkind(p->op);
+ break;
+ }
+ (IR->x.target)(p);
+}
+void setreg(Node p, Symbol r) {
+ p->syms[RX] = r;
+}
+void rtarget(Node p, int n, Symbol r) {
+ Node q = p->kids[n];
+
+ assert(q);
+ assert(r);
+ assert(r->sclass == REGISTER || !r->x.wildcard);
+ assert(q->syms[RX]);
+ if (r != q->syms[RX] && !q->syms[RX]->x.wildcard) {
+ q = newnode(LOAD + opkind(q->op),
+ q, NULL, q->syms[0]);
+ if (r->u.t.cse == p->kids[n])
+ r->u.t.cse = q;
+ p->kids[n] = p->x.kids[n] = q;
+ q->x.kids[0] = q->kids[0];
+ }
+ setreg(q, r);
+ debug(fprint(stderr, "(targeting %x->x.kids[%d]=%x to %s)\n", p, n, p->kids[n], r->x.name));
+}
+static void rewrite(Node p) {
+ assert(p->x.inst == 0);
+ prelabel(p);
+ debug(dumptree(p));
+ debug(fprint(stderr, "\n"));
+ (*IR->x._label)(p);
+ debug(dumpcover(p, 1, 0));
+ reduce(p, 1);
+}
+Node gen(Node forest) {
+ int i;
+ struct node sentinel;
+ Node dummy, p;
+
+ head = forest;
+ for (p = forest; p; p = p->link) {
+ assert(p->count == 0);
+ if (generic(p->op) == CALL)
+ docall(p);
+ else if ( generic(p->op) == ASGN
+ && generic(p->kids[1]->op) == CALL)
+ docall(p->kids[1]);
+ else if (generic(p->op) == ARG)
+ (*IR->x.doarg)(p);
+ rewrite(p);
+ p->x.listed = 1;
+ }
+ for (p = forest; p; p = p->link)
+ prune(p, &dummy);
+ relink(&sentinel, &sentinel);
+ for (p = forest; p; p = p->link)
+ linearize(p, &sentinel);
+ forest = sentinel.x.next;
+ assert(forest);
+ sentinel.x.next->x.prev = NULL;
+ sentinel.x.prev->x.next = NULL;
+ for (p = forest; p; p = p->x.next)
+ for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
+ assert(p->x.kids[i]->syms[RX]);
+ if (p->x.kids[i]->syms[RX]->temporary) {
+ p->x.kids[i]->x.prevuse =
+ p->x.kids[i]->syms[RX]->x.lastuse;
+ p->x.kids[i]->syms[RX]->x.lastuse = p->x.kids[i];
+ }
+ }
+ for (p = forest; p; p = p->x.next) {
+ ralloc(p);
+ if (p->x.listed && NeedsReg[opindex(p->op)]
+ && (*IR->x.rmap)(opkind(p->op))) {
+ assert(generic(p->op) == CALL || generic(p->op) == LOAD);
+ putreg(p->syms[RX]);
+ }
+ }
+ return forest;
+}
+int notarget(Node p) {
+ return p->syms[RX]->x.wildcard ? 0 : LBURG_MAX;
+}
+static void putreg(Symbol r) {
+ assert(r && r->x.regnode);
+ freemask[r->x.regnode->set] |= r->x.regnode->mask;
+ debug(dumpregs("(freeing %s)\n", r->x.name, NULL));
+}
+static Symbol askfixedreg(Symbol s) {
+ Regnode r = s->x.regnode;
+ int n = r->set;
+
+ if (r->mask&~freemask[n])
+ return NULL;
+ else {
+ freemask[n] &= ~r->mask;
+ usedmask[n] |= r->mask;
+ return s;
+ }
+}
+static Symbol askreg(Symbol rs, unsigned rmask[]) {
+ int i;
+
+ if (rs->x.wildcard == NULL)
+ return askfixedreg(rs);
+ for (i = 31; i >= 0; i--) {
+ Symbol r = rs->x.wildcard[i];
+ if (r != NULL
+ && !(r->x.regnode->mask&~rmask[r->x.regnode->set])
+ && askfixedreg(r))
+ return r;
+ }
+ return NULL;
+}
+
+static Symbol getreg(Symbol s, unsigned mask[], Node p) {
+ Symbol r = askreg(s, mask);
+ if (r == NULL) {
+ r = spillee(s, mask, p);
+ assert(r && r->x.regnode);
+ spill(r->x.regnode->mask, r->x.regnode->set, p);
+ r = askreg(s, mask);
+ }
+ assert(r && r->x.regnode);
+ r->x.regnode->vbl = NULL;
+ return r;
+}
+int askregvar(Symbol p, Symbol regs) {
+ Symbol r;
+
+ assert(p);
+ if (p->sclass != REGISTER)
+ return 0;
+ else if (!isscalar(p->type)) {
+ p->sclass = AUTO;
+ return 0;
+ }
+ else if (p->temporary) {
+ p->x.name = "?";
+ return 1;
+ }
+ else if ((r = askreg(regs, vmask)) != NULL) {
+ p->x.regnode = r->x.regnode;
+ p->x.regnode->vbl = p;
+ p->x.name = r->x.name;
+ debug(dumpregs("(allocating %s to symbol %s)\n", p->x.name, p->name));
+ return 1;
+ }
+ else {
+ p->sclass = AUTO;
+ return 0;
+ }
+}
+static void linearize(Node p, Node next) {
+ int i;
+
+ for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++)
+ linearize(p->x.kids[i], next);
+ relink(next->x.prev, p);
+ relink(p, next);
+ debug(fprint(stderr, "(listing %x)\n", p));
+}
+static void ralloc(Node p) {
+ int i;
+ unsigned mask[2];
+
+ mask[0] = tmask[0];
+ mask[1] = tmask[1];
+ assert(p);
+ debug(fprint(stderr, "(rallocing %x)\n", p));
+ for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
+ Node kid = p->x.kids[i];
+ Symbol r = kid->syms[RX];
+ assert(r && kid->x.registered);
+ if (r->sclass != REGISTER && r->x.lastuse == kid)
+ putreg(r);
+ }
+ if (!p->x.registered && NeedsReg[opindex(p->op)]
+ && (*IR->x.rmap)(opkind(p->op))) {
+ Symbol sym = p->syms[RX], set = sym;
+ assert(sym);
+ if (sym->temporary)
+ set = (*IR->x.rmap)(opkind(p->op));
+ assert(set);
+ if (set->sclass != REGISTER) {
+ Symbol r;
+ if (*IR->x._templates[getrule(p, p->x.inst)] == '?')
+ for (i = 1; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
+ Symbol r = p->x.kids[i]->syms[RX];
+ assert(p->x.kids[i]->x.registered);
+ assert(r && r->x.regnode);
+ assert(sym->x.wildcard || sym != r);
+ mask[r->x.regnode->set] &= ~r->x.regnode->mask;
+ }
+ r = getreg(set, mask, p);
+ if (sym->temporary) {
+ Node q;
+ r->x.lastuse = sym->x.lastuse;
+ for (q = sym->x.lastuse; q; q = q->x.prevuse) {
+ q->syms[RX] = r;
+ q->x.registered = 1;
+ if (sym->u.t.cse && q->x.copy)
+ q->x.equatable = 1;
+ }
+ } else {
+ p->syms[RX] = r;
+ r->x.lastuse = p;
+ }
+ debug(dumpregs("(allocating %s to node %x)\n", r->x.name, (char *) p));
+ }
+ }
+ p->x.registered = 1;
+ (*IR->x.clobber)(p);
+}
+static Symbol spillee(Symbol set, unsigned mask[], Node here) {
+ Symbol bestreg = NULL;
+ int bestdist = -1, i;
+
+ assert(set);
+ if (!set->x.wildcard)
+ bestreg = set;
+ else {
+ for (i = 31; i >= 0; i--) {
+ Symbol ri = set->x.wildcard[i];
+ if (
+ ri != NULL &&
+ ri->x.lastuse &&
+ (ri->x.regnode->mask&tmask[ri->x.regnode->set]&mask[ri->x.regnode->set])
+ ) {
+ Regnode rn = ri->x.regnode;
+ Node q = here;
+ int dist = 0;
+ for (; q && !uses(q, rn); q = q->x.next)
+ dist++;
+ if (q && dist > bestdist) {
+ bestdist = dist;
+ bestreg = ri;
+ }
+ }
+ }
+ }
+ assert(bestreg); /* Must be able to spill something. Reconfigure the register allocator
+ to ensure that we can allocate a register for all nodes without spilling
+ the node's necessary input regs. */
+ assert(bestreg->x.regnode->vbl == NULL); /* Can't spill register variables because
+ the reload site might be in other blocks. Reconfigure the register allocator
+ to ensure that this register is never allocated to a variable. */
+ return bestreg;
+}
+static int uses(Node p, Regnode rn) {
+ int i;
+
+ for (i = 0; i < NELEMS(p->x.kids); i++)
+ if (
+ p->x.kids[i] &&
+ p->x.kids[i]->x.registered &&
+ rn->set == p->x.kids[i]->syms[RX]->x.regnode->set &&
+ (rn->mask&p->x.kids[i]->syms[RX]->x.regnode->mask)
+ )
+ return 1;
+ return 0;
+}
+static void spillr(Symbol r, Node here) {
+ int i;
+ Symbol tmp;
+ Node p = r->x.lastuse;
+ assert(p);
+ while (p->x.prevuse)
+ assert(r == p->syms[RX]),
+ p = p->x.prevuse;
+ assert(p->x.registered && !readsreg(p));
+ tmp = newtemp(AUTO, optype(p->op), opsize(p->op));
+ genspill(r, p, tmp);
+ for (p = here->x.next; p; p = p->x.next)
+ for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
+ Node k = p->x.kids[i];
+ if (k->x.registered && k->syms[RX] == r)
+ genreload(p, tmp, i);
+ }
+ putreg(r);
+}
+static void genspill(Symbol r, Node last, Symbol tmp) {
+ Node p, q;
+ Symbol s;
+ unsigned ty;
+
+ debug(fprint(stderr, "(spilling %s to local %s)\n", r->x.name, tmp->x.name));
+ debug(fprint(stderr, "(genspill: "));
+ debug(dumptree(last));
+ debug(fprint(stderr, ")\n"));
+ ty = opkind(last->op);
+ NEW0(s, FUNC);
+ s->sclass = REGISTER;
+ s->name = s->x.name = r->x.name;
+ s->x.regnode = r->x.regnode;
+ q = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, s);
+ q = newnode(INDIR + ty, q, NULL, NULL);
+ p = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, tmp);
+ p = newnode(ASGN + ty, p, q, NULL);
+ p->x.spills = 1;
+ rewrite(p);
+ prune(p, &q);
+ q = last->x.next;
+ linearize(p, q);
+ for (p = last->x.next; p != q; p = p->x.next) {
+ ralloc(p);
+ assert(!p->x.listed || !NeedsReg[opindex(p->op)] || !(*IR->x.rmap)(opkind(p->op)));
+ }
+}
+
+static void genreload(Node p, Symbol tmp, int i) {
+ Node q;
+ int ty;
+
+ debug(fprint(stderr, "(replacing %x with a reload from %s)\n", p->x.kids[i], tmp->x.name));
+ debug(fprint(stderr, "(genreload: "));
+ debug(dumptree(p->x.kids[i]));
+ debug(fprint(stderr, ")\n"));
+ ty = opkind(p->x.kids[i]->op);
+ q = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, tmp);
+ p->x.kids[i] = newnode(INDIR + ty, q, NULL, NULL);
+ rewrite(p->x.kids[i]);
+ prune(p->x.kids[i], &q);
+ reprune(&p->kids[1], reprune(&p->kids[0], 0, i, p), i, p);
+ prune(p, &q);
+ linearize(p->x.kids[i], p);
+}
+static int reprune(Node *pp, int k, int n, Node p) {
+ struct node x, *q = *pp;
+
+ if (q == NULL || k > n)
+ return k;
+ else if (q->x.inst == 0)
+ return reprune(&q->kids[1],
+ reprune(&q->kids[0], k, n, p), n, p);
+ if (k == n) {
+ debug(fprint(stderr, "(reprune changes %x from %x to %x)\n", pp, *pp, p->x.kids[n]));
+ *pp = p->x.kids[n];
+ x = *p;
+ (IR->x.target)(&x);
+ }
+ return k + 1;
+}
+void spill(unsigned mask, int n, Node here) {
+ int i;
+ Node p;
+
+ here->x.spills = 1;
+ usedmask[n] |= mask;
+ if (mask&~freemask[n]) {
+
+ assert( /* It makes no sense for a node to clobber() its target. */
+ here->x.registered == 0 || /* call isn't coming through clobber() */
+ here->syms[RX] == NULL ||
+ here->syms[RX]->x.regnode == NULL ||
+ here->syms[RX]->x.regnode->set != n ||
+ (here->syms[RX]->x.regnode->mask&mask) == 0
+ );
+
+ for (p = here; p; p = p->x.next)
+ for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
+ Symbol r = p->x.kids[i]->syms[RX];
+ assert(r);
+ if (p->x.kids[i]->x.registered && r->x.regnode->set == n
+ && r->x.regnode->mask&mask)
+ spillr(r, here);
+ }
+ }
+}
+static void dumpregs(char *msg, char *a, char *b) {
+ fprint(stderr, msg, a, b);
+ fprint(stderr, "(free[0]=%x)\n", freemask[0]);
+ fprint(stderr, "(free[1]=%x)\n", freemask[1]);
+}
+
+int getregnum(Node p) {
+ assert(p && p->syms[RX] && p->syms[RX]->x.regnode);
+ return p->syms[RX]->x.regnode->number;
+}
+
+
+unsigned regloc(Symbol p) {
+ assert(p && p->sclass == REGISTER && p->sclass == REGISTER && p->x.regnode);
+ return p->x.regnode->set<<8 | p->x.regnode->number;
+}
+
|