编译和链接基础知识

  • 机器语言：能够被计算机识别和执行的二进制指令。
  • 汇编语言：面向机器的程序设计语言，汇编指令和机器语言之间有着一一对应的关系，人看汇编代码很吃力，但是比起一大串的01代码还是简单的多。
  • 高级语言：程序员编写的语言，C、C++、Java等。

 程序员编写的高级语言符合人类的思维模式，但是计算机只认识0和1，无法识别高级语言，因此，我们编写好的代码，需要一种中间过程，将我们写好的代码，转换为二进制代码，从而让计算机得以执行。

 源文件转换为二进制文件经历了以下几个阶段：预处理(prepressing)、编译(compilation)、汇编(assembly)、链接(linking)，如下图所示：

 hello.c文件

1
2
3
4
5
6
#include <stdio.h>
int main()
{
	printf("Hello World\n");
	return 0;
}

 经过gcc编译器编译（指以上的所有阶段，不是单指编译阶段）后，得到可执行文件。

1
gcc hello.c -o hello.out

 预处理需要预处理程序（c中叫cpp）处理、编译需要编译程序（c中叫cc1、c++中叫cc1plus、oc叫cc1obj、java叫jc1……）处理、汇编需要汇编程序程序（c中叫as）处理，链接需要链接器（c中叫ld）处理。gcc实际上是对这些过程的封装，通过不同的参数调用不同的处理程序。
 以上编译过程可以拆解为：

1
2
3
4
gcc -E hello.c -o hello.i        // 预编译
gcc -S hello.i -o hello.s        // 编译
gcc -c hello.s -o hello.o      // 汇编，目标文件
gcc hello.o -o hello.out      // 链接，可执行文件

1. 源代码是如何到二进制的

1.1 预编译

预编译主要是对源文件中的预编译指令进行处理，比如#include、#define等。处理规则如下：

  • 删除所有的”#define”，并展开所有宏定义
  • 处理所有的条件预编译指令，比如 #if、#ifdef……
  • 处理#include预编译指令，将所有被包含的文件插入进该指令位置
  • 删除所有的注释
  • 添加行号和文件名标识，便于编译是产生调试用的信息
  • 保留所有的#pragma指令，供后续使用
    1
    gcc -E hello.c -o hello.i        // 预编译
    预编译之后，文件不再包含任何宏信息，以下是预处理之后文件的部分代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    # 1 "hello.c"
    # 1 "<built-in>" 1
    # 1 "<built-in>" 3
    # 361 "<built-in>" 3
    # 1 "<command line>" 1
    # 1 "<built-in>" 2
    # 1 "hello.c" 2
    # 1 "/Library/Developer/CommandLineTools/SDKs/MacOSX10.14.sdk/usr/include/stdio.h" 1 3 4
    # 64 "/Library/Developer/CommandLineTools/SDKs/MacOSX10.14.sdk/usr/include/stdio.h" 3 4
    # 1 "/Library/Developer/CommandLineTools/SDKs/MacOSX10.14.sdk/usr/include/_stdio.h" 1 3 4

    …………

    extern int __vsnprintf_chk (char * restrict, size_t, int, size_t,
           const char * restrict, va_list);
    # 412 "/Library/Developer/CommandLineTools/SDKs/MacOSX10.14.sdk/usr/include/stdio.h" 2 3 4
    # 2 "hello.c" 2

    int main(int argc, char const *argv[])
    {
     printf("%s\n", "Hello World!");
     return 0;
    }

1.2 编译

 编译过程主要是把预处理之后的文件进行一系列的词法分析、语法分析、语义分析及源码优化，编译后会产生相应的汇编源文件。这也是整个过程中最复杂的一部分。

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

 现代的gcc把预编译和编译两个步骤合并，使用cc1一步完成。

1.3 汇编

 汇编器将汇编代码编程机器可以执行的指令， 每一条汇编指令都对应着一条机器指令。汇编器的执行很简单，不需要优化，只需要对照汇编指令和机器指令表一一翻译即可。

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

1.4 链接

通常我们看到链接会链接一大串文件，如下图所示，它会把编译生成的目标文件和运行时需要的库等打包放一起。具体后面会讲。

1
2
3
4
$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
2
gcc hello.o -o hello.out
gcc hello.c -o hello.out

2. 编译的过程

 编译主要分为6步：词法分析、语法分析、语义分析、中间代码优化、目标代码生成和目标代码优化。这里的编译实际上是上述的编译和汇编两个过程。
编译过程
 其中前4个步骤生成中间代码，它是和机器无关的，被称为前端编译，后2个步骤，和具体的平台架构、字长等相关，又叫做后端编译。

2.1 词法分析

 源代码程序被输入到扫描器，它会做语法分析，运用算法将字符串分割成一系列的记号。
 比如有一行c源码：

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

 包含28个非空字符，扫描后，分割成16个记号。

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

 词法分析产生的记号有几类：关键字、标识符、字面量和特殊符号（加号、括号等），扫描器在识别的同时会做一些其他的事，比如将标识符放到符号表，将数字字符串常量存放到文字表等。

2.2 语法分析

 语法分析器会将词法分析器产生的记号进行语法分析，产生语法分析树。比如以上产生的语法树如下：
语法树

2.3 语义分析

 语义分析由语义分析器完成，它会对上述生成的语法树进行合法性分析，比如数字和数字相加是合法的，但是数字和指针相加则会报错。
 编译器只能做静态语义分析。比如声明和类型的匹配、类型的转换等。经过语义分析后，产生的语法树如下：
