[中文] Compiler Principles Lab Notes

Lv 0#

首先安装并运行 Docker ↗ .

拉取镜像:

docker pull maxxing/compiler-dev

bash

使用镜像创建容器:

docker run -it --name compiler -v <compiler_lab_path>:/root/compiler maxxing/compiler-dev bash

bash

其中参数的含义:

-it 表示以交互模式运行容器.
--name compiler 表示将容器重命名为 compiler.
-v <compiler_lab_path>:/root/compiler 表示将宿主机的编译 Lab 项目文件夹挂载到容器中.
maxxing/compiler-dev 表示使用 maxxing 提供的 compiler-dev 镜像.
bash 表示以 bash 为启动命令.

每次需要进入容器时, 先启动容器, 再进入:

docker start compiler
docker exec -it compiler bash

bash

查看所有容器:

docker ps -a

bash

停止所有容器:

docker stop $(docker ps -aq)

bash

删除所有容器:

docker rm $(docker ps -aq)

bash

Lv 1#

Lab 的第一个 checkpoint 要求大家完成编译器的基础逻辑结构搭建, 包括:

词法分析器的逻辑
语法分析器的逻辑
简单的中间代码 Koopa 生成器

我使用的是 CMake 作为构建系统, 采用了基于 CMake 的 SysY 编译器项目模板 ↗ 的结构

可以先把实验文档 ↗中 Lv 1 中给出的代码复制下来作为 codebase .

Lexer#

我们只需要在 src/sysy.l 中写一段代码说明如何定义 Token 类型, 如何把读到的字符串转化为整数或者浮点数, 然后就可以使用 flex 读入 src/sysy.l 来生成词法分析器, 所以实际上不用自己写一个词法分析器.

示例:

"int"           { return INT; }
"return"        { return RETURN; }
{Identifier}    { yylval.str_val = new string(yytext); return IDENT; }
{Decimal}       { yylval.int_val = strtol(yytext, nullptr, 0); return INT_CONST; }

asm

其中 INT, RETURN, IDENT 等返回值, 其实是 Bison 生成的固定枚举类型值, 就是一个整数.

所以这段代码代表的含义为:

"int" 和 "return" 是正则表达式, 这就是告诉当匹配到这些字符串时, 返回给语法分析器 INT 和 RETURN 类型, 告诉语法分析器这是一个保留字
{Identifier} 是上面定义好的正则表达式, 当这个表达式匹配到某个字符串时, 将这个字符串赋值给语法分析器定义的 yylval.str_val 变量, 然后返回给语法分析器 IDENT 类型, 告诉语法分析器这是一个标识符, 比如函数名, 语法分析器知道现在读取到了一个标识符, 就从 yylval.str_val 中取出这个字符串
{Decimal} 是上面定义好的正则表达式, 当这个表达式匹配到某个字符串时, 将这个字符串赋值给语法分析器定义的 yylval.int_val 变量, 然后返回给语法分析器 INT_CONST 类型, 告诉语法分析器这是一个整数常量, 语法分析器知道现在读取到了一个整数常量, 就从 yylval.int_val 中取出这个整数

Parser#

我们只需要在 src/sysy.y 中写一段代码说明如何定义语法规则, 比如一个函数是如何由函数类型, 函数名, 变量声明列表和函数体组成的, 然后就可以使用 bison 读入 src/sysy.y 来生成语法分析器.

规约示例:

FuncDef
  : FuncType IDENT '(' ')' Block {
    auto ast = new FuncDefAST();
    ast->func_type = unique_ptr<BaseAST>($1);
    ast->ident = *unique_ptr<string>($2);
    ast->block = unique_ptr<BaseAST>($5);
    $$ = ast;
  }

asm

其中 FuncDefAST 等类是 include/ast.hpp 中由你定义好的, 其中包括了每个语法规则包含的语法单元, 比如 FuncDef 语法规则包含 FuncType, IDENT, Block 等语法单元, 语法分析器现在使用这些类来构造抽象语法树.
$1 是代表子语法单元的变量, 比如 FuncDef 语法规则的第一个子语法单元是 FuncType, 那么 $1 就代表 FuncType, 语法分析器递归地从 FuncType 继续规约, 注意这里的变量标号是从 1 开始的.
$$ = ast; 是告诉语法分析器, FuncDef 语法规则规约的结果是一个 FuncDefAST 类, 语法分析器现在知道 FuncDef 语法规则规约的结果 FuncDefAST 类中都是什么数据了.

