MLIR：静态单赋值，SSA

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

Multi-Level Intermediate Representation（MLIR）是创建可重用、可扩展编译器基础设施的新途径。本文为 MLIR 系列第 2 期，介绍基础概念 SSA。

出发点

当前，IR 是 LLVM 的设计核心，它采用 SSA（Single-Static Assignments，静态单赋值）的形式，并具备两个重要特性：

• 代码被组织成三地址指令
• 有无限的寄存器

MLIR 与 SSA 相似，但同时引入了多面体循环优化（下期内容，polyhedral loop optimization）的概念。

来个例子

《编译原理》

下面是一个三地址码的例子，

p = a + b
q = p - c
p = q * d
p = e - p
q = p + q

如果是 SSA 形式，

p_1 = a + b
q_1 = p_1 - c
p_2 = q_1 * d
p_3 = e - p_2
q_2 = p_3 + q_1

简单讲，就是给变量附上了下标来加以区分。静态单赋值说的就是所有赋值针对的变量都是单独的、不同的。

优点

这么做的好处是什么呢？

在这种更一般化、明晰的表示基础上，许多优化技术可以得以展开。最直接的，定义可达性分析（reaching definition analysis）就可以找出没有被用到的定义语句，再删掉它。

比如，

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

到

y_1 := 1
y_2 := 2
x_1 := y_2

显然，通过 SSA 看，第一句话就可以被优化掉。

那么问题来了，如果是控制流语句中定义的变量，出条件后应该是哪个名字？

$\varphi$函数

例如，

if (flag)
  x = -1;
else
  x = 1;
y = x * a;

这段代码换成 SSA 形式的话，末句中的 x 应该是 x_1 还是 x_2 呢？

这就需要引入 $\varphi$ 函数，也即通过 $\varphi$ 函数来判定来源。

if (flag)
  x_1 = -1;
else
  x_2 = 1;
x_3 = p(x_1, x_2);
y = x_3 * a;

其中 x_3 = p(x_1, x_2) 即 $x_3 = \varphi(x_1, x_2)$

引申

• 在哪里插入 $\varphi$ 函数将引出支配边界（dominance frontiers）和最小 SSA（minimal SSA）
• $\varphi$ 函数的具体实现也是不一定的，例如可以基于move操作

都看到这儿了，不如关注每日推送的“科文路”、互动起来~

至少点个赞再走吧~