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

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

--------------------------------------------------------------------------------
1 int eqtype(Type ty1, Type ty2)
2 {
3	if (ty1 == ty2)
4		return 1;
5	if (ty1->op != ty2->op)
6		return 0;
7	if (!eqtype(ty1->type, ty2->type))
8		return 0;

	/*对于函数类型，需要检查其参数类型是否兼容*/
9	Type *p1= ty1->proto, *p2=ty2->proto;
10	for (;p1 && p2 && *p1 && *p2 ; p1++,p2++)
11		if(!eqtype(*p1,*p2))
12			 return 0;
13	if (NULL == p1 && NULL == p2)
14		return 1;
15	if (NULL == p1 || NULL == p2)
16		return 0;
17	return *p1 == *p2;
18 }

1-3		由于除函数类型以外的其它类型都是通过哈希表来构造，
		它们如果类型相同可以通过比较它们的地址来完成。
5		判断当类型符不同时，就可以确定其类型不相同。
7－8	判断函数的返回类型是否兼容，当返回类型不兼容时就可以确定函数类型不兼容。
10-12	判断其参数类型，只要有一个类型不兼容就可以确定函数不兼容。
--------------------------------------------------------------------------------
	6、 输入模块的实现
		考虑到C－－语言编译器处理的输入文件都比较小，完全可能一次性读入整个文件
至内存。这样就可以提高了输入效率，同样可以简化输入模块的实现。输入模块在input.c
中，input.c向外输出两个函数void inputInit(void)和void newline(void)。
inputInit一次性读入整个文件，并设置好缓冲区。在缓冲区的最后设置一个’监视哨‘’换
行符，这样只有当遇到换行符后才需要检查是否以到文件结束。
	7、 输出模块的实现
		输出模块在output.c中。输出模块对输出进行高速缓存，并进行格式化输出。
设有三个缓冲区，0号缓冲区提供临时空间给需要分配存储空间来存储格式化字符串的操作
。1号缓冲区是提供写输出文件的缓冲。2号缓冲区为出错信息的缓冲区。
以上7个模块有些可以做为独立的模块被其它的应用使用，有些只要作些修改，就能用于其它的应用。
	8、 词法分析模块的实现
词法分析器被语法分析模块调用，用于获得下一个记号。它的实现是在lcc的词法分析器
上改写得到的。由于C－－不提供浮点运算、八进制数、十六进制数，以及将数做为有符号数处理等。另外只提供了最基本的转义字符，所以C－－的词法分析器较	lcc的词法分析器简单。对它的说明可以参照＜＜可变目标C编译器－设计与实现＞＞的词法分析部分。C－－编译器的词法分析在lex.c文件中。
	
	9、 C－－编译器语法分析模块的设计：
C－－编译器语法分析器，是在lcc的语法分析器上经过简化得到的。声明符的分析主要在文件decl.c中。只有对初始化声明符列表的分析放在init.c中。表达式分析在exrp.c中，语句的分析在stmt,对它们的说明请参照＜＜可变目标C编译器－设计与实现＞＞的相关部分。
	10、 语义分析模块的实现：
		语义分析模块由enode.c和simp.c组成。simp.c主要进行常量的合并和简化，enode.c建立抽象语法树。
	11、 中间数据结构dag的实现
		中间数据结构dag的实现在dag.c中,将抽象语法树转换成dag的中间数据结构,并削除公共子表达式。为了实现的简化，公共子表达式的削除只限制在单棵dag中。listnodes函数将语法树tp转换成dag，其中参数lev在listnodes内部以1调用，在其它地方以0调用。详细的说明在源代码注释和参考＜＜可变目标C编译器－设计与实现＞＞。另外寄存器的分配策略在函数gencode－对引用频率排在前三位的非地址局部变量，将其做为寄存器变量。
	12、主程序模块
