c－－minusminus语言编译器的设计文档.txt

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

9		boffset = offset;	/*保存当前栈的偏移*/
10		emit_code(p);

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

7		调用prelabel对dag进行寄存器标注。
8		调用mark_instruction对需要生成代码的结点进行标记。
10		为单棵的dag调用emit_code生成代码。
11		free_temp_stack释放在emit_code中由于寄存器溢出而分配的临时空间。
12－13	释放根结点的已不再使用的寄存器。
--------------------------------------------------------------------------------
1 static void emit_code(Node forest)
2 {
3	Node p = forest;
	/*对于溢出结点的重新取值是在get_code_template中进行的*/
4	if (NULL == p || p->x.emitted || p->x.spills)
5		return ;
6	DEBUG(fprint(2, "emit_code begin:%d\n",p->op));
7	if (CALL == generic(p->op)) { 
8		Symbol rs = get_reg(p->syms[RX]);
9		putreg(rs);
10	}	
11	emit_code(p->kids[0]);
12	if (ARG == generic(p->op))
13		emit_asm(p);
14	emit_code(p->kids[1]);

	/*NEG不能改变原寄存器的值，所以不能释放左结点的寄存器。
	 *当右结点发生寄存器溢出时，为了防止为它生成重新取值代码而
	 *占用左结点的寄存器而不释放左结点的寄存器，但如果父结点的
	 *寄存器与左结点的寄存器相同，可以释放在左结点的寄存器，因为
	 *在释放左结点的寄存器之后，在为父结点分配寄存器时，会分配该寄存器。
	 */ 
15	if (generic(p->op) != NEG
16	&& (!p->kids[1] || !p->kids[1]->x.spills
17	|| equal_reg(p,p->kids[0])))
18		free_node_reg(p->kids[0]);
19	reg_alloc(p);
20	if (p->x.isinstruction && generic(p->op) != ARG)
21		emit_asm(p);
22	p->x.emitted = 1;

23	free_node_reg(p->kids[1]);
24	if (DIV == generic(p->op))	/*DIV结点中的edx可以提前释放,以节约寄存器*/
25		put_edx();
26	if (MOD == generic(p->op))	/*MOD结点中的eax可以提前释放*/
27		put_eax();
28	DEBUG(fprint(2, "emit_code end:\n"));
29 }

7－10	由于代码生成是按照后序遍历的顺序，先生成子结点的代码后才会为结点
		申请寄存器。函数调用时会先在ARG结点生成参数压栈指令。
		这时如果eax不是空闲的，则会产生溢出eax寄存器的代码，而破坏了接下来为
		函数调用设置好了的参数区。这里提前在为ARG子结点生成压栈指令前，生成
		溢出eax寄存器的代码来防止上述情况的发生。
11		为左子结点生成代码。
12－13	对于ARG结点需要提前在为右结点生成压栈指令前为本结点发送压栈指令，
		这样才能产生参数按右至左的压栈顺序。函数emit_asm发送汇编代码。
15－18	有选择的释放左子结点的寄存器。
19		为结点申请寄存器。
20		为需要产生指令的结点发送汇编代码。其中ARG结点已经在之前发送了指令。
22		为结点做上己发送指令的标记。
23		free_node_reg函数释放右子结点的寄存器。
24－27	对除运算由于商在寄存器eax中因此可以提前释放edx。同理对于求余运算可以
		释放寄存器eax。
-------------------------------------------------------------------------------
/*emit_asm:为p产生汇编代码*/
1 static void emit_asm(Node p)
2 {
3	DEBUG(fprint(2, "emit_asm begin:\n"));
4	char *fmt;
5	if (p->x.isinstruction && p->x.emitted) {
6		outs(p->syms[RX]->x.name);	
7		return ;
8	}
9	fmt = get_code_templates(p);
10	assert(fmt);
11	if (*fmt == '#')
12		(*IR->x.emit2)(p);
13	else {
14		if (*fmt == '?') {
15			fmt++;
16			assert(p->kids[0]);
17			if (equal_reg(p, p->kids[0]))
18				while (*fmt++ != '\n')
19					;
20		}
21		for (; *fmt; fmt++)
22			if (*fmt != '%')
23				*bp++ = *fmt;
24			else if (*++fmt >= '0' && *fmt <= '2') 
25				emit_asm(p->kids[*fmt - '0']);
26			else if (*fmt >= 'a' && *fmt < 'a' + NELEMS(p->syms)){
27					outs(p->syms[*fmt - 'a']->x.name);
28			}else
29				*bp++ = *fmt;
30	}
31	if (ASGN+A == p->op)
32		putreg(p->syms[RX]);
33	DEBUG(fprint(2, "emit_asm end:\n"));
34 }

5－8		对生成了指令的结点只输出它的寄存器的名字。
9		get_code_templates选择代码模板。
11－12	为需要特殊处理的结点发送代码。
14－20	对于需要生成双指令的结点，例如"?mov %c, %0\nadd %c, %1\n"，在左子结点
		的寄存器与本结点的寄存器相同时，可以省略寄存器复制指令。
