编译是指将某一种语言（源语言）写的程序（源程序）翻译成一个等价的、用另一种语言（目标语言）写的程序（目标程序）的过程。通常，目标程序是一个可执行的机器语言程序，在编译后可以被用户 调用、处理输入并产生输出。常见编译器的流程（目标语言为机器语言）如下图所示：
暂时无法在飞书文档外展示此内容
- 词法分析负责解析关键字、常量等，将源代码程序中的最基本元素提取出来，如int a = 1可以提取出来int, a, =, 1，并记录成一个词表。
- 语法分析负责基于源语言的语法，将词表进一步翻译成抽象语法树（见第三章）。语法错误也是在这一过程中被编译器提示出来的。
Clang/LLVM
LLVM是一个通用的编译优化框架，提供了一个现代化、精心设计的语言无关的中间语言（LLVM IR）。LLVM可以为任意编程语言设计编写前端、为任意机器指令集架构编写后端（x86/64，Arm，Power PC
，MIPS，RISC-V等），且由于其优秀的软件工程流程、严格的代码审查和活跃的社区，大量的编程语言基于LLVM实现了自己的编译器，如Rust、Swift等。
Clang（[k-laeng], [k-lang]）是基于LLVM的C/C++编译器，目前被用作macOS的自带C/C++编译器。
GCC
GCC是GNU Compiler Collection的缩写，是历史最悠久、开发最活跃的C/C++编译器之一。由于出色的优化和长时间的维护，拥有卓越的性能，并支持绝大多数指令平台。然而，尽管GCC是开源的，但文档很难阅读，源代码也很难使用。因此，GCC开发仅限于一小群精英GCC开发人员，他们高度关注特定领域的知识。GCC目前是大部分Linux和Unix发行版的默认C/C++编译器。
ICC/ICX
Intel提供的商用付费C/C++编译器。其实现和IR是完全闭源的，但是IR部分正在逐步过渡到LLVM IR上。现代化的ICC现在被称为ICX。ICC仅支持Intel架构（x86、x64、安腾），可在Linux、Windows和MacOS平台下使用。
MSVC
其它
其它优秀的C语言编译器包括IBM XLC、Cray、SunCC、Open64、Watcom C/C++、Borland/turbo等。部分已经停止维护。
抽象语法树是使用树的形式对源代码语法结构的一种抽象表示，树上的每一个节点都表示源代码中的一种结构。
以下面这个简单的程序为例，
其AST为：
在Clang中，该AST的数据结构被表示为：
从图中可以看出来，Clang抽象的AST的节点包括节点类型（如类型声明、函数声明、语句、表达式等）、唯一标识符、对应源代码位置、数据类型、备注信息、源代码中的字符串等。
LLVM IR是一种基于SSA（Static Single Assignment）的中间代码表示。其整体的文档参见：llvm.org/docs/Passes…
SSA（静态单赋值）
在基于SSA的IR中，每个变量仅被赋值一次，相较于原始的IR或源代码程序，原来的变量会被分割成不同的版本。例如：
y = 1;
y = 2;
...
x = y;
在SSA表示中，会被翻译成：
y_1 = 1;
y_2 = 2;
...
x_1 = y_2;
从这个例子中我们可以看出，使用SSA的优点包括：
LLVM IR Example
在上面的例子中，我们可以使用LLVM提供的工具链获得其LLVM IR。
clang -S -emit-llvm branch.cpp -c
基于LLVM工具链提供的命令行程序或API，我们可以将源程序转换为LLVM IR，分析/操作IR，并将IR编译为机器语言（可执行程序）。参见：llvm.org/docs/Gettin…
LLVM的优化主要是源语言无关的LLVM IR层面的优化，此时，源语言程序已经被对应的前端翻译成LLVM IR，优化的流程如下图：
暂时无法在飞书文档外展示此内容
如图所示，LLVM的优化指令按照功能和目的，被分为了一个个相互独立的优化pass，IR在经过若干轮pass的优化后，最终可以由后端输出为目标程序。
根据pass的特点，pass可以被分为：
在这里我们介绍一些常用的pass，并通过部分pass介绍其他一些编译优化、静态分析常用的基本概念。为了方便表达，我们使用C源代码作为例子，而非LLVM IR。
分析类
调用图（Call Graph）与dot-callgraph pass
Call graph即函数调用关系图，如Code Graph产品。一个例子为：
LLVM中提供了不同的生成call graph的analysis pass，dot-callgraph，可将文件的call grpah生成到dot文件中，并进一步可视化。
Call graph生成的原理也较为简单，只需要遍历声明函数和调用函数的IR。将所有声明的函数作为全集，在遍历调用函数的IR时，函数caller为IR所属的函数、callee为被调用的函数，在全集中为他们之间建立连线即可。
控制流图（CFG）与dot-cfg pass
控制流图研究函数内各个basic block（即不包含控制流的最基本的代码块）之间的控制关系。例子（搬运自：www.geeksforgeeks.org/software-en…
如果对计算并生成CFG感兴趣，可以参考我之前为区块链Solidity语言编写的CFG生成程序：github.com/chao-peng/S…
变换类
Dead Code与dce（Dead Code Elimination）pass
Dead code即确定代码执行过程中不会被覆盖的代码，一个极端的例子为：
#def X 10
if (X != 10) {
// dead code here
}
通过数据流和控制流分析，我们知道X永远不会不等于10，因此这一块代码可以被直接优化掉。
类似的还有dead global elimination（优化掉没有被引用的全局变量）。
函数内联 inlining
Inlining / inline expansion即将函数体直接展开到调用处。可以消除调用函数的开销（压栈、保护/恢复现场），但可能造成产物体积膨胀，影响指令缓存的命中率。有研究表明函数内联展开在缓存小的时候能提升性能，缓存较大的时候性能有可能下降。
举个例子：
int pred(int x) {
if (x == 0)
return 0;
else
return x - 1;
}
int func(int y) {
return pred(y) + pred(0) + pred(y+1);
}
在inlining后：
int func(int y) {
int tmp;
if (y == 0) tmp = 0; else tmp = y - 1;
if (0 == 0) tmp += 0; else tmp += 0 - 1;
if (y + 1 == 0) tmp += 0; else tmp += (y + 1) - 1;
return tmp;
}
合并冗余指令、constant folding（常量折叠）、constant propagation（常量传播）
这一类优化指令基于简单的算术运算，对编译时已知的数值进行相应的优化。
Constant folding指的是当算数运算为已知数（常数）时，可以在编译时直接计算，并将结果直接赋值到变量中。constant propagation指的是通过数据流分析，确定前面已知的常量可以传播到后面的表达式中，并进行进一步的常量折叠。
一些例子：
// 例子1：常量传播 + 折叠 + 逻辑运算优化
bool a = TRUE; // 或 bool a = FALSE;
bool x = a && b;
// 若a为已知值，b取决于输入，当a为TRUE时优化为：
bool x = b;
// 若a为已知False
bool x = FALSE;
// 例子2：使用左移右移优化乘除法
int a = b + b;
// 首先，a = b + b 等价于 a = b * 2，✖️2操作又可以被进一步优化为
int a = b
