该系列笔记是我对之前学过的 Tutorial LLVM Backend Cpu0 教程的填充完善与版本升级，首发于我的知乎专栏：https://www.zhihu.com/column/c_1250484713606819840
这是本教程的序言章节，其他章节请访问最后一节中链接访问。
本笔记对应的源码文件链接：https://github.com/P2Tree/LLVM_for_cpu0

已经上传大部分内容，剩余章节正在编写中。

序

0.1 动机

编译器是一个很复杂的软件系统，在这个系统中，包含的计算机理论非常之多，也和很多数学理论有直接关系。在学校学习编译原理课程中，大多只会讲解一些编译器前端的知识，既抽象、又过于理论化，让很多同学学习起来云里雾里，最后也不清楚编译原理是干什么的，对于实际工作中使用编译器、开发编译器或利用编译器原理完成相关工作来说，会感觉书到用时方恨少。

然而，当遇到实践问题时，只拿着编译原理教材，却依然不知道该怎么做，编译原理的复杂性，使理论和实践之间的鸿沟过宽。而不同的编译器工程师可能面对相关性不大的工作内容，有面向前端的、有面向后端的，也有专门做优化的，具体展开又有很多细分。

一部分商用编译器的代码是开源的，比如gcc 和 clang/LLVM，如果拿商用编译器的代码来学习，但没有掌握学习方法，会感觉跳入泥潭，花费很大精力和时间却无法快速上手。商用编译器的文档和教程非常少，对于国内开发者来说，还有英文阅读水平的阻碍，经常需要一边阅读英文文档，一边翻译编译原理教材，正所谓，每句话都能看懂，连起来还是没弄清什么道理，学习难度也很大。

LLVM 是一套编译器架构，它的设计非常灵活和清晰，相比 gcc 来说，学习会更容易一些。另一个原因是，LLVM 的开源协议（BSD）比较友好，通常是指基于 LLVM 来开发的编译器可以闭源自己的代码，而 gcc 是 GPL 协议，要求必须开源，商业化来讲，LLVM 更有优势。还有个优势是，LLVM 的可重用性强，即使不做编译器，也可以把其中一部分拿出来用在自己的软件中，比如静态分析，或自定义的 DSL 等。

我在学习 LLVM 的过程中，也苦于找不到适合初学者的学习材料，硬着头皮把 LLVM 官网上的几篇超级长的文章读完，并翻译了一部分。然而却发现官方文档很多也不全面，这让我意识到，我该写写代码了 （工作中也会改代码，但不会涉及整个模块重写的需求）。偶然中我遇到了一个教程，由台湾的陳鍾樞（https://github.com/Jonathan2251）编写的《Tutorial: Creating an LLVM Backend for the Cpu0 Architecture》，如获至宝。学习完毕后，颇有收获。书中讲解地非常细致，虽然并没有涉及很复杂的功能，但我认为作为入门材料足矣。

之后，我便有一个想法，LLVM 的中文学习材料中，还没有这样一个 Tutorial，能带着不熟悉 LLVM 后端的朋友一步步入门，为什么我不可以写一个呢？他的教程基于 LLVM 3.1 完成，虽然 3.1 是挺经典的一个版本，但现在都已经 10.0 了，我也刚好可以更新一下（请允许我有点私心，因为工作中用的 8.0.0，所以我的这个教程基于 8.0.0 完成）。于是乎，我一边重新读《Tutorial: Creating an LLVM Backend for the Cpu0 Architecture》这个教程，一边把我的中文版写出来，我打算篇章结构和思路基本不变，毕竟他是花很大精力设计出来的，我便也没必要在这些方面多费心思，直接用优秀的设计即可。在此也对他的工作表示真诚感谢。（注：其中部分内容直接翻译自原文，同时也会按更易理解的方式做一些修改，并排掉一些 bugs）

另外，他的个人主页上还有其他文章，有关于完成一个前端的教程，我还没有看过，相信也非常优秀，如果你的英语阅读能力过关，编译原理知识也扎实，也可参考他的文章（我自己时间有限，很可能写不出他那么丰富的知识）。

