编译器优化--3--数据流分析简介

2024-03-04 16:03:11

编译器优化–3--数据流分析简介

在正式进入主题之前，首先需要明白这两个术语：

定义（define）：对变量的赋值

使用（use）：对变量值的读取

概述

为了优化代码，编译器需要把程序作为一个整体来收集信息，并把这些信息分配给流图各个基本块。如：了解每个基本块的出口处哪些变量是活跃的可以改进寄存器的利用率；使用全局公共子表达式的知识区删除冗余计算；执行常量合并和无用代码删除这样的变换；利用到达定义（reaching definition）计算哪些变量未定义。通过在程序的各个点建立和求解与信息有关的方程即可收集数据流信息。下面仅详细介绍数据流分析中关于到达定定义分析的内容，还有活跃变量分析（live variable analysis）和可用表达式分析仅简单进行概念上的说明。

到达定定义分析

有这样一个代码片段如下所示：
$1: y = 3\\ 2: z = 4\\ 3: x = 5\\ 4: y = 6\\ 5: y = 7\\ 6: z = 8\\ 7: a = y\\$ 1:y=32:z=43:x=54:y=65:y=76:z=87:a=y
对于任意一条定义可以表示为： $[d: x = ...]$ [d:x=...]，其中 $d$ d表示语句的行序号。例如上面代码第一行代码表示为 $[1: y = 3]$ [1:y=3]

规定几个重要的集合:

产生集表达式为： $gen[d: x = ... ] = \{d\}$ gen[d:x=...]={d}简写为 $gen[x] = \{d\}$ gen[x]={d}。含义是：当前这条语句给出了一个什么样的定义。
定义全集表达式为： $defs[x]$ defs[x]，表示所有对 $x$ x定义的产生集的并集。
杀死集表达式为： $kill[d: x = ...] = defs[x] -\{d\}$ kill[d:x=...]=defs[x]−{d}简写为 $kill[x] = defs[x] -\{d\}$ kill[x]=defs[x]−{d}。含义是某个 $x$ x定义的杀死集为定义全集与这个 $x$ x定义产生集的差。

对于上面的代码片段，分别对计算每一行产生集，定义全集，杀死集，如下所示：
$\begin{aligned} 1: y = 3 &\ \ \ ; gen[y] = \{1\}, defs[y] = \{1, 4, 5\}, kill[y] = \{4, 5\}\\ 2: z = 4 &\ \ \ ; gen[z] = \{2\}, defs[z] = \{2, 6\}, kill[z] = \{6\}\\ 3: x = 5 &\ \ \ ; gen[x] = \{3\}, defs[x] = \{3\}, kill[z] = \{\}\\ 4: y = 6 &\ \ \ ; gen[y] = \{4\}, defs[y] = \{1, 4, 5\}, kill[y] = \{1, 5\}\\ 5: y = 7 &\ \ \ ; gen[y] = \{5\}, defs[y] = \{1, 4, 5\}, kill[y] = \{1, 4\}\\ 6: z = 8 &\ \ \ ; gen[z] = \{6\}, defs[z] = \{2, 6\}, kill[z] = \{2\}\\ 7: a = y &\ \ \ ; gen[a] = \{7\}, defs[a] = \{7\}, kill[a] = \{\}\\ \end{aligned}$ 1:y=32:z=43:x=54:y=65:y=76:z=87:a=y ;gen[y]={1},defs[y]={1,4,5},kill[y]={4,5} ;gen[z]={2},defs[z]={2,6},kill[z]={6} ;gen[x]={3},defs[x]={3},kill[z]={} ;gen[y]={4},defs[y]={1,4,5},kill[y]={1,5} ;gen[y]={5},defs[y]={1,4,5},kill[y]={1,4} ;gen[z]={6},defs[z]={2,6},kill[z]={2} ;gen[a]={7},defs[a]={7},kill[a]={}
在程序基本块中，典型的数据流方程形式如下：
$\begin{aligned} &in[s_i] = out[s_{i-1}]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)\\ &out[s_i] = gen[s_i] \cup(in[s_i] - kill[s_i])\ \ \ \ \ \ \ (2) \end{aligned}$ in[si]=out[si−1] (1)out[si]=gen[si]∪(in[si]−kill[si]) (2)
其中

$s_i$ si表示第 $i$ i条语句

$in[s_i]$ in[si]表示进第 $i$ i条语句时，可以见到的所有变量定义的集合

$out[s_{i}]$ out[si]表示出第 $i$ i条语句时，可以见到的所有变量定义的集合