`Koopa IR` Generation#

当语法分析器规约出抽象语法树后, 我们就可以遍历抽象语法树, 遇到叶子节点就 print , 遍历结束就生成了中间代码 Koopa.

在 main.cpp 中定义编译器本身的 main 函数，读入需要编译的源文件，调用词法分析器和语法分析器，得到放好数据的抽象语法树，然后调用语法树类中定义好的 print 函数生成中间代码 Koopa。

我的具体结构安排是:

在 main.cpp 中定义编译器本身的 main 函数, 读入需要编译的源文件, 调用词法分析器和语法分析器, 得到放好数据的抽象语法树, 然后调用语法树类中定义好的 print 函数生成中间代码 Koopa.
在 include/ast.hpp 中定义抽象语法树的节点类, 每个节点类中定义一个 print 函数, 用于生成中间代码 Koopa 或 Debug 信息.
在 ast.cpp 中定义抽象语法树的各个节点类, 并实现 print 函数.

Beyond Codebase#

在 handout 给出的 codebase 中, 词法分析器和语法分析器大部分已经写好了, 但是还有一些需要修改的地方:

在 src/sysy.y 中, 需要加入 include/ast.hpp 的引用, 否则语法分析器会找不到你定义的抽象语法树的节点类, 就不能把数据写到你定义的抽象语法树中.
在 include/ast.hpp 中, 需要定义示例代码中没有给出的抽象语法树的节点类, 并定义 print 函数.
在 ast.cpp 中, 需要实现示例代码中没有实现的抽象语法树的各个节点类, 并实现 print 函数.

好的, 现在已经完成了编译器的基础逻辑结构搭建!

Compile and Test#

以下均默认你已经进入容器, 并且当前目录为编译 Lab 的一级目录.

使用 cmake 生成 Makefile 文件:

cmake -DCMAKE_BUILD_TYPE=Debug -B build

bash

使用 cmake 编译:

cmake --build build

bash

运行编译器, 把 debug/hello.c 编译为 debug/hello.koopa:

./build/compiler -koopa debug/hello.c -o debug/hello.koopa

bash

本地自动评测:

autotest -koopa -s lv1 /root/compiler

bash

Lv 2#

首先回顾一下编译器的三层结构:

在 Lv 1 中已经完成了前端和中端, 现在来完成后端.

虽说是完成后端, 但是实际上助教团队已经帮助实现好了能够处理 Koopa IR 的库, 我们只需要调用他们提供的库 (即调用 koopa.h 中定义的函数) 就可以完成后端的大部分实现了, 我们只需要自己实现 RISC-V 汇编代码的输出就可以了.

具体如何调用, 参阅实验文档 ↗ 把代码复制下来即可.

最后的后端代码入口应该类似:

#include "include/backend.hpp"

int backend(const char *koopa_str)
{
    // 解析字符串 str, 得到 Koopa IR 程序
    koopa_program_t program;
    koopa_error_code_t ret = koopa_parse_from_string(koopa_str, &program);
    assert(ret == KOOPA_EC_SUCCESS); // 确保解析时没有出错
    // 创建一个 raw program builder, 用来构建 raw program
    koopa_raw_program_builder_t builder = koopa_new_raw_program_builder();
    // 将 Koopa IR 程序转换为 raw program
    koopa_raw_program_t raw = koopa_build_raw_program(builder, program);
    // 释放 Koopa IR 程序占用的内存
    koopa_delete_program(program);

    // 处理 raw program
    visit(raw);

    // 处理完成, 释放 raw program builder 占用的内存
    // 注意, raw program 中所有的指针指向的内存均为 raw program builder 的内存
    // 所以不要在 raw program 处理完毕之前释放 builder
    koopa_delete_raw_program_builder(builder);

    return 0;
}

void visit(const koopa_raw_slice_t &slice)
{
  // ...
}

void visit(const koopa_raw_program_t &program)
{
  // ...
}

// ...

cpp

Traverse the Abstract Syntax Tree#

调用库之后我们就得到了以抽象语法树形式表示的 RISC-V 汇编代码, 现在需要 DFS 遍历这棵抽象语法树, 将其转换为字符串并输出, 我们选择使用函数递归的方式来遍历这棵抽象语法树, 具体如何遍历可以参考实验文档, 这里不再赘述, 但是有一些 high level 的 idea 可以帮助你理解这颗树上的各种助教定义的 type.

