intro.md

实验指导 step14：静态单赋值

本节选做实验改编自： https://buaa-se-compiling.github.io/miniSysY-tutorial/challenge/mem2reg/help.html 在此表示感谢！

静态单赋值（Static Single Assignment, SSA）是编译器中间表示（IR）阶段的一个重要概念，它要求程序中每个变量在使用之前只被赋值一次。

例如，考虑使用 IR 编写程序计算 1 + 2 + 3 的值，一种可能的写法为：

_T0 = 1
_T1 = 2
_T2 = 3
_T3 = ADD _T0, _T1
_T3 = ADD _T3, _T2
return _T3

很遗憾，上述程序并不符合 SSA 的要求，因为其中变量 _T3 被赋值了两次。正确的写法应该为：

_T0 = 1
_T1 = 2
_T2 = 3
_T3 = ADD _T0, _T1
_T4 = ADD _T3, _T2
return _T4

我们为什么要这样做呢？

因为 SSA 可以简化每个变量的属性，进而简化编译器的优化过程。

例如，考虑下面这段伪代码：

y := 1
y := 2
x := y

很显然，其中变量 y 的第一次赋值是不必须的，因为变量 y 被使用前，经历了第二次赋值。对于编译器而言，确定这一关系并不容易，需要经过定义分析（Reaching Definition Analysis）的过程。在很多控制流复杂的情况下，上述过程将变得更加困难。

但如果将上述代码变为 SSA 形式：

y1 := 1
y2 := 2
x1 := y2

上述关系变得更加显而易见，由于每一个变量只被赋值一次，编译器可以轻松地得到 x1 的值来自于 y2 这一信息。

正因如此，许多编译器优化算法都建立在 SSA 的基础之上，例如：死代码消除（dead code elimination）、常量传播（constant propagation）、值域传播（value range propagation）等。

我们如何实现 SSA 呢？

例如，考虑使用 IR 编写程序使用循环计算 5 的阶乘。

按照 C 语言的思路，我们可能给出如下写法：

_L0:
  _T0 = 0
  _T1 = 1
  _T2 = 2
  _T3 = ADD _T0, _T1  # int temp = 1
  _T4 = ADD _T0, _T2  # int i = 2
  _T5 = 5
_L1:
  _T6 = LT _T4, _T5   # i < 5
  BEQZ _T6, _L3
_L2:                  # loop label
  _T3 = MUL _T3, _T4  # temp = temp * i
  _T4 = ADD _T4, _T1  # i = i + 1
  JUMP _L1
_L3:                  # break label
  return _T3

我们注意到，变量 _T3 和 _T4 由于循环体的存在可能被赋值多次，因此上述写法并不符合 SSA 的要求。

一种可能的方案是使用 Phi 指令。Phi 指令的语法是 <result> = PHI [<val0>, <label0>], [<val1>, <label1>] ... 。它使得我们可以根据进入当前基本块之前执行的是哪一个基本块的代码来选择一个变量的值。

由此，我们的程序可以改写为：

_L0:
  _T0 = 2
  _T1 = 1
_L1:
  _T2 = PHI [_T0, _L0], [_T6, _L2]  # int i = 2
  _T3 = PHI [_T1, _L0], [_T7, _L2]  # int temp = 1
  _T4 = 5
  _T5 = LT T2, _T4                  # i < 5
  BEQZ _T5, _L3
_L2:                                # loop label
  _T7 = MUL _T3, _T2                # temp = temp * i
  _T6 = ADD _T2, _T1                # i = i + 1
  JUMP _L1
_L3:                                # break label
  return _T3

由此，上述程序中每一个变量只被赋值了一次，满足了 SSA 的要求。（注意，SSA 仅要求变量在静态阶段被单一赋值，而不是在运行时仅被赋值一次）

另一种可能的方案是使用 Alloca、Load 和 Store 的组合。SSA 要求中间表示阶段虚拟寄存器满足单一赋值要求，但并不要求内存地址如此。因此，我们可以在前端生成中间代码时，将每一个变量都按照栈的方式使用 Alloca 指令分配到内存中，之后每次访问变量都通过 Load 或 Store 指令显式地读写内存。使用上述方案编写的程序满足 SSA 的要求，且避免了繁琐地构造 Phi 指令，但频繁地访问内存将导致严重的性能问题。

有没有更好的解决方案呢？

有，我们可以将两种方案结合起来。

在前端生成中间代码时，首先使用第二种方案利用 Alloca、Load、Store 指令快速地构建满足 SSA 要求的代码。 随后，在上述代码的基础上， 将其中分配的内存变量转化为虚拟寄存器，并在合适的地方插入 Phi 指令。 这一解决方案也被称为 mem2reg 技术。

在本次选做实验中，我们希望同学实现这一技术，针对局部的 int 类型变量生成符合 SSA 要求的中间表示代码。

你需要：

1. 改进你的编译器，支持上面提到的 mem2reg 技术。除完成代码实现外，还需要：
   • 为代码添加合理的注释以便批阅。
   • 设计合适的测例并展示生成的中间表示，以证明你的实现是正确的。
2. 完成实验报告（具体要求请看实验指导书的首页）。实验报告中需要包括：
   • 你的学号姓名
   • 简要叙述，为了完成这个 stage 你做了哪些工作（即你的实验内容）
   • 详细说明你的代码的运行逻辑
   • 你设计的测例和对应生成的中间代码，并进行适当的分析。
   • 如果你复用借鉴了参考代码或其他资源，请明确写出你借鉴了哪些内容。并且，即使你声明了代码借鉴，你也需要自己独立认真完成实验。
   • 如有代码交给其他同学参考，也必须在报告中声明，告知给哪些同学拷贝过代码（包括可能通过间接渠道传播给其他同学）。