Vrabche-一种不是很完善的Sysy语言编译器

g** l** © 2023

版权所有

https://github.com/GammaMilk/Vrabche

简介

1. 大赛要求各参赛队综合运用各种知识（包括但不局限于编译技术、操作系统、计算机体系结构等），构思并实现一个综合性的编译系统，以展示面向特定目标平台的编译器构造与编译优化的能力。
2. 大赛鼓励各参赛队充分了解目标语言及目标硬件平台（CPU 指令集、Cache、各类并行加速能力等）特点，使编译出的目标码能够尽可能利用目标硬件平台能力以提高目标码的运行效率。
3. 为展示参赛队的设计水平，增加竞赛的对抗性，进入决赛的参赛队还需针对目标语言或目标平台的变化，现场调整编译系统。
4. 除技术方案特别要求、规定和禁止事项外，各参赛队可自行决定编译器体系结构、前端与后端设计、代码优化等细节。

初赛内容

开发支持特定语言、面向 ARM 硬件平台或 RISC-V 硬件平台的综合性编译系统。

1. 基于 C、C++、Java 或 Rust 语言开发，能够在 Ubuntu18.04（64 位）操作系统的 x86 评测服务器上编译。
2. ARM 硬件平台：能够将符合自定义程序设计语言 SysY2022 的测试程序编译为 ARM 汇编语言程序（32 位，ARMv7），并通过汇编链接后在 Raspberry Pi OS（Raspbian GNU/Linux 10）操作系统的树莓派（Raspberry 4B）设备上运行。
3. RISC-V 硬件平台：能够将符合自定义程序设计语言 SysY2022 的测试程序编译为 RISC-V 汇编语言程序（64 位，RISC-V），并通过汇编链接后在 64 位 Debian64 GNU/Linux bookworm/sid 操作系统的昉·星光2（VisionFive 2）设备上运行。

审题

这个比赛项目是构建一个C语言子集的编译器的实现。和编译原理课程（以下简称“课程”）的内容相似。为了在多条赛道上发挥不一样的作用，考虑到目前商业编译器的大部分实现架构，我选择了前后端分离的形式来构建整个编译系统。

分工

代码

（除去ANTLR自动生成）

g**负责前端、中间代码优化、RISCV后端（共15.6k），l**负责中间代码优化(0.5k)、ARM后端(3.8k)，z**负责前端while处理(共0.05k)，c**负责其他

其他

c**：初赛队长、带饭、联系老师

z**：决赛队长、联系酒店、联系老师、联系报销

架构

总体

我们使用C++17和ANTLR作为支撑，构建中间代码是LLVMIR（完全兼容LLVM的LLVMIR）的编译系统。分为语法词法分析+CST生成、IR生成、IR优化、LIR生成、寄存器分配、目标代码发射几个步骤。

前端

我们考虑到大赛使用的C++版本较新（C++17），同时C++兼容的工具链较多，所以我们选择采用C++作为编写语言来构建整个编译系统。对于前期在词法分析、语法分析自动化工具的考量中，我们发现，在Bison+Flex的结构中，虽然可以一步直接生成AST，但是这里我们需要在Bison中编写C++代码，不能得到完整的语言提示；而使用ANTLR进行词法语法分析时，可以得到一个CST对象，这比在Bison直接编写C++代码以生成AST要方便一些。所以前端我们采用了ANTLR4生成CST，然后进行单趟遍历生成中间代码的流程。

中间代码的选择

考虑到课程中使用的是LLVMIR作为中间代码进行前后端的连接，并且LLVMIR也是业内前后端分离编译器比较常用的IR，所以我选择使用LLVMIR作为中间代码的表示语言。

优化

这里在前期构建的过程中，预留了一个插槽，用来插入优化器。一个优化器可以分别对整个IR、函数级、基本块级进行不同程度的优化。

后端（RISC-V）

这里为了简单起见，依旧使用了单趟遍历来构建LIR的方式。从每一条指令一对一地翻译成一条或者一组LIR指令。由于这里RISC-V的指令集架构不支持RVV（向量），所以无法完成SIMD的优化过程。我在这个后端中不进行寄存器分配，转而在生成所有的LIR之后进行寄存器分配，这一步生成的LIR中只有少量用于传递参数的已分配的物理寄存器，和代表变量的大量物理寄存器。

LIR（RISC-V）

这一步进行寄存器分配。取决于中端是否做了Mem2Reg，这里寄存器分配我们预先完成了基本块级别的线性扫描算法分配。选择先在基本块内进行寄存器分配的原因有：

