运行时空间管理与代码生成

参考文档

• 寄存器分配数据结构、接口说明文档在doc/RegAlloc.md 完成 任务1：寄存器分配 所必要的接口和数据结构说明。

• 汇编指令相关数据结构定义接口文档在doc/AsmValue.md。 在后端中，所有的位置（寄存器、立即数、栈地址等）使用本实验软件包提供的接口进行表示。

• 栈帧结构与ABI约定相关文档在doc/StackFrameAndABI.md。 在 任务3：栈空间分配 实验中你需要按照约定进行栈空间分配。

简介

LLVM IR虽然是一个整体而言靠近底层的中间表示，但是它仍有一些较为理想的假设和高层的语义，需要在代码生成阶段处理，包括

• 无限的虚拟寄存器
• Phi指令
• ...

无限寄存器的假设使得LLVM IR的代码不需要进行太多运行时的空间管理，比如栈的维护、临时寄存器的现场保存、汇编ABI接口的满足（如函数传参约定），所以在代码生成中需要添加这些部分的内容与相关信息的维护。 Phi指令虽然给代码优化过程提供了很多方便，但它的语义是非常高级的语义，它要求在代码执行的过程中感知代码执行路径，同时一个基本块开头的Phi指令并行执行，这基本没有硬件支持的基础，所以代码生成阶段要通过各种手段消除Phi指令。在本次实验中，Phi指令的消除方法是在代码生成阶段直接按照Phi指令的语义生成相关的数据移动代码。具体而言，对于中级IR（LLVM 兼容），每个基本块至多有两个后继，所以当执行到这个基本块的末尾，需要为它即将跳转到的基本块开头的Phi指令完成数据的移动，这部分代码在当前基本块末尾产生。对于有两个后继的分支跳转，可以使用ARM的条件执行指令产生代码，如下所示：

//code in LLVM IR
l0:
%3 = icmp ne i32 %1, i32 %2
br i1 %3, label %l1, label %l2

l1:
%4 = phi i32 [%1, %l0], [0, %l3]
...

l2:
%5 = phi i32 [%2, %l0], [1, %l3]
...


//code in asm, assume that %1->r1, %2->r2, ...
l0:
    cmp r1, r2
    movne r4, r1
    bne l1
    mov r5, r2
    b l2
...

实验内容

实验之前请阅读文档，了解本实验框架给出的数据结构接口。 本实验各个部分之间是相辅相成的，寄存器分配时候的策略（分配哪些寄存器，保留哪些寄存器）和栈空间的分配将直接影响后面实现的难易，同学们可以在这个过程中体会不同的设计选择之间的互相影响。

任务1：寄存器分配

在本部分，你需要补全一个线性扫描的寄存器分配算法。

任务2：Phi指令生成——数据移动

本实验框架提供的代码对于Phi指令的处理正如前面所述，需要你实现的是数据移动部分的代码。

任务3：栈空间分配

由于LLVM IR有无限的虚拟寄存器，所以并没有显式地处理栈相关的操作，只是使用alloca来进行空间的分配。然而，实际体系结构中寄存器的数目是有限的，所以需要把一些寄存器放不下的内容溢出到栈上（包括数组）。在本部分中，你将实现栈空间分配相关代码。

编译命令的flag说明

本实验中新增了-S命令行参数，完成上述3部分后使用-S参数将输出armv7ve架构的汇编。例如：

./compiler -S test.sy -o test.s

评测说明

在完成全部3关后，你可以在平台点击评测按钮进行评测。评测结束后会在项目根目录创建test.log，包含每个测例是否通过的信息。评测时使用交叉编译器arm-linux-gnueabihf-gcc以及qemu在x86平台上编译并执行compiler输出的arm汇编码。

若你想在本地使用交叉编译器并使用qemu模拟arm执行，可以按以下步骤（以ubuntu22.04为例）：

1. 安装交叉编译工具链和 QEMU

sudo apt update
sudo apt install gcc-arm-linux-gnueabihf binutils-arm-linux-gnueabihf qemu-user qemu-user-static

2. 交叉编译。 假设compiler输出的文件是test.s，并且当前在项目根目录：

arm-linux-gnueabihf-gcc test.s lib/lib.c -o test.out

3. 使用qemu模拟arm环境执行

qemu-arm -L /usr/arm-linux-gnueabihf ./test.out

其他

在本实验中你无需考虑float