一、基础概念

1.1 Interpreter 和 Compile

Interpreter 解释器 Compile 编译器
程序步骤 1、创建代码
2、没有文件链接或机器代码生成
3、源语句在执行过程中逐行执行		 1、创建代码
2、将解析或分析所有语言语句的正确性
3、将把源代码转换为机器码
4、链接到可运行程序
5、运行程序
Input 每次读取一行 整个程序
Output 不产生任何的中间代码 生成中间目标代码
工作机制 编译和执行同时进行 编译在执行之前完成
存储 不保存任何机器代码 存储编译后的机器代码在机器上
执行 程序执行是解释过程的一部分，因此是逐行执行的 程序执行与编译是分开的，它只在整个输出程序编译后执行
生成程序 不生成输出程序，所以他们在每次执行过程中都要评估源程序 生成可以独立于原始程序运行的输出程序(以exe的形式)
修改 直接修改就可运行 如果需要修改代码，则需要修改源代码，重新编译
运行速度 慢 快
内存 它需要较少的内存，因为它不创建中间对象代码 内存需求更多的是由于目标代码的创建
错误 解释器读取一条语句并显示错误。你必须纠正错误才能解释下一行 编译器在编译时显示所有错误和警告。因此，不修正错误就不能运行程序
错误监测 容易 难
编程语言 PHP, Perl, Python, Ruby C, C++, C#, Scala, Java

1.2 JIT（Just in time）和AOT（Ahead of time）编译方式

静态编译：程序在执行前全部被编译为机器码，称为 AOT（Ahead of time），即“提前编译”；
动态解释：程序边编译边运行，通常将这种类型称为 JIT（Just in time），即“即时编译”；

Just in time Ahead of time
优点 1. 可以根据当前硬件情况实时编译生成最优机器指令
2. 可以根据当前程序的运行情况生成最优的机器指令序列
3. 当程序需要支持动态链接时，只能使用JIT
4. 可以根据进程中内存的实际情况调整代码，使内存能够更充分的利用		 1. 在程序运行前编译，可以避免在运行时的编译性能消耗和内存消耗
2. 可以在程序运行初期就达到最高性能
3. 可以显著的加快程序的启动
缺点 1. 在程序运行前编译，可以避免在运行时的编译性能消耗和内存消耗
2. 可以在程序运行初期就达到最高性能
3. 可以显著的加快程序的启动		 1. 在程序运行前编译会使程序安装的时间增加
2. 牺牲高级语言的一致性问题
3.将提前编译的内容保存会占用更多的外

Pass：One complete scan or processing of the source program。对源程序的一次完整扫描或处理

1.3 编译系统

image.png

  • 预处理（Pre-Processing）：包括宏定义，文件包含，条件编译三部分。预处理过程读入源代码，检查包含预处理指令的语句和宏定义，并对其进行响应和替换。预处理过程还会删除程序中的注释和多余空白字符。最后会生成 .i 文件。gcc -E hello.c -o hello.i
  • 编译器（Compiling）：编译器会将预处理完的 .i文件进行一些列的语法分析，并优化后生成对应的汇编代码。会生成 .s 文件。gcc -S hello.i -o hello.s
  • 汇编器（Assembling）：汇编器会将编译器生成的 .s 汇编程序汇编为机器语言或指令，也就是可以机器可以执行的二进制程序。会生成 .o 文件。gcc -c hello.s -o hello.o
  • 链接器（Linking）：链接器会来链接程序运行的所需要的目标文件，以及依赖的库文件，最后生成可执行文件，以二进制形式存储在磁盘中。gcc hello.o -o hello

1.4 编译器工作流程

image.png

在我们这个上下文场景中，我们主要关注编译器代码优化流程。

1.5 中间代码(Intermediate Representation - IR)

中间代码（Intermediate Representation）也叫IR，是处于源代码和目标代码之间的一种表示形式。我们倾向于使用IR有两个原因。

  1. 是很多解释型的语言，可以直接执行IR，比如Python和Java。这样的话，编译器生成IR以后就完成任务了，没有必要生成最终的汇编代码。
  2. 我们生成代码的时候，需要做大量的优化工作。而很多优化工作没有必要基于汇编代码来做，而是可以基于IR，用统一的算法来完成。

像GCC、LLVM这种编译器，可以支持N种不同的源语言，并可以生成M个不同机器码，如果没有IR，直接由源语言直接生成真实的机器代码，这个工作量是巨大的。

image.png

有了IR可以让编译器的工作更好的模块化，编译器前端不用再关注机器细节，编译器后端也不用关注编程语言的细节。这种实现会更加合理一些。

IR基于抽象层次划分，可以分为HIR、MIR、LIR。