main.c是主控程序。
C－－编译器支持一个程序可由多个源代码模块组成，它们分别进行编译生成nasm的汇编代码，再由nasm汇编器汇编成可重定位的目标文件，最后通过加载器ld连接成可执行文件。
C－－编译器支持以下的选项。
-S		生成汇编代码，在没有-o选项指定目标文件时，默认后缀为asm。
-c		生成可重定向的目标文件，默认后缀为o。
-o		指定目标名字为选项后的参数。
--------------------------------------------------------------------
1 int main(int argc, char *argv[]) 
2 {
3	int i,j;
4	static struct arg *asmset,*objset;

5	fs = fc = fo = 0;
6	i = doarg(argc, argv);
7	asmset = newarray(sizeof (struct arg ), argc - i + 1, PERM);
8	objset = newarray(sizeof (struct arg ), argc - i + 1, PERM);
9	for (j = 0; j < argc - i + 1; j++) {
10		asmset[j].name = objset[j].name = NULL;
11		asmset[j].generated = objset[j].generated = 0;
12	}
13	(*IR->progbeg)();
14	for (j = 0;i < argc; i++, j++) {
15		char *ps;
16		infile = argv[i];
17		ps = get_suffix(argv[i]);
18		if (!strcmp(ps, ".asm") || !strcmp(ps, ".s")) {
19			asmset[j].name = argv[i];
20			continue;
21		}
22		else if (!strcmp(ps, ".o")) {
23			objset[j].name = argv[i];
24			continue;
25		}
26		if (fo && fs)
27			asmset[j].name  = outfile;
28		else if (fs || (fc && !fo)) {
29			asmset[j].name = genname(infile, ".asm");
30			asmset[j].generated = 1;
31		}
32		else {
33			asmset[j].name  = tempnam(".",NULL);
34			asmset[j].generated = 1;
35		}
36
37		if (infile != NULL)
38			if ((infd = open(infile, 0)) < 0) {
39				fprint(2, "%s: can't read `%s'\n",
40					argv[0], infile);
41				exit(1);
42			}
43		if (asmset[j].name != NULL)
44			if ((outfd = creat(asmset[j].name, 0666)) < 0) {
45				fprint(2, "%s: can't write `%s'\n",
46					argv[0], asmset[j].name);
47				exit(1);
48			}
49		inputInit();
50		outputInit();
51		init_sym();	
52		t = gettoken();
53		program();
54		finalize();
55		outflush();
56		close(infd);
57		close(outfd);
58	}

59	if (!errcnt) {
60		int s;
61		if (fs)
62			goto finish;
63		if (fc && fo) {
64			s = system(stringf("nasm -f elf %s -o %s",
65			asmset[0].name,outfile));
66			if (asmset[0].generated)
67				unlink(asmset[0].name);
68			if (s)
69				exit(1);
70			goto finish;
71		}
72		{char *objstr;
73			for (i = 0; asmset[i].name || objset[i].name; i++) {
74				if (asmset[i].name) {
75					objset[i].name = genname(asmset[i].name, ".o");
76					objset[i].generated = 1;
77					s = system(stringf("nasm -f elf %s -o %s",
78							asmset[i].name, objset[i].name));
79					if (asmset[i].generated)
80						unlink(asmset[i].name);
81					if (s)
82						exit(1);
83				}
84			}
85			if (fc)
86				goto finish;
87			if (!fo) {
88				outfile = "a.out";
89				if (i >= 2)
90					i = 1;
91			}
92			objstr = allocate(_POSIX_ARG_MAX, PERM);
93			*objstr = '\0';
94			for (j = 0; j < i; j++) {
95				if (strlen(objstr) >= _POSIX_ARG_MAX)
96					break;
97				strcat(objstr, stringf("%s ",objset[j].name));
98			}
99			s = system(stringf("ld -o %s -dynamic-linker \
100						/lib/ld-linux.so.2 \
101						/usr/lib/crt1.o \
102						/usr/lib/crti.o \
103						/usr/lib/crtn.o %s \
104						-L/usr/lib -lc -lm",
105						outfile, objstr));
106			for (j = 0; objset[j].name; j++)
107				if (objset[j].generated)
108					unlink(objset[j].name);
109			if (s)
110				exit(1);
111		}
112	}
113 finish:
114	close(errfd);
115	deallocate(PERM);
116	dispose();
117	return errcnt > 0;
118 }

6		调用doarg对选项进行处理。i为第一个输入文件的下标。
7－12	为保存汇编文件集合和可重定向目标文件集合分配空间并初始化。
		其中arg结构中的generated表示name是由C－－编译器生成的名字。
17		获得输入文件的后缀名。
18－21	保存输入文件中的汇编文件。
21－25	保存输入文件中的可重定向目标文件。
26－27	-S选项和-o选项同时出现则汇编文件名也是输出文件名。
28－31	有-S且没有-o或者有-c且没有-o，则生成前缀为输入文件的前缀，后缀名为asm
		的汇编文件。
32－35	其它的情况生成一个临时的汇编文件。
54		由于C－－语言不支持extern，同时为了使C－－能部分使用标准C库，
		在finalize函数里将没有在本文件定义的函数声明为引用外部的记号。
		但对全局变量则不能这样处理，对于没有为全局变量进行初始化的声明，
		将为它保留分配一个没有初始化的空间。 所以C－－支持多模块，但是不能在
		多模块中使用全局的变量进行信息传递。
