感谢 up 主 ZOMI 酱：https://space.bilibili.com/517221395
LLVM IR 与 GCC IR 对比#
| 特性 | LLVM IR | GCC IR (GIMPLE) |
|---|---|---|
| 独立性和库化架构 | 高度模块化，前端和后端分离，易于添加新语言和目标平台 | 传统 GCC 架构，前端和后端耦合较紧密 |
| 表达形式 | 人类可读的汇编形式、C++ 对象形式、序列化后的 bitcode 形式 | GIMPLE 表示形式，三地址代码，SSA 形式 |
| 设计和应用 | 更独立，可在编译器之外的工具中重用，有正式定义和良好的 C++ API，更接近硬件行为 | 降低控制流复杂度，优化相对容易 |
| 适用场景 | 适合学术界的应用，因为已经做了较大简化，可以更快地得出结果 | 适合工业应用，可以自己生成统一的 AST 进行数据流分析，或生成类似 GIMPLE 的三地址码进行分析 |
LLVM IR 的优点#
- 更独立：LLVM IR 设计为可以在编译器之外的任意工具中重用，使得可以轻松集成其他类型的工具，例如静态分析器和插桩器。
- 更正式的定义和更好的 C++ API：这使得处理、转换和分析变得更加容易。
- 更接近硬件行为：LLVM IR 提供了类似 RISCV 的模拟指令集和强类型系统，实现了其 “通用表示” 的目的。
GIMPLE 的优点#
- 降低控制流复杂度：GIMPLE 通过降低控制流复杂度、采用三地址表示和限制语法，使得优化变得相对容易。
LLVM 架构设计#
LLVM 架构图：
LLVM 核心流程分析#
编译器前端工作流程包括词法、语法、语义分析；中间优化层大数据中的 Pass 优化；编译器后端工作流程包括机器指令选择、寄存器分配、指令调度。
实践：Clang 编译流程#
- 生成.i 文件
clang -E -c .\hello.c -o .\hello.i - 将预处理过后的.i 文件转化为.bc 文件
clang -emit-llvm .\hello.i -c -o .\hello.bc clang -emit-llvm .\hello.c -S -o .\hello.ll - 使用 llc 和 lld 链接器
llc .\hello.ll -o .\hello.s llc .\hello.bc -o .\hello2.s - 转变为可执行的二进制文件
clang .\hello.s -o hello - 查看编译过程
clang -ccc-print-phases .\hello.c
总结#
LLVM 组件之间交互发生在高层次抽象，不同组件隔离为单独程序库，易于在整个编译流水线中集成转换和优化 Pass。现在被作为实现各种静态和运行时编译语言的通用基础结构。
LLVM IR 详解#
LLVM IR 设计理念#
LLVM IR 采用静态单赋值形式（Static single assignment，SSA），具有两个重要特征：!
SSA 静态单赋值#
LLVM IR 中，每个变量都在使用前都必须先定义，且每个变量只能被赋值一次。
以 1 * 2 + 3 为例：
LLVM IR 基本语法#
LLVM IR 是类似于精简指令集（RISC）的底层虚拟指令集，支持简单指令的线性序列。
- LLVM IR 是类似于精简指令集（RISC）的底层虚拟指令集；
- 和真实精简指令集一样，支持简单指令的线性序列，例如添加、相减、比较和分支；
- 指令都是三地址形式，它们接受一定数量的输入然后在不同的寄存器中存储计算结果；
- 与大多数精简指令集不同，LLVM 使用强类型的简单类型系统，并剥离了机器差异；
- LLVM IR 不使用固定的命名寄存器，它使用以 ％ 字符命名的临时寄存器；
每个三地址码指令，都可以被分解为一个四元组（4-tuple）的形式：（运算符，操作数 1，操作数 2，结果），由于每个陈述都包含了三个变量，即每条指令最多有三个操作数，所以它被称为三地址码。
| 指令类型 | 指令形式 | 四元组表示 |
|---|---|---|
| 赋值指令 | z = x op y (z = x + y) | (op, x, y, z) |
LLVM IR 内存模型#
LLVM IR 文件的基本单位称为 module
一个 module 中可以拥有多个顶层实体，比如 function 和 global variavle
一个 function define 中至少有一个 basicblock
每个 basicblock 中有若干 instruction，并且都以 terminator instruction 结尾
| 类名 | 详述 |
|---|---|
Module | **Module 类聚合了整个翻译单元用到的所有数据，** 它是 LLVM 术语中的 “module” 的同义词。它声明了 Module::iterator typedef，作为遍历这个模块中的函数的简便方法。你可以用 begin () 和 end () 方法获取这些迭代器。 |
Function | Function 类包含有关函数定义和声明的所有对象。对于声明来说（用 isDeclaration () 检查它是否为声明），它仅包含函数原型。无论定义或者声明，它都包含函数参数的列表，可通过 getArgumentList () 方法或者 arg_begin () 和 arg_end () 这对方法访问它。你可以通过 Function::arg_iterator typedef 遍历它们。如果 Function 对象代表函数定义，你可以通过这样的语句遍历它的内容：for (Function::iterator i = function.begin (), e = function.end (); i != e; ++i)，你将遍历它的基本块。 |
BasicBlock | BasicBlock 类封装了 LLVM 指令序列，可通过 begin ()/end () 访问它们。你可以利用 getTerminator () 方法直接访问它的最后一条指令，你还可以用一些辅助函数遍历 CFG，例如通过 getSinglePredecessor () 访问前驱基本块，当一个基本块有单一前驱时。然而，如果它有多个前驱基本块，就需要自己遍历前驱列表，这也不难，你只要逐个遍历基本块，查看它们的终结指令的目标基本块。 |
Instruction | Instruction 类表示 LLVM IR 的运算原子，一个单一的指令。利用一些方法可获得高层级的断言，例如 isAssociative ()，isCommutative ()，isIdempotent ()，和 isTerminator ()，但是它的精确的功能可通过 getOpcode () 获知，它返回 llvm::Instruction 枚举的一个成员，代表了 LLVM IR opcode。可通过 op_begin () 和 op_end () 这对方法访问它的操作数，它从 User 超类继承得到。 |
LLVM IR 内存模型最重要概念： Value, Use, User
LLVM IR 内存模型中，Value、Use 和 User 是三个核心概念，它们之间的关系定义了 LLVM 中的数据流和控制流。
| 概念 | 描述 |
|---|---|
Value | 在 LLVM 中，Value 是一个非常基础的概念，它表示任何有值的实体，比如常数、变量、函数等。每个 Value 都有一个唯一的编号，用于在 LLVM 内部标识自己。Value 还可以有用户（User），这意味着它可以是其他指令的操作数。 |
Use | Use 是 Value 的一个使用实例。在 LLVM 中，每个 Value 都有一个或多个 Use，表示这个 Value 被哪些指令所使用。Use 包含了指向使用该 Value 的 User 的指针，以及在该 User 中的操作数索引。 |
User | User 是指那些使用 Value 的指令或常量。例如，一条指令可能有多个操作数，每个操作数都是一个 Value，那么这条指令就是一个 User。User 通过 Use 对象来引用它的操作数 Value。 |
这三个概念共同构成了 LLVM IR 的内存模型，它们之间的关系反映了指令之间的数据依赖关系。在 LLVM 的优化过程中，这些概念对于分析和管理指令之间的依赖非常重要。
LLVM 前端和优化层#
LLVM 前端#
编译器前端将源代码变换为编译器的中间表示 LLVM IR。
- Lexical analysis 词法分析
前端的第一个步骤处理源代码的文本输入，将语言结构分解为一组单词和标记，去除注释、空白、制表符等。每个单词或者标记必须属于语言子集，语言的保留字被变换为编译器内部表示。
$ clang -cc1 -dump-tokens hello.c
- Syntactic analysis 语法分析
分组标记以形成表达式、语句、函数体等。检查一组标记是否有意义，考虑代码物理布局，未分析代码的意思，就像英语中的语法分析，不关心你说了什么，只考虑句子是否正确，并输出语法树（AST）。
$ clang -fsyntax-only -Xclang -ast-dump hello.c
- Semantic analysis 语义分析
借助符号表检验代码没有违背语言类型系统。符号表存储标识符和其各自的类型之间的映射，以及其它内容。类型检查的一种直觉的方法是，在解析之后，遍历 AST 的同时从符号表收集关于类型的信息。
$ clang -c hello.c
LLVM 优化层#
优化通常由分析 Pass 和转换 Pass 组成。
优化通常由分析 Pass 和转换 Pass 组成。
- 分析 Pass：负责发掘性质和优化机会；
- 转换 Pass：生成必需的数据结构，后续为后者所用；
opt hello.bc -instcount -time-passes -domtree -o hello-tmp.bc -stats
LLVM 后端代码生成#
后端架构#
后端由一套分析和转换 Pass 组成，它们的任务是代码生成。
Instruction Selection 指令选择#
内存中 LLVM IR 变换为目标特定 SelectionDAG 节点。
Instruction Scheduling 指令调度#
第 1 次指令调度，也称为前寄存器分配（RA）调度；
对指令排序，同时尝试发现尽可能多的指令层次的并行；
然后指令被变换为 MachineInstr 三地址表示。
Register Allocation 寄存器分配#
寄存器分配将无限的虚拟寄存器引用转换为有限的目标特定的寄存器集。
寄存器不够时挤出（spill）到内存。
Instruction Scheduling 指令调度#
第 2 次指令调度，也称为后寄存器分配（RA）调度；
此时可获得真实的寄存器信息，某些类型寄存器存在延迟，它们可被用以改进指令顺序。
Code Emission 代码输出#
代码输出阶段将指令从 MachineInstr 表示变换为 MCInst 实例。