编译器设计与实践

发表于 本文字数： 4.9k 阅读时长 ≈ 18 分钟

作为程序员，谁能拒绝徒手撸一个编译器呢？ 😄

前言

近段时间一直在做《从0开始的编译器实现》，也算是趟了一遍坑。
遂撰文记录一下，希望能给有想法接触这方面的人提供一点帮助。

Q: 有人曾问我，做这种东西有什么意义，直接去学 llvm，搞搞 flex bison yacc 它不香吗？

A: 我想了很多，不知如何回答，也许仅仅是有趣🤔？

总览

教学用编译器往往经过精心的简化，从而将其中一些复杂隐藏起来，
而一个可用的编译器则需要考虑很多的因素，复杂度也会指数上升。

本文将结合一些小型c语言编译器来聊这个话题，
参考了诸如 8cc 9cc chibicc picoc ucc 等。

架构设计

通常来说，编译器会明确的分为前端、优化器、后端三个部分。

image-20221010232651279

就实践经验来看，这三大部分实际上相当耦合。如果一开始就考虑了这种分层的设计，则后续编码过程中必将产生大量冗余和性能上的考量。
除非是有很大的精力，否则不推荐在自研编译器中使用分层的编码方式，这部分的取舍会相当困难。

一个源文件到目标程序的大致流程如下：

  1. 初始化编译器上下文环境
  2. 读取源文件
  3. 通过词法分析器提取词素
  4. 通过语法分析器辨别语法上的正确性，构造语法树
  5. 通过语义分析器辨别语法树语义合理性，提炼符号信息(偏移或对齐等)
  6. 通过语法树构造 IR(SSA) 及 CFG（常量折叠，值编号，强度消弱，代数简化和重结合等）
  7. 基于 IR CFG 的优化（窥孔优化，代码消除，跳转优化等）
  8. 目标代码生成
  9. 目标程序生成
  10. 释放编译器上下文

这里面又实际上隐含了几大必要的系统，内存分配系统，符号系统，类型系统，日志系统。

内存分配系统

一个有益的内存分配系统当然是能自行管理生命周期并防止内存无限膨胀。
这在编译器设计中是极其困难的，
除非在设计初期就能充分知道各个结构体的实现细节，既每一个结构体在何时消费掉。
由于结构体内部的信息本身错综复杂，若简单的采用实时释放策略，
会不可避免的产生大量的拷贝。

举例说明：
在获取到某个 token 后，通常只有部分信息(常量信息，位置信息等)对语法树的构造提供帮助，
如果是一个实时释放的内存系统，通过拷贝这部分有效信息可以减小内存开销。

而如若将宏这类预处理信息作为词法的一部分，则还需要记录对应的宏所对应的 token 流。
另外，在一些复杂的语言中，也有前看多个 token 的需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Foo {
	int x, y;
	Foo(Self) {
		Self = new(sizeof(Foo));
		Self->x = 0;
		return Self;
	}
	struct Bar {
		int x,y;
		Bar(Self) {
			// .....
		}
	};
};

int bar() {
	Foo.Bar *p = Foo.Bar.Bar();
}

将上述情况简记为 S.S 与 S.S.F，在这类场景中，为了获知 S.S 是否会成为 S.S.F 需要不断的前看。
最终它们会分别走向声明和函数调用流程。
当然，上述问题也能通过改善语法来解决，问题也会简化成空间与时间的取舍。

回到内存池的话题，如果仅使用freelist这类池来处理，
会不可避免的遇到预分配大小与空间浪费的问题。
所以采取一种混合式的池将会是自研编译器时的首要目标。
既要满足 动态向量 动态字符串 等数据结构，又要满足一些常驻信息。

在实践中，我使用了一种类 Stack-based Allocators 分配策略实现一级分配器，
而后在其上构建出freelist的二级分配器。
当然，这并非最佳策略，只是实践上的妥协。

符号系统

通常来说，符号系统是为每个标识符附加一定的属性信息，
包括有类型信息，符号自身的作用域信息，不可写或静态等。

当某个符号是成员或参数时，则还需要知道该符号对应的成员或参数的信息，
包括了位域或偏移等。

ucc 实现中，在转换阶段，符号还将作为 IR 的一部分存在，
tmp(SSA 的临时名) 和 const 都会成为符号的一种。