61-62	对于有-S选项的，在生成汇编文件后程序运行结束。
63－71	对于有-c且有-o选项的情况，需要为它调用nasm汇编器生成可重定位
		的目标文件。文件名就是在前面接受的-o选项的参数。如果汇编文件是临时生成
		的，则删除它，然后结束运行
72－84	对于需要生成多个可重定位的目标文件或者没有-c选项的单个文件，为它们
		调用nasm生成相应的文件并删除之前临时的汇编文件。
87－91	没有用-o选项指定输出文件名则默认的输出名为a.out。如果输入文件有二个以上
		则只对第一个进行处理。
92－105	调用加载器ld连接可重定位的目标文件成可执行程序。
106－108删除生成的可重定位的目标文件。

	以上的模块构成了C－－编译器的前端。

二、后端的设计与实现。
	C－－编译器的代码生成是直接在前端生成的dag上进行的（这与lcc有很大的区别）。
C－－编译器的后端包括gen.c和nasm.c两个文件。其中与机器相关的部分主要在nasm.c中，gen.c主要完成代码模板的选择、寄存器分配、寄存器溢出处理和代码发送。代码生成的基本思想是首先为左子结点生成代码，然后为右结点生成代码。这时释放左子结点的寄存器，为本结点分配寄存器、发送代码，最后释放右子结点的寄存器。及经过后序遍历的顺序进行生成代码，但对于特殊结点需要另外处理。现在对主要的函数进行详细说明。
--------------------------------------------------------------------------------
/*rtarget:为p的第n个子结点重定位寄存器r*/
1 void rtarget(Node p, int n, Symbol r)
2 {
3    Node q = p->kids[n];

4    assert(q);
5    assert(r->sclass == REGISTER || !r->x.wildcard);
6    if (NULL == q->syms[RX]
7    || (r != q->syms[RX] && !q->syms[RX]->x.wildcard)){/*LOAD实现将值装入特定的>寄存器*/
8        q->count--; /*因为LOAD会增加q结点的引用计数*/
9        q = newnode(LOAD + optype(q->op),
10            q, NULL, q->syms[0]);
11        p->kids[n] = q;
12    }
13    setreg(q, r);
14 }
4－5	断言检查寄存器r必须为固定寄存器。
6－7	只有在q结点没有分配寄存器或者不是r并且为固定寄存器时，
		才需要LOAD结点将值传送至r寄存器。
9－12	在原dag中增加LOAD结点
13		分配q结点寄存器为r。
--------------------------------------------------------------------------------
/*prelabel:为forest预先设置待分配的寄存器*/
1 static void prelabel(Node forest)
2 {
3	 Node p = forest;
4    if (NULL == p || p->x.emitted)
5        return ;
6    prelabel(p->kids[0]);
7    prelabel(p->kids[1]);
8    if (NeedsReg[index(p->op)]) /*为需要寄存器的结点设置合适的寄存器组*/
9        setreg(p,rmap[optype(p->op)]);
10    switch (generic(p->op)) {
11    case ADDRL:
12        if (REGISTER == p->syms[0]->sclass)
13            p->op = VREG+P;
14        break;
15    case INDIR:
16        if (VREG+P == p->kids[0]->op)
17            setreg(p, p->kids[0]->syms[0]);
18        break;
19    }
20    if (CALL == generic(p->op))
21        docall(p);
22    else if (ARG == generic(p->op))
23        (*IR->x.doarg)(p);
24	(IR->x.target)(p);
25 }

8－9	数组NeedsReg的定义在gen.c中，它以结点操作符为索引，
		值为1时表示结点需要寄存器。
11－13	当为寄存器变量时为了与其它的局部变量相区别
		将结点的操作符改为VREG。
15－17	引用寄存器变量的结点不需要另外分配其它的寄存器，直接使用寄存器
		变量占有的寄存器。
20－21	为函数调用保存参数区的长度，为函数调用后释放参数区做准备。
22－23	计算参数区的长度。
24		(IR->x.target)(p)为需要特殊寄存器的结点进行寄存器重定位。
		target函数定义在nasm.c。
--------------------------------------------------------------------------------
/*gen:为dag森林进行代码生成*/
1 void gen(Node forest)
2 {
3	Node p = forest;
4	int boffset;
5	DEBUG(fprint(2, "gen begin:%d\n", p->op));
6	for (p = forest; p; p = p->link) {
7		prelabel(p);
8		mark_instruction(p);