区间分析 | 山楂片的博客 | 柑橘 RSS 阅读器

这篇文章的内容来自Allen的Control Flow Analysis¹。

基础概念

有向图$G=(B,E)$有节点（块）集合$\{b_1,b_2,\dots,b_n\}$和边集合$\{(b_i,b_j),(b_k,b_l),\dots\}$组成。每个有向边是一个节点有序对$(b_i,b_j)$（不一定互异），代表有向边从$b_i$出发到$b_j$。立即前驱函数$\Gamma^1_G:B\rightarrow P(B)$（$P(B)$是$B$的幂集）被定义为$\Gamma^1_G(b_i)=\{b_j\mid(b_i,b_j)\in E\}$ ，可空。类似的可以定理立即后继函数$\Gamma^{-1}_G:B\rightarrow P(B)$被定义为$\Gamma^{-1}_G(b_j)=\{b_i\mid(b_i,b_j)\in E\}$，同样可空。

一个图是连通的，当且仅当任何一个节点可以通过不断使用$\Gamma^1_G$和/或$\Gamma^{-1}_G$得到。注意这里的连通是不讲求方向的。本文讨论的图是有向且连通的（这里的连通应该是指从$e_0$出发能够到达）。

基本块是有唯一入口和唯一出口的指令序列。它可能有多个立即前驱和立即后继，甚至立即前驱、立即后继是自己。控制流图是节点为基本块，边表示控制流路径的图。

图$G=(B,E)$的子图是$G’=(B’,E’)$，其中$B’\subseteq B,E’\subseteq E$，此外$E’\subseteq B’\times B’$。

一个路径$P$是可以一个节点序列$(b_1,b_2,\cdots,b_n)$，其中$b_{i+1}\in\Gamma^1_G(b_i)$（这里假定不存在重边）。边是隐含的$(b_i,b_{i+1})\in E$。节点和边都可以不是唯一的。

节点$q$是节点$p$的后继当且仅当存在路径$P=(p,\dots,q)$。类似可以定义前驱。一个节点可能既是另一个的前驱又是其后继。

一个闭路径，或者环路是一个$b_1=b_n$的路径$P$。如果除了$b_1$和$b_n$，这个路径上的节点没有重复，那称之为简单环路；否则称之为复合环路。

路径$P$的长度$\delta(P)$是路径中边的数目。基于此可以定义两节点之间的最短路：$\delta_\text{min}(p,q)=\min\{\delta(P_i)\mid P_i=(p,\dots,q)\}$。

有向图的一个强连通分量是一个有向子图，其中从任意节点到任意节点。因而每个节点一定在一个闭路径上，且每个节点都是其本身的前驱和后继。闭环路所代表的子图是一种强连通分量的特例。我们可以观察到强连通分量之间有3种关系：

分离：没有共享的节点；
包含：一个强连通分量是另一个的子集；
其他：有部分节点共享，这时候可以合并成一个更大的强连通分量。

如果对于$G$中的任何一个强连通分量$R$，其他的（不是其子图的）强连通分量$R’$与其不共享节点，那么称这个强连通分量$R$为最大的。一个我认为没有太多用的基于强连通分量建立偏序关系的方案就省略了。

支配关系

在一个有向图内，一个没有后继的节点成为出口节点。类似的定义不太适合可能存在循环入边的入口节点，因而入口节点被认为是控制流图中包含程序入口的节点，它是唯一的。然后给这个有向图添加一个没有前驱的初始节点$e_0$作为入口节点的唯一前驱。

如果一个节点$b_i$出现在了每条从$e_0$到$b_k$的路径上，那么称$b_i$是前支配（back dominate；predominate）$b_k$。令$\mathcal{P}=\{P\mid P=(e_0,\dots,b_k)\}$，则其前支配者集合$BD(b_k)$为：

$$BD(b_k)=\{b_i\mid b_i\neq b_k\land b_i\in\cap\mathcal{P}\}$$

译注：这里的支配者把本身排除了，但实际上一般认为任何一个节点支配其本身。$b_k$的立即前支配者$b_i$是前支配者集合中离$b_k$最近的。

$$b_i=\underset{b_j\in BD(b_k)}{\text{arg\,min}}\delta_\text{min}(b_j,b_k)$$

立即前支配者存在且唯一。由于$e_0$是所有节点的前支配者，所以一定存在。如果同时存在两个不同的立即前支配者，它们有相同的距离，必然在不同的路径上；但又由于立即前支配者必然出现在了每条路径上，因而矛盾，一定唯一。

一个有趣的发现是$BD(b_k)$可以通过$\delta_\text{min}$建立严格偏序关系。

$$BD(b_k)=(b_1,b_2,\dots,b_j)~~\text{where}~b_1=e_0$$