接下来我们再一次对之前的代码片段，利用以上数据流方程分别计算每一行的 $in[s_i]$ in[si]和 $out[s_{i}]$ out[si]，如下表示：
$\begin{aligned} 1: y = 3 &\ \ \ ; in[s_1] = \{\}, out[s_1] = \{1\}\\ 2: z = 4 &\ \ \ ; in[s_2] = \{1\}, out[s_2] = \{1, 2\}\\ 3: x = 5 &\ \ \ ; in[s_3] = \{1, 2\}, out[s_3] = \{1, 2, 3\}\\ 4: y = 6 &\ \ \ ; in[s_4] = \{1, 2, 3\}, out[s_4] = \{2, 3, 4\}\\ 5: y = 7 &\ \ \ ; in[s_5] = \{2, 3, 4\}, out[s_5] = \{2, 3, 5\}\\ 6: z = 8 &\ \ \ ; in[s_6] = \{2, 3, 5\}, out[s_6] = \{3, 5, 6\}\\ 7: a = y &\ \ \ ; in[s_7] = \{3, 5, 6\}, out[s_7] = \{3, 5, 6, 7\}\\ \end{aligned}$ 1:y=32:z=43:x=54:y=65:y=76:z=87:a=y ;in[s1]={},out[s1]={1} ;in[s2]={1},out[s2]={1,2} ;in[s3]={1,2},out[s3]={1,2,3} ;in[s4]={1,2,3},out[s4]={2,3,4} ;in[s5]={2,3,4},out[s5]={2,3,5} ;in[s6]={2,3,5},out[s6]={3,5,6} ;in[s7]={3,5,6},out[s7]={3,5,6,7}
观察第7行， $in[s_7] = \{3, 5, 6\}$ in[s7]={3,5,6}，可以发现 $x, y, z$ x,y,z的可到达的定义正好是 $\{3, 5, 6\}$ {3,5,6}，也就是说对于第7行能够到达的 $y$ y的定义只有 $\{5\}$ {5}。所以结合这样的到达定义分析的方法很容易做常量传播优化。

对于一个基本块，从数据流方程到算法

// 算法：对于一个基本快的到达定义算法
// 输入：基本块中所有的语句
// 输出：对于每个语句计算in和out两个集合
// 算法复杂度：O(n)
list_t statements;
set = {};
reaching_definition(){
    foreach s in statements{
		in[s] = set;
        out[s] = collection_union(gen[s], in[s] -kill[s]); // collection_union函数，接收两个集合求并集
        set = out[s];
    }
}

基本块间数据流分析

一般，基本块间数据流分析基于控制流图来构建数据流方程的。使用下面的图做例子说明：

我们先写出控制流图中每个基本块的 $gen$ gen和 $kill$ kill，结果如下：
$\begin{aligned} gen_{B1} &= \{d1, d2, d3\}\\ kill_{B1} & = \{d4, d5, d6, d7\}\\ \\ gen_{B2} &= \{d4, d5\}\\ kill_{B2} & = \{d1, d2, d7\}\\ \\ gen_{B3} &= \{d6\}\\ kill_{B3} & = \{d3\}\\ \\ gen_{B4} &= \{d7\}\\ kill_{B4} & = \{d1, d4\}\\ \end{aligned}$ genB1killB1genB2killB2genB3killB3genB4killB4={d1,d2,d3}={d4,d5,d6,d7}={d4,d5}={d1,d2,d7}={d6}={d3}={d7}={d1,d4}
控制流图中包含了ENTRY节点以及EXIT节点，对于ENTRY节点，没有定值到达，所以ENTRY基本块的传递函数（out）将返回 $\emptyset$ ∅，写为：
$out[ENTRY] = \emptyset$ out[ENTRY]=∅
对于EXIT节点是比较特殊了，该节点中没有任何的定义，所以写为：
$in[EXIT]=out[EXIT]$ in[EXIT]=out[EXIT]
对于所有不等于ENTRY的基本块B，有：
$\begin{aligned}in[B] &= out[p_1] \cup out[p_2]\ \cup ...\cup\ out[p_n],\ p_i \in pred(B)\\out[B] &= gen[B] \cup (in[B] - kill[B])\end{aligned}$ in[B]out[B]=out[p1]∪out[p2] ∪...∪ out[pn], pi∈pred(B)=gen[B]∪(in[B]−kill[B])

可以使用下面的算法来求这个方程的解。这个算法的结果是这个方程组的最小不动点（least fixed point）。

输入：一个流图，其中每个基本块B的 $kill_B$ killB集和 $kill_B$ killB集都已经算出来

输出：到达流图中各个基本块B的入口点和出口点的定值的集合，即 $in[B]$ in[B]和 $out[B]$ out[B]。

方法：我们使用迭代的方法来求解。一开始初始化所有基本块B为： $out[B]=\emptyset$ out[B]=∅，并逐步逼近想要的 $in$ in和 $out$ out的值。因为我们必须不停迭代知道各个 $in$ in值（因此各个 $out$ out值也）收敛。算法伪代码如下：

