描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787111764151
1）主流新版LLVM详解：本书以LLVM 15版本为核心，深入剖析其内部机制，帮助读者掌握前沿的编译器技术。2）提供配套代码仓库：提供专门的代码仓库镜像，确保读者能够轻松获取并编译书中使用的LLVM版本，实现理论与实践相结合。3）LLVM IR从入门到精通：详尽介绍LLVM IR的基础知识及其设计原理，引导初学者快速上手，进阶至专业水平。4）提供BPF后端实战案例：选用BPF作为示例后端，通过精简的代码示例讲解代码生成的关键步骤，易于理解和跟踪。5）丰富的示例与资源：配套大量示例代码，涵盖C/C 、LLVM IR等多种语言和中间表示形式，并遵循统一命名规则，方便验证学习成果。
全书分为3篇。第1篇介绍编译器基础知识，包括中间表示，重点介绍SSA、数据流分析、支配、循环等知识，此外还介绍了LLVM的后端描述语言TableGen。第二篇剖析分LLVM代码生成，其中对代码生成的每一步骤都有提及，着重介绍指令选择、指令调度、寄存器分配和编译优化。同时还以BPF后端为例总结了如何基于LLVM开发一款新后端的编译器。第三篇附录主要总结了LLVM代码生成过程中使用的IR、BPF指令集以及如何在Linux运行BPF应用，Pass和PassManager的运行机制等知识。通过阅读本书，读者理解和掌握LLVM代码生成过程，可以根据本书指导为基于LLVM开发一款新后端的编译器。同时本书还介绍了各种编译过程中使用到的算法，读者可以根据场景对算法进行增强从而达到性能优化目的。
目 录 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
Preface 前 言
为何写作本书
编译器一端连接着高级编程语言，另一端连接着硬件，近年来这两端的发展都极为迅猛，例如涌现不少新型编程语言（如Rust、Swift等高级语言），所以经常需要实现特定的编译器。另外，由于摩尔定律失效，为了追求性能，领域专用的处理器也越来越流行，新型硬件也需要编译器支持。
成熟的编译器可能是最为复杂的软件系统之一，例如最为流行的GCC、LLVM、JVM等产品的发展都超过了20年，它们的代码量都达到了几百万甚至上千万行。除了工程实现的复杂性，编译器中涉及的数学理论、优化算法、代码生成等知识的复杂性也是其他软件系统无法比拟的。读者熟知的很多高级算法都能在编译器中找到。这些都导致开发和学习编译器非常困难。
近年来，LLVM编译器因有良好的结构（模块化设计）、卓越的性能（和GCC相比，在一些场景中性能更高）和完善的功能（包含编译、调试、运行时库、链接等），应用越来越广泛。不仅传统的编译器可以基于LLVM实现，而且由于LLVM提供了MLIR（多层中间表示），这使得它在AI编译器等新型编译器中的使用也越来越广泛。因此，越来越多的从业人员正在使用LLVM或者期望使用LLVM进行编译器相关工作。
由于LLVM被业界广泛应用于编译器开发，因此其发展迭代极为迅速，目前LLVM的代码量极为庞大，其后端代码量已超过200万行。LLVM的代码复杂度也极高，最新版本已经开始使用C 17语法，想要学习、用好LLVM必须对C 相关语法比较熟悉。这也导致编译器初学者在刚开始接触LLVM的时候会遇到不少困难，笔者希望通过本书帮助相关人员快速掌握和使用LLVM。
本书是《深入理解LLVM》系列图书中的第一本，后续还会写另外两本，分别对MLIR和编译优化进行介绍。
本书内容安排说明
本书以LLVM 15为例进行介绍，不同的LLVM版本对应算法的实现、提供的命令等都可能略有差异，读者在试验时应注意选择正确的版本，否则得到的结果可能和本书中介绍的不一致。为了保证读者和笔者使用相同的源码，笔者维护了一个LLVM代码仓的镜像：https://github.com/inside-compiler/llvm-project，读者可以从该代码仓下载、编译LLVM的代码。同时，因为LLVM是用C 开发的，且使用了较多C 17语法，所以如果读者对C 比较陌生，应先阅读相关书籍，本书不对C 进行介绍。
LLVM代码生成的输入为LLVM IR（Intermediate Representation，中间表示），输出为机器码，所以LLVM IR是基础知识。不熟悉LLVM IR的读者建议先了解这部分内容，你可以写一个简单的C/C 代码，使用Clang或者本书介绍的Compiler Explorer在线工具将其转化为LLVM IR，通过与C/C 源码对比来快速认识和了解LLVM IR。本书在附录A中也对LLVM IR进行了介绍，但这里更多关注的是LLVM IR的设计与演化发展，并没有详细介绍每一条LLVM IR的具体用法，关于如何使用LLVM IR，读者可以参考官方文档https://llvm.org/docs/LangRef.html。
TableGen贯穿整个LLVM代码生成过程，在学习LLVM代码生成时需要对TableGen有所了解。限于篇幅，本书并没有介绍TableGen中的一些高级语法，例如foreach、defvar等，读者可以参考官方文档（https://llvm.org/docs/TableGen/ProgRef.html）进行学习。
本书在介绍代码生成时主要以BPF后端为例。BPF是一套虚拟指令集，指令数非常少，BPF后端代码也较少，很多编译优化工作都不涉及BPF，所以读者只需要关注指令选择、寄存器分配过程，这样更容易把握代码生成的脉络，具体可参见附录B。
本书主要基于Debug版本的LLVM介绍算法详细执行过程，并使用GDB/LLDB以调试的方式获取中间结果，之后对中间结果进行解释。限于篇幅，书中并没有直接给出中间结果，而是对中间结果重新进行描述。在阅读时，建议读者根据第1章介绍的方法构建自己的调试版本，并使用GDB/LLDB对相关代码进行调试。如果仅依赖Compiler Explorer在线学习工具，读者仅能得到最终的结果，很多中间步骤都将被忽略，这可能对算法的理解不利。
另外，本书提供了不少示例代码，涉及C/C 代码、LLVM IR、DAG IR、MIR、MC等。我们按照如下规则对这些代码进行命名：以章节开头，以“–”为分隔符，后面依次为不同的用例编号，同时为同一用例不同的IR表示书中会使用不同的后缀。例如，第1章中第一个代码片段会被命名为代码清单1-1，如果它是C代码，则会命名为“1-1.c”，以此类推。为了便于读者验证，相关代码和命令都上传至代码仓https://github.com/inside-compiler/Inside-LLVM-Code-Gen。
如何阅读本书
本书包括13章和3个附录。
第一部分（第1～6章）为“基础知识”，介绍与体系结构无关的编译基础知识及TableGen工具，以帮助读者更好地理解LLVM项目。
第1章主要对LLVM项目进行简单介绍，同时介绍了如何使用Compiler Explorer在线工具学习LLVM的各种功能。
第2章主要介绍常见的IR，重点介绍了SSA（Static Single Assignment，静态单赋值）形式的相关知识，包括SSA构造、析构等。
第3章主要介绍数据流分析的理论基础、数据流方程。通过学习本章，读者可以了解学习编译优化所需的基础数据流知识。
第4章主要介绍支配、逆支配、支配树、逆支配树等基础知识。在编译优化中通过支配、逆支配等获取控制流信息，并完成相关优化。
第5章主要介绍循环、循环优化（即循环规范化）等基础知识。循环优化是编译优化中最为重要的优化，在代码生成中主要涉及循环不变量外提等，除了针对循环自身的优化外，在一些优化中也需要使用循环信息来生成最优代码。
第6章主要介绍目标描述语言的基本语法、工具的基本功能。LLVM作为通用的编译器需要支持多种后端，虽然不同的后端设计各有不同，但是都会包含寄存器、指令等公共信息，通过设计目标描述语言统一描述后端信息，并通过辅助工具将描述信息生成代码，配合LLVM代码生成框架以供使用（完成指令选择、调度和寄存器分配等工作），从而使得LLVM可以更加优雅地支持多种后端。
第二部分（第7～13章）为“代码生成”，介绍与编译器代码生成相关的知识，帮助读者了解编译器后端所的处理环节。
第7章主要介绍LLVM中实现的3种指令选择算法，分别是SelectionDAGISel、快速指令选择和全局指令选择。SelectionDAGISel算法演示了基于LLVM IR构造SDNode的过程，以及基于SDNode进行指令选择和生成MIR的过程；全局指令选择算法演示了从LLVM IR到GMIR，再到MIR指令选择的过程。
第8章主要介绍LLVM中实现的两类指令调度：局部调度和循环调度。局部调度是当前使用最广泛的调度，本章详细介绍了其中的Linearize、Fast、BURR List等调度器，并通过示例演示不同算法如何构造调度依赖图，以及指令调度实现时的关注点和调度过程；最后介绍了循环调度。
第9章主要介绍LLVM代码生成过程中基于SSA形式的编译优化，涵盖前期尾代码重复、栈槽分配、If-Conversion、代码下沉等多种优化算法。
第10章主要介绍LLVM中实现的4种寄存器分配算法——Fast、Basic、Greedy和PBQP。本章以Basic算法为例介绍了寄存器分配依赖的Pass，并介绍Fast、Basic、Greedy和PBQP的原理和实现，还通过示例演示了每种寄存器分配的过程。
第11章主要介绍在LLVM代码生成过程中，函数栈帧生成以及基于非SSA形式的编译优化。
第12章主要介绍LLVM机器码生成过程，并简单介绍了MC和机器码生成。
第13章主要以BPF为例介绍如何为LLVM添加一个新后端，让读者了解在添加新后端时哪些工作是必需的。
附录部分主要介绍阅读本书需要了解的一些背景知识。
附录A主要介绍LLVM的中间表示，如LLVM IR、DAG、MIR和MC。
附录B主要介绍BPF指令集和在Linux系统上如何运行BPF应用。
附录C主要介绍在LLVM中如何设计和实现Pass、PassManager，以在分析、变换过程中保证编译过程性能最优。
作者贡献说明
本书由彭成寒、李灵、戴贤泽、王志磊和俞佳嘉共同完成。第5章由戴贤泽负责，第6章由李灵负责，第7章由戴贤泽、李灵共同负责，第8章由俞佳嘉负责，第9章由所有作者合著，第12章和第13章由王志磊负责，第1～4章、第10章、第11章以及附录部分由彭成寒负责，全书由彭成寒审读定稿。
勘误与支持
由于笔者水平有限，书中难免存在一些疏漏，恳请读者批评指正。大家可以通过https://github.com/inside-compiler/Inside-LLVM-Code-Gen/issues提交issue。期待能够得到读者朋友们的诚挚反馈，在技术道路上与大家互勉共进。
由于本书篇幅有限，很多内容都未能囊括，为此笔者维护了网站：https://inside-compiler.github.io/，书中没有讨论到的内容将通过该网站呈现。
致谢
首先非常感谢本书其他作者的倾情付出，在过去一年多的时间里，所有作者每个周末都会花费半天时间在线分析和讨论问题、分享源码或相关论文阅读的情况，大家花费了大量的业余时间撰写相关内容，并不断地修改和完善。
另外在写作过程中，得到了很多朋友及同事的帮助和支持，彭成晓博士帮助笔者理解Hopfield网络中能量函数的物理意义和求解方法，杨磊博士帮助笔者证明了Hopfield网络能量函数的收敛。
还要感谢谷祖兴博士、李坚松博士、董如振博士、王篁博士、王亚东、韦清福等，他们对本书提出了很多意见和建议。
最后还要感谢家人对笔者的理解和支持，让笔者有更多时间和精力完成写作。
彭成寒
评论
还没有评论。