0.2 目标读者

本文的目标读者是之前没用过 LLVM 做过开发，但已经有一些编译原理基础知识的朋友。如果你看到 LLVM 的代码后，不知道该怎么写一个后端，搞不懂后端这些文件都是干什么的，应该在哪里写代码，这个教程可能会帮到你。

非常熟悉 LLVM 框架和编译器技术的大佬们，也请多多指教，我也在一边学习一边完善，欢迎交流技术心得。

0.3 前言

由于 LLVM 出色的模块化设计，在 LLVM 的基础上新增一个后端，会非常容易。跟着这篇教程完成整个流程，你就能掌握如何把自己的后端部署在 LLVM 上并为它增加一些功能。

本教程使用 Cpu0 作为硬件的例子，来构建能适配它的编译器后端。Cpu0 是一个非常简单的 RISC 架构处理器，通常是作为学 IC 的同学的练手习题，所以，即使你没有接触过 Cpu0，只要了解一点 RISC 架构处理器（或者 Mips 处理器也成，Cpu0 很多设计依据 Mips 完成），也很容易接受这个处理器；如果你很熟悉它，那更好（其实我并不太熟悉，只要了解地足够详细，并不阻碍编译器后端的设计）。后边我会用一小节的内容介绍一下这个处理器。

《Tutorial: Creating an LLVM Backend for the Cpu0 Architecture》教程中的配套代码中，提供了一套 Cpu0 Simulator 的 Verilog 实现代码，我们只需要把这套代码运行起来，从而不需要你真的有一个 Cpu0 的硬件（实际上也不可能有）。我们最终的测试，是通过我们的编译器，将程序翻译成 Cpu0 支持的 HEX 格式文件，并输入到 Simulator 中运行，最后检查运行结果（教程中也会介绍如何生成 bin 文件，即使它不能运行，但机理是一样的）。

前端语言采用 C 语言，《Tutorial: Creating an LLVM Backend for the Cpu0 Architecture》教程中的目标是 C++ 语言，并且其中一章专门介绍如何支持 C++ 特性，我暂时没打算去做，如果将来有时间，我会再更新。

虽然不支持 C++，但 LLVM 是基于 C++ 语言开发的，所以对于 C++ 语言要足够熟悉。另外，面向对象的思想一定要有，除了 LLVM 后端结构中强表现出继承、多态等特性，还因为会涉及到 TableGen（LLVM 后端中很重要的一种面向对象的 DSL），它也可以看做是一种面向对象语言。

我计划主要讲解代码实现，对于编译器的原理和 LLVM 架构比较复杂的设计，我不会过多涉及，你依然需要搭配 LLVM 官方的一些文档来学习。学习 LLVM 的一个建议是，不要拘泥于与自己无关的功能，就像你在 Linux 上写个串口驱动，便不需要了解太多操作系统实现的东西，适当忽略无关细节，可以让学习更加顺畅。

我会把基于 LLVM 8.0.0 下的 Cpu0 的后端实现代码上传到网络（https://github.com/P2Tree/LLVM_for_cpu0），与教程配合食用极佳。每一章我都会生成一份快照，相对路径一致地存到一个单独路径下（我考虑过使用 git tag，但因为提交比较琐碎，文档也会在未来经常更新，所以 tag 并不完全表示某一章节的结束，不过我还是打入了 tag 供参考）。

我的开发机是 Macbook，系统是 Mojave （10.14.6），编译器版本是系统原生的 clang++ 10.0.0。和我的系统不一致，可能会遇到一些问题，但我估摸着问题不会很大，遇到问题可自行 Google 解决。

0.4 学习 LLVM 知识

如果并不了解 LLVM，那便需要先看一下有关于 LLVM 的入门知识，这可能需要花费一下午的时间，但这真的很值。

这一小节我留着，因为它真的很重要。

