1. 编译器概述

编译器：将用编程语言(源语言)编写的计算机代码翻译成另一种语言(目标语言)的计算机程序。

编译程序以高级程序源代码作为输入，以汇编语言或机器语言表示的目标程序作为输出。目标程序会在机器上运行，得到所需的结果。编译器可能执行以下操作：预处理、词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

编译器前端和中端理论知识与代码可视化的实现最为相关，后端部分和目标机器代码、特定机器架构相关一般很少用到可视化中。

2. 中间代码生成

2.1 为什么需要中间代码？

编译器很难通过一次处理就得到最优的目标代码，实际的编译器大多组织为一连串的处理趟，每一趟处理的结果又作为下一趟的输入持续的运行。随着编译器不断推导有关被编译代码的知识，它必须将这些信息从一趟传递到另一趟。因此，这些能推导出有关程序全部事实的信息需要一种表示方式，称之为中间代码或中间表示(intermediate representation)，简称IR。

广义上可以将源码到目标代码之间的表达形式都称之为中间代码。其目的是为了解耦编译器前端和后端部分，作为高级语言和目标机器语言之间的桥梁，不依赖于特定的源语言或目标机器使得一些代码优化动作能够复用。与高级语言相比，IR 丢弃了大部分高级语言的语法特征和语义特征，比如循环语句、if 语句、作用域、面向对象等等，它更像高层次的汇编语言；而相比真正的汇编语言，它又不会有那么多琐碎的、与具体硬件相关的细节。

如果源语言语法结构较为简单，编译器可能会用唯一的IR，但如果源语言语法结构比较复杂，则在转换为目标语言的过程中可能会使用了一系列的IR，并通过转换进行大量的优化操作。

由于不同语言编译器中IR差异较大，本文后续内容对于概念部分只做点到即止的阐述，但增加了LLVM的中间代码实操用来加深理解。LLVM 是一个开源的编译器基础设施项目，主要聚焦于编译器的后端功能（代码生成、代码优化、JIT……），其在业界被广泛应用，很多语言都是基于它实现的，更多信息可以查看官网。

2.2 中间代码分类

按照与源代码接近的程度可以分为：

• 高级IR：更接近源代码，保留了更多的源代码层面的信息，如数据类型、控制结构等。通常用于编译器前端的语义分析和初步优化阶段。例如：AST等；
• 中级IR：开始脱离源代码的具体语法，引入更多与机器无关的优化。通常用于进行编译器的主要优化，如循环优化、常量传播、死代码消除等。例如：TAC等；
• 低级IR：接近目标机器代码，更多地反映了目标平台的具体特性，如寄存器、指令集等。用于编译器后端的优化，特别是那些与目标机器密切相关的优化，如寄存器分配、指令选择和调度。

根据其结构和表现形式可以分为：

• 图IR： 将编译器生成的信息保存在图中，通过图结构来表示程序的各种属性。图IR非常适合表示并分析程序的复杂结构，如循环、分支等。例如：AST、CFG和DFG等；
• 线性IR： 以线性的方式表示程序，通常是一系列的指令或语句。不像图IR那样直观地表示控制流或数据流，但对于某些分析和转换来说更简单、直接，常用于编译器的早期阶段，进行简化的分析和转换。例如：TAC、SSA等；
• 混合IR： 结合了图IR和线性IR的特点，尝试兼顾两者的优势。一种常见的混合表示为使用线性IR来表示无循环代码的块，使用图来表示这些块之间的控制流。混合IR旨在提供足够的灵活性来支持各种编译阶段的需要，从而使编译器能够有效地执行复杂的优化和分析。

了解了基本的分类，下面介绍几种常见的中间表示方式，并针对表达式A进行不同形式的呈现：

//表达式A
a=(-b+c*d)+c*d

① 抽象语法树（Abstract Syntax Tree, AST）
通过编译器前端生成的抽象语法树也算是高级IR和图IR，它保留了源代码的语法结构，如表达式、语句、函数定义等。这里就不再赘述生成过程，如果忘记了相关知识可以再复习一下前文。表达式A对应的AST为：

