编译和链接——读书笔记

对于下面的程序

#include
int main()
{printf("Hello World\n");return 0;
}


当使用GCC来编译上面的程序时

gcc hello.c
./a.out
Hello World


上述过程可以分为四个步骤&＃xff0c;分别是预处理&＃xff0c;编译&＃xff0c;汇编&＃xff0c;链接。

预编译

首先是源代码文件hello.c和相关的头文件&＃xff0c;如stdio.h等被编译器cpp预编译成一个.i文件。对于c&＃43;&＃43;程序来说&＃xff0c;它的源代码文件的扩展名可能是.cpp或.cxx&＃xff0c;头文件的扩展名可能是.hpp&＃xff0c;而预编译后的文件扩展名是.ii。

第一步预编译的过程相当于如下命令&＃xff08;-E表示只进行预编译&＃xff09;。

$gcc -E hello.c -o hello.i


预编译过程主要处理那些源代码文件中的以"#"开始的预编译指令。比如#include&＃xff0c;#define等。

主要处理规则如下&＃xff1a;

• 将所有的#define删除&＃xff0c;并且展开所有的宏定义。
• 处理所有条件预编译指令&＃xff0c;比如#if&＃xff0c;#ifdef&＃xff0c;#elif&＃xff0c;#else&＃xff0c;#endif。
• 处理#include预编译指令&＃xff0c;将被包含的文件插入到该预编译指令的位置。注意&＃xff0c;这个过程是递归进行的&＃xff0c;也就是说被包含的文件可能还包含其他文件。
• 删除所有注释//和/**/
• 添加行号和文件名表示&＃xff0c;比如#2 "hello.c" 2&＃xff0c;以便编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示行号。
• 保留所有的#pragma编译器指令&＃xff0c;因为编译器要使用它们。

经过预编译后的.i文件不包含任何宏定义&＃xff0c;因为所有的宏都已经被展开&＃xff0c;而且包含的文件也已经被插入到.i文件中。所以当我们无法判断宏定义是否正确或头文件包含是否正确时&＃xff0c;可以查看与编译后的文件来确定问题。

编译

编译过程就是把预处理完的文件进行一系列词法分析&＃xff0c;语法分析&＃xff0c;语义分析及优化后产生相应的汇编代码文件。

编译过程相当于下面的命令

$gcc -S hello.i -o hello.s
# 或者使用下面的指令
$gcc -S hello.c -o hello.s


现在版本的GCC把预编译和编译合并为一个步骤。使用一个叫做ccl的程序来完成这两个步骤。

汇编

汇编器是将汇编代码转变成机器可以执行的指令&＃xff0c;每一个汇编语句几乎都对应一条机器指令。所以汇编器的汇编过程相对简单&＃xff0c;没有复杂的语法&＃xff0c;也没有语义&＃xff0c;也不需要做指令优化&＃xff0c;只是根据汇编指令和机器指令的对照表一一翻译就可以了。可以使用汇编器as来完成。

$as hello.s -o hello.o
#或者
$gcc -c hello.c -o hello.o


生成目标文件。

链接

编译器就是将高级语言翻译成机器语言的一个工具。比如使用C/C&＃43;&＃43;语言写的一个程序可以使用编译器将其翻译成机器可以执行的指令及数据。

编译过程一般可以分为6步&＃xff1a;扫描&＃xff0c;词法分析&＃xff0c;语法分析&＃xff0c;语义分析&＃xff0c;源代码优化&＃xff0c;代码生成和目标代码优化。

整个过程如下所示

以下面的代码作为例子

//CompilerExpression.c
array[index] &＃61; (index &＃43; 4) * (2 &＃43; 6);


词法分析

首先源代码程序被输入到扫描器&＃xff0c;扫描器只是简单地进行词法分析&＃xff0c;运用一种有限状态机的算法可以很轻松地将源代码的字符序列分割成一系列的记号&＃xff08;token&＃xff09;。

词法分析产生的记号一般可以分为如下几类&＃xff1a;关键字&＃xff0c;标识符&＃xff0c;字面量&＃xff08;包含数字&＃xff0c;字符串等&＃xff09;和特殊符号&＃xff08;加号&＃xff0c;等号&＃xff09;。在识别记号的同时&＃xff0c;扫描器也完成了其他工作&＃xff0c;比如将标识符存放到符号表&＃xff0c;将数字&＃xff0c;字符串常量存放到文字表等&＃xff0c;以备后面的步骤使用。

有个叫做lex的程序可以实现词法扫描&＃xff0c;它会按照用户之前扫描好的词法规则将输入的字符串分割成一个个记号。

语法分析

语法分析器将对由扫描器产生的记号进行语法分析&＃xff0c;从而产生语法树。整个分析过程采用了上下文无关语法的分析手段。简单地说&＃xff0c;由语法分析器生成的语法树就是以表达式为节点的树。C语言的一个语句是一个表达式&＃xff0c;而复杂的语句是很多表达式的组合。上面的例子就是一个由赋值表达式&＃xff0c;加法表达式&＃xff0c;乘法表达式&＃xff0c;数组表达式&＃xff0c;括号表达式组成的复杂语句。

