LLVM 这个名字源于 Low Level Virtual Machine，但并不限于创建一个虚拟机，它已经发展成当今炙手可热的编译器基础框架。所谓编译器，就是把人类可读的高级语言转化为机器码的组件。LLVM采用模块化思想，使得每一个编译单元彼此独立。

LLVM 的设计目标是成为一系列的库。LLVM 代码有三种表示形式：内存编译器的IR，基于磁盘的Byte Code和汇编码。LLVM IR致力于成为一种足够底层的通用IR，基于静态单赋值，提供类型安全性，底层操作性和灵活性。

C 代码转化为LLVM汇编码

将C代码编译为LLVM IR的过程从词法分析开始——将C代码分解成token流，每个token可表示标识符、字面量、运算符等；token流会传递给语法分析器，语法分析器会在语言的CFG（上下文无关文法）的指导下将token流组织成抽象语法树；接下来会进行语义分析，检查语义正确性，然后生成IR。

在multiply.c 中编写一段C代码：

1
2
3
4
5
6
int mult() {
  int a =5;
  int b = 3;
  int c = a * b;
  return c;
}

使用以下命令来将C代码转换成LLVM IR：

clang -emit-llvm -S multiply.c -o multiply.ll

生成如下的LLVM IR：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
; ModuleID = 'multiply.c'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-redhat-linux-gnu"

; Function Attrs: nounwind uwtable
define i32 @mult() #0 {
  %a = alloca i32, align 4
  %b = alloca i32, align 4
  %c = alloca i32, align 4
  store i32 5, i32* %a, align 4
  store i32 3, i32* %b, align 4
  %1 = load i32* %a, align 4
  %2 = load i32* %b, align 4
  %3 = mul nsw i32 %1, %2
  store i32 %3, i32* %c, align 4
  %4 = load i32* %c, align 4
  ret i32 %4
}

attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = metadata !{metadata !"clang version 3.4.2 (tags/RELEASE_34/dot2-final)"}

LLVM IR结构

  • Module（模块）是LLVM IR的顶层容器，对应于编译前端的每个翻译单元（TranslationUnit）。每个模块由目标机器信息、全局符号（全局变量和函数）及元信息组成。
  • Function（函数）就是编程语言中的函数，包括函数签名和若干个基本块，函数内的第一个基本块叫做入口基本块。
  • BasicBlock（基本块）是一组顺序执行的指令集合，只有一个入口和一个出口，非头尾指令执行时不会违背顺序跳转到其他指令上去。每个基本块最后一条指令一般是跳转指令（跳转到其它基本块上去），函数内最后一个基本块的最后条指令是函数返回指令。
  • Instruction（指令）是LLVM IR中的最小可执行单位，每一条指令都单占一行

LLVM IR中标识符有两种基本类型：全局标识符（以@开头）和局部标识符（以%开头）。

局部变量有两种分类方案：

按照是否命名分类：

  • 命名局部变量：顾名思义，比如%tmp
  • 未命名局部变量：以带前缀的无符号数字值表示，比如%1、%2

按照分配方式分类：

  • 寄存器分配的局部变量：此类局部变量多采用%1 = some value形式进行分配，一般是接受指令返回结果的局部变量
  • 栈分配的局部变量：使用alloca指令在栈帧上分配的局部变量，比如%2 = alloca i32，%2也是个指针，访问或存储时必须使用load和store指令

LLVM IR 转换为 Bit Code

LLVM bitcode由两部分组成：位流（可类比字节流）和将LLVM IR编码成位流的编码格式。

llvm-as是LLV汇编器，将 LLVM IR 转为 bitcode。为了将 LLVM IR转换为bitcode，引入区块（block）和记录（record）。

区块表示位流的区域，记录由记录码和整数组成。

LLVM bitcode转换为目标平台汇编码

llc将LLVM输入编译编译为特定架构的汇编语言

实现编译器前端

使用自定义的语言TOY，为其编写词法分析器和语法分析器，以及使用前端从抽象语法树生成IR代码。

定义TOY语言