IR数据结构常见的有几种：类似三地址指令（Three Address Code - TAC）线性结构、树结构、有向无环图（Directed Acyclic Graph - DAG）、程序依赖图（Program Dependence Graph，PDG）

二、LLVM（Low Level Virtual Machine）

2.1 Lib base LLVM

模块
LLVM Core 即 LLVM 的核心库，主要是围绕 LLVM 中间代码的一些工具，它提供了一个“源”和“目标”无关的优化器和几乎所有主流 CPU 类型的代码（机器码）生成器。
Clang 是 LLVM 项目中的一个子项目。它是基于 LLVM 架构的轻量级编译器，诞生之初是为了替代 GCC，提供更快的编译速度。它是负责编译C、C++、Objecte-C 语言的编译器，它属于整个 LLVM 架构中的，编译器前端。
Compiler-RT 项目用于为硬件不支持的低级功能提供特定于目标的支持。例如，32位目标通常缺少支持64位的除法指令。Compier-RT通过提供特定于目标并经过优化的功能来解决这个问题，该功能在使用32位指令的同时实现了64位除法。为代码生成器提供了一些中间代码指令的实现，这些指令通常是目标机器没有直接对应的，例如在32位机器上将double转换为unsigned integer类型。此外该库还为一些动态测试工具提供了运行时实现，例如 AddressSanitinzer、ThreadSanitizer、MemorySanitizer 和 DataFlowSanitizer 等。
LLDB LLDB是一个LLVM的原生调试器项目，最初是XCode的调试器，用以取代GDB。LLDB提供丰富的流程控制和数据检测的调试功能。
LLD clang/llvm内置的链接器。
Dragonegg GCC插件，可将GCC的优化和代码生成器替换为LLVM的相应工具。
libc C标准库实现。
libcxx/libcxxabi C++标准库实现。
libclc OpenCL标准库的实现。
OpenMP 提供一个OpenMP运行时，用于Clang中的OpenMP实现。
polly 支持高级别的循环和数据本地化优化支持的LLVM框架，使用多面体模型实现一组缓存局部优化以及自动并行和矢量化。
vmkit 基于LLVM的Java和.Net虚拟机实现。
klee 基于LLVM编译基础设施的符号化虚拟机。它使用一个定理证明器来尝试评估程序中的所有动态路径，以发现错误并证明函数的属性。klee的一个主要特征是它可以在检测到错误时生成测试用例。
SAFECode 用于C/C++程序的内存安全编译器。它通过运行时检查来检测代码，以便在运行时检测内存安全错误（如缓冲区溢出）。它可以用户保护软件免受安全攻击，也可用作Valgrind等内存安全错误调试工具。

2.2 LLVM vs GCC

  • 把编译器移植给新的语言只需要实现一个新的编译前端，已有的优化和后端都能实现复用；
  • 如果前后端和解析器没有相互解耦，新语言编译器需要支持 N 个目标机和 M 种语言(N*M)；
  • LLVM 组件之间交互发生在高层次抽象，不同组件隔离为单独程序库，易于在整个编译流水线中集成转换和优化 Pass。现在被作为实现各种静态和运行时编译语言的通用基础结构；
  • GCC 饱受分层和抽象漏洞困扰：编译前端生成编译后端数据的结构，编译后端遍历前端抽象语法树（AST）来生成调试信息，整个编译器依赖命令行设置的全局数据结构；

2.3 LLVM Architectrue

clang -E -c hello.c -o hello.i
clang -emit-llvm hello.i -c -o hello.bc
clang -emit-llvm add.c -S  -o add.ll
llvm-dis add.bc -o add.ll
llvm-as add.ll -o add.bc 
llc add.ll -o add.s
clang add.s -o add1
clang -ccc-print-phases add.c
clang -Xclang -ast-dump -c add.c

image.png

image.png

2.4 LLVM IR

image.png

// clang -S -emit-llvm test.c
void test(int a, int b){
    int c = a*b+100;
}

image.png

相关符号含义：

  1. 注释以;开头
  2. 全局表示以@开头，局部变量以%开头
  3. alloca在函数栈帧中分配内存
  4. i32 32位 4个字节的意思
  5. align字节对齐
  6. store写入
  7. load读取

LLVM IR 作为一种编译器 IR，它的两个基本原则指导着核心库的开发：

  • SSA 表示，代码组织为三地址指令序列和无限寄存器让优化能够快速执行。
  • 整个程序的 IR 存储到磁盘让链接时优化易于实现。

LLVM IR 采用静态单赋值形式（Static single assignment，SSA），具有两个重要特征：

  • 代码组织为三地址指令序列
  • 寄存器数量无限制

