gen.c

unix环境下实现的cmm语言编译器

#include "cmm.h"
#include <limits.h>

static void docall(Node p);
static void prelabel(Node p);
static void mark_instruction(Node forest);
static void free_node_reg(Node p);
static void set_spill_protector(Node p);
static void reset_spill_protector(Node p);
static Symbol sel_over_reg(Symbol s);
static void overflow(Symbol s);
static Symbol ask_reg(Symbol rs);
static Symbol get_reg(Symbol s);
static void reg_alloc(Node p);
static char *get_code_templates(Node p);
static void emit_asm(Node p);
static void emit_code(Node forest);
static Symbol askfixedreg(Symbol rs);
static char NeedsReg[] = { /*值为1的结点需要分配寄存器*/ 
	0,		/*unuse*/
	0,		/*CNST*/
	0,		/*ARG*/
	0,		/*ASGN*/
	1,		/*INDIR*/
	1,		/*CVC*/
	1,		/*CVI*/
	1,		/*CVP*/
	1,		/*CALL*/
	0,		/*RET*/
	0,		/*ADDRG*/
	1,		/*ADDRL*/
	1,		/*ADD*/
	1,		/*SUB*/
	1,		/*MOD*/
	1,		/*DIV*/
	1,		/*MUL*/
	0,		/*EQ*/
	0,		/*GE*/
	0,		/*GT*/
	0,		/*LE*/
	0,		/*LT*/
	0,		/*NE*/
	0,		/*JUMP*/
	0,		/*LABEL*/
	0,		/*NOT*/
	1,		/*NEG*/
	1,		/*CVU*/
	1,		/*LOAD*/
	0,		/*VREG*/
};

int offset;			/*记录栈的偏移量*/
int maxoffset;		/*栈的最大偏移量*/
int argoffset;		/*参数区的长度*/
int maxargoffset;
unsigned freemask;	/*记录寄存器的空闲状态*/
static unsigned non_spill_mask;	/*为寄存器设置溢出保护*/
Symbol rmap[16];

/*mkreg:生成寄存器fmt为寄存器的名字，n为寄存器的编号*/
Symbol mkreg(char *fmt, int n)
{
	Symbol p;

	NEW0(p, PERM);
	p->x.name = stringf(fmt, n);
	NEW0(p->x.regnode, PERM);
	p->x.regnode->number = n;
	p->x.regnode->mask = 1<<n;
	return p;
}

/*mkwildcard:生成通用寄存器组*/
Symbol mkwildcard(Symbol *syms){
	Symbol p;

	NEW0(p, PERM);
	p->x.name = "wildcard";
	p->x.wildcard = syms;
	return p;
}

/*blockbeg:在块的开始保存当前的栈的偏移并为局部变量分配存储空间*/
void blockbeg(Env *e)
{
	e->offset = offset;
	if (offset > maxoffset) { /*为局部变量在栈中分配存储空间*/
		print("sub esp, %d\n", offset - maxoffset);
		maxoffset = offset;
	}	
}

/*mkauto:为变量在栈中分配空间*/
void mkauto(Symbol p)
{
	assert(AUTO == p->sclass);
	offset = roundup(offset + p->type->size, p->type->align);
	p->x.offset = -offset;
	p->x.name = stringd(-offset);
}

/*blockend:在块的结束处恢复之前在块的开始处保存的值*/
void blockend(Env *e)
{
	offset = e->offset;
}

/*mkactual:返回参数区按align字节对齐后的长度，
 并由size计算加入参数后参数区的长度*/
int mkactual(int align, int size) 
{
	int n = roundup(argoffset, align);

	argoffset = n + size;
	return n;
}

/*docall:为CALL结点保存参数区的总的长度，以便在函数调用完成后释放该区域*/
static void docall(Node p)
{
	p->syms[1] = p->syms[0];
	p->syms[0] = intconst(argoffset);
	if (argoffset > maxargoffset) 
		maxargoffset = argoffset;
	argoffset = 0;
}

/*rtarget:为p的第n个子结点重定位寄存器r*/
void rtarget(Node p, int n, Symbol r)
{
	Node q = p->kids[n];
	
	assert(q);
	assert(r->sclass == REGISTER || !r->x.wildcard);
	if (NULL == q->syms[RX] 
	|| (r != q->syms[RX] && !q->syms[RX]->x.wildcard)){/*LOAD实现将值装入特定的寄存器*/
		q->count--;	/*因为LOAD会增加q结点的引用计数*/
		q = newnode(LOAD + optype(q->op),
			q, NULL, q->syms[0]);
		p->kids[n] = q;
	}
	setreg(q, r);	
}

