gen.c

lcc,一个可变目标c语言编译器的源码

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