经过语法分析器以后形成的如下图所示的语法树。

从上图可以看出&＃xff0c;整个语句被看成一个赋值表达式&＃xff1b;赋值表达式的左边是一个数组表达式&＃xff0c;右边是一个乘法表达式&＃xff1b;数组表达式由两个符号表达式组成。符号和数字是最小的表达式&＃xff0c;它们不是由其他的表达式来组成的&＃xff0c;所以它们通常作为整个语法树的叶节点。在语法分析的同时&＃xff0c;很多运算符号的优先级和含义也被确定下来。比如乘法表达式的优先级比加法高&＃xff0c;而圆括号表达式的优先级比乘法高。另外有些符号具有多重含义&＃xff0c;比如星号在C语言中可以表达乘法表达式&＃xff0c;也可以表示对指针取内容的表达式&＃xff0c;所以语法分析阶段必须对这些内容进行区分。如果出现了表达式不合法&＃xff0c;比如各种括号不匹配&＃xff0c;表达式中缺少操作符等&＃xff0c;编译器就会报告语法分析阶段的错误。

语义分析

语义分析器完成语义分析。语法分析仅仅完成了对表达式的语法层面的分析&＃xff0c;但是它并不了解这个语句是否真正有意义。比如C语言中两个指针做乘法运算是没有意义的&＃xff0c;但是这个语句在语法上是合法的&＃xff1b;比如同样一个指针和一个浮点数做乘法运算是否合法等。编译器所能分析的语义是静态语义&＃xff0c;所谓静态语义是指在编译期间可以确定的语义&＃xff0c;与之对应的动态语义就是只有在运行起才能确定的语义。

静态语义通常包括声明和类型的匹配&＃xff0c;类型的转换。比如当一个浮点型的表达式赋值给一个整型的表达式时&＃xff0c;其中隐含了一个浮点型到整型转换的过程&＃xff0c;语义分析过程中需要完成这个步骤。比如将一个浮点型赋值给一个指针的时候&＃xff0c;语义分析程序会发现这个类型不匹配&＃xff0c;编译器将会报错。动态语义一般指在运行期间出现的语义相关的问题&＃xff0c;

经过语义分析阶段以后&＃xff0c;整个语法树的表达式都被标识了类型。如果有些类型需要做隐式转换&＃xff0c;语义分析程序会在语法树中插入相应的转换节点。上面的语法树在经过语义分析阶段后成为下图所示的形式。

可以看到&＃xff0c;每个表达式&＃xff08;包括符号和数字&＃xff09;都被标识了类型。

中间代码生成

现代编译器有很多层次的优化&＃xff0c;往往在源代码级别会有一个优化过程。源码级优化器在不同编译器中可能会有不同的定义或有一些其他的差异。源代码级优化器会在源代码级别进行优化。上面的例子中&＃xff0c;(2&＃43;6)这个表达式可以被优化掉&＃xff0c;因为它的值在编译期间就可以被确定。

经过优化的语法树如下图所示。

可以看到&＃xff08;2&＃43;6&＃xff09;这个表达式被优化成8。直接在语法树上做优化很困难&＃xff0c;所以源代码优化器往往将整个语法树转换成中间代码&＃xff0c;它是语法树的顺序表示&＃xff0c;其实它已经非常接近目标代码了&＃xff0c;但是它一般跟目标机器和运行时环境是无关的&＃xff0c;比如它不包含数据的尺寸&＃xff0c;变量地址和寄存器的名字等。

中间代码使得编译器可以被分成前端和后端。编译器前端负责产生机器无关的中间代码&＃xff0c;编译器后端将中间代码转换成目标机器代码。

目标代码生成与优化

源代码级优化器产生中间代码标志着下面的过程属于编译器后端。编译器后端主要包括代码生成器和目标代码优化器。代码生成器将中间代码转换成目标机器代码&＃xff0c;这个过程十分依赖于目标机器&＃xff0c;因为不同的机器有着不同的字长&＃xff0c;寄存器&＃xff0c;整数数据类型和浮点数数据类型等。对于上面的中间代码&＃xff0c;代码生成器可能会生成下面的代码序列。

movl index, %ecx;
addl $4, %ecx;
mull $8, %ecx;
movl index, %eax;
movl %ecx,array(,eax,4);


最后目标代码优化器对上述的目标代码进行优化&＃xff0c;比如选择合适的寻址方式&＃xff0c;使用位移来替代乘法运算&＃xff0c;删除多余的指令等。上面的例子中&＃xff0c;乘法由一条相对复杂的基址比例变址寻址的lea指令完成&＃xff0c;虽有由一条mov指令完成最后的赋值操作&＃xff0c;这条mov指令的寻址方式与lea是一样的。