在上式中对任意$1\leq m<n\leq j$，有$\delta_\text{min}(b_m)>\delta_\text{min}(b_n)$。不仅如此，对任意的$1\leq m<j$，有$b_m$是$b_{m+1}$的立即前支配者；对任意的$1\leq m<n\leq j$，$b_m$是$b_n$的前支配者。

类似地我们可以定义节点$b_i$后支配节点$b_k$当且仅当$b_i$出现在了每条$b_k$前往任意出口的路径上。同样地，我们可以引入一个节点$x_0$作为所有出口节点的后继。后支配的相关概念和前支配类似，这里不重复表述了。

一个关节节点出现在了每条从入口到出口的路径上。对一有唯一入口$e_0$的图，关节节点就是$e_0$以及$e_0$的后支配者集合。

区间

给定一个节点$h$，区间$I(h)$是指最大的，以$h$为唯一入口的子图，并且该子图中的所有环路都包含$h$。$h$被称为区间头或者头节点。区间可以用其包含的节点表示，区间的边则可以被隐含地得到。

通过选取适当的节点作头节点集合的元素，一个图可以被唯一地划分为区间。以下是一个划分图的算法。

算法用到以下的数据结构：

$H$：存放处理过的和待处理的节点；
$I(h)$：$Map\langle B, Set\langle B\rangle\rangle$，以$h$作为区间头的节点集合。

过程A：

添加$e_0$到$H$中并标记为待处理。
如果$H$有待处理的$h$：
1. 标记$h$为已处理。
2. $I(h)\leftarrow\{h\}$
3. 对所有的$b\in G$且$b\notin I(h)$且$\Gamma^{-1}_G(b)\subseteq I(h)$：（这一步不断重复，直到无法继续，实际实现需要一个工作队列）
  1. $I(h)\leftarrow I(h)\cup\{b\}$
4. 对所有的$b\in G$且$b\notin H$且$b\notin I(h)$且$\Gamma^{-1}_G(b)\cap I(h)\neq\varnothing$：
  1. 添加$b$到$H$中并标记为待处理。

上图包含以下区间：

区间	节点集合
$I(1)$	$1$
$I(2)$	$2$
$I(3)$	$3,4,5,6$
$I(7)$	$7,8$

首先我们证明所有的$I(h)$都是最大的、单入口的，且所有$I(h)$的环路都包含$h$，稍后我们会证明这是个划分。

论断1-3论证算法的正确性。

论断 1 $I(h)$只包含一个入口节点，$h$。

证明假设还存在另一个节点$b\in I(h),b\neq h$是入口节点，那么$b$的立即前导节点中一定存在节点不在$I(h)$中，这与算法中$b$添加到$I(h)$的条件即步骤2.3矛盾。此外可以注意到，$h\neq e_0$有至少一个立即前导节点在$I(h)$外，这可以有步骤$2.3$推导出。

论断 2 $I(h)$中所有的闭环都包含$h$。

证明假设存在一条环路$P=(b_1,b_2,\dots,b_n,b_1)$不包含$h$。我们知道$b_{i-1}$是$b_i$的立即前驱节点。因此只有$b_{i-1}$成为$I(h)$的成员后，$b_i$才能成为；此外，只有$b_n$成为了$I(h)$的成员后之后，$b_1$才能成为。结果就是没有一个能成为$I(h)$的成员。矛盾。

论断 3 $I(h)$是最大的。

证明由步骤2.3可以得到，即不断执行知道无法有更多的节点添加的步骤。

区间具有一些性质，这里在下方给出，这些限制不限于过程A给出的区间，也不需要“最大”这个性质。

论断4-7寻找区间与支配的关系。

论断 4 区间头支配区间内的所有节点。

证明论断1的推论。

对于区间$I(h)$内的任意一个节点$b_i$可以定义一个更加严格的局部后继函数$L^1_I$，将后继限制在区间内的非头节点中：

$$L^1_I(b_i)=\{b_j\mid b_j\in\Gamma^1_I(b_i)\land b_j\neq h\}$$

借助这个局部后继函数，可以定义局部前导函数$L^{-1}_I$。特别地我们有$L^{-1}_I(h)=\varnothing$。

使用局部后继函数，可以在区间内定义一种特殊的路径：前向路径$F=(b_1,b_2,\dots,b_n)$，其中$b_{i+1}\in L^1_I(b_i)$。可以注意到从$h$到$I(h)$内某节点的所有路径上的节点都在$I(h)$内（这是支配决定的）。

论断 5 可以通过局部后继函数在区间内的节点定义偏序关系。也就是对于给定的区间，可以表示为节点的序列$I(h)=(b_1=h,b_2,\dots,b_n)$，并且对于所有的$i<j$，要么$b_i$在某个前向路径上是$b_j$的前驱，要么$b_i$和$b_j$不同时出现在任何一个前向路径上。