这颗语法树的节点大致是 program, function, basic_block, value, 这些节点很多都包含同类型的东西, 比如一个程序有很多的函数, 一个函数有很多的基本块, 一个基本块有很多指令, 那么比如 program 这个节点的这一堆函数就会存在一个 koopa_raw_slice_t 类型中, 所以对于一个 program 节点中的所有函数, 只需要对包含这些函数的这一个 koopa_raw_slice_t 调用一次 visit 函数即可, 如下所示, visit 函数会把这一堆东西逐个帮你访问.

void visit(const koopa_raw_slice_t &slice)
{
    for (size_t i = 0; i < slice.len; ++i)
    {
        auto ptr = slice.buffer[i];
        // 根据 slice 的 kind 决定将 ptr 视作何种元素
        switch (slice.kind)
        {
        case KOOPA_RSIK_FUNCTION:
            // 访问函数
            visit(reinterpret_cast<koopa_raw_function_t>(ptr));
            break;
        case KOOPA_RSIK_BASIC_BLOCK:
            // 访问基本块
            visit(reinterpret_cast<koopa_raw_basic_block_t>(ptr));
            break;
        case KOOPA_RSIK_VALUE:
            // 访问指令
            visit(reinterpret_cast<koopa_raw_value_t>(ptr));
            break;
        default:
            // 我们暂时不会遇到其他内容, 于是不对其做任何处理
            assert(false);
        }
    }
}

cpp

访问 koopa_raw_value_t 类型的函数大致如下所示, koopa_raw_value_t 类型是一个指针, 这个指针可以指向 RISC-V 汇编代码的一个值 (一条指令的结果可以代表这个指令, 所以一条指令也算一个值)

如果碰上代表一个指令, 就可能重复调用 visit koopa_raw_value_t 两次, 因为指令中包含值, 比如调用 visit koopa_raw_value_t 时发现这是一个返回指令, 就调用 visit koopa_raw_return_t , 返回值就会需要再调用一次 visit koopa_raw_value_t.

void visit(const koopa_raw_value_t &value)
{
    // 根据指令类型判断后续需要如何访问
    const auto &kind = value->kind;
    switch (kind.tag)
    {
    case KOOPA_RVT_RETURN:
        // 访问 return 指令
        visit(kind.data.ret);
        break;
    case KOOPA_RVT_INTEGER:
        // 访问 integer 指令
        visit(kind.data.integer, value);
        break;
    // ...
    default:
        // 其他类型暂时遇不到
        throw std::runtime_error("visit: invalid instruction");
    }
}

cpp

Link Middleend and Backend#

与此同时, 你还需要将你在 Lv 1 中输出的 Koopa IR 输入给后端, 在这里我推荐使用 std::stringstream 类型来存储 Koopa IR, 然后交给后端即可, 实现代码可以类似:

std::ostringstream koopa_ir; // 用于存储 Koopa IR 的 stringstream
// ...
ast->print(&koopa_ir);
  // ...
  // inside print(): 你的中端代码将 Koopa IR 输出到 koopa_ir 中
  // ...
freopen(output, "w", stdout); // 将 stdout 重定向到 output 文件, output 是你的输出文件路径
backend(koopa_ir.str().c_str()); // 将 stringstream 转换为 C style string 后交给后端
  // ...
  // inside backend(): 后端代码将 RISC-V 汇编代码输出到 stdout 中
  // ...
fclose(stdout);

cpp

这样写的优点包括：

实现简洁明了
无需进行硬盘交互 (把 Koopa IR 输出到文件系统再从硬盘读取, 再交给后端), 这样实现之后 Koopa IR 的数据保存在内存中, 后端直接从内存中读取即可

Compile and Test#

运行编译器, 把 debug/hello.c 编译为 debug/hello.i:

./build/compiler -riscv debug/hello.c -o debug/hello.i

bash

本地自动评测:

autotest -riscv -s lv1 /root/compiler

bash

Lv 3#

本章将在上一章的基础上, 实现一个能够处理表达式 (一元/二元) 的编译器.

需要完成对抽象语法树和 RISC-V 汇编代码输出这两部分的修改.