1. 正确性：没进行Mem2Reg之前，一切基本块中不会共用虚拟寄存器，一切变量都在内存中，而不在寄存器。所以，一切寄存器在基本块之间无冲突。
2. 便利性：无需进行数据流分析等操作，考虑到编程人员能力限制，简化编程人员的工作流程，体现人文关怀。同时，为了快速完赛需要，先将100%正确的代码提交之后在进行下一步重构也未尝不可。

目标平台优化

这一步在构建初期也预留了插槽，用来插入对于目标平台的优化。比如无用的寄存器移动等。

技术细节

总体

对于头疼的指针问题，我使用shared_ptr和unique_ptr来实现所有权划分、移动语义、自动释放等操作。

前端

.g4文件编写

.g4是ANTLR4的语法规则文件。我们根据Sysy语言的语法规则，编写了g4文件。此处不在赘述。

使用ANTLR构建词法语法分析器

安装好ANTLR之后，根据ANTLR4官方网站的demo，使用如下指令可以构建一个Visitor模型的遍历器（默认构建的是Listener模型的，但是在此编译系统设计方案中，我们没有采取Listener模型）。

antlr4 -Dlanguage=Cpp Sysy.g4 -visitor

通过以上代码，可以生成SysyLexer.h/.cpp, SysyVisitor.h/.cpp, SysyParser.h/.cpp等文件，这些源代码用于分析输入的文件，从而输出一个ParserTree。

实现各种Visitor方法

通过新建另一个类，来继承自动生成的SysyVisitor类，使用CLion自动代码生成来生成所有override的函数声明和函数实现。如下：

class IRVisitor : public SysyVisitor
{
public:
    std::any visitCompUnit(SysyParser::CompUnitContext* context) override;
    std::any visitCompUnitItem(SysyParser::CompUnitItemContext* context) override;
    std::any visitDecl(SysyParser::DeclContext* context) override;
    std::any visitConstDecl(SysyParser::ConstDeclContext* context) override;
	// ...
}

在每次的Visit之中，如果需要生成一条IR指令，则将其插入到“当前基本块”中，否则将内容返回到上一级。

以下是一个示例，用来分析“大于等于”

/// relExp:
///	| relExp Geq addExp	# geq;
/// \param context
/// \return
std::any IRVisitor::visitGeq(SysyParser::GeqContext* context)
{
    // 3<b<c is not allowed. so let's assume that there is only one < in the expression
    // that means, relExp is always a single addExp
    // 先访问两边的子表达式
    auto relExp   = context->relExp()->accept(this);
    auto [lt, ls] = getLastValue(relExp);
    tie(lt, ls)   = ZExtOrNot(lt, ls);// 处理bool->i32的流程（针对性处理!a<b）
    auto addExp   = context->addExp()->accept(this);
    auto [rt, rs] = getLastValue(addExp);
    // 检查两侧类型。如果不相同，则需要进行隐式的类型转换
    if (lt != rt) {
        g_builder->checkTypeAndCast(rt, lt, rs);
        rs = g_builder->getLastLabel();
    }
    // 对于浮点和整数分别进行比较语句的生成
    if (lt == VT_FLOAT) {
        // 生成IR指令
        auto fcmp = MU<FcmpSen>(g_builder->getNewLabel(), FCMPOp::UGE, ls, rs);
        // 插入到当前基本块
        g_builder->addSen(std::move(fcmp));
    } else if (lt == VT_INT) {
        auto icmp = MU<IcmpSen>(g_builder->getNewLabel(), ICMPOp::SGE, ls, rs);
        g_builder->addSen(std::move(icmp));
    } else {
        RUNTIME_ERROR("Unknown type in lt");
    }
	// 全局开关，用来表示当前（对于之后执行的指令，就是上一条）指令是bool类型。
    g_sw->isBool = true;
    return 0;
}

数组初始化处理

这部分我在编写的过程中倍感压力。因为数组的初始化过程中过于多种多样。比如int a[2][3][4]={{1,2,3,4,5,6},{{1},{2}}}这种。需要将他们填入正确的位置。数组位置指针我使用了vector<int>，我实现了void ArrayPosPlusN，用来将当前数组目的地指针加N；struct CArrGenerator用来生成一个常数多维数组，std::shared_ptr<CArr> Utils::buildAnCArrFromInitList用来从CST生成的初始化表中生成一个多维数组的中间表示；ZeroInitCArr用来使用zeroinitializer填充全〇部分；string VArr::toString()用来将数组的内存表示输出到字符串。详见以下原始代码链接。