函数名，记录名(结构体，联合体)，类型别名，是否都存在于同一个符号表取决于语言本身的设计。
例如 c 语言中，记录名是独立的符号名，而 类型别名 与 变量名 位于同一符号表中。

一个典型的符号结构设计如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct _symbol {
Token id; // 符号名
Type ty; // 类型

int ref; // 被引用次数
int is_const;  // 是否是常量
int is_static; // 是否是静态
int is_type;   // 是否是类型
int is_def;    // 是否被定义

Scope in_scope; // 所在作用域

union {
int va_off; // 全局偏移或栈偏移
int pc_off; // 函数的指令偏移
};

union {
Enum e;
Field f;
Param p;
};
};

类型系统

类型系统想要尽可能的包含 2^n 长度的数据。

通常会有如下基础类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 空类型
void

// 通用类型
any

// 整数类型
i8 i16 i32 i64 isz u8 u16 u32 u64 usz

// 实数类型
f32 f64

// 指针类型
ptr

// 数组类型
[]

// 记录类型
struct union

// 枚举类型
enum

// 函数类型
fn

// 标签类型
label

其中每种类型都有一个大小，代表其占用的字节数，fn void 通常为1，这是为了便于做指针的数学运算。

默认类型，在现有语言中通常会被设计为 i32，一个32位长度的有符号类型。
对于弱类型系统来说，比较的典型的 lua 则会将所有数据置于一个 double 中。

c语言的类型系统背负了历史包袱，其本身就比较复杂，
主要体现在 unsigned、long 关键字及函数、数组等方面，
对于语法分析来说，它们并不友好。

就函数来说，若不涉及指针相关问题，
使用诸如 rust 或 golang流的 fn 关键字会更加优雅。

作为c语言灵魂的指针，如果使用了 fn 关键字，则会引入其它方面的不便利。

在c语言中，指针数组，函数指针，函数指针数组…，解析起来相对复杂。

1
2
3
4
5
6
7
8

T id;
T (*(*id));
T (*id)[];
T id(T, T);
T (*id)(T, T);
T (*id[])(T, T);
....

而函数的声明和定义则更进一步。

1
2
3
4
5
T id(T, T);
T id(T id, T id);
T id(T id, T id) {
	// ...
}

你必须在完整解析整个声明部分之后才能确定主 id 到底是什么类型。

以上仅是冰山一角，接下来，还会面对另一个严肃的问题，类型兼容与类型转换。

很多情况下，编译器都需要判断出两个类型是否兼容，或者是否合理。

对于c语言这种不纯粹的强类型语言来说，隐式类型转换会发生的更加频繁。
这是一个让人又爱又恨的机制，它很容易让人犯错，但也很方便，
没有人希望顶着一堆类型转换写完代码，除非你压根不知道自己在写什么。

1
2
3
2 + 1.0f;
2 + (int*)0;
...

在进行表达式语义分析时，编译器作者不得不一遍又一遍的比较左右子树的类型，为其添加对应的转换过程。
同时这个转换过程还会受到一些限制，比如 +- 的两边不能都是指针，但其中一边可以是指针，
位运算则要求必须是整数，逻辑运算则要求两边都是可计算的类型等等。

除此之外，类型系统还有另一个复杂点，函数名，数组名，标签名在表达式中会退化为一种特别的指针类型。
例如对函数名取值、取地址操作得到的依旧函数本身的偏移值，即源函数指针。
而对数组名取值会取到一个元素。标签名则不允许取值操作，同样也不应参与运算。
对于gcc 这种 label as value 的机制则需要更多的处理。

日志系统

日志系统从表面上看，只是一个用于打印输出的模块，但实际的内容会比一眼看上去的多。

首先一个好的编译器日志系统不仅要能辅助编译器实现，即报出编译器自身的异常信息和调试信息，同时也应用于输出编译过程中的警告错误等。

一个典型的编译错误日志如下：

1
2
3
4
int a b
------^

[main.c:1] error: expect ';' but got 'b'

对于编译自身日志，可以和普通的打印一致，立即输出到屏幕，而对于编译日志则需要更多的工作。
一方面，需要打印错误的代码位置，方便语言使用者定位问题。
另一方面，还需要考虑到错误恢复机制带来的影响，即不是所有的 err 日志都能立即退出。
如果编译器本身被嵌入了复杂的系统环境中，则不一定支持立即退出这种一劳永逸的办法，而是应该在统一的出口处报错。