入门看这篇文章：http://llvm.org/docs/GettingStarted.html#id8，里边的细节不用记，将来还会回头查。

也可以看我之前写的入门教程：https://zhuanlan.zhihu.com/p/140462815。

这篇文章要看一下：http://www.aosabook.org/en/llvm.html，有了 Getting Started 的基础后，大概浏览一下，几个重点要看，一个是三段式结构，一个是 LLVM IR，一个是 TableGen

• 三段式结构是现在主流编译器的标配，懂得为什么这么做很重要；
• LLVM IR 的知识，达到看到 LLVM IR 和源程序，指令能基本对应的水平就行。
• TableGen 大概懂它是干什么的就行了，可以看我写的这篇文章：https://zhuanlan.zhihu.com/p/141265959
• 怎么写 pass 我认为没必要细看，本教程后边会讲，而且对其他部分的理解也没啥影响。

后端流程的东西也要懂一点，LLVM 的后端主要是：

• 指令选择：先将输入的 LLVM IR 翻译成 DAG（有向无环图，后端 SelectionDAG 是很重要的一种中间表示），再多次做下降、合法化（知道有这个东西就好）。
• 指令调度：对指令做重排，优化流程。这之后就是列表了，但依然是 SSA（静态单赋值）形式。
• 寄存器分配：SSA 形式中的寄存器是虚拟寄存器，这里全部替换成物理寄存器（之前的步骤也会有个别替换，这里是最终替换），之后就都是物理寄存器了。
• 代码生成：之后就是吐出代码了，包括汇编代码或者是二进制代码。这里 LLVM 和 gcc 的一个不同是，LLVM 可以直接吐出二进制代码，也就是汇编器的功能嵌入到编译器后端中，这得益于 LLVM 的模块化设计。
• 这些步骤中，会穿插不同的优化进去，优化 pass 的输入和输出是同一种形式，可以暂时忽略掉（编译器优化属于编译器进阶工作，我并不打算覆盖太多优化的内容）。

了解后端流程可以详细看一下这篇官方文档：https://llvm.org/docs/CodeGenerator.html，也可以看我写的译文：https://zhuanlan.zhihu.com/p/301653651。推荐分章节多次阅读，而不是一口气读完，虽然前边的内容简单，但后边的内容会突然很深入，并且讲解并不完善，需要配合去翻代码。

在这个教程里边不会展开讨论 LLVM 的基础知识，我会尽可能的不涉及太多不相关的知识，所以，如果依然看不懂，这一节的推荐网址还是要好好读一读。

0.5 教程章节介绍

• 第 1 章 新后端初始化和软件编译 （https://zhuanlan.zhihu.com/p/352718079）

  这一章介绍 Cpu0 的硬件配置，以及简单介绍 LLVM 代码的结构和编译方法。然后，我们会搭建起后端的框架，并能让 LLVM build 通过，通过完成新后端注册的操作，可以让 llc 识别到我们新后端的存在。

• 第 2 章 后端架构搭建（https://zhuanlan.zhihu.com/p/356837953）

  这一章介绍 LLVM 后端代码的组成结构，并分别实现这些结构下的类。这一章结束时，我们的后端就能够正常生成简单代码的汇编码了。这一章会增加不少代码，Cpu0 的后端代码主要参考 Mips 后端的代码，建议直接复制拿去用，然后根据实际情况修改。

  这一章需要留意一下类关系。还需要知道指令选择、寄存器分配等概念。到调整栈帧的时候，可能会有点难，但只要对计算机体系结构比较清楚，相对会好理解。

• 第 3 章 支持算术和逻辑指令（https://zhuanlan.zhihu.com/p/362363094）

  这一章首先增加了更多的 Cpu0 算术指令，并且在其中一个章节讲解了如何使用 Graphviz 图形化展示你的 DAG 优化步骤和 llc 显示选项。这些在各个优化步骤中存在的 DAG 转换过程可以使用 Graphviz 来图形化显示，展示出更多的有效信息。算术运算之后是逻辑运算。

  不同于上一章，这一章，你应该专注于 C 代码的操作和 llvm IR 之间的映射以及如何在 td 文件中描述更复杂的 IR 与指令。这一章定义了另外一些寄存器类，你需要了解为什么需要它们，如果有些设计没有看懂，可能是对 Cpu0 的硬件不够熟悉，可以结合硬件来理解。