你的编译器将可以处理如下的 SysY 程序:

int main() 
{
  return 1 + 2 * -3;
}

cpp

需要完成对抽象语法树和 RISC-V 汇编代码输出这两部分的修改.

Update the Abstract Syntax Tree#

Lexer#

修改 src/sysy.l 文件, 添加对运算符的识别, 比如 ! 和 - 运算符.

/* 运算符 */
ExclusiveUnaryOp       "!"
MulOp         [\*/%]
AddOp         [\+\-]
RelOp         ("<"|">"|"<="|">=")
EqOp          ("=="|"!=")
AndOp         "&&"
OrOp          "||"

asm

这里我的逻辑是对每一种运算都定义一个正则表达式, 用来表达这个运算会使用的所有字符, 这样就不用在语法分析器中对每一个运算符都写一个规约规则了.

但是有一个问题是单元运算符和二元加减运算符有两个符号是重叠的, 所以我选择使用 ExclusiveUnaryOp 来表示只有单元运算符使用的符号, AddOp 就代表着单元运算和二元加减运算共同使用的符号了.

另外还要加入识别 token 之后如何返回给语法分析器, 类似 Identifier 和 Decimal 那样, 使用 yylval 来返回字符串给语法分析器.

{ExclusiveUnaryOp}      { yylval.str_val = new string(yytext); return EXCLUSIVE_UNARY_OP; }

asm

Parser#

修改 src/sysy.y 文件和 include/ast.hpp 文件, 添加对新的语法规则的规约.

举例说明:

UnaryExp
  : PrimaryExp {
    auto ast = new UnaryExpAST();
    ast->primary_exp = unique_ptr<BaseAST>($1);
    $$ = ast;
  }
  | EXCLUSIVE_UNARY_OP UnaryExp {
    auto ast = new UnaryExpAST();
    ast->op = *unique_ptr<string>($1);
    ast->unary_exp = unique_ptr<BaseAST>($2);
    $$ = ast;
  }
  | ADD_OP UnaryExp {
    auto ast = new UnaryExpAST();
    ast->op = *unique_ptr<string>($1);
    ast->unary_exp = unique_ptr<BaseAST>($2);
    $$ = ast;
  }
  ;

asm

对应如下的抽象语法树类:

/**
 * @brief 一元表达式抽象语法树类。
 */
class UnaryExpAST : public BaseAST
{
public:
    std::optional<std::unique_ptr<BaseAST>> primary_exp; // 可选的基本表达式
    std::optional<std::string> op;                       // 可选的操作符 ("+", "-", "!")
    std::optional<std::unique_ptr<BaseAST>> unary_exp;   // 可选的一元表达式

    /**
     * @brief 打印抽象语法树。
     * @param[in] output_stream 输出流。
     * @return 打印操作的结果
     */
    Result print(std::stringstream &output_stream) const override; // 打印抽象语法树, 稍后解释这个返回类型的用处
};

cpp

其中有两个实现细节:

std::optional
1. 是 C++17 引入的类型, 你可能需要修改 VSCode 的编译器版本, 否则无法正常高亮显示.
2. 它用于表示一个可能存在也可能不存在的值, 如果值存在, 则可以使用 value() 方法获取该值, 如果值不存在, 则可以使用 has_value() 方法判断是否存在, 或者使用 operator* 获取该值, 用来判断在多个规约规则中具体选了那个规约规则.
3. 比如下面的规约规则有两个选择, 分别是 PrimaryExp 和 UnaryOp UnaryExp, 如果选择了 PrimaryExp 那么 primary_exp 就会存在, op 和 unary_exp 就不存在, 反之亦然.
print 函数返回一个 Result 类型的变量, 稍后解释这个返回类型的用处.

以上的代码代表着如下的规约规则:

UnaryExp    ::= PrimaryExp | UnaryOp UnaryExp;
UnaryOp     ::= "+" | "-" | "!";

asm

其中使用了我们在对词法分析器作修改的时候定义的新 token 种类 EXCLUSIVE_UNARY_OP 和 ADD_OP.

当然别忘了要在 src/sysy.y 文件中定义新的终结符和非终结符的类型.

// lexer 返回的所有 token 种类的声明, 终结符的类型为 str_val 和 int_val
%token INT RETURN
%token <str_val> IDENT
%token <int_val> INT_CONST
%token <str_val> EXCLUSIVE_UNARY_OP MUL_OP ADD_OP REL_OP EQ_OP AND_OP OR_OP // Operators

