LLVM 后端实践笔记

该系列笔记是我对之前学过的 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 来验证编译器生成的内容的合法性,从而判断我们编译器的功能完整性。

上一篇:iOS编译简析


下一篇:MD5算法