编译器在经过词法分析、语法分析之后,就把源代码变成了抽象语法树(AST)。
接下来,编译器的任务就是把AST变成机器码。
AST,是一个表示代码逻辑的树形结构,它是不能直接顺序遍历的,而只能递归遍历。
递归遍历的逻辑更复杂,不适合用在机器码、汇编码、字节码上。
越是底层代码越贴近数字电路,而数字电路不适合直接处理复杂的逻辑。
递归也属于复杂的逻辑,
所以C语言的入门程序之一就是“汉诺塔”,而数学归纳法可以成为一种常用的证明方法。
AST的树形结构,肯定是不适合直接在CPU上运行的,而要先把它变成机器码。
AST是怎么变成机器码的?
1,语义分析,
语义分析的作用有3个:
1)类型检查,
2)常量表达式的计算,
3)函数重载,
如果不是OOP语言,语义分析时不需要考虑函数重载问题。
语义分析最主要的作用还是类型检查。
编译器报出来的很多错误或警告信息,都是类型检查时给出来的,例如:
A* p = malloc(sizeof(A));
在C++中就会报错:从void指针到A的指针没有加类型转换(type cast)。
AST
赋值运算符=两边的类型,是语义分析时首先要检查的(其他运算符也一样)。
如果类型不匹配,在强类型语言的编译器里就要给出错误提示。
另外,sizeof(A) 都是常量表达式,也要在语义分析时计算出来。
把常量表达式提前在编译时计算出来,可以提高运行时的速度。
如果是脚本语言的解释器的话,在语义分析之后,就可以直接在AST运行了:
给每个运算符节点定义一个处理函数,该调用哪个就调用哪个,就可以得出程序的结果;
if / while / for 等分支循环的关键字,也可以一样看做是运算符。
如果是编译器或虚拟机,还需要继续往下处理。
虚拟机也是运行机器码的,只是和CPU的机器码不一样:虚拟机的机器码一般叫字节码。
2,三地址码的生成,
三地址码,是编译器的后端常用的中间代码。
生成了三地址码之后,就把AST的树形结构变成了顺序结构了,跟汇编码、机器码、字节码一样了。
struct A { int x, y; };
A* p = malloc(sizeof(A));
生成的三地址码是这样的:
call ret; malloc, 8
assign p; ret
第一个词是三地址码的指令(opcode),分号前面的是目的操作数(dst operand),分号后面的是源操作数列表(src operands list),多个源操作数之间以逗号分隔。
按照源代码的执行顺序,把AST遍历一遍,就可以生成三地址码。
源代码里分为顺序语句、if else语句、while语句、for语句等等,每种语句类型生成的三地址码是不一样的。
if else语句的三地址码会有分支跳转:往函数的结尾方向跳转。
while语句、for语句的三地址码会有循环跳转:往函数的开头方向跳转。
for (i = 0; i < 10; i++) printf("%dn", i);
上述for循环的AST和三地址码
汇编码,是机器码的人类阅读版[呲牙]
生成了三地址码之后,把它变成机器码还是很容易的(如果不考虑运行效率的话)。
编译器后端的各种优化,主要还是为了让生成的机器码运行更快,而不仅仅是为了让机器码运行正确。
编译器的后端优化是个无底洞,因为程序员对代码的理解总是比编译器更深刻。
毕竟程序员是个大活人,而编译器有赖于程序员给它升级版本。
3,正确运行相关的优化,
加载(load)和保存(save)指令的位置,都是跟机器码的正确运行相关的优化。
除非每条运算指令都把结果写到内存,否则加载和保存指令的位置必须正确。
加载指令的位置在基本块的开头,保存指令的位置在基本块的末尾。
基本块,指的是没有跳转指令的顺序语句块。
for (i = 0; i < 10; i++) printf("%dn", i);
还是以前面的for循环为例子:
assign i, 0
这就是第1个基本块,因为接下来就要比较 i < 10了,而且还可能从后面跳回来多次比较。
cmp i, 10
这是第2个基本块,接下来会根据i < 10的比较结果进行跳转。
call printf, "%dn", i
inc i
这两行是第3个基本块,它们之间也没有跳转,而再往后就要跳转回开头,再次检查条件表达式。
跳转的源位置和跳转的目的位置,都是一个新的基本块的开始位置:
因为它们(前面或后面)的代码的执行分支是可能变化的,所以要单独划到一个基本块里。
for循环的流程图
如果在某个基本块里修改了某个变量,就要在末尾把它保存到内存。
如果在某个基本块里要使用某个变量,就要在开头把它加载到寄存器。
如上图:
对 i 赋值 0 之后要把它保存到内存,见绿色的save i指令;
在比较i < 10之前要把它从内存加载到寄存器,见绿色的load i指令。
这样生成指令,就可以保证运行结果的正确。
但为了让它运行的更快,一般会把循环内的加载放到循环的开头,把循环内的保存放到循环的末尾。
goto不受待见,从编译器的层面来看,就是goto会导致循环的出口和入口有多个。
4,变量之间的冲突,
互相冲突的变量不能使用相同的寄存器,这是寄存器分配的原则。
怎么判断变量之间互相冲突呢?
就是某个变量如果在后面还要用,那么它跟其他变量就是冲突的。
例如:
a = 1;
b = 2;
c = a + b;
那么a和b就是冲突的。
因为第3行代码都要用到它们两个,所以在第2行代码的时候:a占用的寄存器不能腾出来,b必须找其他寄存器用。
第3行代码之后,a和b都没用了,c可以跟a或b的任何一个使用相同的寄存器。
所以上面的代码翻译成汇编,可以这样:
mov eax, 1
mov ebx, 2
add eax, ebx
a和c都使用eax,b使用ebx。
但是a和b不能都使用eax,否则结果就是错的。
变量之间是否冲突,要从后往前看。
编译器里在检查变量的冲突时,都是从函数的末尾往开头反向遍历每一条代码,看看哪些变量之间是冲突的。
有兴趣的可以看看我写的scf编译器框架的代码,在文件scf_basic_block.c里。
5,寄存器的分配,
确定了变量之间的冲突情况之后,就可以给代码里的变量分配寄存器了。
例如:
a = 2;
b = 3;
c = 4;
d = a + b + c;
这个例子的abc三者之间都是冲突的,因为在第4行同时用到了它们3个。
画个变量的冲突图如下:
变量的冲突图
a, b, c之间是互相冲突的,每一对冲突的变量之间有一条连线,所以正好画成一个三角形。
在分配寄存器时,abc互相之间不能分配相同的寄存器。
也就是说,把寄存器的编号作为颜色的话,上图三角形的3个顶点不能着同样的颜色。
在变量的冲突图上,每一条边的两个端点必须着不同的颜色。
这就是用于寄存器分配的图的着色算法。
分配完寄存器之后就好办了,按照每种CPU的手册生成指令的机器码就可以了。
例如:
给a, b, c分别分配eax, ebx, ecd,
d与a共用eax,
那么汇编指令就是:
mov eax, 2
mov ebx, 3
mov ecx, 4
add eax, ebx
add eax ecx.
x64的机器码我实在记不住,但在汇编层面,我还是可以充当个人形编译器的[大笑]
有兴趣的可以看看我的scf编译器框架的源码,非常的清晰。
编译原理(龙书)确实没怎么细说后端是怎么写的,只是提了一下图的着色算法。
不过对于我来说,我只要知道有这么个软件,我就能把它写出来!
求个赞赏[捂脸]
虽然重阳一生不弱于人,但还是要靠九阴真经来破解古墓派的武功啊。