dag.c

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

/*dag.c:将抽象语法树转换成dag的中间数据结构*/
#include "cmm.h"
#define iscall(p) (generic((p)->op) == CALL)
static struct dag {
	struct node node;
	struct dag *hlink;
}*buckets[16];

static int nodecount;	/*公共子表达式的结点数*/
static Node forest;		/*forest指向dag森林链的最后一个元素*/
static struct dag *dagnode(int op, Node l, Node r, Symbol sym);
static void reset(void);
static void fixup(Node p);
static void list(Node p);
static Symbol equated(Symbol p);
static  Node listnodes(Tree tp, int tlab, int flab, int lev);

int reg_var_count = 0; /*对寄存器变量进行计数*/

/*node:生成dag结点，并采用哈希表的算法削除公共子表达式结点。*/
static Node node(int op, Node l, Node r, Symbol sym)
{
	int i;
	struct dag *p;

	i = (index(op)^((unsigned)sym>>2))&(NELEMS(buckets)-1);
	for (p = buckets[i]; p ; p = p->hlink) 
		if(p->node.op == op && p->node.syms[0] == sym
		&& p->node.kids[0] == l && p->node.kids[1] == r)
			return &p->node;
	p = dagnode(op, l, r, sym);
	p->hlink = buckets[i];
	buckets[i] = p;
	++nodecount;
	return &p->node;
}

/*dagnode:生成单独的dag结点*/
static struct dag *dagnode(int op, Node l, Node r, Symbol sym)
{
	struct dag *p;
	
	NEW0(p, FUNC);
	p->node.op = op;
	if((p->node.kids[0] = l) != NULL)
		l->count++; /*对子结点引用计数*/
	if((p->node.kids[1] = r) != NULL)
		r->count++;
	p->node.syms[0] = sym;
	return p;
}

Node newnode(int op, Node l, Node r, Symbol sym)
{
	return &dagnode(op, l, r, sym)->node;
}

/*reset:清空结点表*/
static void reset(void)
{
	if(nodecount > 0)
		memset(buckets, 0, sizeof buckets);
	nodecount = 0;
}

/*list:将p添加到dag森林链中。forest总是指向链的最后一个元素*/
static void list(Node p)
{
	if (p && NULL == p->link) {
		if (forest) {
			p->link = forest->link;
			forest->link = p;
		}else 
			p->link = p;
		forest = p;
	}		
}

/*walk:函数将语法树e转换成dag，并将dag添加到代码表中*/
void walk(Tree e, int tlab, int flab)
{
	listnodes(e, tlab, flab, 0);
	if (forest) {
		code(Gen)->u.forest = forest->link;
		forest->link  = NULL;
		forest = NULL;
	}
	reset();
	deallocate(STMT);
}

/*listnodes:将语法树tp转换成dag,其中参数lev
 *在listnodes内部以1调用，在其它地方以0调用。
 */
Node listnodes(Tree tp, int tlab, int flab, int lev)
{
	Node p = NULL, l, r;

	if (NULL == tp)
		return NULL;
#ifndef NDEBUG
	if (!lev) {			/*用于输出调试信息，为了防止
						 *重复输出其中只有在首次进入树
						 *根结点时才调用printtree函数*/
		printtree(tp);	/*打印树tp*/
		fprint(2,"\n");
	}
#endif

	if (tp->node)
		return tp->node;
	switch(generic(tp->op)) {
	case CVC: case CVI: case CVU: 
	case CVP: case NEG:	case INDIR:
		assert(0 == tlab && 0 == flab);
		l = listnodes(tp->kids[0], 0, 0,1);
		p =  node(tp->op, l, NULL, NULL);
		break;
	case ADD: case SUB: case MUL:
	case MOD: case DIV: 
		assert(0 == tlab&& 0 == flab);
		l = listnodes(tp->kids[0], 0, 0,1);
		r = listnodes(tp->kids[1], 0, 0,1);
		p = node(tp->op, l, r, NULL);
		break;
	case ADDRL:
	case ADDRG:
		assert(0 == tlab && 0 == flab);
		p = node(tp->op, NULL, NULL, tp->u.sym);
		break;
	case EQ: case GE: case GT:
	case LE: case LT: case NE:
		/*条件表达式总是做为根结点出现*/
		l = listnodes(tp->kids[0], 0, 0,1);
		r = listnodes(tp->kids[1], 0, 0,1);
		if (tlab != 0) 
			list(newnode(tp->op, l, r, findlabel(tlab)));
		else if (flab != 0) {
			int op = tp->op;
			switch (generic(op)) { 
			case EQ: op = NE + optype(op);break;
			case GE: op = LT + optype(op);break;
			case GT: op = LE + optype(op);break;
			case LE: op = GT + optype(op);break;
			case NE: op = EQ + optype(op);break;
			case LT: op = GE + optype(op);break;
			}
			list(newnode(op, l, r, findlabel(flab)));
		}
		if (forest && forest->syms[0])
			forest->syms[0]->ref++;
		break;
	case NOT:
		return listnodes(tp->kids[0], flab, tlab, 0);
	case CNST:
		if (tlab || flab) {
			if (tlab && tp->u.v.i != 0)
				list(jump(tlab)); 
			else if (flab && 0 == tp->u.v.i)
				list(jump(flab));
		}else 
			p = node(tp->op, NULL, NULL, constant(tp->type, tp->u.v));
		break;
	case ASGN:
		l = listnodes(tp->kids[0], 0, 0,1);
		p = r = listnodes(tp->kids[1], 0, 0,1);
		list(newnode(tp->op, l, r, NULL));
		forest->syms[0] = intconst(tp->kids[1]->type->size);
		forest->syms[1] = intconst(tp->kids[1]->type->align);
		reset();
		break;
	case CALL:
		l = listnodes(tp->kids[0], 0, 0, 1);
		r = listnodes(tp->kids[1], 0, 0, 1);
		p = newnode(tp->op, l, r, NULL);
		if (!lev)	/*CALL结点只有在没有其它结点引用时才会成为根结点*/
			list(p);
		reset();
		break;
	case ARG: 
		l = listnodes(tp->kids[0], 0, 0,1);
		r = listnodes(tp->kids[1], 0, 0,1);
		p = newnode(tp->op, l, r, NULL);
		p->syms[0] = intconst(tp->type->size); /*保存参数的大小*/
		p->syms[1] = intconst(tp->type->align); /*保存参数的对齐字节*/
		reset();
		break;	
	case RET:
		l = listnodes(tp->kids[0], 0, 0, 1);
		list(newnode(tp->op, l, NULL, NULL));
		break;
	}
	tp->node = p;
	return p;
}

