Subversion Repositories eco32

#include "c.h"

static char rcsid[] = "$Id: gen.c,v 1.1 2002/08/28 23:12:43 drh Exp $";

#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 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");

}

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);