MarkdownLog/Build-Project/程序员的自我修养/README.md

程序员的自我修养

源码执行过程

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

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

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

// 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 进行 预处理

# 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 下完全无法运行

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

英文	中文
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

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; 这种错误就是在语法分析阶段被检查出来

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

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

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

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

语义分析

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

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

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

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

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

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

中间语言生成

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

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

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

上述的语法树经过优化了

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// 原始三地址码
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

目标代码生成与优化

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

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

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

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

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

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

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

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

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

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

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)，它是支持程序运行的最基本函数的集合

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

// 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. 合并和优化：链接器合并相同的代码段和数据段，并进行优化以提高执行效率

目标文件