② 有向无环图（Directed Acyclic Graph，DAG）
有向无环图是在树结构的基础上，消除了冗余的子树。其结点可以有多个父结点，相同子树可以被重用，可以理解为是一种具有共享机制的AST。表达式A对应的DAG为：

③ 三地址代码（Three-Address Code, TAC）
三地址代码是中级IR和线性IR，它是一种接近于汇编语言但又保持了高级语言特征的代码形式。这种形式的IR特别适合于执行和表示各种编译时优化。在三地址代码中，每条指令通常涉及到两个操作数（y、z）和一个结果（x），指令的一般形式可以是：
x = y op z
其中，op 是一个二元运算符，y 和 z 是操作数，可以是常量、变量或者临时变量，x 是存放结果的变量或临时变量。三地址代码也支持一元运算符，这种情况下指令的形式为：
x = op y
常用的三地址代码有：

表达式A对应的TAC为（可以通过遍历AST生成TAC）：

④ 静态单赋值形式（Static Single Assignment, SSA）
静态单赋值形式也是一种线性IR，它和三地址代码的主要区别在所有赋值指令都是对不同名字的变量的赋值。每个变量很确定地只会被定义一次，然后可以多次使用。这种特点使得基于SSA更容易做数据流分析，而数据流分析又是很多代码优化技术的基础，所以几乎所有语言的编译器、解释器或虚拟机中都使用了SSA。下图展示了两种表示方式的区别：

另外，表达式A生成的TAC和SSA是一样的，大家不妨验证一下是否符合SSA的特性😁。

除了上述中间表示形式外还有CFG、CallGraph等更复杂的IR这里就不展开说了，有兴趣的同学可以自行查阅资料。

3. 生成LLVM中间代码

LLVM IR是一种基于静态单赋值（SSA）的表示法，提供了类型安全、底层操作、灵活性以及简洁地表示 高级语言的能力。它实际上有三种不同的表示方式，它们在功能上是等价的，但用途和表现形式各有不同。这三种表示分别是：

• LLVM汇编语言（LLVM Assembly Language）：这是一种文本格式的表示，提供了可读性较好的代码形式。它允许开发者和工具以文本形式查看和编辑IR，非常适合调试和教学。这种格式通常保存为以.ll为扩展名的文件；
• LLVM字节码（LLVM Bitcode）：这是一种二进制格式的表示，它将IR编码为二进制文件，通常用于在不同编译阶段之间传递IR，或者作为发布应用程序的一部分以支持延迟编译（JIT编译）或跨平台移植。字节码格式更加紧凑，加载和处理速度也更快。这种格式的文件扩展名通常是.bc。
• 内存中的IR（In-memory IR）：这是LLVM库在内存中操作的数据结构形式。当- LLVM的前端（如Clang）解析源代码时，它会构建出一个内存中的IR表示，后续的优化和转换操作都是在这种形式上进行的。这种表示不直接面向用户，而是由LLVM的API操作和修改。

下面实操使用LLVM工具生成这.bc和.ll这两种中间代码：
① 安装LLVM
可以参考官方下载地址安装，Mac可以使用HomeBrew安装。

brew install llvm

由于LLVM 带了一个版本的 Clang 和 C++ 的标准库，与本机原来的工具链可能会有冲突，所以 brew 安装的时候并没有在 /usr/local 下建立符号链接。使用 LLVM 工具的时，要配置好相关的环境变量。

# 可执行文件的路径
export PATH="/usr/local/opt/llvm/bin:$PATH"
# 让编译器能够找到LLVM
export LDFLAGS="-L/usr/local/opt/llvm/lib"
export CPPFLAGS="-I/usr/local/opt/llvm/include"

② 准备源码文件fun1.c

int fun1(int a, int b){
    int c = 10;
    return a+b+c;
}

③ 生成IR

# 生成LLVM汇编语言
clang -emit-llvm -S fun1.c -o fun1.ll
# 生成LLVM字节码
clang -emit-llvm -c fun1.c -o fun1.bc

④ IR转换
两种中间代码可以互相转换，我们将前面生成的.ll转换为.bc。

# 转换命令
llvm-as fun1.ll -o fun1.bc
# 查看结果
hexdump -C fun1.bc

4. 扩展阅读

• 书籍：《龙书》、《虎书》、《鲸书》
• CS143