• 第 4 章 生成目标文件（https://zhuanlan.zhihu.com/p/371534867）

  之前的章节只介绍了汇编代码生成的内容，这一章，我们将介绍对 ELF 目标格式文件的支持以及如何使用 objdump 工具来验证生成的目标文件。在 LLVM 代码框架下，只需要增加少量的代码，Cpu0 后端就可以生成支持大端或小端编码的目标文件。目标注册机制以及它的结构也在本章介绍。

• 第 5 章 支持全局变量（https://zhuanlan.zhihu.com/p/378338026）

  在这一章中，我们要处理全局变量的访问。全局变量的 DAG 翻译不同于之前的 DAG 翻译。依据 llc -relocation-model 参数（指定重定位模式是静态重定位还是运行时重定位），它会在运行时（编译器编译时）在后端创建 IR DAG 节点，而其他的 DAG 只是根据输入文件来做 DAG 的翻译 （伪指令除外）。大家需要专注于如何在运行时创建 DAG 节点而增加的代码，以及如何在 td 文件中定义 Pat 结构。另外，全局变量的机器指令打印功能也需要完成。

• 第 6 章 其他数据类型（https://zhuanlan.zhihu.com/p/382189083/edit）

  之前的章节只实现了 int 和 32 位的 long 类型数据，这一章会新增很多更复杂的数据类型，比如 char, bool, short, long long，还会增加结构体，浮点，和向量类型。这一部分内容相对比较简单，其实这些类型也都是标准语言都支持的类型，所以 LLVM 自身已经实现了很大一部分功能，只要我们的后端不那么奇怪，就很容易填补缺失的内容。

• 第 7 章 控制流（https://zhuanlan.zhihu.com/p/386457923）

  这一章介绍与控制流相关的 IR 的处理，比如 if, else, while, for 等，会说明如何将这些 IR 转换为机器指令；之后的小结，会介绍一个优化控制流的后端 pass，通过这个小结，会讲解如何编写一个简单的后端优化 pass。之后还会简单介绍如何处理条件指令 select 和 select_cc，以此支持控制流状态的后端优化。

• 第 8 章 支持函数调用（待上传）

  这一章会支持后端对子过程/函数的处理。首先需要读者对栈帧的概念有一定了解，虽然不同的 ABI 中 Calling Convention 不一定相同，但 RISC 机器遵循的基本规律是类似的，如果不了解的话，读这一章会比较费劲，可以初步了解 Mips 的 ABI 即可，因为我们的 Cpu0 借用了 Mips 的 ABI。

  我们会完成依据栈帧的参数输入和返回值返回，然后研究更复杂一些的结构体传参。之后会介绍两个基于函数调用的优化，尾调用优化和递归优化。最后会介绍一些可选功能。

• 第 9 章 支持 ELF 文件格式（待上传）

  自此我们要开始支持生成 ELF 文件格式，因为关于指令的编码在之前完成指令的同时就已经实现，所以目前我们只需要完成 elf 文件格式和重定位就可以了。

• 第 10 章 支持汇编（待上传）

  这一章对独立汇编器做支持，主要实现独立汇编器的 parser，另外也会实现内联汇编的功能。这部分内容相对来说会简单一些。

  完成到这里，一个简单的编译器就基本实现了。

• 第 11 章 支持 C++ 特性（暂无计划）

  暂时不考虑更新 C++ 特性的支持，将来有时间会再补充。

• 附录 A 使用 Simulator 验证编译器（待上传）

  这个附录要介绍 Cpu0 使用 Simulator 来验证编译器生成的内容的合法性，从而判断我们编译器的功能完整性。