寒暑易节,始一反焉。—— 《愚公移山》
winter, summer ➡ remmus,retniw ➡ remniw
以往我在学习编译技术时,更多是阅读 LLVM 源码,停留在读上面,因此可能对编译原理理解不够深刻。
本项目的初衷是通过动手实践来加深理解,帮助我更好地学习编译技术(包括不限于静态分析、机器无关优化、代码生成、垃圾回收)。
目前,该项目实现了一个简单的编译器,该编译器将 remniw 语言(自己设计的一个玩具语言)源代码编译为 x64 汇编。
未来,预计会在该编译器上实现更多的内容:如垃圾回收算法、经典的机器无关优化算法等。
希望本项目对编译技术爱好者有所帮助。
因本人水平有限,代码中很多不足之处,欢迎各位以 Issue 和 Pull Request 的方式批评指正,感激不尽。
$ git clone git@github.com:Enna1/remniw.git
$ cd remniw
$ ./utils/bootstrap.sh
$ mkdir build
$ cmake ..
$ make
$ cat /path/to/remniw/test/more_args.rw
func f(arg1 int, arg2 int, arg3 int, arg4 int, arg5 int,
arg6 int, arg7 int, arg8 int, arg9 int, arg10 int) int {
return arg1 + arg2 + arg3 + arg4 + arg5 + arg6 + arg7 + arg8 + arg9 + arg10;
}
func main() int {
output f(1,2,3,4,5,6,7,8,9,10);
return 0;
}
# generate executable
$ /path/to/remniw/build/bin/remniw /path/to/remniw/test/more_args.rw -o more_args
# execute
$ ./more_args
55
remniw 编译器包含 5 个 phase:
- frontend 前端。输入为 remniw 的源代码,输出为 AST。remniw 使用 ANTLR4 来定义 remniw 的语法、生成 Lexer 和 Parser。
- semantic analysis 语义分析。不是本项目的重点,只在 AST 上做了非常简单的 type checking。
- ir code generation 生成 LLVM IR。输入为 AST,输出为 IR。remnniw 编译器的中间表示使用的是 LLVM IR 的一个子集,只使用 LLVM IR 的子集有一个好处,在实现程序的静态分析、优化时只需要考虑有限的 llvm instruction,这样方便我们实现算法,更专注于分析、优化算法本身,而不会陷于繁多的 llvm instruction。
- optimization 机器无关优化。输入为 LLVM IR,输出为优化后的 LLVM IR。
- asm code generation 生成汇编代码。输入为优化后的 LLVM IR,输出为 x64 汇编。
remniw 语言的语法设计脱胎于 Static Program Analysis 中的 TIP 语言,目前支持的变量类型包括整型、指针、数组。
下面给出一个使用 remniw 语言编写的计算斐波那契数列的程序源代码:
func apply(f func(int) int, a int) int {
return f(a);
}
func fib(n int) int {
var result int;
if( n>1 ){
result = fib(n-1)+fib(n-2);
} else {
result=1;
}
return result;
}
func main() int {
output apply(fib,5);
return 0;
}
remnniw 编译器的中间表示使用的是 LLVM IR 的一个子集,目前只使用了如下 instruction:
ret
Instructionbr
Instructionadd
Instructionsub
Instructionmul
Instructionsdiv
Instructionalloca
instructionload
Instructionstore
Instructionicmp
Instructioncall
Instructiongetelementptr
Instruction
只使用 LLVM IR 的子集有一个好处,在实现机器无关优化时只需要考虑有限的 llvm instruction,这样方便我们更专注于分析、优化算法本身,而不会陷于繁多的 llvm instruction。
本项目与其他一些基于 LLVM 实现的编译器相比,不同点在于:没有使用 LLVM 的提供的由 LLVM IR 生成汇编代码的接口,而是自己动手实现了从 LLVM IR(子集)生成 x64 汇编。
remniw 编译器 5 个 phase 的详细文档位于 docs 目录下,这些详细文档中记录了我在实现各个 phase 时的思路及参考资料: