如何构建SSA形式的CFG

这篇文章是关于如何从非SSA(静态单一赋值) (opens new window)形式的CFG(控制流图) (opens new window)构造出SSA形式的控制流图。这主要涉及到图论中的Dominator理论 (opens new window)。难点在于formula函数的插入。

# 1 简介

SSA中的每个变量仅被定义一次。SSA形式的代码极大地降低了定义使用链的可能数目。在传统的非SSA形式的代码中,如果有formula处定义和formula处使用,就可能有formula种可能的组合。因而SSA形式的代码有利于程序的优化和分析。

顺序执行的代码SSA形式较为简单。但程序会有分支和合并,通过在合并处插入formula函数,就能解决带分支代码的SSA形式。formula函数表示从进来的分支中选取某一个值作为新的值。如下面的代码:

if (p)
  v = 1;
else
  v = 2;
return v;

就会被转化成:

if (p)
  v1 = 1;
else
  v2 = 2;
v3 = phi(v1, v2);
return v3;

使用SSA形式中的一个分析例子是常量传播分析。常量传播分析是指分析哪些变量是常量,对于非SSA形式的分析,这较为困难。对于SSA形式,我们可以将那些使用常量定义的变量,将其所有出现的地方替换成常量,不断迭代直到到达不动点即可。

# 1.1 何处安放formula函数

假设formula在程序中只有一处赋值。那么formula的值要么是程序开始处的formula,要么是被赋值后的formula(注:这里可能在原作者[1]眼中所有的变量都是在程序入口处有定义的,见2 控制流图(CFG))。假设formula是给formula赋值的基本块,那么对于formula严格支配的基本块formula,它见到的值一定是formula。如果控制流跑到了formula,而formula不被formula严格支配,且formula是这个路径中的第一个,那么formula即可能从formula看到formula又可能从程序开始处看到formulaformula被称为formula的支配边界(dominance frontier),需要添加formula函数。因此总的来说,我们可以寻找到给formula赋值的基本块的所有支配边界,它们就是需要插入formula函数的地方。

使用支配边界进行SSA计算的这个想法也适用于计算控制依赖控制依赖可以确定语句执行的条件。

# 2 控制流图(CFG)

程序的语句可以被组织成基本块,控制流从基本块的第一个语句进入,到最后一条语句流出。CFG是一个有向图,其节点除了基本块外,还有Entry和Exit节点。Entry到程序的任何入口基本块会有一条边,程序的任何出口到基本块会有一条边。此外还有一条从Entry到Exit的边,原因之后解释。其他的边代表执行流的跳转。一个拥有多个后继的节点称为分支,一个拥有多个前驱的节点称为合并。每个节点在Entry节点都会有一个赋值,代表程序进入时它的值,这个赋值与其他赋值同等对待。

我们使用formula代表一般的路径(可空,长度formula的路径包含formula个节点和formula个边),使用formula代表非空路径。

对于两个非空路径formulaformula,我们说它们交汇于节点formula如果:

formula

直觉来说,就是formulaformula从不同的节点出发,然后没有在中间交于相同的节点,只是在最后交于formula,然后其中有的边可能包含循环formula的路径。

# 3 静态单一赋值形式(SSA)

一个赋值语句formula形如formula。其中formula是一个互异的目标变量元组,而formula是一个表达式元组,两个元组长度相等。语义上,formula中的每一个表达式都赋值给了对应的formula的目标变量。

将程序转换成SSA形式分为两步,首先,一些平凡的formula函数被插入,形如formula。第二步则是替换所有的formula为新的变量formula,这里被替换的formula包括分支语句中出现的和赋值中出现的。因而,本文中,一个赋值可能是个普通赋值或者formula赋值。

先前提到的formula赋值有如下的形式formula,其中formula是变量,formula赋值位于基本块的开始。右手边变量的个数应当与进入基本块的前驱数目相等,这里要求基本块的前驱以某种形式排序。如果控制流从第formula个前驱流入,那么formula的取值就是右手边第formula个变量。

SSA形式可以被看作一个程序的性质,或者一个从不具备该性质的程序到具备的变换。作为变换,它要求新程序满足以下的性质,对于每一个原始程序的变量formula

  1. 如果formulaformula交汇于节点formula,且formulaformula包含了对formula的赋值(原始程序中的),formula赋值应当被插入到formula中(新程序);
  2. 每一个对formula的使用(包括formula函数)都被替换为formula,使程序成为静态单一赋值;
  3. 沿着任何控制流路径,源程序中的formula的取值于新程序中的formula的取值必须一样。