https://github.com/GammaMilk/Vrabche/blob/d938d623b37a7a63bc32522e4fff9c6914b445db/IRGen/IRUtils.cpp

重复的变量名称处理

对于如下的示例：

{
    int a=1;
    {
        int a=3;
    }
}

表面上是a被赋值两次，而实际上这是两个不同的变量。所以我们要处理好这种关系。我采取的方式是：对于所有的变量，都有一个作用域。我称之为Layer。

class IRLayerController
{
public:
    IRLayerController();
    void dive();
    void ascend();
    void push(const std::shared_ptr<IRVal>& val);
    void push(const string& name, const std::shared_ptr<IRVal>& val);
    void pushGlobal(const std::shared_ptr<IRVal>& val);
    std::shared_ptr<IRVal> query(const std::shared_ptr<IRVal>& val, bool recursively = true);
    std::shared_ptr<IRVal> query(const std::string& symbol_name, bool recursively = true);
}

如上述代码所展示，进行dive表示当前指令在一个新的block中，而ascend代表退出了当前的block。在实现上，我采用了一个栈来保存当前层级的变量信息。如果当前层没有这个变量，就再深入一层进行查找。所以当有重复命名的变量时，就会首先找到最后放入的变量，所以两次查询a得到的值是不同的。

分支处理

首先实现如此的一个类，用于控制在遍历CST时各个分支的层级关系。进入while/if语句时push，退出之前pop。

using SPBB = shared_ptr<IRBasicBlock>;
/// This class intends to deal with BRANCH and ITERATION
class IRCondAndIterController
{
public:
    IRCondAndIterController();
    void pushIf(SPBB trueBB_, SPBB ifFalseBB_, SPBB ifAfterBB_, size_t curLayerNum_);
    void pushWhile(SPBB trueBB_, SPBB whileCondBB_, SPBB whileBreakBB_, size_t curLayerNum_);
    void pushOr(SPBB falseBB_);
    void pushAnd(SPBB trueBB_);
    void pop();
    SPBB queryWhileBreakBB();
    SPBB queryWhileCondBB();

    SPBB queryTrueBB();
    SPBB queryFalseBB();

protected:
    vector<shared_ptr<IRBBLayer>> _layers;
};

以if举例，当进入ifelse语句中，首先创建trueBB/falseBB和afterBB.然后分别进入这些block（将curBB指针指向新创建的BasicBlock），退出时将指针指向afterBB即可。

日志工具

我自己写的一个简单的Logger，实现了LOGD, LOGE, LOGW, RUNTIME_ERROR, IR_ASSERT宏，用来输出日志到控制台和保证调试时数据一致性。输出使用std::cerr实现，RUNTIME_ERROR和IR_ASSERT使用throw std::runtime_error实现.

优化

工程通过依赖注入的方式实现优化器的排列和运行。优化的终点是所有优化器不再进行任何改动。

IROptimizerBase作为所有优化器的基类，传入IRAST，有抽象函数bool run(),返回优化器是否做出了改动。返回值用来判断是否到达优化终点。

此处实现了如下的优化：

• 加法合并(g**)
• 常数折叠、常数传播(g**)
• 公共子表达式删除(l**/g**)
• 死代码删除(g**/l**)
• GetElementPtr拆分(l**/g**)
• 全局变量常量化(g**)
• 指令合并(l**)
• 内联(g**)
• 冗余Load/Store删除(g**)

这里介绍几个比较值得讲的优化

1. 公共子表达式删除(g**)

   作用域：基本块

   这是一个针对IR的算数优化。假设我们重复计算了%3 = %1+%2和%4 = %1+%2，那么我们就可以用之前计算的%3来替换掉后面所有的%4。所以如何知道%4和%3相等，成为该优化的关键。

   我的实现是：自定义一个哈希函数，将操作符（加减乘除）、操作数1、操作数2合在一起哈希化，保证相同的(+,op1,op2)三元组得到的哈希值相同。细节上，对操作符进行编码，对应到数字，设为hash1；操作数的哈希对应到存储操作数结构的内存地址（如果操作数是立即数，则它的哈希是数本身）。总的哈希即uint64_t hash = hash1<<60 ^ hash2<<32 ^ hash3.

   （参考我的源代码：https://github.com/GammaMilk/Vrabche/blob/d938d623b37a7a63bc32522e4fff9c6914b445db/MiddleOpt/IROptCSE.h#L28）

   为了实现哈希表，我们需要将这个三元组抽象成一个数据结构。如下所示：

   struct IMathTriple {
       IMathInst::IMathOp _op;
       SP<MiddleIRVal>    _lhs;
       SP<MiddleIRVal>    _rhs;
   }
   

   在标准库的unordered_map构造中，我们还需要一个表示两个Triple相等的函数。这个函数比较简单，对IMathTriple实现括号重载即可，这里不再赘述。

