本篇依托于 2023 年华为毕昇杯 CompilerBagel 组参赛作品和本院 lab 教程。

受比赛时间限制,性能优化做得比较少,只先考虑满足正确性。

仓库地址:CompilerBagel

课程网站:NJU 软件学院编译原理课程,涉及本院课程教程的地方不再赘述。另外,也可以在 b 站关注 ant-hengxin ,我们伟大的蚂蚁老师,并观看相关课程视频。

image-20230926010443166

好用的编译网站: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 课越来越好~

下一篇来聊聊如何手搓后端。