编写快速编译器

# 编写快速编译器 - Marc Kerbiquet 来源：https://tibleiz.net/blog/2024-02-04-writing-a-fast-compiler.html 2024-02-04 我将介绍我为自己的编程语言编写快速编译器时所使用的各种技巧。所谓快速编译，指的是在单核CPU上每秒至少编译50万行代码（不包括空行和注释）。 ## 这重要吗？ 你可能会争论说编译时间并不重要。毕竟，一旦发布，谁会在意程序构建花了几个小时；作为用户，我们只希望它能工作且运行得快。这就像抱怨上一部皮克斯电影最终渲染花了几天时间一样。 然而，它会严重影响开发周期并让开发者感到不满。现在已经是2024年，我看到对Rust最常见的抱怨仍然是它的编译时间。 编译速度也会影响编译器的设计：当我的最大程序不到10万行源代码，而我每秒能编译50万行源代码时，我实际上无需担心单独编译，因为完整构建耗时不到200毫秒。这很好，因为单独编译在处理泛型时可能会很棘手。 ## 为快速编译而设计语言 如果你正在为现有语言（例如C++）编写编译器，你在这方面无能为力，你不得不处理LL(k)语法、预处理器和糟糕的模块系统。相反，如果你在为自己的编程语言编写编译器，谨慎的设计选择会有很大帮助。 我总是使用上下文无关文法，它可以通过简单的递归下降解析器轻松解析。如果语法对计算机来说容易解析，那么对人类来说也会容易解析。 简单的语法也会让独立工具（静态分析器、格式化工具、重构工具、语法高亮等）的开发变得更容易。 ## 通用规则 ### 最小化代码和内存访问 执行的代码更少，内存访问更少，通常意味着执行更快。虽然现代架构使得这个原则并非绝对正确，但这仍然是一个值得遵循的好规则。 我尽可能避免复制数据。许多语言使用零终止字符串。我更倾向于使用（*起始指针*，*大小*）或（*起始指针*，*结束指针*）的组合：例如，这允许直接引用输入缓冲区中的任何子字符串，而无需进行复制。 ### 减少内存使用 我使用的内存越少，就越有可能放入缓存。 - 仔细排列结构体中的变量可以显著减小这些结构体的大小，尤其是在64位系统上，因为对齐限制。 - 将多个标志组合到一个整数中可以节省内存，同时通过使用掩码一次执行多个测试。C语言的位域在这里很有用。 - 为枚举使用字节或位域。 ### 优化常见路径 编译器中的大量工作是检查错误，但一个程序通常没有错误或只有很少错误。因此，代码必须针对错误是特殊情况这一事实进行优化。 - 如果一个错误需要满足两个条件，我会先评估最快的那个条件，这样第二个条件就永远不会被评估。 - 我只在检测到实际错误时才计算那些仅用于错误报告的内容。 ### 内存管理：使用内存区域 内存区域是一块连续的内存，其中的部分可以被分配但不能被释放（整个区域必须一起释放）。分配只需推进指针，当区域满时最终创建一个新区域。这使得分配极其快速。释放也极其快速，因为区域的所有对象一次性被释放。 这种内存管理方式非常适合编译器：一个编译单元可以使用一个区域。实际上，我使用3个区域： - 一个用于存储抽象语法树（AST）， - 一个用于存储程序对象， - 一个用于代码生成，这样我可以在代码生成期间丢弃AST。 然而，在编译函数时，会创建大量临时对象，主要是每个词法作用域的名称字典。为了处理这个问题，我创建了区域池：不是创建和销毁区域，而是从池中取一个，用完后放回池中。 可调整大小的数组和开放寻址哈希表不适合内存区域，因为它们需要大量的释放和重新分配。 为了存储元素列表，在可能的情况下，我先计算元素数量，然后分配一个固定大小的数组；在不可能的情况下，我只使用链表。 对于大量用于名称的哈希表，我使用分离链接法而不是开放寻址法。它消除了数组的重新分配，但需要仔细选择哈希表的大小：全局命名空间将比函数内部作用域需要更大的哈希表。 ## 词法分析器：标识符作为数字 CPU不是为处理字符串而设计的，它们是为处理固定大小的整数而设计的。 - 比较两个字符串需要额外访问两个内存区域。 - 对字符串进行哈希处理很慢。 编译过程的一个重要部分是找到哪个实体与标识符关联。如果标识符存储为字符串，那会很慢。 除了在出错时向用户展示或将其存储在对象文件的调试符号表中之外，编译器不需要知道标识符的内容。它只需要测试标识符之间的相等性，因此可以在内部为每个不同的标识符分配一个整数。 由于词法分析器已经需要对关键字进行字典查找，因此在词法分析期间将标识符转换为唯一整数的额外开销非常小。 以下源代码： `` func main(args) if args.size < 2 `` 将产生以下词法单元流： 1. 类型=关键字，值=Keyword.func 2. 类型=标识符，值=1 3. 类型=左括号 4. 类型=标识符，值=2 5. 类型=换行 6. 类型=关键字，值=Keyword.if 7. 类型=标识符，值=2 8. 类型=点 9. 类型=标识符，值=3 10. ... 其中： - 1对应`main`， - 2对应`args`， - 3对应`size`。 ## 优化语法分析 我为编译器使用简单的经典架构： `` 词法分析 ---> 语法分析 ---> 构建 ---> 代码生成 `` 其中： - 词法分析器（*lexer*）读取源代码并生成词法单元（*tokens*）。 - 语法分析器（*parser*）读取词法单元并生成抽象语法树（AST）。 - 构建器读取AST并生成程序的表示。 - 代码生成器读取程序并生成机器码或为LLVM生成中间代码。 通过精心设计的语法，词法分析器只是一个包含处理输入字符的巨大*switch*语句的循环，而语法分析器是一个手写的递归下降解析器，结合了用于中缀表达式的运算符文法。 递归下降解析器由这样的函数组成： `` e = parseExpression i = parseInstruction b = parseBlock id = parseIdentifier ... `` 处理错误的自然方式是在出现语法错误时返回一个特殊值。例如，返回一个空值，但这迫使每个调用者检查返回值。 `` e = parseExpression if e == nil return nil end `` 技巧是报告错误并返回一个虚拟表达式。例如，返回一个 '0' 表达式。*语法错误*函数会显示第一个错误，并忽略后续的错误，因为它们可能与输入完全无关。 这样不仅通过消除许多测试使代码更快，而且更简单：它没有被每行的测试所混乱，它具有异常的好处却没有其缺点（隐藏的退出点、栈展开的成本）。 这个技巧有一个代价：我在第一个语法错误处就停止了（与构建步骤不同，后者我尝试报告尽可能多的错误）。 ## 只编译需要的内容 导入库时，你最终会得到大量未使用的常量、结构体和函数。 分析需要的内容是一个好主意。 语法分析必须读取并解析整个输入以创建AST。 `` class Label: Widget attr caption: String attr color: Color def init(caption: String) ... // ... 数百行代码 ... end `` 但对于构建步骤来说，它只是： 类的内容及其父类可以完全忽略，直到需要时。编译器只需要将*Label*与一个尚未定义的实体关联起来，以便在需要时可以找到它，并确保没有其他实体以相同的名称定义。 这意味着编译器在代码被使用之前不会验证它。在某些情况下这可能会很烦人，例如，当你编写库并希望确保所有内容都能编译时。命令行选项可以强制编译所有内容。 此外，语言的设计也可以在这里提供帮助。通过不将所有内容放在全局命名空间中，你可以大大减少需要定义的声明数量。例如，GTK+是一个带有C API的库，但在我的语言中，我可以将许多函数作为各自Widget类中的方法暴露出来： 原始C API `` typedef struct _GtkLabel GtkLabel; GtkWidget* gtk_label_new (const gchar *str); void gtk_label_set_text (GtkLabel *label, const gchar *str); const gchar* gtk_label_get_text (GtkLabel *label); ... `` 在Copper中 `` class GtkLabel: GtkMisc import func "gtk_label_new" new(String): Self import def "gtk_label_set_text" set_text(String) import def "gtk_label_get_text" get_text: String ... end `` 如果`GtkLabel`未被使用，所有嵌套实体甚至不会被声明。 对于只使用了其中少数元素的大型库来说，这可以节省大量时间。 ## 代码生成 除了LLVM和C后端之外，我还开发了自己的x64代码生成器。 LLVM很棒；它非常易于使用，生成高度优化的代码并支持许多平台。但它很慢，我通过开发自己的x64后端观察到30倍的加速。 我的LLVM后端有2000行直接的代码，而我自己的x64后端有超过10,000行复杂的代码，甚至还不支持浮点数。开发自己的x64生成器付出了巨大努力，但这是值得的。也许应该有人开发一个非SSA的LLVM替代方案，以允许实现快速编译器。 我的代码生成器主要由以下部分组成： 1. 伪代码生成器 2. 重复函数移除器 3. 寄存器分配器 4. 两遍汇编器 ### 伪代码生成器 生成一种中间伪代码，这使得某些优化变得更容易。它可以直接汇编成机器码，无需转换成汇编代码传递给汇编器。 它很像带变量的x64汇编。在寄存器分配之后，变量将被替换为寄存器或内存访问。这种伪代码不像LLVM的IR那样通用，它是为x64优化的：例如使用了索引内存访问。 ### 重复函数移除器 这部分是必要的，因为我的语言中的泛型会产生许多具有不同数据类型但生成相同代码的函数。一方面，这个重复查找器在性能上代价很大，因为在具有潜在递归的图中查找重复项可能很棘手；另一方面，它消除了很多需要汇编的函数。 ### 寄存器分配器 我使用线性扫描算法（PDF）(http://web.cs.ucla.edu/%7Epalsberg/course/cs132/linearscan.pdf)进行寄存器分配。原始论文将其描述为用于JIT编译器，但在我看来，它也完美适合那些想要生成相当快速代码的快速编译器。 ### 两遍汇编器 通过两遍汇编，起初看起来更慢，但在第一遍我不写任何内容：我不需要使用可调整大小的动态增长缓冲区，我只需要计算字节以计算偏移量。在第二遍，我知道确切大小，因此可以预分配正确大小的缓冲区，并且无需检查限制即可写入。代价是*write*函数是虚函数。没有真正的基准测试，我无法判断两遍汇编是否比一遍汇编更快，但我发现两遍汇编并不差。 ## 未来工作 在100毫秒内编译我的项目已经足够好了，所以我目前不需要更多的优化。总之，上面描述的所有技巧都只是基本技术和常识，仍有很大的改进和实验空间： - 使用索引代替指针（64位指针太浪费内存）。 - 代码生成使用单遍。 - 利用多核。 - 抽象语法树有太多指针，许多间接引用可以消除。 ## 结论 如果你计划编写编译器或想让现有的编译器更快，我希望它能有所帮助。