SSA Form

SSA Form

SSA 全称是 Static Single Assignment Form 即静态单赋值形式,LLVM 就采用了 SSA Form,当然 LLVM 处理 SSA 的过程是透明的,生成 LLVM IR 的时候只需要处理好 Basic Block 之间的关系,LLVM 就会自动将 IR 转换成 SSA Form。然而对于布尔短路,则需要自己实现 SSA 过程。

简单讲,SSA 形式只允许一个变量被赋值一次,这叫单赋值。程序中存在循环结构,循环结构可能被动态执行多次,循环结构中的变量仍然可能被重新赋值,所以称为“静态单赋值”而不是简单的“单赋值”。

好处是,def-use china 更简洁,有利于数据流分析和优化,等。

当两个控制流汇聚在一起,如何保证变量只赋值一次呢?为了解决这个问题,引入了一个虚构函数 $\phi$ 可以用 $a_3:=\phi(a_1, a_2)$ 实现合并。

$\phi$ 函数自动根据控制流入边选择 $a_1$ 或 $a_2$ 赋值给 $a_3$。$\phi$ 函数底层实现原理是在入边的基本块尾部添加 MOVE 指令。

转换 SSA 算法

来搞点理论学习hhhhh

转换 SSA 最复杂的是如何添加 $\phi$ 函数。最简单的做法是在汇聚点为每一个变量都添加 $\phi$ 函数,但是这样做非常低效。

Dominance Relation

  • X dominates Y if every path from the start node to Y goes through X

    dominate 就是说 X 是 Y 的必经结点

  • D(X) is the set of nodes that X dominates

  • X strictly dominates Y if X dominates Y and X ≠ Y

  • Dominance Frontier (DF) of node X is the set of all nodes Y such that:

    • X dominates a predecessor of Y, and
    • X does not strictly dominate Y
    • 简单讲这个就是边 X 必经结点的边界,DF(X) 中的结点的前驱中有一个是 D(x) 中的结点而另一个前驱就不属于 D(X)。再讲简单一点,DF(X) 中的结点控制流可能经过X,也可能还有其它路径,不经过 X。

    如图,D(5) = {6, 7, 8}, DF(5) = {4, 13, 12, 5}

如果一个变量 a 在 X 结点中定义,显而易见,有以下性质:

  • D(X) 中的结点不需要为 a 变量插入 $\phi$ 函数

  • DF(X) 中的结点需要为 a 变量插入 $\phi$ 函数

这样就避免了添加重复无用的 $\phi$ 函数。

DF(X) 的计算

这个是一个递归计算算法,DF(X) 计算子结点的 DF(X) 合并。

DF(X) 需要的辅助函数

  • Local(X) := set of successors of X that X does not immediately dominate

    • 个人理解就是, X 的子结点中,X 无法直接 dominate 的结点(这些结点前驱除了X还有其它的前驱)
  • Up(X) := if X dominates K, Up(X) is the set of nodes in DF(K) that are not dominated by X.

  • 个人理解就是,X 的子节点 K 的 DF(K )集合中不属于 D(X) 的结点,可以理解成子节点的边界。。(突然发现人话好难描述。。)

  • $DF(X) = Local(X) \cup \bigcup\limits_{c \in children[X]}Up(X)$

算法描述

插入 $\phi$ 函数

每次插入 $\phi$ 函数都会引入新的定义,所以要迭代不停检查DF,直到没有新的 $\phi$ 插入。

举个例子。

DF(5) = {6}, 在 6 结点为 W 插入 $\phi$ 函数

DF(6) = {7}, 在 7 结点为 W 插入 $\phi$ 函数

重命名变量名

用脚标对同一个变量命名区分。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!