static void print_forest(Node forest)
{
	for ( ; forest; forest = forest->link) {
		print_dag(forest);
		fprint(2,"\n");
	}
}
/*print_code_label:用于调试本编译程序时输出代码表*/
static void print_code_label(Code cp)
{
	for ( ; cp; cp = cp->next) {
		switch (cp->kind) {
		case Blockbeg:{
			Symbol *p = cp->u.block.locals;
			fprint(2, "block begin %d: ",cp->u.block.level);
			for ( ;p && *p; p++)
				fprint(2, "%s,", (*p)->name);
			fprint(2, "\n");
		 }break;
		case Blockend:
			fprint(2, "block end:%d\n",cp->u.begin->u.block.level);
			break;
		case Label: case Jump: case Gen:
			print_forest(cp->u.forest);
			break;
		}
	}
}

void gencode(Symbol caller[], Symbol callee[])
{
	Code cp;

	{ /*对参数进行转换，并将转换的赋值结点插入到代码表的开始处*/
		int i;
		Symbol p,q;
		cp = codehead.next->next;
		codelist = codehead.next;
		for (i = 0; (p = callee[i]) != NULL
			&& (q = caller[i]) != NULL ; i++) {
			if (p->type != q->type)
				walk(asgn(p, idtree(q)), 0, 0);
		}
		codelist->next = cp;
		cp->prev = codelist;
	}
	cp = codehead.next;
#ifndef NDEBUG
	print_code_label(cp);
#endif
	for (; errcnt <= 0 && cp; cp = cp->next)
		switch(cp->kind) {
		case Blockbeg: {
				Symbol *p = cp->u.block.locals;
				for (; p && *p; p++) {
					/*对引用频率排在前三
					 *位的非地址局部变量，将其做为寄存器变量*/
					if (!(*p)->addressed
					&& (reg_var_count < 3)) {
						(*p)->sclass = REGISTER;
						reg_var_count++;
					}
					if ((*p)->ref != 0.0)
						(*IR->local)(*p);
				}
				(*IR->blockbeg)(&cp->u.block.x);
			}
			break;
		case Blockend: (*IR->blockend)(&cp->u.block.x); break;
		case Label: case Gen: case Jump:
			fixup(cp->u.forest);
			(*IR->gen)(cp->u.forest);
			break;
		}
}

/*fixup:为标号结点查找等价的标号*/
static void fixup(Node p)
{
	for (; p; p = p->link)
		switch (generic(p->op)) {
		case JUMP:
			if (ADDRG+P == p->kids[0]->op)
				p->kids[0]->syms[0] = equated(p->kids[0]->syms[0]);
			break;
		case EQ: case NE: case GE: case GT: case LE: case LT:
			assert(p->syms[0]);
			p->syms[0] = equated(p->syms[0]);
		}
}
static Symbol equated(Symbol p)
{
	while(p->u.l.equatedto)
		p = p->u.l.equatedto;
	return p;
}