词法分析器

纯手写词法分析器并不困难，值得注意的只有以下几点：

  1. 常量字面量类型处理
  2. 转义字符
  3. 保留字识别
  4. ch 前看支持
  5. token 前看支持

  • 常量字面量 存在有前后缀问题，需要注意。且对于??.??.?? 或 0x??.?? 也需要进一步处理。

  • 转义字符 需要获取转义值。

  • 保留字 则和标识符的处理逻辑共用，通常是获取标识符后，判断该标识符是否是保留字。

  • ch 前看支持 在解析诸如 ++ += \n …。

  • token 前看支持：
    c语言语法中强制类型转换是较为特别的存在，
    (T) 或 (id) ，
    对比上述两者，前者为强制类型转换，
    后者则是普通的表达式主语。
    故为了识别出具体是哪种，需要前看支持。
    在支持 S.S.F 的编译器中，这一问题会变得更为复杂，例如 c++ 的静态成员函数等。

编译器设计初期就应为上述问题提供一个合理的方案，包含但不局限于此。

语法分析器

自研编译器中，可以把语法分析和语义分析放到一个趟中处理。

语法分析器只表明语法上是否合规，基本是一套固定的逻辑。
通常会采用递归下降的语法分析器，也有像 c4 那种特别定制的分析器。

这一部分可以直接对照语法实现，在各类编译器书籍中出现较多。

对于c语言来说，最复杂的部分是 ExternalDeclaration，其中牵扯声明定义，导出静态，常量…需要尤其注意。

另外在关于 Ast_Node 结构的选型上，不同编译器采用了不同的形式。
例如 ucc 中会为不同的语句等设计独立的 node 结构，将所有的二元``一元规整到一起设计一个通用结构。
在 chibicc 中，则全部使用一个通用结构，其内部可以用联合体优化。

二者只能说各有千秋，前者的问题在于需要更多的强制类型转换才能将所有的节点串到一起，
后者的问题则是编写过程中很容易搞混。

如果语法分析和语义分析器是独立的，则在处理初始化列表时会增加一定难度。

如果二者是融合的，则以常量表达式及常量折叠入手编写会更加容易。
当然，融合实现时，代码也会更加复杂，

语义分析器

自研编译器中，若采用独立的语义分析器，则语法分析部分不考虑语义问题。

语义分析阶段，除去检查符号重定义或类型声明及语句的合法性外，还应检查类型是否兼容等问题。

该阶段要为每一个表达式的节点确定类型，同时还需要确定其是否是左值，是否可写，是否为常量等等。

符号表的建立也会发生在该阶段，
需要特别注意的是，在部分情况下(函数声明时的参数检查，record类型的成员检查)，符号只应检查是否在当前作用域发生重定义。

变量的偏移值可以在其定义时获取，没有初始化定义的变量都可以被简化成一个偏移值，即可消除掉对应的节点 。

初始化列表是否匹配也发生在该阶段，需要处理各种可能的情景。

1
2
int a[][2] = {{1,2}, 2, 3, 4, {5,6}};
int b = {{0}};

如果涉及 goto，按照 clang 的结论是会重复执行初始化赋值。

1
2
3
4
__foo:
int a = 0;
a=1;
goto __foo;

对于位域问题和匿名 record 内嵌问题，对齐问题，也都需要一一处理。

例如位域是否应该采取紧凑型，又或者是否应该支持 int:31 这类场景，还有一些不能对位域取地址限制的检查。

大部分常量折叠也会发生在这一阶段。

例如 int a[1+1] ，1+1 需要被折叠以确定 [] 中是一个大于等于零的整数。
同时常量指针也应参与折叠过程 0+(void*)0。

IR 生成

SSA IR 是一种比起语法树更简洁的表现形式，在其基础上优化会更容易。
同时生成过程中也可以完成一些前期优化工作，收集必要信息，构造控制流图等。

常量折叠

在逻辑与算法生成短路现象时，会将 && 的左右拆开，生成条件跳转，这会在原来的节点上填充新的算术节点。
对于会填充新算术节点的情况就需要再次进行常量折叠。

强度消弱

1
2
3
4
t = i * 7
->
t = i << 3
t = t - i

代数简化和重结合

1
2
3
4
5
6
7
8
9
10
a*1 = a
a/1 = a
a+0 = a
a-0 = a
-(-a) = a
i + (-a) = i-a
*(&p) = p
(&q)->s = q.s
....