// 非终结符的类型定义
%type <ast_val> FuncDef FuncType Block Stmt Exp UnaryExp PrimaryExp MulExp AddExp LOrExp LAndExp RelExp EqExp
%type <int_val> Number

asm

`Koopa IR` Generation#

修改 ast.cpp 文件, 添加对新的语法规则的 print 函数.

在实现之前我们先来思考一个例子:

int main() 
{
  return 6;
}

cpp

这是之前的编译器可以处理的代码, 我们在调用 RetAST 的 print 函数时, 先输出 ret 然后调用 NumberExpAST 的 print 函数, 输出 6, 最后回到 RetAST 的 print 函数输出 \n, 就可以得到如下的 Koopa IR 代码:

fun @main(): i32 {
%entry:
  ret 6
}

asm

现在我们考虑这个例子:

int main() 
{
  return -6;
}

cpp

如果还是按照之前的逻辑, 先输出 ret 然后调用 ExpAST 的 print 函数, 就会出现问题, 因为我们还需要一个 sub 指令才能计算出 -6, 但是此时 Koopa IR 已经输出到文件中了, 我们无法在 ret 指令后面继续输出 sub 指令了.

这是我们期望得到的 Koopa IR 代码:

fun @main(): i32 {
%entry:
  %0 = sub 0, 6
  ret %0
}

asm

所以我们在进入任何一个 print 函数时, 不能先入为主地输出任何 Koopa IR 指令, 需要先调用这个抽象语法树的所有子变量的 print 函数, 等到它们把类似上文的 sub 指令输出完成之后再输出当前的 Koopa IR 指令.

但是如果子变量的所有 print 函数都没有返回任何信息, 那么我们怎么知道这些子变量把计算结果储存到哪里了呢?

比如 RetAST 的 print 函数, 当它调用完成 ExpAST 的 print 函数之后, 它怎么知道 ExpAST 的计算结果是储存在 %0 这个寄存器中了而不是 %1 或者其他寄存器中呢?

我们不希望使用全局变量解决任何问题, 这样非常 dirty, 所以我们需要每一个 print 函数返回一个 Result 类型的变量, 告诉父变量这个子变量的计算结果储存在哪里, 以便父变量决定如何输出当前的 Koopa IR 指令.

/**
 * @brief 用于存储计算结果的类，可以是符号或立即数。
 * @note 如果当前函数会产生一个计算结果, 那么这个计算结果会存储在返回的 `Result` 类型的变量中
 * @note 比如 `PrimaryExpAST` 的 `print` 函数, 当它是从数字规约而来时, 它的 `Result` 变量会被初始化为立即数, 返回 `Result(Result::Type::IMM, *number)` 这样一个变量
 * @note 如果当前函数不会产生计算结果, 那么返回的 `Result` 变量会被初始化为立即数 0
 * @date 2024-11-27
 */
class Result
{
public:
    /**
     * @brief 当前计算值，存储在 `%current_value_symbol_index` 符号中。
     * @date 2024-11-27
     */
    static int current_symbol_index;

    enum class Type
    {
        IMM, // 立即数
        REG  // 寄存器
    };
    Type type; // 结果的类型
    int val;   // 结果的值

    // 默认构造函数，初始化为立即数 0, 没有用到它的地方
    Result() : type(Type::IMM), val(0) {}

    // 带有指定类型的构造函数, 主要用来初始化寄存器
    Result(Type type) : type(type), val(0)
    {
        if (type == Type::REG)
        {
            val = ++current_symbol_index;
        }
    }

    // 带有指定类型和值的构造函数, 主要用来初始化立即数
    Result(Type type, int val) : type(type), val(val)
    {
        if (type == Type::REG)
        {
            val = ++current_symbol_index;
        }
    }

    // 重载 <<
    friend std::ostream &operator<<(std::ostream &os, const Result &result)
    {
        os << (result.type == Result::Type::REG ? "%" : "") << result.val;
        return os;
    }
};

cpp

Result 类中有一个静态变量 current_symbol_index, 这个变量用于给每一个计算结果分配一个唯一的寄存器. 当 Result 类被初始化为立即数时, 这个变量不会被用到, 而当 Result 类被初始化为寄存器时, 这个变量会被用来给计算结果分配一个唯一的寄存器, 然后这个 current_symbol_index 的值会加一.