证明由过程A可以看出一个非$h$的节点在变成$I(h)$成员前，其立即前驱节点必须已经成为$I(h)$的成员。

其实这个区间序列就是过程A中添加到$I(h)$的先后顺序。

论断 6 前支配列表中序列的相对顺序和区间序列是一致的。...

这篇文章的内容来自Allen的Control Flow Analysis¹。

基础概念

图$G=(B,E)$的子图是$G’=(B’,E’)$，其中$B’\subseteq B,E’\subseteq E$，此外$E’\subseteq B’\times B’$。

节点$q$是节点$p$的后继当且仅当存在路径$P=(p,\dots,q)$。类似可以定义前驱。一个节点可能既是另一个的前驱又是其后继。

一个闭路径，或者环路是一个$b_1=b_n$的路径$P$。如果除了$b_1$和$b_n$，这个路径上的节点没有重复，那称之为简单环路；否则称之为复合环路。

路径$P$的长度$\delta(P)$是路径中边的数目。基于此可以定义两节点之间的最短路：$\delta_\text{min}(p,q)=\min\{\delta(P_i)\mid P_i=(p,\dots,q)\}$。

分离：没有共享的节点；
包含：一个强连通分量是另一个的子集；
其他：有部分节点共享，这时候可以合并成一个更大的强连通分量。

支配关系

$$BD(b_k)=\{b_i\mid b_i\neq b_k\land b_i\in\cap\mathcal{P}\}$$

译注：这里的支配者把本身排除了，但实际上一般认为任何一个节点支配其本身。$b_k$的立即前支配者$b_i$是前支配者集合中离$b_k$最近的。

$$b_i=\underset{b_j\in BD(b_k)}{\text{arg\,min}}\delta_\text{min}(b_j,b_k)$$

一个有趣的发现是$BD(b_k)$可以通过$\delta_\text{min}$建立严格偏序关系。

$$BD(b_k)=(b_1,b_2,\dots,b_j)~~\text{where}~b_1=e_0$$

一个关节节点出现在了每条从入口到出口的路径上。对一有唯一入口$e_0$的图，关节节点就是$e_0$以及$e_0$的后支配者集合。

区间

通过选取适当的节点作头节点集合的元素，一个图可以被唯一地划分为区间。以下是一个划分图的算法。

算法用到以下的数据结构：

$H$：存放处理过的和待处理的节点；
$I(h)$：$Map\langle B, Set\langle B\rangle\rangle$，以$h$作为区间头的节点集合。

过程A：

添加$e_0$到$H$中并标记为待处理。
如果$H$有待处理的$h$：
1. 标记$h$为已处理。
2. $I(h)\leftarrow\{h\}$
3. 对所有的$b\in G$且$b\notin I(h)$且$\Gamma^{-1}_G(b)\subseteq I(h)$：（这一步不断重复，直到无法继续，实际实现需要一个工作队列）
  1. $I(h)\leftarrow I(h)\cup\{b\}$
4. 对所有的$b\in G$且$b\notin H$且$b\notin I(h)$且$\Gamma^{-1}_G(b)\cap I(h)\neq\varnothing$：
  1. 添加$b$到$H$中并标记为待处理。

上图包含以下区间：

区间	节点集合
$I(1)$	$1$
$I(2)$	$2$
$I(3)$	$3,4,5,6$
$I(7)$	$7,8$

首先我们证明所有的$I(h)$都是最大的、单入口的，且所有$I(h)$的环路都包含$h$，稍后我们会证明这是个划分。

论断1-3论证算法的正确性。

论断 1 $I(h)$只包含一个入口节点，$h$。

论断 2 $I(h)$中所有的闭环都包含$h$。

论断 3 $I(h)$是最大的。

证明由步骤2.3可以得到，即不断执行知道无法有更多的节点添加的步骤。

区间具有一些性质，这里在下方给出，这些限制不限于过程A给出的区间，也不需要“最大”这个性质。

论断4-7寻找区间与支配的关系。

论断 4 区间头支配区间内的所有节点。

证明论断1的推论。

对于区间$I(h)$内的任意一个节点$b_i$可以定义一个更加严格的局部后继函数$L^1_I$，将后继限制在区间内的非头节点中：

$$L^1_I(b_i)=\{b_j\mid b_j\in\Gamma^1_I(b_i)\land b_j\neq h\}$$

借助这个局部后继函数，可以定义局部前导函数$L^{-1}_I$。特别地我们有$L^{-1}_I(h)=\varnothing$。