31－32	对于局部数组初始化，在生成传送指令后，需要特别的为它释放计数器ecx寄存器
-------------------------------------------------------------------------------
/*get_code_templates:为p选择汇编代码模板*/
1 static char *get_code_templates(Node p)
2 {
3	assert(p);
4	DEBUG(fprint(2, "get_code_templates begin:%d\n", p->op));
5	if (p->kids[0] && p->kids[0]->x.spills)
6		gen_re_load(p, 0);
7	if (p->kids[1] && p->kids[1]->x.spills)
8		gen_re_load(p, 1);
9	switch (generic(p->op)){	
10	case CVI: case CVP: 
11	case CVU: 
12		if (CVIU == p->op || CVUI == p->op
13		|| CVUP == p->op || CVPU == p->op)
14			if (!p->x.isinstruction)
15				return "%0";
16		break;
17	case ASGN:
18		if (A == optype(p->op)) /*为初始局部数组选择指令*/
19			get_reg(p->syms[RX]);	/*设置寄存器ecx*/	
20		if (VREG == generic(p->kids[0]->op))
21			return "mov %0, %1\n";
22		break;
23	case INDIR:
24		if (VREG == generic(p->kids[0]->op))
25			return "#read register\n";
26		break;
27	case ADDRL:
28		if (p->x.isinstruction)	/*计算局部变量的地址*/
29			return "mov %c, ebp\nadd %c, %a\n";
30		break;
31	}
32	DEBUG(fprint(2, "get_code_templates end:%d\n", p->op));
33	return templates[p->op];	
34 }

5－8	为寄存器溢出的子结点重新生成取值的代码。
12－15	CVUI等转换指令可以不生成寄存器传送指令，而直接使用子结点的寄存器。
17－19	为局部数组的初始化分配传送字节的计数器ecx。
20－21	为寄存器变量赋值。
33		templates是一个以结点的操作符为索引，值为指示生成代码的字符串。
-------------------------------------------------------------------------------
/*get_node_reg: 为p分配寄存器*/
1 static void get_node_reg(Node p, int t)
2 {
3	Symbol rs = NULL;
4	if (!p->syms[RX]->x.wildcard) { /*需要固定的寄存器*/
5		if ((DIV == generic(p->op) || MOD == generic(p->op)) && t) {
6			rs = p->syms[RX];	/*保存原来的寄存器*/
7			set_eax(p);			/*设置为eax寄存器*/
8			get_node_reg(p, 0);
9			set_edx(p);			/*设置为edx寄存器*/
10			get_node_reg(p, 0);
11			p->syms[RX] = rs;	/*恢复原来的寄存器*/
12			rs->x.lastuse = p;
13			return ;
14		}
15		rs = askfixedreg(p->syms[RX]);
16		if (!rs && p->syms[RX]->x.lastuse->kids[0] == p) 
		/*如果是它的父结点占用了寄存器则不必溢出寄存器
		 *这主要是为了处理在子结点出现寄存器溢出时，为它生成
		 *重新取值代码，而分配寄存器时可能会溢出它的父结点寄存器的情况
		 */
17			return ; 
		
18	}
19	if (NULL == rs)
20		rs = get_reg(p->syms[RX]); 
21	rs->x.lastuse = p;/*lastuse指向使用它的结点*/
22	p->syms[RX] = rs;
23 }

5－14	对于除和求余需要为它们分配eax和edx寄存器，其中t在get_node_reg内部
		调用时0，在其它结点调用为1。
15		申请固定的寄存器。
19－20	对于需要通用寄存器或需要溢出寄存器的结点调用get_reg函数进行处理。
21		将申请到的寄存器指向引用它的结点，这是为了在溢出寄存器时，能够为结点
		生成重新取值的代码。
--------------------------------------------------------------------------------
/*get_reg:为结点获得寄存器rs*/
1 static Symbol get_reg(Symbol rs)
2 {
3	assert(rs);
4	Symbol r = ask_reg(rs);
5	if (NULL == r) {	/*需要溢出寄存器*/
6		r = sel_over_reg(rs);
7		overflow(r);
8		r = ask_reg(r);
9	}
10	return r;
11 }

get_reg首先调用ask_reg申请寄存器。若失败则调用sel_over_reg选择需要溢出的寄存器。
然后调用overflow产生溢出代码。最后再次调用ask_reg申请寄存器，这次申请会一定成功
。
--------------------------------------------------------------------------------
/*sel_over_reg选择溢出的寄存器*/
1 static Symbol sel_over_reg(Symbol rs)
2 {
3	int i, min;
4	Node p;
5	if (!rs->x.wildcard)
6		return rs;
7	for (i = 7, min = INT_MAX; i >= 0; i--) {
8		Symbol ri = rs->x.wildcard[i];
9		if (ri != NULL && ri->x.lastuse) {
10			Node q = ri->x.lastuse;
11			if (q->count < min 			/*查找引用次数最小的结点*/
12			&& (!ri->x.regnode->vbl)	/*不溢出寄存器变量*/
13			&& (ri->x.regnode->mask & ~non_spill_mask)){
14				min = q->count;
15				p = q;
16			}
17		}
18	}
19	return p->syms[RX];
20 }
5－6	对于固定的寄存器，直接返回该寄存器进行溢出。
7－18	sel_over_reg总是选择引用次数最小、且不是寄存器变量、同时不受保护的
		寄存器，做为溢出寄存器。
--------------------------------------------------------------------------------
/*overflow:保存溢出寄存器rs中的值，并将重新产生为引用rs的值的结点*/
1 static void overflow(Symbol rs)
2 {
3	int ty;
4	assert(rs);
5	Node p = rs->x.lastuse;
6	assert(p);

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

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

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

8－12	调用newtemp生成保存寄存器的临时变量，并且在栈中分配存储空间。
		maxoffset记录了栈的最大的偏移。
14－17	直接生成溢出指令。
18－25	重新产生引用栈中己溢出寄存器的值的结点。
26		释放寄存器。
--------------------------------------------------------------------------------
以上各函数位于gen.c中