/*setreg:为p结点设置寄存器r*/
void setreg(Node p, Symbol r)
{
	p->syms[RX] = r;
}

/*prelabel:为forest预先设置待分配的寄存器*/
static void prelabel(Node forest)
{
	Node p = forest;
	if (NULL == p || p->x.emitted)
		return ;
	prelabel(p->kids[0]);
	prelabel(p->kids[1]);
	if (NeedsReg[index(p->op)]) /*为需要寄存器的结点设置合适的寄存器组*/
		setreg(p,rmap[optype(p->op)]);
	switch (generic(p->op)) {
	case ADDRL:
		if (REGISTER == p->syms[0]->sclass) 
			p->op = VREG+P; 
		break;
	case INDIR:
		if (VREG+P == p->kids[0]->op) 
			setreg(p, p->kids[0]->syms[0]);
		break;
	}
	if (CALL == generic(p->op))
		docall(p);
	else if (ARG == generic(p->op))
		(*IR->x.doarg)(p);
	(IR->x.target)(p);
}

/*mark_instruction:对dag森林中需要产生指令的结点进行标记*/
static void mark_instruction(Node forest)
{
	Node p = forest;
	if (NULL == p || p->x.marked)
		return ;
	mark_instruction(p->kids[0]);
	mark_instruction(p->kids[1]);
	switch(generic(p->op)) {
	case ARG: 
	case CVC: case CALL: case ADD:
	case SUB: case MOD:  case DIV:
	case MUL: case EQ:	 case GE:
	case GT:  case LE:	 case LT:
	case NE:  case JUMP: case LABEL:
	case NEG: case LOAD: case ADDRL:
		p->x.isinstruction = 1;
		break;
	case CVI: case CVU: case CVP:
	/*对于像CVIU类的结点在子结点己产生指令的情况下可以不产生指令*/
		if (C == optype(p->op) || !p->kids[0]->x.isinstruction) 
			p->x.isinstruction = 1;
		break;
	case ASGN:	
		if (A == optype(p->op)) {
			p->x.isinstruction = 1;
			break;
		}
	case INDIR:	
	/*从局部变量中取右值,或者使用其左值都可以用[ebp+i]。
	 不需要生成计算地址的代码*/
		if (ADDRLP == p->kids[0]->op) 
			p->kids[0]->x.isinstruction = 0;
		p->x.isinstruction = 1;
		break;
	default:
		p->x.isinstruction = 0;
		break;
	}
	p->x.marked = 1; 
}

/*free_temp_stack:释放为溢出的寄存器而分配的临时栈*/
static void free_temp_stack(int boffset)
{
	if (offset > boffset)
		print("add esp, %d\n", offset - boffset);
	maxoffset =  offset = boffset;	
}

/*gen:为dag森林进行代码生成*/
void gen(Node forest)
{
	Node p = forest;
	int boffset;
	DEBUG(fprint(2, "gen begin:%d\n", p->op));
	for (p = forest; p; p = p->link) {
		prelabel(p);
		mark_instruction(p);
		boffset = offset;	/*保存当前栈的偏移*/
		emit_code(p);

		/*释放临时栈是为防止计算函数的参数时
		 *因寄存器溢出而破坏原来压栈的参数区*/
		free_temp_stack(boffset);
		if (NeedsReg[index(p->op)] && 0 == p->count)
			free_node_reg(p);	/*释放根结点的寄存器*/
	}
	DEBUG(fprint(2, "gen end:\n"));
}

/*free_node_reg:释放p的寄存器*/
static void free_node_reg(Node p)
{
	Symbol r;

	/*在结点发生了溢出时不能释放之前的寄存器*/
	if ( !p || !p->x.isinstruction || !NeedsReg[index(p->op)] || p->x.spills)
		return ;
	r = p->syms[RX];
	assert(r);
	if (r->sclass != REGISTER && --p->count <= 0) 
            putreg(r); /*释放不是为公共结点或寄存器变量分配的寄存器*/
}

/*set_spill_protector:设置寄存器溢出保护器，保护为p结点分配的寄存器被溢出*/
static void set_spill_protector(Node p)
{
	assert(p);
	if (NeedsReg[index(p->op)] && p->x.isinstruction)
		non_spill_mask |= p->syms[RX]->x.regnode->mask;
}

/*reset_spill_protector复位p结点的寄存器溢出保护器*/
static void reset_spill_protector(Node p)
{
	assert(p);
	if (NeedsReg[index(p->op)] && p->x.isinstruction)
		non_spill_mask &= ~p->syms[RX]->x.regnode->mask;
}

