如何构建SSA形式的CFG

这篇文章是关于如何从非SSA(静态单一赋值)形式的CFG(控制流图)构造出SSA形式的控制流图。这主要涉及到图论中的Dominator理论。难点在于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,记为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的唯一进而确保是棵树)。

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

例子如下,考虑下面的图:

graphviz image

其支配者树就是:

graphviz image

假设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函数的地方。

# 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个变量。

# 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中。

# 3.2 SSA算法概览

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

# 4 控制

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

# 4.1 支配边界

首先我们给出支配边界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. ↩︎

2016-2020 Ziping Sun
京ICP备 17062397号