movl index, %edx;
leal 32(,%edx,8), %eax;
movl %eax,array(,%edx,4);


经过这些扫描&＃xff0c;语法分析&＃xff0c;语义分析&＃xff0c;源代码优化和目标代码优化&＃xff0c;源代码被编译成了目标代码&＃xff0c;但是这个目标代码有一些问题&＃xff0c;就是index和array的地址没有确定。如果要把目标代码使用汇编器编译成真正能够在机器上执行的指令&＃xff0c;那么index和array的地址应该从哪得到呢&＃xff1f;如果index和array定义在跟上面的源代码同一个编译单元里面&＃xff0c;那么编译器可以为index和array分配空间&＃xff0c;确定它们的地址&＃xff1b;如果定义在其他的程序模块呢&＃xff1f;

事实上&＃xff0c;定义在其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件&＃xff0c;然后由链接器最终将这些目标文件链接起来形成可执行文件。

一个复杂的系统可以分成若干个小的系统&＃xff0c;把每个源代码模块独立地编译&＃xff0c;然后按照顺序将它们组装起来&＃xff0c;这个组装模块的过程就是链接。链接的主要内容就是把各个模块之间相互引用的部分都处理好&＃xff0c;使得各个模块之间能够正确地衔接。从原理上来说&＃xff0c;链接的工作就是把一些指令对其他符号地址的引用加以修正。链接过程主要包括了地址和空间分配&＃xff0c;符号决议&＃xff0c;重定位等这些步骤。

符号决议有时候也被叫做符号绑定&＃xff0c;名称绑定&＃xff0c;名称决议&＃xff0c;甚至还有叫做地址绑定&＃xff0c;指令绑定&＃xff0c;大体上它们的意思都一样&＃xff0c;决议倾向于静态链接&＃xff0c;而绑定倾向于动态链接。

最基本的静态链接如下图所示&＃xff08;Object File&＃xff0c;一般扩展名为.o或.obj&＃xff09;&＃xff0c;目标文件和库一起链接形成最终可执行文件。最常见的库就是运行时库&＃xff0c;它是支持程序运行的基本函数的集合。库其实是一组目标文件的包&＃xff0c;就是一些最常用的代码编译成目标文件后打包存放。

现代的编译和链接过程并没有那么难。比如我们在程序模块main.c中使用另外一个模块func.c中的函数foo()。在main.c模块中每一处调用foo的时候都必须确切知道foo这个函数的地址&＃xff0c;但是由于每个模块都是单独编译的&＃xff0c;在编译器编译main.c的时候它并不知道foo函数的地址&＃xff0c;所以它暂时把这些调用foo的指令的目标地址搁置&＃xff0c;等待最后链接的时候由链接起曲江这些指令的目标地址修正。如果没有链接器&＃xff0c;我们必须手工把每个调用foo的指令进行修正&＃xff0c;则填入正确的foo函数地址。当func.c模块被重新编译&＃xff0c;foo函数的地址有可能改变时&＃xff0c;那么我们在main.c中所有使用foo的地址的指令将要全部重新调整。使用链接器&＃xff0c;你可以直接引用其他模块的函数和全局变量而无须知道它们的地址&＃xff0c;因为链接器在链接的时候&＃xff0c;会根据所引用的符号foo&＃xff0c;自动去相应的func.c模块查找foo的地址&＃xff0c;然后将main.c模块中所有应用到foo的指令重新修正&＃xff0c;让它们的目标地址为真正的foo函数的地址。这就是静态链接的最基本的过程和作用。

在链接过程中&＃xff0c;对其他定义在目标文件中的函数调用的指令必须要重新调整&＃xff0c;对使用其他定义在其他目标文件的标量来说&＃xff0c;也存在同样的问题。可以结合具体的CPU指令来了解这个过程。

假设有一个全局变量叫做var&＃xff0c;它在目标文件A里面&＃xff0c;当在目标文件B里面要访问这个全局变量&＃xff0c;比如在目标文件B里面有这么一条指令&＃xff1a;

movl $0x2a,var;


这条指令就是给这个var变量赋值0x2a&＃xff0c;相当于C语言中的var&＃61;42&＃xff0c;然后编译目标文件B&＃xff0c;得到这条指令机器码&＃xff0c;如下图所示&＃xff1a;

由于在编译目标文件B时&＃xff0c;编译器并不知道变量var的目标地址&＃xff0c;所以编译器在无法确定地址的情况下&＃xff0c;将这条mov指令的目标地址置为0&＃xff0c;等待链接器在将目标文件A和B链接起来的时候再将其修正。我们假设A和B链接后&＃xff0c;变量var的地址确定下来为0x1000&＃xff0c;那么链接器将会把这个指令的目标地址部分修改成0x1000。这个地址修正的过程也被叫做重定位&＃xff0c;每个要被修正的地方叫一个重定位入口。重定位所做的就是给程序中每个这样的绝对地址引用的位置“打补丁”&＃xff0c;使它们指向正确的地址。