同时为了方便输出寄存器和立即数, 我们重载了 << 操作符.

Result UnaryExpAST::print(std::stringstream &output_stream) const
{
    if (primary_exp && !op && !unary_exp)
    {
        return (*primary_exp)->print(output_stream);
    }
    else if (!primary_exp && op && unary_exp)
    {
        Result unary_result = (*unary_exp)->print(output_stream);
        Result result = Result(Result::Type::REG);
        if (*op == "+")
        {
            output_stream << "\t" << result << " = add 0, " << unary_result << "\n";
        }
        else if (*op == "-")
        {
            output_stream << "\t" << result << " = sub 0, " << unary_result << "\n";
        }
        else if (*op == "!")
        {
            output_stream << "\t" << result << " = eq 0, " << unary_result << "\n";
        }
        else
        {
            throw std::runtime_error("UnaryExpAST::print: invalid unary operator");
        }
        return result;
    }
    else
    {
        throw std::runtime_error("UnaryExpAST::print: invalid unary expression");
    }
}

cpp

这样看起来就很清晰了.

当 UnaryExpAST 的 print 函数被调用时, 如果它选择了 UnaryExp ::= PrimaryExp 这条规约规则, 那么它就会调用 PrimaryExpAST 的 print 函数
此时 UnaryExpAST 并没有做任何计算, 所以直接返回 PrimaryExpAST 的计算结果即可.
如果它选择了 UnaryExp ::= UnaryOp UnaryExp 这条规约规则, 就需要根据 UnaryOp 的值输出相应的 Koopa IR 指令, 运算的结果需要使用一个新的寄存器来储存, 所以构造一个新的 Result(Result::Type::REG) 变量, 并返回这个变量.
最后如果出现任何例外情况, 直接抛出异常, 这样是很好的防御型编程操作实践.

Compile and Test#

运行编译器, 把 debug/hello.c 编译为 debug/hello.koopa:

./build/compiler -koopa debug/hello.c -o debug/hello.koopa

bash

本地自动评测:

autotest -koopa -s lv3 /root/compiler

bash

`RISC-V` Assembly Code Generation#

在这一部分你需要修改 include/backend.hpp 和 src/backend.cpp 文件, 完成新的语法规则的 print 函数来输出 RISC-V 汇编代码.

这部分的难点在于如何分配寄存器, 储存在内存中的 RISC-V 汇编代码是没有进行寄存器分配的.

比如一个加法运算, 你只知道左操作数和右操作数是两个表达式, 但是你并不知道这两个表达式的结果分别在哪个寄存器当中, 内存中的汇编代码也不提供具体的寄存器编号, 所以你需要在输出的同时为每一行运算都分配一个寄存器来保存运算的结果, 并且不能覆盖之前刚计算完还没用过的寄存器.

寄存器分配问题是一个 NPC 问题, 但是很好的一点是 Lv3 的测试样例中不会出现需要寄存器复用的情况, 所以我们可以使用贪心算法来解决这个问题.

首先仔细观察一个例子:

int main() 
{
  return 1 + 2 * -3;
}

cpp

可以得到如下 RISC-V 汇编代码:

	.text
	.globl main
main:
  li  t0, 2
  li  t1, 3
  mul t1, t0, t1
  li  t2, 1
  add t2, t1, t2
  mv a0, t2
  ret

asm

可以发现当前每一行汇编代码的计算结果都只会被使用一次, 如果把这个汇编代码修改为:

	.text
	.globl main
main:
  li  t0, 2
  li  t1, 3
  mul t0, t0, t1
  li  t1, 1
  add t0, t0, t1
  mv a0, t0
  ret

asm

不会有任何问题.

Register Manager#

为了方便管理寄存器, 我设计了一个 RegisterManager 类, 这个类可以设置一个寄存器为可以覆盖, 判断一个值是否占用了一个寄存器, 给一个值分配一个寄存器, 输出某个值对应的寄存器名称.

所有计算结果, 包括一个表达式, 一个立即数, 都是跟一个 koopa_raw_value_t 类型的指针一一对应的, 所以我们可以使用 koopa_raw_value_t 类型的指针来作为寄存器管理器中的键值, 这样就可以方便地找到一个值对应的寄存器名称.

