# 程序员的自我修养

## 源码执行过程

源码执行的过程可以被分成四部分

1. 预处理(Prepressing)：主要处理那些源码中以 `#` 开始的预编译指令，例如 `#include`、`#define`
2. 编译(Compilation)：把预处理完的文件进行一系列**词法分析**、**语法分析**、**语义分析**以及**优化**后生产相应的**汇编代码文件**
3. 汇编(Assembly)：汇编器是将汇编代码转变成机器可以执行的指令，每一个汇编语句几乎都对应一条机器指令。汇编器根据汇编指令和机器指令的对照表一一翻译就可以了
4. 链接(Linking)

以 `hello.c`、`hello1.c`、`hello2.c` 为例

```cpp
// hello2.c
int mul(int a, int b){
 return a * b;
}

// hello1.c
#include "hello2.c"
int add(int a, int b) {
 return a + b;
}

// hello.c
#include "hello1.c"
int main() {
 add(1, 2);
 return 0;
}
```

使用命令 `gcc -E hello.c -o hello.i`，对 `hello.c` 进行 **预处理**

```cpp
# 0 "hello.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 2 "hello.c"
# 1 "hello1.c" 1
# 1 "hello2.c" 1
int mul(int a, int b){
 return a * b;
}

# 2 "hello1.c" 2
int add(int a, int b) {
 return a + b;
}
# 2 "hello.c" 2
int main() {
 add(1, 2);
 return 0;
}
```

> `#include` 会递归执行

- 在预处理阶段删除 `#define` 并展开所有的宏定义
- 处理的条件预编译指令 `#if`、`#ifdef`、`#elif`、`#else`、`#endif`
- 处理 `#include` 将包含的文件插入到该预编译指令的位置
- 删除所有的注释
- 添加行号和文件名标识
- 保留 `#pragma` 编译器指令，编译器要用到

使用 `gcc -S hello.i -o hello.s` 将预处理后的文件编译得到汇编代代码

> 汇编文件内容较多，不贴代码

使用 `gcc -c hello.s -o hello.o` 得到机器指令的文件，但是这个文件还不可以执行

在最后执行了**链接**之后，才能够执行

## 编译器做了什么

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

> 使用汇编语言或机器指令编写程序效率低下，且机器语言和汇编依赖特定机器，一个专门为某种 CPU 编写的程序在另一种 CPU 下完全无法运行

使用高级语言能够使开发者尽量少的考虑计算机本身的限制：字长、内存大小、通信方式、存储方式等

![](Image/001.png)

| 英文 | 中文 |
| --- | --- |
| Source Code | 源码 |
| Scanner | 扫描器 |
| Tokens | 记号 |
| Parser | 语法分析 |
| Syntax Tree | 语法树 |
| Semantic Analyzer | 语义分析 |
| Commented Syntax Tree | 语法树 |
| Source Code Optimizer | 源码级优化器 |
| Intermediate Representation | 中间代码 |
| Code Generator | 目标代码生成 |
| Target Code | 目标代码 |
| Code Optimizer | 目标代码优化器 |

### 词法分析

**扫描器**：简单地进行**词法分析**，运用类似有**限状态机**的算法可以将源代码的字符序序列分割成一系列的**记号**(`Token`)

通过 `Scanner` 扫描器的词法分析产生的记号 `Token` 一般分为一下几类：关键字、标识符、字面量(数字、字符串等)和特殊符号（加号、减号等）

> 语法分析工具有 lex

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

上面的代码通过扫描器之后会得到 16 个 Token

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

### 语法分析

语法分析器(`Grammar Parser`) 对扫描器(`Scanner`) 产生的记号进行语法分析，从而产生语法树(`Syntax Tree`)，整个过程采用上下文无关语法(`Context-Free Grammar`)

对于 `int x = (1 + 2;` 这种错误就是在语法分析阶段被检查出来

通过**语法分析器**生成的**语法树**就是以**表达式**为节点的树

![](Image/002.png)

> 赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式等

词法分析工具有 `yacc`(`Yet Another Compiler Compiler`)，可以根据用户给定的语法规则对输入的记号序列进行解析，从而构建出一颗语法树

> 对于不同的语言，编译器的开发者只需要改变语法规则，而无需为每个编译器编写一个语法分析器

### 语义分析

语法分析仅仅完成了对表达式的语法层面的分析，但是并不了解这个语句是否真正有意义

```cpp
int* p1 = NULL;
int* p2 = NULL;
int p3 = p1 * p2;
```

比如上述代码在语法分析阶段是通过的，但是在语义分析阶段不能通过

编译器能分析的语义是静态语义（`Static Semantic`），也就是编译器可以确定的语义。对应的还有动态语义（`dynamic Semantic`），只有在运行期才能确定的语义

