本篇依托于 2023 年华为毕昇杯 CompilerBagel 组参赛作品和本院 lab 教程。
受比赛时间限制,性能优化做得比较少,只先考虑满足正确性。
仓库地址:CompilerBagel
课程网站:NJU 软件学院编译原理课程,涉及本院课程教程的地方不再赘述。另外,也可以在 b 站关注 ant-hengxin
,我们伟大的蚂蚁老师,并观看相关课程视频。
好用的编译网站:https://godbolt.org
语言:java(使用语言识别工具 antlr4)
目标翻译高级语言:sysy(简易删减版的 c)
中间代码:LLVM
汇编语言:risc-v
注:语言要求和测试用例均可在华为毕昇杯的官网上找到,感兴趣的话,也可以来参加这项蛮有趣且在我心中含金量很高的比赛。
# antlr
首先,将一个高级语言翻译成汇编语言,先要分析它的词法和语法,就和学习英语需要理解单词和句型一样。
我们使用 antlr 进行词法和语法的分析,我们编写的.g4 文件可参考 /src/main/java/antlr
文件夹。
在词法和语法方面,在课程实验之外,我们实现增加了浮点数的内容。在编写完.g4 文件之后,可利用下载好的 antlr 包(工具)自动生成辅助类。
# 仿 LLVM API 构建
参考 /IRBuilder
/Instruction
比赛中,是不允许调用 LLVM 的 API 的(显然,这是一个编译系统设计赛)。
因此,我们选择手搓了一个简陋版 LLVM API 的系统。
如何存储基本块、指令的信息?我们构建了一个 Module-FunctionBlock-BaseBlock-Instruction-Operand/Operator 的自上而下的系统存储,以及针对每个指令,我们输出对应的 LLVM 代码 String(在 emit
方法中)
如何设计 API?我们直接对标了 lab 中使用过的 API,可见下面的部分 API 文档,介绍了部分常用的 API 功能,如生成函数、添加指令、声明变量、模块跳转等。
输出 LLVM IR 到文件
PrintModuleToFile(module, "test.ll"); |
创建模块
// 创建 module | |
IRModule module = IRModuleCreateWithName("module"); | |
// 初始化 IRBuilder,后续将使用这个 builder 去生成 LLVM IR | |
IRBuilder builder = IRCreateBuilder(); | |
// 可以通过下面的语句为 LLVM 的 int 型和 float 型重命名方便以后使用 | |
Type int32Type = IRInt32Type(); | |
Type floatType = IRFloatType(); |
创建全局变量 / 局部变量
// TODO: | |
// 局部变量 | |
// 为变量分配内存地址 | |
ValueRef IRBuildAlloca(builder, type , "_tmp"); | |
// 将 valueRef 存入 pointer 指向的内存中 | |
ValueRef IRBuildStore(builder, valueRef, pointer); | |
// 从内存中将值取出 | |
ValueRef value = IRBuildLoad(builder, /*pointer: ValueRef*/pointer, /*varName:String*/"value"); | |
// 全局变量 | |
// 申明全局变量 | |
ValueRef IRAddGlobal(module , type , "globalVarName"); | |
// 初始化全局变量 | |
void IRSetInitializer(module , valueRef , valueRef); |
生成函数
● 先生成返回值类型 (Type)
● 多个参数时需先生成函数的参数类型,再生成函数类型
● 用生成的函数类型去生成函数
// 生成返回值类型 | |
Type returnType = int32Type; | |
// 生成函数参数类型 | |
List<Type> params = new ArrayList<>(); | |
params.add(int32Type); | |
params.add(floatType); | |
// 生成函数类型 | |
Type funcType = new FunctionType(params, returnType); | |
// 生成函数,即向之前创建的 module 中添加函数 | |
FunctionBlock function = IRAddFunction(module, "main", funcType); |
创建基本块并添加指令
// 通过如下语句在函数中加入基本块,一个函数可以加入多个基本块 | |
BaseBlock block1 = IRAppendBasicBlock(function, "mainEntry"); | |
// 选择要在哪个基本块后追加指令 | |
IRPositionBuilderAtEnd(builder, block1); | |
// TODO:Add, Sub, Mul, (F/S)Div, Br, ... | |
ValueRef IRBuildAdd(builder, lhsValRef, rhsValRef, name); | |
// 决定跳转到哪个块 | |
IRBuildBr(builder, block1); | |
// 条件跳转指令,选择跳转到哪个块 | |
IRBuildCondBr(builder, | |
/*condition:ValueRef*/ condition, | |
/*ifTrue:BaseBlock*/ ifTrue, | |
/*ifFalse:BaseBlock*/ ifFalse); | |
// 生成比较指令 | |
ValueRef condition = IRBuildICmp(builder, /* 这是个 int 型常量,表示比较的方式 */IRIntEQ, n, zero, "condition = n == 0"); | |
/* 上面参数中的常量包含如下取值 | |
IRIntEQ, | |
IRIntNE, | |
IRIntUGT, | |
IRIntUGE, | |
IRIntULT, | |
IRIntULE, | |
IRIntSGT, | |
IRIntSGE, | |
IRIntSLT, | |
IRIntSLE, | |
*/ | |
// 函数返回指令 | |
LLVMBuildRet(builder, /*result:ValueRef*/result); |
# visitor 的改写
参考 IRGenVisitor.java
这里采用 visitor 遍历语法树的方式生成类 LLVM 中间代码。
课程实验中,我们逐步实现了返回常数的主函数、局部变量定义、加减乘除、函数定义和调用、全局变量定义、条件表达式、控制流(无条件跳转、条件跳转、if、while、break、continue)、一维数组。
相较于课程实验,我们增加了浮点数、类型转换、多维数组的访问和初始化等内容。
# 写在最后
虽然编译原理课程并不完整,比如没有教更多后端和性能优化的内容,但是没有前端积累的 lab 经验,我们就没有信心走完剩下的全部,在此感谢蚂蚁和 fy 老师的悉心教导,也希望你软 byyl 课越来越好~
下一篇来聊聊如何手搓后端。