最小SSA形式是指插入的formula函数尽可能少。一些没有必要的formula函数可能会影响程序的优化。另一种是修剪的SSA形式,它是指如果变量没有在交汇点formula中及之后使用,就删掉formula语句。不过有时我们会需要在所有交汇的地方放置formula函数,但本文的算法经过微小的改动就可以得到修剪的SSA形式。

# 3.1 其他的程序结构

对于数组,将数组元素视为变量会很不方便,因而可以引入两个函数formula表示访问数组formula的第formula个元素,其返回值就是formula的第formula个元素的值,formula表示修改数组formula的第formula个元素,将其值置为formula,并返回新的数组formula。所以对formula某个元素的赋值相当于对整个数组formula赋值。

结构体大体上可以看成是数组。

除此之外,可能存在到变量的隐式引用,比如全局变量被子过程的使用和改变、变量别名、解引用指针等等。对于语句formula,3中类型的引用影响到了到SSA形式的转换:

  • formula:一定被formula修改的变量集合;
  • formula:可能被formula修改的变量集合;
  • formula:在formula执行之前的值可能被formula用到的变量集合。

formula转化为赋值语句formula时,formula中的所有变量应当出现在formula中,formula的所有变量出现在formula中(这部分我不太理解)。

对于堆内存的访问,将堆内存视为一整个变量对于大多优化算法足够。如果我们不能获取到函数体,那就要假定所有的全局变量及参数引用的对象会被改变,而调用者的局部变量不应假定为会改变。当然更细致的堆内存模型和别名分析是很有帮助的。更细致的分析可以减少副作用以及减少formulaformula元组的长度。

# 3.2 SSA算法概览

  1. 从CFG中构造出支配边界映射;
  2. 使用支配边界插入formula函数;
  3. 重命名变量。

# 4 支配

# 4.1 支配者树

图论中的相关概念

  • 支配formula支配formula 从起始节点到formula的每条路径都经过了formula,记为formula;从定义来说formula支配formula;这是一个偏序关系(满足自反、传递)。
  • 严格支配formula严格支配formula支配formula,记为formula;如果formula不严格支配formula,则记为formula
  • 支配边界formula的支配边界formula支配了formula的前驱节点,但formula没有严格支配formula;从定义来说formula的支配边界可能包含formula自己;直观理解支配边界就是支配从有到无的界线。
  • 立即支配者formulaformula的立即支配者formula严格支配formulaformula严格支配formulaformula不严格支配formula;我们会用idom来表示立即支配者;直观理解formula的idom就是离formula最接近的严格支配formula的节点;一个节点的idom是唯一的。
  • 支配者树:每个节点的立即支配者组成了一棵树(支配的偏序确保是有向无环的,idom的唯一进而确保是棵树)。

注意支配的概念是对于一个有起始节点的有向图的。

在CFG中,支配者树的根是Entry,除了Entry外,其他节点都有idom。支配者树可以在formula的时间内给出,甚至可以用更复杂的算法在formula时间内给出。由于formula很小,我们假定支配者树是线性时间内求解的。

考虑下面的图:

graphviz image

其支配者树如下,其中节点formula的标签为:

formula

graphviz image

下文中,前驱formula、后继formula和路径这些名词是CFG上的,而父亲formula、孩子formula、祖先、子孙这些名词是指支配者树的。关于支配者树的计算我将在稍后给出。

# 4.2 支配边界

首先我们给出支配边界formula的形式化定义:

formula

直接依据定义计算支配边界会具有很高的复杂度(二次复杂度)。为了以线性于formula的速度计算支配边界,我们对每个节点定义两个中间的集合formulaformula,使得:

formula

对于任意节点formula,一些formula的后继可能会对formula有贡献,这种贡献formula被定义为:

formula

对于任意非Entry的节点formulaformula中的一些节点或许会对formula,这种贡献formula被定义为:

formula

提示

引理1: 公式是正确的。

引理1证明: 由于支配关系是自反的,所以公式中,formula支配自己,故而formula。由于支配关系是传递的,所以公式中的formula严格支配formula的前驱而formula,故而formula。类似的,我们可以证明formula的支配边界在其前驱为formula的情况下在formula中,否则在formula中。

引理2: 对于任意节点formula

formula