- 静态语义：类型检查、变量声明检查、控制流检查等。例如，编译器会检查变量是否在使用前声明，类型转换是否合法等。这些检查在编译时就能确定，因此称为静态语义
- 动态语义：数组越界、除零错误等。这些错误只有在程序实际运行时才能被检测到，因此称为动态语义

经过语义分析之后，语法树的表达式都会被标识上类型，如果有些类型需要做隐式转换，语义分析程序会在语法树中插入相应的转换节点

![](Image/003.png)

### 中间语言生成

现代编译器有很多层次的优化，往往在**源代码级别**会有一个优化过程

这里定义的**源码级优化器**(`Source Code Optimizer`)在不同的编译器中可能会有不同的定义或者一些其他的差异

比如之前的例子 `array[index] = (index + 4) * (2 + 6);` 中 **(2 + 6)** 的值在编译期就可以被确定

![](Image/004.png)

> 上述的语法树经过优化了

但是一般不会直接优化在语法树上做优化，这比较困难，**源代码优化器** 往往将整个语法树转换成**中间代码**(`Intermediate Code`)，它是语法树的顺序表示，非常接目标代码

> 中间代码一般与目标机器和运行时环境无关，比如不包含数据的尺寸、变量地址和寄存器的名字等

中间代码有很多类型，在不同编译器中有不同的形式，比较常见的有：**三地址码**（`Three-Address Code` Or `TAC`）和 **P-代码**(`P-Code`)

**三地址码** 是常见的中间表示形式，每条三地址码指令最多包含三个地址：两个操作数和一个结果

1. 四元组表示，每条三地址码可以表示为一个四元组(`4-tuple`)：运算符、操作数1、操作数2、结果
2. 简单命令
3. 线性表示，便于编译器进行顺序处理和优化

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

上述代码以 **三地址码** 为例，会生成如下的中间代码

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

**三地址码**的优化过程主要包括消除公共子表达式、常量折叠、赋值传播等技术

所以**优化程序**在三地址码的基础上进行优化时

- 常量折叠：会将 `2 + 6` 计算出来得到 `t1 = 8`，然后将后面代码中的 t1 替换成数字 3
- 复制传播：省去一个临时变量 t3，因为 t2 可以重复利用

最后得到优化后的三地址码如下

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

至于什么是消除公共子表达式，例子如下

```cpp
// 原始三地址码
t1 = b + c
a = t1
t2 = b + c
d = t2
t3 = a * d
e = t3

// 因为 t1 和 t2 表达式相同
t1 = b + c
a = t1
d = t1  // 直接使用 t1 而不是重新计算 b + c
t3 = a * d
e = t3
```

### 目标代码生成与优化

**源代码级优化器**产生的中间代码标志着下面的过程都属于**编译器后端**

编译器后端负责将中间代码转换为目标机器代码，并进行各种优化以提高代码的执行效率。主要包括：**代码生成器**和**目标代码优化器**

代码生成器将中间代码转换成目标机器代码，这个过程十分依赖目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等

```x86asm
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
```

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

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

> 乘法由一条相对复杂的 **基址比例变址寻址**（`Base Index Scale Addressing`） 的 lea 指令完成

首先C++ 语言的定义极为复杂；然后现代 CPU 也相当复杂，CPU 采用了流水线、多发射、超标量等诸多复杂的特性。为了支持这些特性，编译器的机器指令优化过程也变得十分复杂

使编译过程更为复杂的是有些编译器支持多种硬件平台，即允许编译器编译出多种目标 CPU 的代码

> 比如 GCC 编译器就几乎支持所有 CPU 平台

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

经过前面的扫描、词法分析、语法分析、语义分析、源代码优化、代码生成和目标代码优化后，源代码被编译成了目标代码

那么问题来了，`array` 和 `index` 的地址如何得到？

进而引入新的问题：代码中有变量定义在其他模块，该怎么办？

## 链接器

```
0001 0100
...
...
...
1000 0111
```

在很久之前纯二进制指令（打孔纸条）控制机器时，假设 `0001` 是跳转指令，那么上述代码第一条 `0001 0100` 就是跳转到 `0100` 也就是第四条指令中

但是代码并不是一成不变的，如果在第四条之前插入新的指令，那么原本第四条指令就变成第五条指令了，对应的第一条指令也要修改 `0001 0101`。这一步就是 **重定位**(`Relocation`)

再后面开始使用汇编语言，使用类似 `jmp` 来替代 `0001` 表示跳转命令。可以使用符号来标记位置，比如使用 `divide` 来表示一个除法子程序的起始地址

如果将之前二进制代码的第四条指令的起始地址使用符号 `foo` 来标记，那么命令就从 `0001 0100` 变成了 `jmp foo`

