中间代码生成
介绍
前端解析后，我们会得到一棵抽象语法树，接下来我们需要将这棵抽象语法树转换为中间代码。依据你设计的IR，你需要在保证语义的情况下，将AST用你的IR表示出来。可以参考基础实验框架中frontend/tacgen/的代码。推荐在生成中间代码时就先利用 Alloca、Load、Store 指令来简单地实现 SSA 形式的中间代码，方便之后用mem2reg进一步优化（你可以先阅读静态单赋值简单了解什么是SSA）。
部分处理思路
整体思路是通过遍历AST的节点，根据节点类型进行相应的处理。推荐先根据AST的遍历顺序写一个框架，再填充具体的处理逻辑。
由于每个组的AST和IR设计不尽相同，本部分仅介绍一些重点的处理思路和具体示例，结合小实验文档食用效果更佳。
注意：
- 本部分仅供参考，你需要根据自己设计的AST和IR进行调整。
- 在遍历AST的过程中，要记得维护一些数据，比如当前所在函数、当前所在基本块、函数的寄存器数量、函数的基本块数量、前端变量到IR的
Data对象的映射表等。
program
对于program节点，先新建一个IR的Program对象，然后我们只需要再遍历子节点。
- 如果子节点是
function，就新建一个IR的Function对象，再访问该function节点，从而将该函数的前端信息存入Function对象中，最后将其加入到当前Program对象中的functions列表。 - 如果子节点是
declaration，说明这是一个全局变量，就新建一个Data对象，再访问该declaration节点，从而将该全局变量的前端信息存入Data对象中，最后将其加入到当前Program对象中的global_data列表。
parameter_list
对于parameter_list节点，可以把前几个寄存器编号分配给参数。
- 如果是标量参数，要另外在栈上开空间。（这是为了满足 SSA 形式）
- 如果是数组参数，则可以直接保存在寄存器中。
declaration
对于declaration节点，需要根据是否为全局变量、是否为数组来进行处理。为了满足 SSA 形式，哪怕是局部标量，也要用Alloca指令得到一个地址，后续就通过这个地址来对该变量进行读写操作。
如果有初始化，
- 对于标量，需要访问
expression节点并获取其运算结果对应的寄存器，然后新增Store指令，表示将得到的寄存器的值存入该标量对应的地址。 - 对于数组则需要遍历
Integer节点，并分别使用Store指令将数组元素存入数组的相应地址，对于全局变量可以考虑是否加入.bss段。
lvalue
lvalue节点表示的是左值，可能出现的地方为：assignment的等号左边部分、expression的某个部分，如果是后者且该节点表示的是一个具体值，则返回存有该值的寄存器，否则返回其对应地址的寄存器。（下面会对“表示的是一个具体值”进行解释）
- 先通过前端变量到IR的
Data对象的映射表，找到该节点所表示的前端变量对应的Data对象。- 如果这是个全局变量，则新增
LoadAddr指令，表示加载全局变量的地址，获取对应地址的寄存器 - 如果这是个局部变量，则直接通过
Data对象获取对应地址的寄存器
- 如果这是个全局变量，则新增
- 如果这是个数组，那么前端节点应该会记录下标，每个下标都是
expression节点，故需要访问每个下标节点，获取其运算结果对应的寄存器，可以将这些寄存器存起来，比如存进index_temps中，之后再利用这些信息来构造相应的GetElementPtr指令，表示通过数组基地址和下标获取元素的地址。 - 目前不管是全局变量还是局部变量，不管是标量还是数组，我们得到的都是存有其对应地址的寄存器，需要根据具体情况确定返回内容。
- 如果该
lvalue节点是expression的某个部分，且表示的是一个具体值，则先新增Load指令，表示将地址里的值加载到一个寄存器中，最后返回这个寄存器；否则，就直接返回其对应地址的寄存器。 - 什么是“表示的是一个具体值”？举个例子，如果已知有一个数组
a[2][3]，那么如果该lvalue节点表示的是a[1][2]，则表示的是一个具体值，如果表示的是a、a[0]，则不是一个具体值而是一个地址。
- 如果该
中场休息
看了前面的内容感觉很抽象怎么办？没关系，我们不急着往后学，先休息一下，看一个具体的用到parameter_list, declaration, lvalue节点的例子，希望能帮到你。
int a = 1;
int foo(int x, int y[]) {
return x + y[1];
}
int main() {
int b[2][3] = {1, 2, 3, 4, 5, 6};
return foo(a, b[1]);
}
生成的AST可能如下：
Program
|- (children[0]) Declaration
|- (spec) Specifier(TINT)
|- VarDecl
|- (type) TInt
|- (ident) Identifier("a")
|- (init) IntLiteral(1)
|- (children[1]) Function
|- (ret_t) TInt
|- (ident) Identifier("foo")
|- (params) ParameterList
|- (children[0]) Parameter
|- (spec) Specifier(TINT)
|- (decl) Declarator(Identifier("x"))
|- (children[1]) Parameter
|- (spec) Specifier(TINT)
|- (decl) Declarator(Identifier("y"), ArrayType())
|- (body) Block
|- (children[0]) Return
|- (expr) BinOp(ADD)
|- (lhs) Identifier("x")
|- (rhs) ArrayRef
|- (array) Identifier("y")
|- (index) IntLiteral(1)
|- (children[2]) Function
|- (ret_t) TInt
|- (ident) Identifier("main")
|- (params) ParameterList # Empty
|- (body) Block
|- (children[0]) Declaration
|- (spec) Specifier(TINT)
|- (decl) Declarator(Identifier("b"), ArrayType(2, ArrayType(3, TINT)))
|- (init) InitList
|- (children[0]) InitList
|- (children[0]) IntLiteral(1)
|- (children[1]) IntLiteral(2)
|- (children[2]) IntLiteral(3)
|- (children[1]) InitList
|- (children[0]) IntLiteral(4)
|- (children[1]) IntLiteral(5)
|- (children[2]) IntLiteral(6)
|- (children[1]) Return
|- (expr) Call
|- (func) Identifier("foo")
|- (args) ArgumentList
|- (children[0]) Identifier("a")
|- (children[1]) ArrayRef
|- (array) Identifier("b")
|- (index) IntLiteral(1)
上述代码转化为IR后可能如下：
i32 foo(i32 _T0, i32* _T1) {
_B0:
alloca i32* _T2 = 4
store *(i32* _T2 + 0) = i32 _T0
load i32 _T3 = *(i32* _T2 + 0)
i32 _T4 = 1
i32* _T5 = elementptr: i32* _T1[i32 _T4]
load i32 _T6 = *(i32* _T5 + 0)
i32 _T7 = i32 _T3 + i32 _T6
return i32 _T7
}
i32 main() {
_B0:
alloca i32[3]* _T0 = 24
i32 _T1 = 1
store *(i32[3]* _T0 + 0) = i32 _T1
i32 _T2 = 2
store *(i32[3]* _T0 + 4) = i32 _T2
i32 _T3 = 3
store *(i32[3]* _T0 + 8) = i32 _T3
i32 _T4 = 4
store *(i32[3]* _T0 + 12) = i32 _T4
i32 _T5 = 5
store *(i32[3]* _T0 + 16) = i32 _T5
i32 _T6 = 6
store *(i32[3]* _T0 + 20) = i32 _T6
i32* _T7 = LoadAddr $a
load i32 _T8 = *(i32* _T7 + 0)
i32 _T9 = 1
i32* _T10 = elementptr: i32[3]* _T0[i32 _T9]
i32 _T11 = call foo(i32 _T8, i32* _T10)
return i32 _T11
}
在本例中，
foo函数的参数表示为_T0,_T1。为了满足 SSA 形式，使用标量x时，需要另外在栈上开空间，这样之后对x的读写操作都可以直接通过_T2来进行。对于y[1]，利用下标和getElementptr指令可以得到其地址，然后通过load指令可以得到其值。（getElementptr指令是为了写起来方便快捷；这里你也可以通过基地址_T1和下标1，构造出_T1 + 1 * 4的式子来计算出y[1]的地址）main函数中对于数组b，先使用Alloca指令获取其栈上地址，再将初始值存到各个元素的地址中。由于a是foo函数的实参，所以这是一个lvalue节点，同时我们知道这是一个具体值，所以在LoadAddr指令获取a的地址之后，还要用Load指令将其值加载到一个寄存器中。b[1]在这里虽然也是一个lvalue节点，但是由于它不是一个具体值，所以我们直接使用其对应地址的寄存器。
expression
访问expression节点之后需要返回存有其运算结果的寄存器，方便后续使用。以下分两种情况进行处理：
unary '=' expression，表示赋值表达式。- 对于等号左边，访问该
lvalue节点并获取其对应地址的寄存器。 - 对于等号右边，访问该
expression节点并获取其运算结果对应的寄存器。 - 最后新增
Store指令，表示将右边的寄存器里的值存入左边的寄存器里的地址，并返回左边的寄存器。
- 对于等号左边，访问该
conditional，表示条件表达式。- 如果这是个三目运算符，可参考
if节点的处理方式，区别在于，对于:?运算符，then和else是两个表达式节点，对于if语句，这两个变量是两个语句节点。 - 如果这是个
logical_or节点，则直接访问logical_or节点，由于可能出现逻辑短路的情况，所以你需要思考如何新增Branch指令来进行分支跳转，可以参考短路求值。
- 如果这是个三目运算符，可参考
- 具体示例可以参考短路求值。
if
- 先给当前函数新增一个基本块
true_bb表示if语句的true分支入口。 - 如果有
else部分，则给当前函数新增一个基本块false_bb表示if语句的false分支入口。 - 给当前函数新增一个基本块
next_bb表示if之后的基本块。 - 分支条件是一个
expression节点，访问该expression节点并获取其运算结果对应的寄存器。- 由于
expression节点可能出现逻辑短路的情况，所以你需要思考如何新增Branch指令来进行分支跳转，可以参考短路求值。
- 由于
- 将当前基本块改为
true_bb，然后访问true分支的前端节点，再新增一个Jump指令，表示从true_bb跳转到next_bb。 - 如果有
else部分，则将当前基本块改为false_bb，然后访问false分支的前端节点，再新增一个Jump指令，表示从false_bb跳转到next_bb。 - 最后将当前基本块改为
next_bb。 例：
int main(){ int a = 2; int b = 0; if(a) b = 1; else b = -1; return b; }生成的AST可能如下：
Program |- (children[0]) Function |- (ret_t) TInt |- (ident) Identifier("main") |- (body) Block |- (children[0]) VarDecl |- (type) TInt |- (ident) Identifier("a") |- (init) IntLiteral(2) |- (children[1]) VarDecl |- (type) TInt |- (ident) Identifier("b") |- (init) IntLiteral(0) |- (children[2]) If |- (cond) Identifier("a") |- (children[0]) Assign |- (lhs) Identifier("b") |- (rhs) IntLiteral(1) |- (children[1]) Assign |- (lhs) Identifier("b") |- (rhs) UnaryOp(NEG) |- (expr) IntLiteral(1) |- (children[3]) Return |- (expr) Identifier("b")上述代码转化为IR后可能如下：
i32 main() { _B0: alloca i32* _T0 = 4 i32 _T1 = 2 store *(i32* _T0 + 0) = i32 _T1 alloca i32* _T2 = 4 i32 _T3 = 0 store *(i32* _T2 + 0) = i32 _T3 load i32 _T4 = *(i32* _T0 + 0) if i32 _T4 == 0 jump _B2 else jump _B1 _B1: i32 _T5 = 1 store *(i32* _T2 + 0) = i32 _T5 jump _B3 _B2: i32 _T6 = 1 i32 _T7 = -i32 _T6 store *(i32* _T2 + 0) = i32 _T7 jump _B3 _B3: load i32 _T8 = *(i32* _T2 + 0) return i32 _T8 }在本例中，生成了
_B1,_B2,_B3三个基本块，分别表示true分支入口、false分支入口和if之后的基本块。_B0的结尾是一个Branch指令，_B1,_B2结尾都是Jump指令，表示从true_bb、false_bb跳转到next_bb。
while
这里的翻译方式采用的是step8的思考题中的第二种。在翻译过程中，你还要维护好循环所需的break/continue标签。
- 给当前函数新增一个基本块
body_bb表示while语句的循环体入口。 - 给当前函数新增一个基本块
body_cond_bb表示第二个while语句的条件部分。 - 给当前函数新增一个基本块
next_bb表示while之后的基本块。 - 开始访问第一个
while语句的条件部分，分支条件是一个expression节点，可以直接访问该expression节点。- 由于
expression节点可能出现逻辑短路的情况，所以你需要思考如何新增Branch指令来进行分支跳转，可以参考短路求值进行学习。
- 由于
- 将当前基本块改为
body_bb，然后访问true分支的前端节点，再新增一个Jump指令，表示从body_bb跳转到body_cond_bb。 - 将当前基本块改为
body_cond_bb，第二个while语句的条件部分是一个expression节点，访问该expression节点并获取其运算结果对应的寄存器。- 由于
expression节点可能出现逻辑短路的情况，所以你需要思考如何新增Branch指令来进行分支跳转，可以参考短路求值进行学习。
- 由于
- 最后将当前基本块改为
next_bb。 - 例：
int main(){ int a = 0; while(a < 10){ if(a == 5){ a = 10; break; } a = a + 1; } return a; }
上述代码转化为IR后可能如下：Program |- (children[0]) Function |- (ret_t) TInt |- (ident) Identifier("main") |- (body) Block |- (children[0]) VarDecl |- (type) TInt |- (ident) Identifier("a") |- (init) IntLiteral(0) |- (children[1]) While |- (cond) BinaryOp(LT) |- (lhs) Identifier("a") |- (rhs) IntLiteral(10) |- (body) Block |- (children[0]) If |- (cond) BinaryOp(EQ) |- (lhs) Identifier("a") |- (rhs) IntLiteral(5) |- (children[0]) Assign |- (lhs) Identifier("a") |- (rhs) IntLiteral(10) |- (children[1]) Break |- (children[1]) Assign |- (lhs) Identifier("a") |- (rhs) BinaryOp(ADD) |- (lhs) Identifier("a") |- (rhs) IntLiteral(1) |- (children[2]) Return |- (expr) Identifier("a")
在本例中，i32 main() { _B0: alloca i32* _T0 = 4 i32 _T1 = 0 store *(i32* _T0 + 0) = i32 _T1 load i32 _T2 = *(i32* _T0 + 0) i32 _T3 = 10 i32 _T4 = i32 _T2 < i32 _T3 if i32 _T4 == 0 jump _B3 else jump _B1 _B1: load i32 _T5 = *(i32* _T0 + 0) i32 _T6 = 5 i32 _T7 = i32 _T5 == i32 _T6 if i32 _T7 == 0 jump _B5 else jump _B4 _B2: load i32 _T12 = *(i32* _T0 + 0) i32 _T13 = 10 i32 _T14 = i32 _T12 < i32 _T13 if i32 _T14 == 0 jump _B3 else jump _B1 _B3: load i32 _T15 = *(i32* _T0 + 0) return i32 _T15 _B4: i32 _T8 = 10 store *(i32* _T0 + 0) = i32 _T8 jump _B3 _B5: load i32 _T9 = *(i32* _T0 + 0) i32 _T10 = 1 i32 _T11 = i32 _T9 + i32 _T10 store *(i32* _T0 + 0) = i32 _T11 jump _B2 _B6: jump _B5 }_B0的最后是第一个while语句的条件部分，while语句还生成了_B1,_B2,_B3三个基本块，分别表示while语句的循环体入口、第二个while语句的条件部分和while之后的基本块。if语句生成了_B4,_B5两个基本块。多出来的_B6是个不可达基本块，可以在之后生成目标代码时消掉。（思考一下，为什么要生成_B6？提示：如果break;语句后面加上a = 1;语句，IR会如何改变？）
预期目标
完成这部分内容后，你的编译器应该能将 MiniDecaf 程序翻译成满足 SSA 形式的 IR，并能够输出 IR。进一步地，如果你希望参加性能评测，你还需要实现一些中端优化。