前言

为何写作本书

编译器一端连接着高级编程语言，另一端连接着硬件，近年来这两端的发展都极为迅猛，例如涌现不少新型编程语言（如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网络能量函数的收敛。

还要感谢谷祖兴博士、李坚松博士、董如振博士、王篁博士、王亚东、韦清福等，他们对本书提出了很多意见和建议。

最后还要感谢家人对笔者的理解和支持，让笔者有更多时间和精力完成写作。

彭成寒