Fork me on GitHub

基于 LLVM 自制编译器(10)——总结

展望

本章是本系列教程的最后一章。通过本教程,我们实现并扩展 Kaleidoscope 编程语言,使其语言的特性和功能不断增强。

在这个过程中,我们构建了词法分析器、解析器、AST、代码生成器、REPL、JIT,并为可执行文件支持了调试信息。所有的功能仅仅用了 1000 行左右代码就实现了。

我们的语言支持几个有趣的特性,比如:支持自定义的二元运算符和一元运算符,支持 JIT 编译并执行,支持构造控制流等。

本教程的初衷是为了向开发者展示定义、构建、使用语言是如此简单和有趣,编译器的实现也并不是难如登天!现在,我们已经了解了自制编译器的一些基础知识,这里强烈建议开发者能够使用代码对其进行魔改。比如,可以尝试支持以下这些特性:

  • 全局变量:虽然全局变量在软件工程中并不是一个非常有价值的特性,但是将它应用于 Kaleidoscope 中,其实是非常有用的。在目前的实现中,我们可以非常容易地为 Kaleidoscope 支持全局变量:只需要在全局变量符号表中查找未解析的变量即可。如果要创建全局变量,请使用 LLVM GlobalVariable 类。
  • 类型变量:目前,Kaleidoscope 只支持一种数据类型 double。由于只支持一种类型,因此无需指定变量类型。如果要支持多种数据类型,最简单的方法是要求用户为每个变量定义指定类型,并在符号表中记录变量的类型及其值。
  • 数组、结构体、向量:一旦支持了多种类型,我们可以通过各种方式对类型系统进行扩展。对于数组、结构体、向量等类型,其核心是基于 LLVM getelementptr 进行实现。
  • 标准运行时:目前,Kaleidoscope 运行用于访问任意外部函数,比如:printdputchard 等。当我们扩展语言以支持更高级的特性时,可以考虑实现运行时。比如:对于实现哈希表,哈希表底层封装了一系列实现,如果将这些实现内联至代码中,那么每定义一个哈希表会生成底层的实现代码,如果我们将哈希表的底层实现作为一个子程序定义在运行时,那么将会非常具有优化意义。
  • 内存管理:目前,Kaleidoscope 只能访问栈内存。如果为 Kaleidoscope 支持通过调用标准的 libc malloc/free 接口或使用垃圾收集器来分配堆内存,那么也能够极大地增强语言的能力。对此,LLVM 是完全支持精准垃圾收集(Accurate Garbage Collection)功能的,包括对象移动、栈扫描与更新等算法。
  • 异常处理:LLVM 支持生成零开销异常。此外,我们还可以隐式地使每个函数返回一个错误值并检查,从而生成代码。我们还可以显式地使用 setjmp/longjmp
  • 面向对象、泛型、数据库访问、复数、几何编程…:我们可以为语言扩展任何特性。
  • 其他领域:我们可以将 LLVM 应用至很多领域,从而构建特定语言。当然,还有很多其他领域会利用编译相关技术,比如:LLVM 被用于实现 OpenGL图形加速、C++ 代码转换为 ActionScript 等等。甚至,也许你将是第一个使用 LLVM 将正则表达式解释器 JIT 编译成本机代码的人!

LLVM IR 属性

对于 LLVM IR,我们经常会有一些疑问。本章,我们梳理了一些常见的问题,并进行解答。

目标独立

Kaleidoscope 是可移植语言 的一个例子:任何用 Kaleidoscope 编写的程序都可以在它运行的任何目标上以相同的方式工作。绝大多数编程语言都具有此属性,如:lisp、java、haskell、javascript、python 等。但需要注意的是,虽然这些语言是可移植的,但并非所有的库都是如此。

LLVM 有一个特性是它通常能够在 IR 中保持目标独立:我们可以将 LLVM IR 用于 Kaleidoscope 编译的程序并在 LLVM 支持的任何目标上运行它。简而言之,Kaleidoscope 编译器生成与目标无关的代码,因为它在生成代码时不会查询任何特定于目标的信息。

安全保证

