From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- lcc/src/gen.c | 1660 ++++++++++++++++++++++++++++----------------------------- 1 file changed, 830 insertions(+), 830 deletions(-) (limited to 'lcc/src/gen.c') diff --git a/lcc/src/gen.c b/lcc/src/gen.c index ab8506a..7202c45 100755 --- a/lcc/src/gen.c +++ b/lcc/src/gen.c @@ -1,830 +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<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; -} - +#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<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; +} + -- cgit v1.2.3