out[ENTRY]={};
list_t basicblock_except_entry;
foreach (B in basicblock_except_entry){
	out[B]={}; // 初始化
}
while (there is a out[B] still changing in set){
    foreach (B in basicblock_except_entry){
        in[B] = out[p1] + out[p2] + ... + out[pn]; // pi属于B的前驱基本块的集合
        out[B] = collection_union(gen[B], in[B] - kill[B]); // collection_union函数，接收两个集合求并集
    }
}

值得注意的是迭代中检查的是，各个 $out[B]$ out[B]集合都不变时停止循环。因为如果各个 $out[B]$ out[B]不再改变了，下一趟中各个 $in[B]$ in[B]就不会变。对于之前提到的控制流图应用该算法，每次迭代的 $in[B]$ in[B]和 $out[B]$ out[B]的值如下表所示：

Block B	${out[B]}^0$ out[B]0	${in[B]}^1$ in[B]1	${out[B]}^1$ out[B]1	${in[B]}^2$ in[B]2	${out[B]}^2$ out[B]2
$B_1$ B1	$\emptyset$ ∅	$\emptyset$ ∅	$\{d1, d2, d3\}$ {d1,d2,d3}	$\emptyset$ ∅	$\{d1, d2, d3\}$ {d1,d2,d3}
$B_2$ B2	$\emptyset$ ∅	$\{d1, d2, d3\}$ {d1,d2,d3}	$\{d3, d4, d5\}$ {d3,d4,d5}	$\{d1, d2, d3, d5, d6, d7\}$ {d1,d2,d3,d5,d6,d7}	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}
$B_3$ B3	$\emptyset$ ∅	$\{d3, d4, d5\}$ {d3,d4,d5}	$\{d4, d5, d6\}$ {d4,d5,d6}	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}	$\{d4, d5, d6\}$ {d4,d5,d6}
$B_4$ B4	$\emptyset$ ∅	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}
EXIT	$\emptyset$ ∅	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}

Block B	${in[B]}^3$ in[B]3	${out[B]}^3$ out[B]3
$B_1$ B1	$\emptyset$ ∅	$\{d1, d2, d3\}$ {d1,d2,d3}
$B_2$ B2	$\{d1, d2, d3, d5, d6, d7\}$ {d1,d2,d3,d5,d6,d7}	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}
$B_3$ B3	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}	$\{d4, d5, d6\}$ {d4,d5,d6}
$B_4$ B4	$\{d3, d4, d5, d6\}$ {d3,d4,d5,d6}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}
EXIT	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}	$\{d3, d5, d6, d7\}$ {d3,d5,d6,d7}

迭代到第三次 $out[B]$ out[B]就不再改变了，数据流分析不定点算法中while循环将退出得到最终的 $out[B]$ out[B]结果。

活跃变量分析

有些代码改进转换所依赖的信息是按照程序控制流的相反方向进行计算的。在活跃变量分析中，我们希望知道对于变量 $x$ x和程序点 $p$ p， $x$ x在点 $p$ p上的值是否会在流图中的某个条件，从点 $p$ p出发的路径中使用。如果是，我们说 $x$ x在 $p$ p上活跃，否则就说 $x$ x在 $p$ p上是死的。

活跃变量信息的重要用途之一是为基本块进行寄存器分配。一个值被计算并保存到一个寄存器中后，它很可能会在基本块中使用。如果他在基本块的结尾处是死的，就不必在结尾处保存这个值。另外，在所有寄存器都被占用时，如果我们还需要申请一个寄存器的话，那么应该考虑使用一个存放了已死亡的值的寄存器，因为这个值不需要保存了。

可用表达式

如果从流图入口结点到达程序点 $p$ p的每条路径都对表达式 $x+y$ x+y求值，且从最后一个这样的求值之后到 $p$ p点的路径上没有再次对 $x$ x或 $y$ y赋值，那么 $x+y$ x+y在点 $p$ p上可用（available）。对于可用表达式数据流模式而言，如果一个基本块对 $x$ x或 $y$ y赋值（或可能对它们赋值），并且之后没有在重新计算 $x+y$ x+y，我们就说该基本块杀死了表达式 $x+y$ x+y。如果一个基本块一定对 $x+y$ x+y求值，并且之后没有在对 $x$ x或 $y$ y定值，那么这个基本块生成表达式 $x+y$ x+y。

请注意，杀死或生成一个可用表达式的概念和到达定义中的概念并不完全相同，尽管如此，这些杀死或生成的概念在行为上和到达定义中相应的概念是一致的。

可用表达式信息的主要用途是寻找全局公共子表达式。

参考

《编译原理》

《Engineering a Compiler》

ronnie88597 发布了20 篇原创文章 · 获赞 20 · 访问量 468 私信关注

码农公寓

编译器优化–3--数据流分析简介

概述

到达定定义分析

基本块间数据流分析

活跃变量分析

可用表达式

参考

相关文章