链接装载与库（一）编译和链接

分类于 Technology Blog ， Programming ， Principle 阅读次数： Disqus：本文字数： 3.4k 阅读时长 ≈ 12 分钟

原图

被隐藏了的过程

#include <stdio.h>

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

在 Linux 下，当我们使用 GCC 来编译 Hello World 程序时，只须使用最简单的命令（假设源代码文件名为 hello.c）：

1
2
3

gcc hello.c
./a.out
Hello world

事实上，上述过程可以分解为 4 个步骤，分别是预处理（Prepressing）、编译（Compilation）、汇编（Assembly）和链接（Linking）。

预编译

第一步预编译的过程相当于如下命令（-E 表示只进行预编译）：

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

或者：

1	cpp hello.c hello.i

预编译过程主要处理那些源代码文件中的以“#”开始的预编译指令。比如“#include”、“#define”等，预编译成一个。i 文件，主要处理规则如下：

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

经过预编译后的。i 文件不包含任何宏定义，并且包含的文件也已经被插入到。i 文件中。

编译

编译过程就是把预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后生产相应的汇编代码文件，这个过程往往是我们所说的整个程序构建的核心部分，也是最复杂的部分之一。上面的编译过程相当于如下命令：

1	gcc -s hello.i -o hello.s

现在版本的 GCC 把预编译和编译两个步骤合并成一个步骤，使用一个叫做 cc1 的程序来完成这两个步骤。这个程序位于“/usr/lib/gcc/i486-linux-gnu/4.1/”，我们也可以直接调用 cc1 来完成它：

1	/usr/lib/gcc/i486-linux-gnu/4.1/cc1 hello.c

或者使用如下命令：

1	gcc -s hello.c -o hello.s

汇编

汇编器是将汇编代码转变成机器可以执行的指令，每一个汇编语句几乎都对应一条机器指令。所以汇编器的汇编过程相对于编译器来讲比较简单，只是根据汇编指令和机器指令的对照表一翻译就可以了。上面的汇编过程我们可以调用汇编器 as 来完成：

1	as hello.s -o hello.o

或者：

1	gcc -c hello.s -o hello.o

或者使用 gcc 命令从 C 源代码文件开始，经过预编译、编译和汇编直接输出目标文件（Object File):

1	gcc -c hello.c -o hello.o

链接

下面让我们来看看怎么样调用 ld 才可以产生一个能够正常运行的 HelloWorld 程序：

ld -static /usr/lib/crt1.o /usr/lib/crti.o
/usr/lib/gcc/i486-linux-gnu/4.1.3/crtbeginT.o
-L/usr/lib/gcc/i486-linux-gnu/4.1.3 -L/usr/lib -L/lib hello.o --start-group
-lgcc -lgcc_eh -lc --end-group /usr/lib/gcc/i486-linux-gnu/4.1.3/crtend.o/usr/lib/crtn.o

如果把所有的路径都省略掉，那么上面的命令就是：

1	ld -static crt1.o crti.o crtbeginT.o hello.o -start-group -lgcc -lgcc_eh -lc -end-group crtend.o crtn.o

可以看到，我们需要将一大堆文件链接起来才可以得到“a.out”，即最终的可执行文件。

编译器做了什么

从最直观的角度来讲，编译器就是将高级语言翻译成机器语言的一个工具。

编译过程一般可以分为步：扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化。整个过程如下图所示：

我们将结合上图来简单描述从源代码（Source Code）到最终目标代码（Final Target Code）的过程。以一段很简单的 C 语言的代码为例子来讲述这个过程。比如我们有一行 C 语言的源代码如下：

1 2	array[index] = (index +4)*(2 +6) CompilerExpression.c

词法分析

首先源代码程序被输入到扫描器（Scanner），扫描器的任务很简单，它只是简单地进行词法分析，运用一种类似于有限状态机（Finite State Machine）的算法可以很轻松地将源代码的字符序列分割成一系列的记号（Token）。比如上面的那行程序，总共包含了 28 个非空字符，经过扫描以后，产生了 16 个记号，如下所示。

记号	类型
array	标识符
[	左方括号
index	标识符
]	右方括号
=	赋值
(	左圆括号
index	标识符
+	加号
4	数字
)	右圆括号
*	乘号
(	左圆括号
2	数字
+	加号
6	数字
)	右圆括号

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

语法分析

语法分析器生成的语法树就是以表达式（Expression）为节点的树。上面例子中的语句就是一个由赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式组成的复杂语句。

从上图中我们可以看到，整个语句被看作是一个赋值表达式；赋值表达式的左边是一个数组表达式，它的右边是一个乘法表达式；数组表达式又由两个符号表达式组成，等等。在语法分析的同时，很多运算符号的优先级和含义也被确定下来了。如果出现了表达式不合法，编译器就会报告语法分析阶段的错误。

语义分析

