第2章 静态链路

预处理（预编译）: 处理那些源代码文件中的以“#”开始的预编译指令。

编译：扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化，生成汇编代码。

汇编：将汇编代码转变成机器可以执行的指令。

链接：将各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确地衔接。即把一些指令对其他符号地址的引用加以修正。

概述

IDE和编译器提供了默认配置，编译和链接参数对于大部分应用程序开发而言已经足够了。我们需要探究程序背后的细节和本质，就需要了解软件运行背后的机理及支撑软件运行的各种平台和工具。

被隐藏了的过程

在Linux下，使用GCC来编译Hello World程序时，只需要简单地执行：

gcc hello.c
./a.out

上述过程可以细化为4个步骤，分别是预处理（Prepressing）、编译（Compilation）、汇编（Assembly）和链接（Linking），如图所示：

预编译

gcc -E hello.c -o hello.i

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

  • 将所有的“#define”删除，并且展开所有的宏定义。

  • 处理所有条件预编译指令，比如“#if”、“#ifdef”、“#elif”、“#else”、“#endif”。

  • 处理“#include”预编译指令，将被包含的文件插入到该预编译指令的位置。注意，这个过程是递归进行的，也就是说被包含的文件可能还包含其他文件。

  • 删除所有的注释“//”和“//”。**

  • 添加行号和文件名标识，比如#2“hello.c” 2，以便于编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示行号。

  • 保留所有的#pragma编译器指令，因为编译器须要使用它们。

  • 备注：#pragma 指令可能是最复杂的了，它的作用是设定编译器的状态或者是指示编译器完成一些特定的动作。

    • #pragma once 指定在创建过程中该编译指示所在的文件仅仅被编译程序包含（打开）一次。

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

编译

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

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

/usr/lib/gcc/i486-linux-gnu/4.1/ccl hello.c
gcc -S hello.c -o hello.s

对于c语言，这个预编译和编译的程序是ccl，对于c++，对应程序为cclplus；Objective-C是cclobJ；fortran是f771：Java是jcl。

所以实际上gcc这个命令只是这些后台程序的包装，它会根据不同的参数要求去调用预编译编译程序ccl、汇编器as、链接器ld。

汇编

汇编器是将汇编代码转变成机器可以执行的指令，每一个汇编语句几乎都对应一条机器指令。所以汇编器的汇编过程相对于编译器来讲比较简单，它没有复杂的语法，也没有语义，也不需要做指令优化，只是根据汇编指令和机器指令的对照表一一翻译就可以了，“汇编”这个名字也来源于此。上面的汇编过程我们可以调用汇编器as来完成：

as hello.s -o hello.o

gcc -c hello.s -o hello.o

链接器

如何调用ld才可以产生一个能够正常运行的HelloWorld程序：

省略掉路径前缀后

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

可以看到，我们需要将一大堆文件链接起来才可以得到“a.out”，即最终的可执行文件。看了这行复杂的命令，可能很多读者的疑惑更多了，crt1.o、crti.o、crtbeginT.o、crtend.o、crtn.o这些文件是什么？它们做什么用的？-lgcc -lgcc-eh -1c这些都是什么参数？为什么要使用它们？为什么要将它们和hello.o链接起来才可以得到可执行文件？等等。

编译器做了什么

编译器就是将高级语言翻译成机器语言的一个工具。

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

array[index] = (index + 4) * (2 + 6)

词法分析

首先源代码程序被输入到扫描器（Scanner), 扫描器的任务很简单，它只是简单地进行词法分析，运用一种类似于有限状态机（Finite State Machine)的算法可以很轻松地将源代码的字符序列分割成一系列的记号(Token）。

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

有一个叫做lex的程序可以实现词法扫描，它会按照用户之前描述好的词法规则将输入的字符串分割成一个个记号。因为这样一个程序的存在，编译器的开发者就无须为每个编译器开发个独立的词法扫描器，而是根据需要改变词法规则就可以了。

语法分析

语法分析器（Grammar Parser)将对由扫描器产生的记号进行语法分析，从而产生语法树（Syntax Tree)。整个分析过程采用了上下文无关语法（Context-free Grammar)的分析手段，如果你对上下文无关语法及下推自动机很熟悉，那么应该很好理解。

正对上述C语言表达式生成的语法树如下：

语法分析也有一个现成的工具叫做yacc（Yet Another compiler compiler)。它也像lex一样，可以根据用户给定的语法规则对输入的记号序列进行 解析，从而构建出一棵语法树。对于不同的编程语言，编译器的开发者只须改变语法规则，无须为每个编译器编写一个语法分析器，所以它又被称为“编译器编译器（compiler Compiler)”。

语义分析

