gen.c

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

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