上面提到的一些编程语言,很多都是 安全 的语言。比如,用 Java 编写的程序不可能破坏其地址空间并使进程崩溃(假设 JVM 没有错误)。 安全性是一个有趣的属性,它需要结合语言设计、运行时支持以及操作系统支持。

在 LLVM 中实现安全语言是完全可以的,但 LLVM IR 本身并不能保证安全。LLVM IR 允许不安全的指针转换、释放错误后使用、缓冲区溢出和各种其他问题。要实现安全的特性,我们需要在 LLVM 之上构建一个层来实现。

语言特定优化

和其他工具一样,LLVM 不能在一个系统中解决所有的问题。对此,很多开发者会抱怨 LLVM 无法执行高级语言的特定优化,因为 LLVM 丢失了太多信息。对此,本章给出了如下的一些看法。

首先,LLVM 确实会丢失信息。例如,在撰写本教程时,在 LLVM IR 中无法区分 SSA 值是来自 ILP32 机器上的 C int 还是 C long(调试信息除外)。两者都被编译为 i32 值,并且关于它来自什么的信息丢失了。这里更普遍的问题是 LLVM 类型系统使用 “结构等价” 而不是 “命名等价”。另一个让人感到惊讶的地方是,如果我们在高级语言中有两种具有相同结构的类型(例如,两个具有单个 int 字段的不同结构),那么这些类型将被编译成单个 LLVM 类型。

其次,虽然 LLVM 确实会丢失信息,但 LLVM 并不是一个固定的目标:我们会继续以许多不同的方式增强和改进它。除了添加新功能(LLVM 并不总是支持异常或调试信息)外,我们还扩展了 IR 以捕获重要信息以进行优化(例如,参数是符号扩展还是零扩展、指针别名信息等)。许多增强功能都是用户驱动的:开发者希望 LLVM 包含一些特定功能,为此,开发者们一直在对它进行扩展。

第三,添加特定于语言的优化是可能且容易的。举一个简单的例子,我们可以很容易地添加特定于语言的优化通道,从而为一种语言编译的代码。对于 C 系列,有一个标准 C 库函数的优化通道。如果我们在 main() 中调用 exit(0),它会知道将其优化为 return 0; 是安全的。

此外,还可以将各种其他语言特定的信息嵌入到 LLVM IR 中。即使在最坏的情况下,我们也可以将 LLVM 视为纯粹的代码生成器,并在特定于语言的 AST 上在编译前端实现我们想要的高级优化。

提示与技巧

在使用 LLVM 之后,我们会了解到许多有用的提示与技巧,这些技巧和技巧乍一看并不明显。这里,我们只讨论其中的一些问题。

实现可移植的 offsetof/sizeof

如果我们希望让编译器生成的代码保持 目标独立,那么会出现一件有趣的事情,那就是我们经常需要知道某些 LLVM 类型的大小或 llvm 结构中某些字段的偏移量。 例如,我们可能需要将类型的大小传递给分配内存的函数。

不幸的是,这在不同目标之间可能会有很大差异:例如,指针的宽度是特定于目标的。不过,有一种巧妙的方法,即使用 getelementptr 指令,它允许我们以可移植的方式计算它。

垃圾回收栈帧

某些语言想要显式地管理栈帧,通常是为了支持垃圾收集栈帧或允许实现闭包。事实上,通常有比显式管理栈帧更好的方法来实现这些功能,但如果我们执意这么做,LLVM 也是支持的。 这需要我们的编译前端将代码转换为连续传递样式并使用尾调用(LLVM 也支持)。

总结

本系列教程通过基于 LLVM 自制一款针对 Kaleidoscope 编程语言的编译器,在这个过程中,展示了自制编程语言或编译器所涉及的一些相关概念和知识,从而产生一个系统的认知。至此,本教程结束了!如果希望有更进一步探索,建议大家着手开始 LLVM,毕竟代码才是真理!

参考

  1. Conclusion and other useful LLVM tidbits
  2. getelementptr
  3. The Often Misunderstood GEP Instruction
  4. clever way to use the getelementptr instruction
欣赏此文?求鼓励,求支持!