实现词法分析器和语法分析器之前，先需要定义这门语言的语法。

一门编程语言会有一些变量、函数调用、常量等。TOY语言只包含32位的整型常量类型，以及不需要声明类型的变量。

语法通过如下的推导规则来定义：非终结符号在左边，终结符号和非终结符的组合在右边；当遇到一个LHS，就会根据推导规则生成与之对应的RHS。

一个算术表达式可以是一个数字常量：numeric_expr := number

括号表达式会在左右括号之间包含一个表达式：paran_expr := ‘(‘ expression ‘)’

抽象语法树

抽象语法树(AST)是编程语言的抽象语法结构的树形表示。

语法分析器根据语言的语法规则来解析代码

Command Description
llvm-as 将人类可读的 .ll 文件汇编成字节代码
llvm-dis 将字节代码文件反编成人类可读的 .ll 文件
opt 在一个字节代码文件上运行一系列的 LLVM 到 LLVM 的优化
llc 为一个字节代码文件生成本机器代码
lli 直接运行使用 JIT 编译器或者解释器编译成字节代码的程序
llvm-link 将几个字节代码文件连接成一个
llvm-ar 打包字节代码文件
llvm-ranlib 为 llvm-ar 打包的文件创建索引
llvm-nm 在 打印出LLVM中间格式或者object文件的符号表
llvm-prof 将 ‘llvmprof.out’ raw 数据格式化成人类可读的报告
llvm-ld 带有可装载的运行时优化支持的通用目标连接器
llvm-config 打印出配置时 LLVM 编译选项、库、等等
llvmc 一个通用的可定制的编译器驱动
llvm-diff 比较两个模块的结构
bugpoint 自动案例测试减速器
llvm-extract 从 LLVM 字节代码文件中解压出一个函数
llvm-bcanalyzer 字节代码分析器 （分析二进制编码本身，而不是它代表的程序）
FileCheck 灵活的文件验证器，广泛的被测试工具利用
tblgen 目标描述阅读器和生成器
lit LLVM 集成测试器，用于运行测试
AddressSanitizer 一个快速内存错误探测器
Term Description
ADCE (Aggressive Dead Code Elimination) 积极的死代码消除
AST (Abstract Syntax Tree) 抽象语法树
BB Vectorization (Basic-Block Vectorization) 基本块向量化
BURS (Bottom Up Rewriting System) 自底向上重写系统
CSE (Common Subexpression Elimination) 共同子表达式消除 例如 (a+b)*(a+b) 有两个相同的子表达式: (a+b)。这个优化使得只做一次加法然后执行乘法。
DAG (Directed Acyclic Graph) 有向无欢图
DSE (Dead Store Elimination) 可不达存储消除
FCA (First Class Aggregate) 第一类集合
IPA (Inter-Procedural Analysis) 过程间分析
IPO 过程间优化。引用到过程、函数和编译单元之间发生的大量代码优化。
ISel 指令选择
LCSSA (Loop-Closed Static Single Assignment Form) 闭环静态单赋值形式
LICM (Loop Invariant Code Motion) 循环不变量
Load-VN 负荷值编号
LTO 链接时优化
MC 机器码
Object Pointer 指向对象的指针，使得垃圾回收器可以追踪对象内的引用。
PRE (Partial Redundancy Elimination) 部分冗余消除
Safe Point ()
SDISel (Selection DAG Instruction Selection) DAG 指令选择
SCC (Strongly Connected Component) 强链接组件
SCCP (Sparse Conditional Constant Propagation) 稀疏的条件常量传播
SLP (Superword-Level Parallelism)
SRoA (Scalar Replacement of Aggregates) 聚合标量替换
SSA (Static Single Assignment) 静态单赋值
Stack Map 在垃圾回收中，由代码生成器发出的元数据在一个函数调用的栈帧中标识了roots
TBAA (Type-Based Alias Analysis) 基于类型的别名分析

Reference：

  1. LLVM Cookbook
  2. 用LLVM开发新语言
  3. LLVM入门笔记
  4. LLVM IR入门指南