语义分析器(Semantic Analyzer)。语法分析仅仅是完成了对表达式的语法层面的分析，但是它并不了解这个语句是否真正有意义。比如C语言里面两个指针做乘法运算是没有意义的，但是这个语句在语法上是合法的。

编译器所能分析的语义是静态语义（Static Semantic），所谓静态语义是指在编译期可以确定的语义，与之对应的动态语义（Dynamic Semantic）就只有在运行期才能确定的语义。

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

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

中间语言生成

源码级优化器(Source Code Optimizer)在不同编译器中可能会有不同的定义或有一些其他的差异。源代码级优化器会在源代码级别进行优化，优化后的语法树如图：

我们看到（2+6）这个表达式被优化成8。其实直接在语法树上作优化比较困难，所以源代码优化器往往将整个语法树转换成中间代码(Intermediate Code)，它是语法树的顺序表示，其实它己经常接近目标代码了。但是它一般跟目标机器和运行时环境是无关的，比如它不包含数据的尺寸、变量地址和寄存器的名字等。

中间代码有很多种类型，在不同的编译器中有着不同的形式，比较常见的有：三地址码（Three-address Code）和P-代码（P-Code）。我们就拿最常见的三地址码来作为例子，最基本的三地址码是这样的：

x = y op z

上述优化过程：

t1 = 2 + 6
t2 = index + 4
t3 = t2 * t1
array[index] = t3

//优化为

t2 = index + 4
t2 = t2 * 8
array[index] = t2

中间代码使得编译器可以被分为前端和后端。**编译器前端负责产生机器无关的中间代码，编译器后端将中间代码转换成目标机器代码。**这样对于一些可以跨平台的编译器而言，它们可以针对不同的平台使用同一个前端和针对不同机器平台的数个后端。

目标代码生成与优化

源代码级优化器产生中间代码标志着下面的过程都属于编辑器后端。编译器后端主要包括代码生成器(Code Generator)和目标代码优化器(Target Code Optimizer)。代码生成器将中间代码转换成目标机器代码，这个过程十分依赖于目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。对于上面例子中的中间代码，代码生成器可能会生成下面的代码序列：

movl index, %ecx        ; value of index to ecx
addl $4, %ecx           ; ecx = ecx + 4
mull $8, %ecx           ; ecx = ecx * 4
movl index, %eax        ; value of index to eax
movl %ecx, array(,eax,4); array[index] = ecx

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

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

经过这些扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化，源代码被编译成了目标代码。但是这个目标代码中有一个问题是：index和array的地址还没有确定。

如果我们要把目标代码使用汇编器编译成真正能够在机器上执行的指令，那么index和array的地址应该从哪儿得到呢？

这个看似简单的问题引出了一个很大的话题：目标代码中有变量定义在其他模块，该怎么办？事实上，定义其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件，然后由链接器最终将这些目标文件链接起来形成可执行文件。让我们带着这个问题，走进链接的世界。

链接器年龄比编译器长

重新计算各个目标的地址过程被叫做重定位(Relocation)。

C语言中，最小的单位是变量和函数，若干个变量和函数组成一个模块，存放在一个“.c”的源代码文件里，然后这些源代码文件按照目录结构来组织。

在现代软件开发过程中，软件的规模往往都很大，动辄数百万行代码，如果都放在一个模块肯定无法想象。所以现代的大型软件往往拥有成千上万个模块，这些模块之间相互依赖又相对独立。这种按照层次化及模块化存储和组织源代码有很多好处，比如代码更容易阅读、理解、重用，每个模块可以单独开发、编译、测试，改变部分代码不需要编译整个程序等。

在一个程序被分割成多个模块以后，这些模块之间最后如何组合形成一个单一的程序是必须解决的问题。最常见的属于静态语言C/C++模块之间通信有两种方式，一种是模块间的函数调用，另外一种是模块间的变量访问。函数访问须知道目标函数的地址，变量访问也须知道目标变量的地址，所以这两种方式都可以归结为一种方式，那就是模块间符号的引用。模块间依靠符号来通信类似于拼图版，定义符号的模块多出一块区域，引用该符号的模块刚好少了那一块区域，两者一拼接刚好完美组合。这个模块的拼接过程就是本书的一个主题：链接(Linking)。

链接的主要内容就是把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确地衔接。链接器所要做的工作其实跟前所描述的“程序员人工调整地址”本质上没什么两样，只不过现代的高级语言的诸多特性和功能，使得编译器、链接器更为复杂，功能更为强大，但从原理上来讲，它的工作无非就是把一些指令对其他符号地址的引用加以修正。

链接过程主要包括了地址和空间分配（Address and Storage Allocation）、符号决议(Symbol Resolution）和重定位（Relocation）等这些步骤。

静态链接过程如图：

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

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

Last Updated:
Contributors: klc407073648