内容简介
通过阅读本书，读者理解和掌握LLVM代码生成过程，可以根据本书指导为基于LLVM开发一款新后端的编译器。同时本书还介绍了各种编译过程中使用到的算法，读者可以根据场景对算法进行增强从而达到性能优化目的。
作者简介
彭成寒：AI编译器与虚拟机技术专家，目前主要专注于LLVM、MLIR相关的AI编译器研究，并在JVM、V8和WebAssembly等虚拟机技术方面有着丰富的研发经验。他深耕IT领域近20年，曾涉足应用软件和大数据开发等多个领域，并著有《JVM G1源码分析和调优》《新一代垃圾回收器ZGC设计与实现》《深入探索JVM垃圾回收：ARM服务器垃圾回收的挑战和优化》等重要领域专著。
李灵：毕业于上海交通大学，拥有6年编译器和虚拟机相关的研发工作经验，深度参与了多项LLVM编译器及V8、WebAssembly虚拟机等开源项目的研发工作，目前正在从事AI编译器研发工作。
戴贤泽：毕业于南京理工大学，拥有7年编译器和虚拟机相关工作经验，深入参与了方舟编译器及V8、WebAssembly虚拟机等开源项目的研发工作，目前正在从事编译器和虚拟机的设计与研发工作。
王志磊：毕业于浙江大学，拥有6年编译器和虚拟机相关的研发工作经验，参与了多项编译器及虚拟机的开发项目，并为llvm-bolt、V8、WebAssembly等开源项目贡献代码，目前专注于虚拟机相关的研发，精通AOT和JIT技术。
俞佳嘉：南京大学硕士研究生，现任华为编译器与编程语言实验室鸿蒙开发者生态构建技术首席专家。他拥有10余年的丰富工作经验，在Intel、Microsoft、华为等世界知名公司从事过编译器、虚拟机、指令翻译等技术的相关研发工作，并深入参与了Intel Houdini、华为方舟编译器等产品的核心研发工作。
目录
目 录 Contents
前言
第一部分 基础知识
第1章 绪论2
1.1 LLVM设计思路分析3
1.2 LLVM主要子项目4
1.3 LLVM构建与调试5
1.4 LLVM在线工具7
1.5 本章小结9
第2章 IR基础知识10
2.1 IR分类11
2.1.1 树IR11
2.1.2 线性IR11
2.1.3 图IR12
2.2 CFG的基本块与构建14
2.2.1 基本块14
2.2.2 构建CFG15
2.3 静态单赋值15
2.3.1 基本概念16
2.3.2 SSA构造19
2.3.3 SSA析构19
2.3.4 SSA分类28
2.3.5 基本块参数和Phi节点29
2.4 本章小结30
第3章 数据流分析基础知识31
3.1 半格、格与不动点31
3.1.1 半格和偏序集31
3.1.2 格33
3.1.3 不动点34
3.2 数据流分析原理及描述35
3.2.1 数据流方程形式化描述36
3.2.2 数据流分析的理论描述40
3.3 数据流方程示例43
3.3.1 活跃变量43
3.3.2 到达定值45
3.3.3 常量传播46
3.4 扩展阅读：数据流的遍历性能分析49
3.5 本章小结50
第4章 支配分析51
4.1 支配和逆支配51
4.1.1 支配和逆支配相关定义51
4.1.2 支配和逆支配含义解析53
4.2 支配树和支配边界的实现55
4.2.1 半支配节点及相关概念56
4.2.2 LT算法和Semi-NCA的差异57
4.2.3 支配边界的实现58
4.3 扩展阅读：支配树相关小课堂58
4.3.1 支配树构造算法及比较59
4.3.2 如何快速判断任意两个节点的支配关系60
4.4 本章小结62
第5章 循环基本知识63
5.1 自然循环64
5.2 LLVM的循环实现65
5.2.1 循环识别66
5.2.2 循环规范化67
5.3 本章小结71
第6章 TableGen介绍72
6.1 目标描述语言72
6.1.1 词法72
6.1.2 语法74
6.2 TableGen工具链77
6.2.1 从TD定义到记录78
6.2.2 从记录到C++代码81
6.3 扩展阅读：如何在TD文件中定义匹配83
6.3.1 隐式定义匹配模板83
6.3.2 复杂匹配模板84
6.3.3 匹配规则支撑类86
6.4 本章小结86
第二部分 代码生成
第7章 指令选择91
7.1 指令选择的处理流程92
7.2 SelectionDAGISel算法分析94
7.2.1 SDNode分类96
7.2.2 LLVM IR到SDNode的转换98
7.2.3 SDNode合法化108
7.2.4 机器指令选择117
7.2.5 从DAG输出MIR123
7.3 快速指令选择算法分析126
7.4 全局指令选择算法原理与实现128
7.4.1 全局指令选择的阶段128
7.4.2 GMIR生成129
7.4.3 指令合法化133
7.4.4 寄存器类型选择137
7.4.5 机器指令选择141
7.4.6 合并优化143
7.5 本章小结146
第8章 指令调度147
8.1 LLVM指令调度149
8.1.1 指令调度算法150
8.1.2 拓扑排序算法151
8.2 Linearize调度器152
8.2.1 构造依赖图153
8.2.2 对依赖图进行调度153
8.3 Fast调度器156
8.3.1 Fast调度器实现157
8.3.2 物理寄存器依赖场景的处理158
8.3.3 示例分析162
8.4 BURR List调度器166
8.4.1 影响指令调度的关键因素166
8.4.2 指令优先级计算方法168
8.4.3 示例分析170
8.5 Source List调度器173
8.6 Hybrid List调度器174
8.7 Pre-RA-MISched调度器174
8.7.1 Pre-RA-MISched调度器实现174
8.7.2 调度区域的划分175
8.7.3 影响Pre-RA-MISched调度器的关键因素175
8.7.4 MIR指令时延的计算175
8.7.5 寄存器压力的计算177
8.7.6 示例分析181
8.8 Post-RA-TDList调度器186
8.8.1 Post-RA-TDList调度器实现186
8.8.2 示例分析186
8.9 Post-RA-MISched调度器189
8.10 循环调度190
8.10.1 循环调度算法实现190
8.10.2 示例分析194
8.11 扩展阅读：调度算法的影响因素200
8.12 本章小结203
第9章 基于SSA形式的编译优化204
9.1 前期尾代码重复205
9.1.1 尾代码重复原理205
9.1.2 尾代码收益判断207
9.1.3 执行尾代码重复优化209
9.2 Phi优化212
9.3 栈着色213
9.4 栈槽分配217
9.5 死指令消除218
9.6 IPL优化之If-Conversion219
9.7 循环不变量外提224
9.8 公共子表达式消除224
9.9 代码下沉227
9.10 窥孔优化228
9.11 本章小结231
第10章 寄存器分配232
10.1 寄存器分配流程解析233
10.1.1 Fast算法执行流程233
10.1.2 Basic算法执行流程233
10.2 寄存器分配涉及的Pass241
10.2.1 死亡和未定义子寄存器检测241
10.2.2 隐式定义指令处理243
10.2.3 不可达MBB消除243
10.2.4 活跃变量分析244
10.2.5 Phi消除246
10.2.6 二地址指令变换249
10.2.7 指令编号255
10.2.8 变量活跃区间分析256
10.2.9 寄存器合并256
10.2.10 MBB的频率分析259
10.2.11 寄存器分配：直接分配与间接分配265
10.2.12 将虚拟寄存器映射到物理寄存器266
10.2.13 栈槽着色266
10.2.14 复制传播267
10.2.15 循环不变量外提269
10.3 Fast算法实现269
10.3.1 Fast算法实现思路269
10.3.2 示例分析270
10.4 Basic算法实现276
10.4.1 算法实现思路276
10.4.2 示例分析277
10.5 Greedy算法实现289
10.5.1 Greedy算法实现思路290
10.5.2 算法实现的核心：拆分291
10.5.3 区域拆分之Hopfield网络详解293
10.5.4 使用Hopfield网络求解拆分296
10.5.5 示例分析300
10.6 PBQP算法实现313
10.6.1 PBQP介绍313
10.6.2 寄存器分配和PBQP的关系314
10.6.3 PBQP问题求解314
10.6.4 寄存器分配问题建模示例317
10.6.5 PBQP实现原理以及示例分析318
10.7 扩展阅读：图着色分配324
10.8 4种算法对比326
10.9 本章小结329
第11章 函数栈帧生成和非SSA形式的编译优化330
11.1 函数栈帧生成以及相关优化331
11.1.1 栈帧生成331
11.1.2 代码下沉332
11.1.3 栈帧范围收缩335
11.2 MIR优化337
11.2.1 分支折叠337
11.2.2 尾代码重复347
11.2.3 复制传播347
11.3 MIR指令变换和调度347
11.4 MIR信息收集及布局优化348
11.4.1 基本块布局优化349
11.4.2 公共代码提取355
11.4.3 函数冷热代码分离359
11.4.4 代码布局优化比较363
11.5 扩展阅读：后缀树构造和应用365
11.5.1 后缀树的构造365
11.5.2 后缀树的应用372
11.6 本章小结372
第12章 生成机器码373
12.1 MC374
12.2 机器码生成过程375
12.2.1 汇编代码生成376
12.2.2 二进制代码生成378
12.3 本章小结381
第13章 添加一个新后端382
13.1 适配新后端的各个阶段382
13.1.1 指令选择阶段的适配383
13.1.2 寄存器分配相关的适配383
13.1.3 插入前言/后序384
13.1.4 机器码生成相关的适配384
13.2 添加新后端所需要的适配385
13.2.1 定义TD文件386
13.2.2 指令选择处理386
13.2.3 栈帧处理387
13.2.4 机器码生成处理388
13.2.5 添加新后端到LLVM框架中388
13.3 本章小结389
附录
附录A LLVM的中间表示392
附录B BPF介绍407
附录C Pass的分类与管理413