证明由过程A可以看出一个非$h$的节点在变成$I(h)$成员前，其立即前驱节点必须已经成为$I(h)$的成员。

其实这个区间序列就是过程A中添加到$I(h)$的先后顺序。

论断 6 前支配列表中序列的相对顺序和区间序列是一致的。...

这篇文章的内容来自Allen的Control Flow Analysis¹。

基础概念

图$G=(B,E)$的子图是$G’=(B’,E’)$，其中$B’\subseteq B,E’\subseteq E$，此外$E’\subseteq B’\times B’$。

节点$q$是节点$p$的后继当且仅当存在路径$P=(p,\dots,q)$。类似可以定义前驱。一个节点可能既是另一个的前驱又是其后继。

一个闭路径，或者环路是一个$b_1=b_n$的路径$P$。如果除了$b_1$和$b_n$，这个路径上的节点没有重复，那称之为简单环路；否则称之为复合环路。

路径$P$的长度$\delta(P)$是路径中边的数目。基于此可以定义两节点之间的最短路：$\delta_\text{min}(p,q)=\min\{\delta(P_i)\mid P_i=(p,\dots,q)\}$。

分离：没有共享的节点；
包含：一个强连通分量是另一个的子集；
其他：有部分节点共享，这时候可以合并成一个更大的强连通分量。

支配关系

$$BD(b_k)=\{b_i\mid b_i\neq b_k\land b_i\in\cap\mathcal{P}\}$$

译注：这里的支配者把本身排除了，但实际上一般认为任何一个节点支配其本身。$b_k$的立即前支配者$b_i$是前支配者集合中离$b_k$最近的。

$$b_i=\underset{b_j\in BD(b_k)}{\text{arg\,min}}\delta_\text{min}(b_j,b_k)$$

一个有趣的发现是$BD(b_k)$可以通过$\delta_\text{min}$建立严格偏序关系。

$$BD(b_k)=(b_1,b_2,\dots,b_j)~~\text{where}~b_1=e_0$$

一个关节节点出现在了每条从入口到出口的路径上。对一有唯一入口$e_0$的图，关节节点就是$e_0$以及$e_0$的后支配者集合。

区间

通过选取适当的节点作头节点集合的元素，一个图可以被唯一地划分为区间。以下是一个划分图的算法。

算法用到以下的数据结构：

$H$：存放处理过的和待处理的节点；
$I(h)$：$Map\langle B, Set\langle B\rangle\rangle$，以$h$作为区间头的节点集合。

过程A：

添加$e_0$到$H$中并标记为待处理。
如果$H$有待处理的$h$：
1. 标记$h$为已处理。
2. $I(h)\leftarrow\{h\}$
3. 对所有的$b\in G$且$b\notin I(h)$且$\Gamma^{-1}_G(b)\subseteq I(h)$：（这一步不断重复，直到无法继续，实际实现需要一个工作队列）
  1. $I(h)\leftarrow I(h)\cup\{b\}$
4. 对所有的$b\in G$且$b\notin H$且$b\notin I(h)$且$\Gamma^{-1}_G(b)\cap I(h)\neq\varnothing$：
  1. 添加$b$到$H$中并标记为待处理。

上图包含以下区间：

区间	节点集合
$I(1)$	$1$
$I(2)$	$2$
$I(3)$	$3,4,5,6$
$I(7)$	$7,8$

首先我们证明所有的$I(h)$都是最大的、单入口的，且所有$I(h)$的环路都包含$h$，稍后我们会证明这是个划分。

论断1-3论证算法的正确性。

论断 1 $I(h)$只包含一个入口节点，$h$。

论断 2 $I(h)$中所有的闭环都包含$h$。

论断 3 $I(h)$是最大的。

证明由步骤2.3可以得到，即不断执行知道无法有更多的节点添加的步骤。

区间具有一些性质，这里在下方给出，这些限制不限于过程A给出的区间，也不需要“最大”这个性质。

论断4-7寻找区间与支配的关系。

论断 4 区间头支配区间内的所有节点。

证明论断1的推论。

对于区间$I(h)$内的任意一个节点$b_i$可以定义一个更加严格的局部后继函数$L^1_I$，将后继限制在区间内的非头节点中：

$$L^1_I(b_i)=\{b_j\mid b_j\in\Gamma^1_I(b_i)\land b_j\neq h\}$$

借助这个局部后继函数，可以定义局部前导函数$L^{-1}_I$。特别地我们有$L^{-1}_I(h)=\varnothing$。

证明由过程A可以看出一个非$h$的节点在变成$I(h)$成员前，其立即前驱节点必须已经成为$I(h)$的成员。

其实这个区间序列就是过程A中添加到$I(h)$的先后顺序。

论断 6 前支配列表中序列的相对顺序和区间序列是一致的。...