当使用符号命名子程序或跳转目标之后，不管 `foo` 之前插入或减少了多少条指令导致 `foo` 目标地址发生了什么变化，汇编器在每次汇编程序的时候会重新计算 `foo` 这个符号的地址

上述整个过程不需要人工参与，终于不用在人工进行低级繁琐的地址调整工作

现在软件开发过程中，往往会拆分成多个模块，这些模块之间互相依赖有，又相对独立。这种模块化开发的好处就是代码容易阅读、理解、重用，每个模块单独开发、编译、测试，改变部分代码不用编译整个程序等

C++ 模块之间通信有两种方式：模块间的**函数调用**和模块间的**变量访问**

函数访问必须知道目标函数的地址，变量访问也必须知道目标变量的地址，所以总的来的两种方式都可以归结为**模块间符号的引用**

这个过程也被称为**链接**

链接的主要内容就是把各个模块之间互相引用的部分都处理好，使得各个模块之间能够正确地衔接

链接器要做的工作跟前面说的人工调整地址本质没什么两样。**链接**过程主要包括了**地址和空间分配**（Address And Storage Allocation）、**符号决议**（Symbol Resolution）和**重定位**（Relocation）等步骤

| 步骤 | 作用 | 过程 |
| --- | --- | --- |
| 步骤和空间分配 | 为每个模块中的代码和数据分配内存地址和存储空间 | 链接器首先扫描所有输入的可重定位目标文件，确定每个模块的大小和对齐要求。根据这些信息，链接器为每个模块分配内存地址和存储空间，确保他们在内存中的布局符合要求 |
| 符号决议 | 将每个符号引用与其定义关联起来 | 每个模块中定义和引用的符号都会被记录在符号表中。链接器扫描所有输入的目标文件，解析每个符号的定义和引用。链接器将每个符号引用与其定义关联起来，确保所有引用都能正确解析 |
| 重定位 | 调整代码和数据中的地址引用，使他们指向正确的内存位置 | 编译器和汇编器生成的代码和数据通常从地址 0 开始，在实际运行时会发生变化。链接器根据地址和空间分配的结果，调整代码和数据中的地址引用，使他们指向正确的内存位置。也包括修改指令中的地址引用、调整数据段中的指针等 |
| 合并和优化 | 合并相同的代码和数据段，并进行优化以提高执行效率 | 链接器会合并相同的代码和数据段，减少冗余。链接器还会进行一些优化操作，如消除未使用的代码和数据、优化指令顺序等 |

> 代码在运行的时候才会被加载到内存中，所以上述所有的内存地址都是虚拟地址，而不是物理内存地址，这些虚拟内存地址在程序运行时会被映射到实际的物理内存地址

一般来说，每个模块的源代码文件经过编译器编译成**目标文件**(Object File，一般后缀为 .0)，**目标文件**和**库**(`Library`) 一起链接形成最终的可执行文件

最常见的库就是**运行时库**(Runtime Library)，它是支持程序运行的最基本函数的集合

**库**其实时一组目标文件的包，就是一些最常用的代码编译成目标文件后打包存放

```cpp
// main.c
#include <stdio.h>
#include <stdbool.h>

extern bool foo();

int main() {
    if (foo()) {
        printf("foo returned true\n");
    } else {
        printf("foo returned false\n");
    }
    return 0;
}


// foo.c
#include <stdbool.h>

bool foo() {
    return true;
}
```

> `c89` 中没有定义 `bool`，`c99` 中在 `stdbool.h` 中定义了 `bool`

通过 `gcc -c main.c -o main.o` 和 `gcc -c foo.c -o foo.o` 生成目标文件

1. 地址和空间分配：为每个模块中的代码和数据分配虚拟地址和存储空间
   - 扫描器扫描 `main.o` 和 `foo.o` 确定模块大小和对齐要求
   - 为 `main` 函数和 `foo` 函数分配虚拟地址
   - 为犬奴变量和静态数据分配存储空间

2. 符号决议：链接器解析每个符号的定义和引用，将符号引用与其定义关联起来
   - 在 `main.o` 中，链接器发现 `foo` 函数是一个外部符号(`extern`)，需要解析其定义
   - 在 `foo.o` 中，链接器找到 `foo` 函数的定义，并将 `main.o` 中对 `foo` 的引用于 `foo.o` 中的定义关联起来

3. 重定位：链接器调整代码和数据中的地址引用，使他们指向正确的虚拟地址
   - 链接器修改 `main.o` 中对 `foo` 函数的调用地址，使其指向 `foo.o` 中 `foo` 函数的实际地址

4. 合并和优化：链接器合并相同的代码段和数据段，并进行优化以提高执行效率

## 目标文件