语法分析仅仅是完成了对表达式的语法层面的分析，但是它并不了解这个语句是否真正有意义。比如语言里面两个指针做乘法运算是没有意义的，但是这个语句在语法上是合法的。编译器所能分析的语义是静态语义（Static Semantic），所谓静态语义是指在编译期可以确定的语义，与之对应的动态语义（Dynamic Semantic）就是只有在运行期才能确定的语义。

静态语义通常包括声明和类型的匹配，类型的转换。比如当一个浮点型的表达式赋值给一个整型的表达式时，其中隐含了一个浮点型到整型转换的过程，语义分析过程中需要完成这个步骤。

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

可以看到，每个表达式（包括符号和数字）都被标识了类型。我们的例子中几乎所有的表达式都是整型的，所以无须做转换，整个分析过程很顺利。语义分析器还对符号表里的符号类型也做了更新。

中间语言生成（前端）

现代的编译器有着很多层次的优化，往往在源代码级别会有一个优化过程。源代码级优化器会在源代码级别进行优化，在上例中，细心的读者可能己经发现，（2+6）这个表达式可以被优化掉，因为它的值在编译期就可以被确定。经过优化的语法树如图 2-5 所示。

我们看到（2+6）这个表达式被优化成 8。其实直接在语法树上作优化比较困难，所以源代码优化器往往将整个语法树转换成中间代码（Intermediate Code），它是语法树的顺序表示，其实它已经非常接近目标代码了。中间代码使得编译器可以被分为前端和后端，编译器前端负责产生机器无关的中间代码，编译器后端将中间代码转换成目标机器代码，这样可以跨平台。

目标代码生成与优化（后端）

属于编译器后端，编译器后端主要包括代码生成器（Code Generator）和目标代码优化器（Target Code Optimizer）。代码生成器将中间代码转换成目标机器代码，这个过程十分依赖于目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。

最后目标代码优化器对上述的目标代码进行优化，比如选择合适的寻址方式、使用位移来代替乘法运算、删除多余的指令等。

经过这些扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化，编译器忙活了这么多个步骤以后，源代码终于被编译成了目标代码，但是这个目标代码中有一个问题是变量和函数的地址还没有确定。

链接器

假设有一种计算机，它的每条指令是 1 个字节，也就是 8 位。我们假设有一种跳转指令，它的高 4 位是 0001，表示这是一条跳转指令：

低 4 位存放的是跳转目的地的绝对地址。我们可以从上图中看到，这个程序的第一条指令就是一条跳转指令，它的目的地址是第 5 条指令（注意，第 5 条指令的绝对地址是 4）。

现在问题来了，程序并不是一写好就永远不变化的，它可能会经常被修改。比如我们在第 1 条指令之后、第 5 条指令之前插入了一条或多条指令，那么第 5 条指令及后面的指令的位置将会相应地往后移动，原先第一条指令的低位的数字将需要相应地调整。这种重新计算各个目标的地址过程被叫做重定位（Relocation）。

先驱者发明了汇编语言，这相比机器语言来说是个很大的进步。汇编语言可以使用符号来标记位置，比如一个符号“divide”表示一个除法子程序的起始地址，比记住从某个位置开始的第几条指令是除法子程序方便得多。最重要的是，这种符号的方法使得人们从具体的指令地址中逐步解放出来。比如前面纸带程序中，我们把刚开始第 5 条指令开始的子程序命名为“foo”，那么第一条指令的汇编就是：

jmp foo

符号（Symbol）这个概念随着汇编语言的普及迅速被使用，它用来表示一个地址，这个地址可能是一段子程序的起始地址，也可以是一个变量的起始地址。

在一个程序被分割成多个模块以后，这些模块之间最后如何组合形成一个单一的程序是须解决的问题，那就是模块间符号的引用。这个模块的拼接过程就是链接（Linking）。

静态链接

链接的主要内容就是把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确地衔接。链接器所要做的工作其实跟前面所描述的“程序员人工调整地址”本质上没什么两样，链接过程主要包括了地址和空间分配（Address and Storage Allocation）、符号决议（Symbol Resolution）和重定位（Relocation）等这些步骤。

使用链接器，你可以直接引用其他模块的函数和全局变量而无须知道它们的地址，因为链接器在链接的时候，会根据你所引用的符号 foo，自动去相应的 func.c 模块查找 foo 的地址，然后将 main.c 模块中所有引用到 foo 的指令重新修正，让它们的目标地址为真正的 foo 函数的地址。这就是静态链接的最基本的过程和作用。

让我们结合具体的 CPU 指令来了解这个过程。假设我们有个全局变量叫做 var，它在目标文件 A 里面。我们在目标文件 B 里面要访问这个全局变量，比如我们在目标文件里面有这么一条指令：

1	movl %Ox2a,var

这条指令就是给这个 var 变量赋值 0x2a，相当于 C 语言里面的语句 var=42。然后我们编译目标文件 B，得到这条指令机器码，如下图所示：

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

参考文献

《程序员的自我修养》