minidecaf-tutorial

中间代码生成

介绍

前端解析后，我们会得到一棵抽象语法树，接下来我们需要将这棵抽象语法树转换为中间代码。依据你设计的IR，你需要在保证语义的情况下，将AST用你的IR表示出来。可以参考基础实验框架中frontend/tacgen/的代码。推荐在生成中间代码时就先利用 Alloca、Load、Store 指令来简单地实现 SSA 形式的中间代码，方便之后用mem2reg进一步优化（你可以先阅读静态单赋值简单了解什么是SSA）。

部分处理思路

整体思路是通过遍历AST的节点，根据节点类型进行相应的处理。推荐先根据AST的遍历顺序写一个框架，再填充具体的处理逻辑。

由于每个组的AST和IR设计不尽相同，本部分仅介绍一些重点的处理思路和具体示例，结合小实验文档食用效果更佳。

注意：

program

对于program节点，先新建一个IR的Program对象，然后我们只需要再遍历子节点。

parameter_list

对于parameter_list节点，可以把前几个寄存器编号分配给参数。

declaration

对于declaration节点，需要根据是否为全局变量、是否为数组来进行处理。为了满足 SSA 形式，哪怕是局部标量，也要用Alloca指令得到一个地址，后续就通过这个地址来对该变量进行读写操作。

如果有初始化，

lvalue

lvalue节点表示的是左值，可能出现的地方为：assignment的等号左边部分、expression的某个部分，如果是后者且该节点表示的是一个具体值，则返回存有该值的寄存器，否则返回其对应地址的寄存器。（下面会对“表示的是一个具体值”进行解释）

中场休息

看了前面的内容感觉很抽象怎么办？没关系，我们不急着往后学，先休息一下，看一个具体的用到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
}

在本例中，

expression

访问expression节点之后需要返回存有其运算结果的寄存器，方便后续使用。以下分两种情况进行处理：

if

while

这里的翻译方式采用的是step8的思考题中的第二种。在翻译过程中，你还要维护好循环所需的break/continue标签。

预期目标

完成这部分内容后，你的编译器应该能将 MiniDecaf 程序翻译成满足 SSA 形式的 IR，并能够输出 IR。进一步地，如果你希望参加性能评测，你还需要实现一些中端优化。