本文来源于这篇Efficient building and placing of gating functions论文。该论文提供了一种算法，能够直接从CFG（控制流图）构建GSA（Gated单一赋值）形式。而之前的方法需要先插入phi节点即转换成SSA（静态单一赋值）形式，再进行构建。其核心思想是借助了他们提出的gating path这一概念。

内容主要来自这篇¹论文。

背景及相关知识

支配

摘自“如何构建SSA形式的CFG”。

• 支配：$x$支配$y \Leftrightarrow$ 从起始节点到$y$的每条路径都经过了$x$，记为$x\underline{\gg}y$；从定义来说$\forall x, x$支配$x$；这是一个偏序关系（满足自反、传递）。
• 严格支配：$x$严格支配$y \Leftrightarrow x$支配$y \land x \neq y$，记为$x\gg y$；如果$x$不严格支配$y$，则记为$x\rlap{\hspace{.5em}/}\gg y$。
• 支配边界：$y \in x$的支配边界$\Leftrightarrow x$支配了$y$的前驱节点，但$d$没有严格支配$y$；从定义来说$x$的支配边界可能包含$x$自己；直观理解支配边界就是支配从有到无的界线。记$DF(X)$为节点$X$的支配边界。$DF$也可以定义在集合$\mathcal{X}$上，$DF(\mathcal{X})=\bigcup_{x\in \mathcal{X}}DF(X)$。 $$DF(X) = {Y|\exists P\in Pred(Y)(X\underline{\gg}P\land X\rlap{\hspace{.6em}|}\gg Y)}$$
• 立即支配者：$x$是$y$的立即支配者$\Leftrightarrow x$严格支配$y$且$\forall z$严格支配$y$，$x$不严格支配$z$；我们会用idom来表示立即支配者；直观理解$y$的idom就是离$y$最接近的严格支配$y$的节点；一个节点的idom是唯一的。
• 支配者树：每个节点的立即支配者组成了一棵树（支配的偏序确保是有向无环的，idom的唯一进而确保是棵树）。

注意支配的概念是对于一个有起始节点的有向图的。在CFG中，支配者树的根是Entry。

可归约性与循环

可归约性

首先介绍两种变换，称为“归约”：

1. T1变换：移除一个节点的自环；
2. T2变换：对于一个有唯一前继$p$的节点$n$（可能有重边），移除$n$并让其后继成为$p$的后继。

可归约有很多等价的定义，现在给出其中的两种：

• CFG中的边可以分为两个不重叠的集合：前向边和回边，并满足：
  • 前向边组成了DAG，且都能从入口节点到达；
  • 回边的终止节点支配了起始节点。
• 反复使用T1和T2变换能将CFG转换为单一节点。

不可归约图主要是存在强连通分量有多个入口的情况。在结构化编程、不使用goto语句的情况下，创造出的CFG都是可归约图。

循环特指那些只有单一入口的强连通分量。在可归约图中识别循环将变得很简单，其切入点是回边检测：那些从被支配节点到支配节点的边就是回边，对应的支配节点是循环头，被支配节点是循环尾。下一小节会有更多关于循环的定义。

可归约图除了在识别循环上有帮助外，还能极大地简化程序分析复杂性。

对于不可归约图，可以通过复制分裂节点，转换成可归约图。

可归约图的逆图不一定是可归约图。

循环

以下是关于循环的一些概念，注意循环通常是可归约图的概念：

• 循环：CFG上有唯一入口节点（循环头）的强连通子图；
• 循环入边：起点在循环外，终点在循环内；
• 循环出边：起点在循环内，终点在循环外；
• 循环头：循环入边的终点。支配循环内所有节点；
• 回边：终点是循环头，起点在循环内；
• 某回边的自然循环：被循环头支配，并能到达该回边的节点集合；
• 循环尾：回边的起点；
• 循环出口：循环出边的终点；
• 嵌套循环：循环头在另一循环内的的循环。

对于两个不同的自然循环，它们可能有3种关系：

1. 互相分离：没有任何节点共享；
2. 互相嵌套：一个的循环头严格支配另一个循环头；
3. 共享循环头：循环头是共享的。

对于第3种情况，可以添加公共的循环尾合并为一个循环。进而循环只剩下两种关系：分离，嵌套。

SSA（静态单一赋值）形式

通过对CFG进行转化，确保每个变量只有一次定义（即一处赋值），可以极大地简化程序分析，这种转化的结果就是SSA形式。顺序执行的代码只需要给变量添加版本号，就能转化为SSA形式。而在CFG的交汇节点处，如果流入同一变量的不同版本，就需要插入一个选择函数来确保单一赋值。这种函数称为$\phi$函数，形如$x_{n+1}=\phi(x_1,x_2,\dots,x_n)$。它位于CFG节点的起始处（如果有多个变量的话,可能有多个$\phi$函数）。它的参数是那些流入的不同版本。语义上，根据控制流是从哪条边流入，$\phi$函数会返回对应的变量版本。