2. 常量传播(g**)

   作用域：函数

   数据流分析方式：类似于到达定值分析，使用常量传播-半格(UNDEF-C-NAC)。

   算法：

   所有alloca定义的单变量（非数组）标记为UNDEF
   函数 对一个函数执行():
   	do
   		changed=false
   		队列={所有基本块}
   		访问过={}
   		while 队列非空：
               块=队列.pop()
               访问过.insert(块)
               mapAllocaToVal = mapEachBBValStatus[bb]
               ExecuteCurBB(mapAllocaToVal, 块)
               for 后继 in 块.后继：
                   更改=false
                   更改 |= merge(mapEachBBValStatus[s], mapAllocaToVal)
                   if 更改：队列.添加(后继)
   	while changed;
   	
   	for 块 in 函数：
   		mapReplaceReady = {UNDEF...}
   		合并所有前驱节点到mapReplaceReady
   		替换所有能替换的
   		ConstFold(块)
   

   经过一些次数的迭代，当块中的值都稳定之后，即可进行替换，将load替换为常数。

3. 死代码删除1（g**）

   死代码删除我主要通过树覆盖法，从“影响”出发。这里“影响”是指能够影响到整个程序状态机的语句，比如ret,store,call等。这里认为所有store都具有“影响”。而实际上没有影响的store会在RSE中被删除。

   首先，从“影响”出发，进行BFS，所有被BFS覆盖的语句都被标记为“有用”。为了简单起见，所有数组有关操作都被标记为“有用”。特别地，如果一个alloca被认为“有用”，那么所有有关该alloca的语句也将被标记为“有用”。通过所有的BFS之后，就只剩下“没用”的语句。删除即可。

后端

RISC-V(g**)

单趟遍历

我们采取单趟遍历每个基本块的方式，将LLVMIR转化为LowLevel-IR(以下简称LIR).在这一步我们不进行寄存器分配。

对于一般的指令，是可以进行一对一的翻译的。这里我们需要注意的是，对于一个函数而言，我们需要在生成LIR的过程中，为变量分配内存空间（实现alloca语句），这一步我们需要在栈上分配空间。对应到LIR中就是在-?(fp)的位置上划分出区域，供alloca和spill来使用。其中alloca分配的区域无需释放，而spill产生的区域需要释放。这里我手写了一个类似于C标准库的malloc函数，用来在一段线性的内存上分配空间。这个类叫做TaichiMap.

提供以下接口：

// 分配新的内存块，并返回变量的地址
int64_t allocate(const std::string& variableName, int64_t size);
// 释放内存块
void release(const std::string& variableName);
// 查询变量地址（-1为不合法地址）
int64_t query(const std::string& variableName);
// 获取内存大小
int64_t getSize() const;
int64_t getMaxSize() const;

接口极其简单，但是实现略微复杂。我将一系列偏移地址分为内存块，

struct MemoryBlock {
    int64_t address;
    int64_t size;
    bool    allocated;
    MemoryBlock(int64_t addr, int64_t sz);
};

挂载到内存链表上。每次分配的时候如果找到合适的块，则将这个块切出一部分以分配给调用者，否则新挂载一个块分配给调用者。在每次释放的时候会合并空闲的块。这里我仅进行了一个简单的实现，最坏时间复杂度是O(n)，因为我线性地遍历这个内存块链表。

对于分支指令，我使用的方法是每次循环读取两条指令，如果第一条是比较，第二条是分支，则将两条指令合并为比较跳转指令（ble等）。

寄存器分配

在项目初期，我们为了避免繁琐的数据流分析，我采用直接在基本块上进行寄存器分配的方式。优点是无需数据流分析，无需进行各种冲突检测，缺点也很明显：在两个基本块之间没用共用的寄存器，也就是说明每次取变量的时候都需要读内存。这就耗费了比较长的时间。我觉得这就是我们取得优胜奖而非三等奖的关键。

但是这里还是介绍一下我采用的算法：

