中间代码生成

介绍

前端解析后，我们会得到一棵抽象语法树，接下来我们需要将这棵抽象语法树转换为中间代码。依据你设计的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可能如下：

```
上述代码转化为IR后可能如下：
```asm
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;
  }

生成的AST可能如下：

上述代码转化为IR后可能如下：

  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。进一步地，如果你希望参加性能评测，你还需要实现一些中端优化。

中间代码生成

中间代码生成

介绍

部分处理思路

program

parameter_list

declaration

lvalue

中场休息

expression

if

while

预期目标

results matching ""

No results matching ""

results matching ""

No results matching ""