/**
 * @brief 寄存器管理器, 可以设置一个寄存器为可以覆盖, 判断一个值是否占用了一个寄存器, 给一个值分配一个寄存器, 输出某个值对应的寄存器名称
 */
class RegisterManager
{
private:
    // 值到寄存器名称的映射
    std::unordered_map<koopa_raw_value_t, std::string> _value_to_reg_string;
    // 存储当前所有寄存器是否可能会再次被利用, 比如将立即数转移给 a0 寄存器, 我们现在就认为 a0 寄存器被占用了, 但是如果 a0 寄存器之后被调用了, 这个立即数被使用过了, 那么 a0 寄存器就会被标记为不被占用, 因为到目前为止我们认为每一个结果只被使用一次
    std::unordered_map<std::string, bool> _reg_is_used;
    /**
     * @brief 设置一个值对应哪个寄存器, 内部函数不被外部调用
     * @param[in] value 值
     * @param[in] reg_string 寄存器名称
     */
    void _set_value_to_reg_string(const koopa_raw_value_t &value, const std::string &reg_string);

public:
    /**
     * @brief 构造函数, 初始化所有寄存器为未占用
     */
    RegisterManager()
    {
        // 初始化所有寄存器为未占用
        for (int i = 0; i <= 6; ++i)
        {
            _reg_is_used["t" + std::to_string(i)] = false;
        }
        for (int i = 0; i <= 7; ++i)
        {
            _reg_is_used["a" + std::to_string(i)] = false;
        }
    }

    /**
     * @brief 设置一个值对应的寄存器为未占用, 当一个值被使用过之后, 我们将它占用的寄存器设置为未占用, 因为我们认为每一个结果只被使用一次
     * @param[in] value 值
     */
    void set_reg_free(const koopa_raw_value_t &value);

    /**
     * @brief 判断一个值是否已经分配了寄存器
     * @param[in] value 值
     * @return 是否已经分配了寄存器
     */
    bool exist(const koopa_raw_value_t &value);

    /**
     * @brief 给一个值分配一个寄存器, 自动选择一个未被占用的寄存器
     * @note x0 是一个特殊的寄存器, 它的值恒为 0, 且向它写入的任何数据都会被丢弃, t0 到 t6 寄存器, 以及 a0 到 a7 寄存器可以用来存放临时值
     * @param[in] value 值
     * @param[in] is_zero 如果是立即数, 那么是否是立即数 0
     */
    void allocate_reg(const koopa_raw_value_t &value, bool is_zero = false);

    /**
     * @brief 找出这个值占用哪个寄存器, 用于输出 RISC-V 汇编代码
     * @param[in] value 值
     * @return 寄存器名称
     */
    std::string value_to_reg_string(const koopa_raw_value_t &value);
};

cpp

`RISC-V` Assembly Code Output#

为了方便维护 RegisterManager 类, 我选择将 koopa_raw_value_t 类型的指针也传给 koopa_raw_integer_t 和 koopa_raw_binary_t 的 visit 函数, 这样在这两个函数中就可以调用 RegisterManager 类的方法来管理寄存器了.

// 访问 koopa_raw_value_t
void visit(const koopa_raw_value_t &value)
{
    const auto &kind = value->kind;
    switch (kind.tag)
    {
    case KOOPA_RVT_RETURN:
        visit(kind.data.ret);
        break;
    case KOOPA_RVT_INTEGER:
        visit(kind.data.integer, value);
        break;
    case KOOPA_RVT_BINARY:
        visit(kind.data.binary, value);
        break;
    default:
        throw std::runtime_error("visit: invalid instruction");
    }
}

// 访问 return 指令
void visit(const koopa_raw_return_t &ret)
{
    // 根据 ret 的 value 类型判断后续需要如何访问
    if (ret.value)
    {
        // 特判如果是立即数, 则直接赋值给 a0 寄存器, 跳过访问 value 的过程
        if (ret.value->kind.tag == KOOPA_RVT_INTEGER)
        {
            std::cout << "\tli a0, " << ret.value->kind.data.integer.value << std::endl;
        }
        // 否则, 访问这个值, 然后把这个值存储在的寄存器名称移动给 a0 寄存器, 注意不是 li
        else
        {
            bool is_allocated = register_manager.exist(ret.value);
            if (!is_allocated)
            {
                visit(ret.value);
            }
            std::cout << "\tmv a0, " << register_manager.value_to_reg_string(ret.value) << std::endl;
        }
    }
    // 如果 ret 的 value 为空, 则直接赋值 0 给 a0 寄存器, 然后返回
    else
    {
        std::cout << "\tli a0, 0" << std::endl;
    }
    std::cout << "\tret" << std::endl;
}