LLVM IR 基本语法

  • LLVM IR 是类似于精简指令集（RISC）的底层虚拟指令集；
  • 和真实精简指令集一样，支持简单指令的线性序列，例如添加、相减、比较和分支；
  • 指令都是三地址形式，它们接受一定数量的输入然后在不同的寄存器中存储计算结果；
  • 与大多数精简指令集不同，LLVM 使用强类型的简单类型系统，并剥离了机器差异；
  • LLVM IR 不使用固定的命名寄存器，它使用以 ％ 字符命名的临时寄存器；

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超类继承得到。

Value, Use, User

一切皆 Value，这是个夸张的说法，不过在 LLVM 架构中，的确几乎所有的东西都是一个 Value，这里有张继承关系图。

  • BasicBlock，Argument，User 都继承了 Value 类
  • Constant 和 Instruction 继承了 User
  • 图中没有 Function 类，但实际上 Function 类通过多重继承继承了 Constant 类，所以 Function 也是 Value 和 User

BasicBlock 表示的是基本块类，Arugument 表示的是函数的形参，Constant 表示的是形如 i32 4 的常量，Instruction 表示的是形如 add i32 %a,%b 的指令

Value 是一个非常基础的基类，一个继承于 Value 的子类表示它的结果可以被其他地方使用。 一个继承于 User 的类表示它会使用一个或多个 Value 对象 根据 Value 与 User 之间的关系，还可以引申出 use-def 链和 def-use 链这两个概念。use-def 链是指被某个 User 使用的 Value 列表，def-use 链是使用某个 Value 的 User 列表。实际上，LLVM 中还定义了一个 Use 类，Use 就是上述的使用关系中的一个边。

LLVM 架构中最重要的概念，以及编译器设计的提示

image.png

2.5 LLVM 前端

  • 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

2.6 LLVM 优化层

Passes

Finding Pass

优化通常由分析Pass和转换Pass组成。

  • 分析Pass：负责发掘性质和优化机会；
  • 转换Pass：生成必需的数据结构，后续为后者所用；

opt hello.bc -instcount -time-passes -domtree -o hello-tmp.bc -stats

Pass Relation

在转换Pass和分析Pass之间，有两种主要的依赖类型：

  • 显式依赖：转换Pass需要一种分析，则Pass管理器自动地安排它所依赖的分析Pass在它之前运行。
  • 隐式依赖：转换或者分析Pass要求IR代码运用特定表达式。需要手动地以正确的顺序把这个Pass加到Pass队列中，通过命令行工具（clang或者opt）或者Pass管理器。

Pass API

Pass类是实现优化的主要资源。然而，我们从不直接使用它，而是通过清楚的子类使用它。当实现一个Pass时，你应该选择适合你的Pass的最佳粒度，适合此粒度的最佳子类，例如基于函数、模块、循环、强联通区域，等等。常见的这些子类如下：

  • ModulePass
  • FunctionPass
  • BasicBlockPass

2.7 LLVM 后端

LLVM Backend Pass

整个后端流水线用到了四种不同层次的指令表示：

  • 内存中的LLVM IR，SelectionDAG 节点，MachineInstr，和 MCInst。

image.png

Instruction Selection 指令选择

  • 内存中 LLVM IR 变换为目标特定 SelectionDAG 节点；
  • 每个DAG能够表示单一基本块的计算；
  • 节点表示指令，而边编码了指令间的数据流依赖；
  • 让LLVM代码生成程序库能够运用基于树的模式匹配指令选择算法。

第一次 Instruction Scheduling 指令调度

  • 第1次指令调度（Instruction Scheduling），也称为前寄存器分配（RA）调度；
  • 对指令排序，同时尝试发现尽可能多的指令层次的并行；
  • 然后指令被变换为MachineInstr三地址表示。

Register Allocation 寄存器分配

  • LLVM IR 两个特性之一：LLVM IR 寄存器集是无限；
  • 这个性质一直保持着，直到寄存器分配（Register Allocation）；
  • 寄存器分配将无限的虚拟寄存器引用转换为有限的目标特定的寄存器集；
  • 寄存器不够时挤出（spill）到内存。

第二次 Instruction Scheduling 指令调度

  • 第2次指令调度，也称为后寄存器分配（RA）调度；
  • 此时可获得真实的寄存器信息，某些类型寄存器存在延迟，它们可被用以改进指令顺序。

Code Emission 代码输出

  • 代码输出阶段将指令从 MachineInstr 表示变换为 MCInst 实例；
  • 新的表示更适合汇编器和链接器，可以输出汇编代码或者输出二进制块特定目标代码格式。