Cytron²给出了一个高效的转化SSA形式的算法。为了理解这篇论文的理论基础，首先定义支配边界闭包的$DF^+(\mathcal{X})$为下列序列的极限： $$\begin{cases} DF_1=DF(\mathcal{X})\newline DF_{i+1}=DF(\mathcal{X}\cup DF_i) \end{cases}$$ 也就是说$DF^+(\mathcal{X})$是$\mathcal{X}$的支配边界，并上支配边界的支配边界，等等。然后这篇论文给出了最重要的定理：令$\mathcal{X}$为某个变量所有赋值语句出现过的CFG节点集合，$DF^+(\mathcal{X})$是赋值语句交汇的点，也就是最少的需要为该变量插入$\phi$函数的地方。依据这个定理，Cytron给出了两步算法，先是放置$\phi$函数，再重命名变量（给变量加上版本号）。

GSA（Gated单一赋值）形式

虽然SSA形式的CFG更清楚的显示了def-use链，但它仍属于控制流的一种表示。Ottenstein³提出了GSA，它是一种更加易于分析的值流表示。在此工作基础上，Havlak⁴进一步简化了GSA为TGSA（T是Thinned，意为简化 ）。在这篇论文里，他们给出的TGSA构造方法是以SSA结果为输入的。而本文则试图给出一个不依赖于SSA结果的算法。这里给出TGSA向传统SSA添加并用以替代$\phi$函数的3种新gating函数。

$\gamma$函数，含有谓词的合并

V1 := ...
if (P) then
    V2 := ...
endif
V3 := phi(V1, V2)

V1 = ...
if (P) then
    V2 := ...
endif
V3 := gamma(P, V2, V1)

$\gamma$试图表示条件分支语句的合并，它用于替换除循环头起始处的$\phi$函数。$\gamma$函数有如下的形式$V_3 := \gamma(P,V_1,V_2)$。含义是，如果$P$（谓词输入）为真，$V$的取值为$V_2$否则为$V_1$（$V_1$、$V_2$统称为值输入）。注意到，$\phi$函数是依据流入控制流选取多个值，而$\gamma$则是根据条件选取多个值，后者便于值流分析。$\gamma$函数很容易被扩展为多分支用于switch，类似于$\gamma(P,V_1,V_2,\dots,V_n)$。

$\gamma$函数可能嵌套，构成DAG（嵌套表达式在合并公共子表达式后，就构成了DAG）。该合并节点CFG上的立即支配者为DAG的根$\gamma$函数提供谓词输入。而从DAG的根到末端经过的$\gamma$函数的顺序，应当与从合并节点CFG上的立即支配者到合并节点的前向CFG路径（除去循环回边的CFG）经过的分支顺序一致。

某些情况下，若某个分支条件不可能发生，用$\top$表示（译注：这里这个符号很困惑，它明明是底类型$\bot$）。这个记号和后文中$\varnothing$具有相同的意义，只是来源于不同的文章。

考虑上图中的例子，在$A_3$处，将$\phi$函数替换为$\gamma$函数，结果应该为$\gamma(P,\gamma(Q,A_1,\top),A_2)$。

$\mu$函数，循环合并

$\mu$函数被插入在循环头起始处，并有如下的形式$V’:=\mu(V_{init},V_{iter})$。其中$V_{init}$是从循环外获得的初始输入，$V_{iter}$是从循环内回边获得的迭代输入。如果有多条循环外入边或有多条回边，相应的$V_{init}$和$V_{iter}$可能是一个$\gamma$ DAG。语义上，$\mu$函数产生了一个无穷的序列。而这个序列中的符合条件的第一个元素会被循环出口处的$\eta$函数选取。

一个循环头可能会被若干自然循环共享，即嵌套，或者除循环头外不共享节点。后者可以通过一个post-body节点合并多个回边化为一个自然循环。无论何种情况，$V_{iter}$应该是考虑了所有循环路径的结果。

这里使用了TGSA而不是GSA论文中的定义。

$\eta$函数，循环值选取

$\eta$函数被插入在循环出口的尾部，用于从$\mu$函数产生出来的序列中，选取符合某一条件的第一个值，其形式为$V’:=\eta(P,V_{final})$。其中$V_{final}$是一个由$\mu$函数产生的序列。而$P$则是断言，如果$P$依赖于循环内的变量，那么它也是序列。语义上，当$P$为真时，$V_{final}$的值被选取并赋值给$V’$。与$P$和$V_{final}$不同$V’$是序列中的一个值。

值得注意的是，与$\gamma$和$\mu$不同，$\eta$不表示合并。因此$\eta$的$P$和$V_{final}$一般不是$\gamma$ DAG。当然，如果从循环头到基本块有多个包含赋值的路径的话，那么$\eta$所处基本块的开始处会有$\gamma$节点。其插入的位置也有所不同。$\gamma$和$\mu$与$\phi$类似，都位于基本块的开头，而$\eta$插入在基本块的尾部。

此外，即使是在可归约图中，一个循环也可能存在多个循环出口。循环出口可能与循环头是同一个基本块（...