/*sel_over_reg选择溢出的寄存器*/
static Symbol sel_over_reg(Symbol rs)
{
	int i, min;
	Node p;
	if (!rs->x.wildcard)
		return rs;
	for (i = 7, min = INT_MAX; i >= 0; i--) {
		Symbol ri = rs->x.wildcard[i];
		if (ri != NULL && ri->x.lastuse) {
			Node q = ri->x.lastuse;
			if (q->count < min 			/*查找引用次数最小的结点*/
			&& (!ri->x.regnode->vbl)	/*不溢出寄存器变量*/
			&& (ri->x.regnode->mask & ~non_spill_mask)){
				min = q->count;
				p = q;
			}
		}
	}
	return p->syms[RX];
}

/*overflow:保存溢出寄存器rs中的值，并将重新产生为引用rs的值的结点*/
static void overflow(Symbol rs)
{
	int ty;
	assert(rs);
	Node p = rs->x.lastuse;
	assert(p);

	DEBUG(fprint(2, "overflow register:%s,%d\n", rs->x.name, p->op));
	Symbol temp = newtemp(AUTO,optype(p->op));
	if (offset > maxoffset)  {	/*为临时变量在栈中分配存储空间*/
		print("sub esp, %d\n", offset - maxoffset);
		maxoffset = offset;
	}
	ty = optype(p->op);

	/*将寄存器中的值保存到临时变量中*/
	if (C == ty) 
		print("mov byte [ebp + %s], %s\n", temp->x.name, p->syms[RX]->x.name);
	else 
		print("mov dword [ebp + %s], %s\n", temp->x.name, p->syms[RX]->x.name);

	/*重新产生引用寄存器的结点*/
	p->kids[0] = newnode(ADDRL+P, NULL, NULL, temp);
	p->op = INDIR+optype(p->op);
	p->syms[RX] = NULL;
	p->kids[1] = NULL;
	p->x.isinstruction = 0;	
	p->x.emitted = 0;		/*需要重新生成取值代码*/
	p->x.spills = 1;		
	p->x.marked = 0;
	putreg(rs);
}

/*askfixedreg:申请固定的寄存器rs*/
static Symbol askfixedreg(Symbol rs)
{
	Regnode r = rs->x.regnode;

	assert(rs && !rs->x.wildcard);
	if (r->mask &~freemask) /*freemask中相应的位置位时，表示对应的寄存器空闲*/
		return NULL;
	else {
		freemask &= ~r->mask;
		return rs;
	}
	return NULL;
}

/*ask_reg:申请寄存器*/
static Symbol ask_reg(Symbol rs)
{
	int i;

	if (NULL == rs->x.wildcard) /*rs为固定的寄存器*/
		return askfixedreg(rs);
	for (i = 7; i >= 0; i--) {
		Symbol r = rs->x.wildcard[i];
		if (r != NULL && askfixedreg(r))
			return r;
	}
	return NULL;
}

/*askregvar:为p申请寄存器regs*/
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 ((r = ask_reg(regs)) != NULL) {
		p->x.regnode = r->x.regnode;
		p->x.regnode->vbl = p;
		p->x.name = r->x.name;
		return 1;
	}else {
		p->sclass = AUTO;
		return 0;
	}
}

/*get_reg:为结点获得寄存器rs*/
static Symbol get_reg(Symbol rs)
{
	assert(rs);
	Symbol r = ask_reg(rs);
	if (NULL == r) {	/*需要溢出寄存器*/
		r = sel_over_reg(rs);
		overflow(r);
		r = ask_reg(r);
	}
	return r;
}

/*get_node_reg: 为p分配寄存器*/
static void get_node_reg(Node p, int t)
{
	Symbol rs = NULL;
	if (!p->syms[RX]->x.wildcard) { /*需要固定的寄存器*/
		if ((DIV == generic(p->op) || MOD == generic(p->op)) && t) {
			rs = p->syms[RX];	/*保存原来的寄存器*/
			set_eax(p);			/*设置为eax寄存器*/
			get_node_reg(p, 0);
			set_edx(p);			/*设置为edx寄存器*/
			get_node_reg(p, 0);
			p->syms[RX] = rs;	/*恢复原来的寄存器*/
			rs->x.lastuse = p;
			return ;
		}
		rs = askfixedreg(p->syms[RX]);
		if (!rs && p->syms[RX]->x.lastuse->kids[0] == p) 
		/*如果是它的父结点占用了寄存器则不必溢出寄存器