// 访问 integer
void visit(const koopa_raw_integer_t &integer, const koopa_raw_value_t &value)
{
    if (integer.value == 0)
    {
        register_manager.allocate_reg(value, true);
    }
    else
    {
        register_manager.allocate_reg(value);
        std::cout << "\tli " << register_manager.value_to_reg_string(value) << ", " << integer.value << std::endl;
    }
}

// 访问 binary 指令
void visit(const koopa_raw_binary_t &binary, const koopa_raw_value_t &value)
{
    // lhs 和 rhs 是否已经分配过寄存器, 如果没分配过, 则需要先访问 lhs 和 rhs, 访问过程中会分配寄存器, 注意 ricsv 不能直接操作立即数, 必须先加载到寄存器中!
    bool lhs_is_allocated = register_manager.exist(binary.lhs);
    if (!lhs_is_allocated)
    {
        visit(binary.lhs);
    }
    bool rhs_is_allocated = register_manager.exist(binary.rhs);
    if (!rhs_is_allocated)
    {
        visit(binary.rhs);
    }
    // 我们认为每个结果仅使用一次, 所以可以设置两个子结果的寄存器可以被覆盖了.
    // 比如将立即数转移给 a0 寄存器, 我们现在就认为 a0 寄存器被占用了, 但是如果 a0 寄存器之后被调用了, 这个立即数被使用过了, 那么 a0 寄存器就会被标记为不被占用, 因为到目前为止我们认为每一个结果只被使用一次
    register_manager.set_reg_free(binary.lhs);
    register_manager.set_reg_free(binary.rhs);
    register_manager.allocate_reg(value);

    // 获取当前结果, lhs 和 rhs 对应的寄存器名称
    std::string cur = register_manager.value_to_reg_string(value);
    std::string lhs = register_manager.value_to_reg_string(binary.lhs);
    std::string rhs = register_manager.value_to_reg_string(binary.rhs);

    // 根据二元运算符的类型进行处理
    switch (binary.op)
    {
    case KOOPA_RBO_EQ:
        std::cout << "\txor " << cur << ", " << lhs << ", " << rhs << std::endl;
        std::cout << "\tseqz " << cur << ", " << cur << std::endl;
        break;
    case KOOPA_RBO_NOT_EQ:
        std::cout << "\txor " << cur << ", " << lhs << ", " << rhs << std::endl;
        std::cout << "\tsnez " << cur << ", " << cur << std::endl;
        break;
    // ...
    default:
        throw std::runtime_error("visit: invalid binary operator");
    }
}

cpp

如果无法通过全部 Lv3 的测试样例, 可以检查如下几个问题:

把数据从寄存器移动到寄存器时, 使用的是 mv 指令, 而不是 li 指令.
访问 return 指令时, 在访问 ret.value 之前有没有检查它是否已经分配了寄存器, 否则可能造成同一个运算被输出多次.
还有一个测试样例, 可以检查你的寄存器是否会溢出:

int main() 
{
  return 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0 + 0 * 0;
}

cpp

Compile and Test#

运行编译器, 把 debug/hello.c 编译为 debug/hello.i:

./build/compiler -riscv debug/hello.c -o debug/hello.i

bash

本地自动评测:

autotest -riscv -s lv3 /root/compiler

bash

Related Links#

Lv 0#

Lv 1#

Lexer#

Parser#

Koopa IR Generation#

Beyond Codebase#

Compile and Test#

Lv 2#

Traverse the Abstract Syntax Tree#

Link Middleend and Backend#

Compile and Test#

Lv 3#

Update the Abstract Syntax Tree#

Lexer#

Parser#

Koopa IR Generation#

Compile and Test#

RISC-V Assembly Code Generation#

Register Manager#

RISC-V Assembly Code Output#

Compile and Test#

Lv 4#

`Koopa IR` Generation#

`Koopa IR` Generation#

`RISC-V` Assembly Code Generation#

`RISC-V` Assembly Code Output#