值编号

值编号是判断两个计算是否等价并删除其中之一的一种办法。
为 op src dst 计算一个hash，判断该计算是否已经生成变量 t，
判断 t 是否位于当前基本块。

1
2
3
4
5
6
7
8
9
10
11
int b,x;
//
int a = b + 1;
int c = b + 1 + x;

IR:
t0 = b + 1
a = b
t1 = t0 + x  ; 这里就发生了简化，不再生成 b+1 的计算
c = t1

当 src dst 发生改变时，其对应的值编号将不能再被使用。

1
2
3
4
5
6
7
8
9
b = b + 1;
int c = b + 1 + x

IR:
t0 = b + 1
b = t0
t1 = b + 1    ; 不能简化
t2 = t1 + 1
c = t2

限于篇幅，本文只举出几个简单的例子，后面有机会再摊开说明。

优化器

窥孔优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 移除无用的 MOV
CALL t0 foo (...)
MOV  a, t0

-->
CALL a foo (...)

// 移除无用的 MOV
ADD t0 <- b 1
MOV b  <- t0
-->
ADD b <- b 1

// 优化指令
ADD b <- b 1
->
INC b

窥孔优化即根据几条相邻的指令内容简化指令，除了基于 IR 的优化外，还可以在代码生成阶段，根据目标平台指令，进一步优化。

变量消除

移除未引用的临时变量

跳转消除

1
2
3
4
5
6
7
jmp lab0

lab0:
jmp lab1

-->
jmp lab1

合并基本块

移除没有指令的基本块或将跳转消除后的基本块合并。

死码消除

遍历控制流图，仅保留可达的基本块。

代码生成

寄存器分配

将无限的虚拟寄存器映射到有限的真实寄存器的过程。
一种常用的方案是图着色分配方法，由 构造、简化、溢出、选择 四个主要阶段构成。
在 《高级编译器设计与实现》《现代编译原理：c语言描述》等书中有细致的描述。

后面有时间再单独结合代码聊一下这个。

指令调度

略，这个我还没搞明白，自研编译器鲜有实现到这里的。
大概意思是调度重排指令，使其能更好利用目标处理器的流水线。

虚拟机

基于栈还是寄存器

对于虚拟机本身来说二者区别实际上不大。
对于编译器来说，更容易生成高质量的寄存器虚拟机指令。

栈式虚拟机在栈上产生的值需要额外的弹出操作，
虽然也可以优化，但我了解不多。

类型表示

虚拟机在计算时，仍旧需要关注类型及类型转换。
有符号与无符号，实数与整数等运算都有涉及。

虚拟机交互

虚拟机应提供中止或打断的介入能力，以用于监视其执行过程。
同时也应该能有效的调用外部函数，拥有类似 dyncall libffi 的功能。
当虚拟机内部函数被作为回调函数传送到外部时，应使用某种识别机制以包装该函数。
多线程情况下的资源协调与同步问题。

解析交互模式

开始确实有引入交互模式的想法，但是后来发现错误回滚方面有着巨大的代价，同时不能很好的融入编译模式。
picoc 在这方面提供了很好的参考，虽然它也未能很好的解决错误回滚问题，也许需要一个更好的内存分配系统和一个更好的内存快照机制才能解决。

综上，实现的价值太低，代价又太大，遂放弃。

总结

本文结合我数月的实践经验，简单聊了一下自研编译器时会遇到各种问题。
文中很多地方没有使用规范的术语，而且只是从实践的角度进行片面的描述。
实践并不代表符合编译器设计的各种规范。

从 8cc 到 9cc 再到 chibicc，可以看到作者的一路征程。
同样的 ucc 是我认为写的比较完善的小型c编译器之一了，
其中也存在着很多的 bug。
一个完善的c编译器，只能说非常难。
可以想象 c++ 编译器得复杂到何种程度。

文中还有很多很多没有写到的地方，比如类型推导之类。
回过头再看，其实有很多更好的实践方案。很多地方都是时间上的妥协。

碎语

这几个月，前后推翻重写了6，7次，才写出一个相对可用的框架。
目前也才实现到了IR 生成一小部分。

总之，钱烧完了，得去找工作了😄。
之后也会持续更新本文，为实现一个真正可用的编译器而努力💪。

参考