引理3: 对于任意节点formula和它的任意孩子formula(支配树上的),

formula

引理3证明: 推导公式可以推导出公式较为复杂。使用反证法。

于是就有了下方计算formula的算法:

  1. 自底向上遍历支配者树上的每个节点formula
    1. formula
    2. 对于每个formula
      1. 如果formula,则formula(计算formula
    3. 对于每个formula
      1. 对于每个formula
        1. 如果formula,则formula(计算formula

formula总的计算时间为formulaformula为CFG的边集),formula总的计算时间正比于所有formula的大小和,最坏情况为formulaformula为CFG的顶点集),但通常而言,formula的计算时间是线性的。

# 4.3 支配边界与合并的关系

对于CFG上的节点集合formulaformula是它们的合并节点formula,也就是存在两个非空的CFG路径,从formula中不同的两点出发,交汇在formula。而formula被定义为下列序列的极限(其实是闭包):

formula

特别的,如果formula是某变量formula的赋值节点集合,formulaformulaformula函数节点集合。

同时,我们定义节点集合上的formula

formula

同样就可以定义formula为下列序列的极限:

formula

这里只是给出一个定义,并不是最快的计算方法。

如果formula是某变量formula的赋值节点集合,我们会证明(这个定理依赖于formula的定义在Entry):

formula

提示

引理4: 对任意CFG中非空路径formula,存在路径上的一个节点formula支配formula。除非formula支配formula的每个节点,formula

引理5: 对CFG中两个不同的节点formula,若有非空路径formulaformula交汇于formula。那么formula

引理5证明: 假设formulaformula分别是引理4中formulaformula存在的节点。formulaformula上时,即formula,只需要考虑formula的情况,此时formula。同理formulaformula上也成立。如果formula不在formula上且formula不在formula上,则可以推导出formulaformula支配formula,进而推导出formula支配formulaformula支配formula,与交汇定义矛盾(存在中间交点)。

引理6: 对于任意CFG节点集合formulaformula

引理7: 对于任意包含formula的CFG节点集合formulaformula

定理: 对于任意包含formula的CFG节点集合formulaformula

# 5 构造最小SSA形式

# 5.1 使用支配边界寻找ϕ函数需要的地方

接下来给出放置平凡formula函数的算法,它需要用到以下3个数据结构:

  • formula
  • formula
  • formula

算法如下:

  1. 对于每个变量formula
    1. formula的所有赋值节点
    2. formulaformula
    3. formulaformula
    4. 如果formula为假
      1. formula
      2. 对每个formula,如果formula为假
        1. formula
        2. formula处放置formula
        3. 如果formula为假
          1. formula
          2. formula

这个算法的复杂度为formula。这里formula是总的赋值数目(包括formula),一般情况下,这个算法线性于formula

# 5.2 重命名

我们给出一个递归函数formula,它有唯一的参数formula是一个CFG节点。此外还有以下的“全局变量”作为上下文:

  • formula
  • formula

首先:

  1. formula全为空栈
  2. formula全为0
  3. 调用formula

formula实现如下:

  1. 对于每个formula
    1. 如果formula是个普通赋值:
      1. 对每个formula
        1. 使用formula替换formula,其中formulaformula
    2. 对每个formula
      1. 使用formula替换formula,其中formulaformula
      2. formula
      3. formula
  2. 对于每个formula
    1. formula基本块formulaformula的边的序号
    2. 对每个formula函数formula
      1. 使用formula替换formula的第formula个操作数,其中formulaformula
  3. 对于每个formula
    1. 调用formula
  4. 对于每个formula
    1. 对每个formula
      1. formula

# 6 控制依赖的构建

控制依赖是反向控制流图的支配边界。类似地我们定义反向支配和立即反向支配者等概念。

一个CFG节点formula被认为是控制依赖formula,如果满足下面两条:

  1. 存在一个非空路径formula,使得formula反向支配formula之后的formula上所有节点。
  2. formula没有严格反向支配formula

这等价于formula的某条出边使得formula一定被执行,但也存在一些从formula出发的路径formula不被执行。

formula是CFG节点,那么formula控制依赖于formula,当且仅当在RCFG中formula。因而计算formula控制依赖算法如下:

  1. 对每个CFG节点formula
    1. 对每个formula
      1. formula

通过添加formula的边,控制依赖的根将成为formula


  1. Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., & Zadeck, F. K. (1991). Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(4), 451-490. ↩︎