语义分析后的语法树

2.4 中间代码优化

 在生成汇编语言之前，编译器会对源代码进行优化。比如上述例子中的2+6，在编译时期是可以确定的，这是属于源代码优化的一种，类似的还有很多。
优化之后的语法树
 但是编译器直接对语法树进行优化很难，因此它会将整个语法树转换成中间代码。它是语法树的中间表示，很接近目标代码，但是和机器无关。
 中间代码在不同的编译器中有不同形式，常见的有三地址码（Three-address Code）和P-代码（P-Code）。
 最基本的三地址码：x = y op z，表示将y和z进行op操作后，赋值给x。因此，上述代码被翻译成三地址码后是这样的

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

可以被优化成这样

1
2
3
t2 = index + 4
t2 = t2 * 8
array[index] = t2

 中间代码是编译分为前端和后端。前端负责产生和机器无关的中间代码（不是汇编代码），后端服务将中间代码转换成目标机器代码。一些跨平台的语言编译时，可以使用一个前端和不同的多个后端。

2.5 目标代码生成与优化

 编译器后端主要包括代码生成器和目标代码优化器。代码生成器会将中间转换成目标机器代码，这个过程依赖目标机器，不同的机器字长、寄存器、整型长度等都不一样。假设目标机器cpu使用x86架构，则会生成以下汇编代码

1
2
3
4
5
movl index, %ecx			; index放入ecx寄存器
addl $4, %ecx				; ecx = ecx + 4
mull $8, %ecx				; ecx = ecx * 8
movl index, %eax			; index放入eax寄存器
movl %ecx, array(,eax,4) 	; array[index] = ecx

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

3. 链接的过程

 经过编译器的词法分析、语法分析、语义分析、源代码优化、代码生成和目标代码优化后，源代码终于被编译成了目标代码。但是目标代码中有一个问题：index和array的地址还没有确定？如果引用的是其他程序模块变量，地址怎么确定呢？
 事实上，定义的其他模块的全局变量和函数最终运行时的绝对地址都要在最终链接的时候确定，这个过程由链接器实现。
 链接器是一个将编译器产生的目标文件打包成可执行文件或者库文件或者目标文件的程序。
 程序由若干个模块组成，各个模块之间会进行通信，比如调用其他模块的函数，需要知道函数的地址，访问其他模块的变量，也需要变量的地址，这都归结于一种方式，即模块间符号的引用。
 模块间依靠符号来通信，定义符号的模块多出来的区域，刚好拼接上引用该符号的模块缺少的区域，这个拼接的过程就叫：链接。
链接

 链接器主要的工作就是把一些指令对其他符号地址的引用修正为真正的地址。
 链接过程主要包括地址和空间分配（Address and Storage Allocation）、符号决议（Symbol Resolution）和重定向（Relocation）等步骤。
 符号决议在在静态链接的时候称为符号决议或者名称决议（Name Resolution），在动态链接的时候被叫做符号绑定（Symbol Binding）或者名称绑定（Name Binding），有时候甚至叫做地址绑定（Address Binding）、指令绑定（Instruction Binding）。从名称上可以区分出来，决议偏向静态链接，绑定偏向动态链接。

  • 符号决议：其实就是指用符号来去标识一个地址。比如说 int a = 6;这样一句代码，用a来标识一个块4个字节大小的空间，空间里边存放的内容就是4.
  • 重新计算各个目标的地址过程叫做重定位。

3.1 静态链接

 如下图，最基本的静态链接就是把目标文件和库文件一起链接，形成最终可执行文件。最常见的库是运行时库。
静态链接过程
 我们在main.c模块中调用另一个模块func.c中的函数foo，必须知道foo的地址，但是每个模块都是单独编译的，在编译main.c的的时候并不知道foo函数的地址，所以编译器会暂时搁置调用foo的指令的目标地址，等链接的时候，链接器会根据引用符号foo，自动去相应的func.c模块查找foo的地址，然后将main.c模块中所有引用到foo的指令重新修正，让他们的目标地址为真正foo函数的地址。这就是静态链接最基本的过程和作用。
 假设A里面有个全局变量p，我们再B里面要访问这个全局变量，B里面有这么一条指令：

1
movl $0x2a, p     // p = 42，x86架构

 意思是给p变量赋值0x2a。编译B得到指令机器码 C7 05 00 00 00 00 2a 00 00 00，c705是mov指令码，2a为源常量，由于不知道地址所以暂时置为0，等链接器链接A和B的时候，假设确定p的地址为0x1000，则把目标地址修改为0x1000，即C7 05 00 00 10 00 2a 00 00 00。

3.2 动态链接

 把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件

 假设现在有两个程序program1.o和program2.o，这两者共用同一个库lib.o,假设首先运行程序program1，系统首先加载program1.o，当系统发现program1.o中用到了lib.o，即program1.o依赖于lib.o，那么系统接着加载lib.o，如果program1.o和lib.o还依赖于其他目标文件，则依次全部加载到内存中。当program2运行时，同样的加载program2.o，然后发现program2.o依赖于lib.o，但是此时lib.o已经存在于内存中，这个时候就不再进行重新加载，而是将内存中已经存在的lib.o映射到program2的虚拟地址空间中，从而进行链接（这个链接过程和静态链接类似）形成可执行程序。

 链接是一个很复杂的过程，后续有时间再写。

编译和链接

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！