首先进行逆序遍历以进行def-use分析，将每个虚拟、物理寄存器的分配点和释放点（对应LIR的标号）标记在一个轴上。

在顺序遍历之前，我们首先介绍我用来派遣物理服务器的工具，称为R5RegDispatcher 。这个工具传入各个虚拟和实体寄存器的生命周期，用于计算是否存在冲突的分配问题。同时记录所有虚拟寄存器对应的物理寄存器，以便在替换的过程中查找。这里用的spill规则是没有规则，也就是预留3个寄存器不分配，用于spill的resave和reload处理。spill的内存管理就是上面提到过的TaichiMap.

现在开始顺序遍历。

我们获取到一条LIR指令时：

• 第一次替换：用于替换use的虚拟寄存器（由于use可能在下一步会释放，所以先替换）；
• 释放；
• 分配：调用R5RegDispatcher ；
• 第二次替换：替换def。由于def可能在第三部刚刚分配到寄存器，所以要最后替换。

这里着重说明一下spill的操作。在释放和分配的过程中无需获取spill到的内存地址。这个内存地址在替换时用到即可。在第一次替换中，use被替换，在spill方面即reload处理。所以在第一次替换之前先访问stack将内存中的值取出，取出到保留的寄存器中，然后将use的寄存器替换为保留的寄存机即可。同理，在第二次替换中，在指令之后加入resave的指令即可。

有关spill的简化代码如下.其中R5Yang代表一个物理寄存器。

if (int64_t offset = dispatcher.queryStackOffset(name); offset != -1) {
    // 通过加载指令，将内存中的值加载到寄存器中。
    spillSaveCount += 1;
    auto reservedR2 = dispatcher.getReservedFReg(spillSaveCount++);
    auto tmpReg     = dispatcher.getReservedIReg(spillSaveCount);
    accessStackWithTmp(
        spillWriteBackFutureInst, FSW, reservedR2, offset, s0, tmpReg
    );
    r = make_shared<R5Yang>(reservedR2);
}

ARM(l**)

单趟遍历

我们也是采用的线性扫描的方式直接将llvmir语言转换为arm汇编（是的，第一次做没有经验，没有留下优化的余地，因此甚至没有为llvmir写一个结构体，读取信息时都是直接操作字符串，因此效果十分不好，寄存器也是直接赋的）。

特殊处理

因为我们的寄存器分配方式为线性扫描分配法，而经过提醒已知除了全局变量已经常数没有跨基本块的临时变量，所以将常数和全局变量提出放在的每个函数的最开头（至于为什么放在最开头，是因为为了防止寄存器冲突，我将r12分给了全局变量，在函数最开始时用r12将其存到内存中去，而有的函数即使优化了也过于冗长，就会导致之后在调用全局的标签时由于距离过远而显示跳转错误）。

寄存器分配

同上也是采用了基本块上线性扫描进行寄存器分配的方式。

唯一不同的是，将函数所需的以r0开始的一些寄存器先分配给相应的临时变量上，这就省去了来回存放的一些步骤。

总结

总之，这次的arm后端写的很是失败，基本就是一个纯粹的一对一翻译器，甚至没有留下优化的余地，这也是为什么我们小组最后选择了risc-v赛道。

最后，译研定珍(这种关于编译研究经历我一定会好好珍惜)，鉴定为要好好学习写优秀代码。

人文元素

Врабче由来

麻雀虽小，五脏俱全。

保加利亚语，麻雀。

图标

来自《降临》。外星生物heptapod语言。

思考

（待定）

批评与自我批评

（待定）

鸣谢

（不分先后）

• 杨**
• 所有队员

参考文献

（待定）

本栏目推荐文章
• 【C语言】
• 【C语言】形参和实参的一些注意点
• Go 语言为什么不支持并发读写 map？
• 【C语言】函数的递归调用
• Scala编程语言day1
• NUS CS1101S：SICP JavaScript 描述：四、元语言抽象
• 学了这么多编程语言，你学会了几种“Hello world”呢？
• 各种语言版本的“Hello, world”程序汇总
• 2024年·用50种语言对你说“Hello，World!”
• 用36种语言说“新年快乐”

编译器 Vrabche 语言 Sysy编译器vrabche语言sysy 编译语言 编译器 模块 原理 语言 编译语言language语言level 解释器 编译器 编程语言 语言 sysy 编译器centos7语言centos 混合型 编译语言 语言java 语言基础 编译器 语言 基础 vrabche