程序依赖图

• 一.控制依赖
• • 1.1.示例1
  • 1.2.示例2
  • 1.3.示例3
  • 求CPG
• 二.数据依赖

程序依赖图，主要包括控制依赖图（CDG）和数据依赖图（PDG），在做程序切片时有重要作用。这里对它们的定义引用SySeVR论文中的话。

一.控制依赖

定义：（这里我对它的表达进行了一些简化，这里考虑的是一个函数内的情况）：给定函数 f f f 的 CFG G = ( V , E ) G = (V, E) G=(V,E)，以及2个结点 n i , n j n_i, n_j ni​,nj​（假定 j j j 在 i i i 后面），并且 i ≠ j i \neq j i​=j。

• 如果CFG中所有从 n j n_j nj​ 开始到 end 结点的路径都经过 n i n_i ni​，那么称 n j n_j nj​ post-dominate n i n_i ni​（后面的支配前面的）。

• 如果存在CFG中存在一个从 n i n_i ni​ 到 n j n_j nj​ 的路径，并且满足 n j n_j nj​ post-dominate 这个路径上除了 n i n_i ni​ 和 n j n_j nj​ 之外的所有结点并且不post-dominate n i n_i ni​。那么 n j n_j nj​ 控制依赖于 n i n_i ni​。

1.1.示例1

以下面伪代码为例（ S i S_i Si​ 表示statement i， C i C_i Ci​ 表示condition i）：

S1;
if (C1){
    S2;
    S3;
}
else
    S4;
S5;
S6;

CFG如下

在这个CFG中，可以看到 S1 和 C1 到 END 的2条路径都经过了 S5,S6，因此S5，S6 post-dominate C1。但是S2,S3,S4不post-dominate C1和S1。

对于路径C1->S2->S3 来说，S3 post-dominate S2 但是不post-dominate C1，所以 S3 依赖于 C1。依此类推，可以发现控制依赖源点是condition，终点是block中的语句。

所以CPG为

1.2.示例2

那么现在来一个嵌套循环的看看：

S1;
if (C1){
    S2;
    if (C2)
       S7;
}
else
    S4;
S5;
S6;

CFG:

首先看C1 -> S2 -> C2 中，C2 post-dominate S2，但是C1 -> S2 -> C2 -> S7 中，S7 既不post-dominate C2 也不 post-dominate S2，所以依赖的作用域只在1层条件中。

CPG：

1.3.示例3

S1;
while (C1){
    S2;
    S3;
}
S4;

CFG

重点看 C1 和 S2 S3 的关系。C1->S2->S3 中 S3不post-dominate C1 并且post-dominate S2，所以 S3 依赖于 C1。依此类推

CPG为

可以看到上面得到的CPG都是树状结构，父节点为条件，子结点为block中的语句。

求CPG

如何求CPG还没找到一个靠谱的资料，不过按照这篇博客。求CPG首先求前向支配树FDT。FDT由post-dominate关系构成，不过这里只保存直接post-dominate。比如示例1中，存在

S6 -> C1
S5 -> C1
S6 -> S5

那个 S6 -> C1 会被删除。那么示例1计算出来的FDT如下

然后就是进行抵消操作，把CFG中能抵消的边都抵消了。比如S1 -> C1 和 C1 -> S1 互相抵消。不过这还剩一个问题，就是像 C1 -> S3 这种依赖是怎么产生的？或许计算CFG时就把这些加上（跟AST求并集？）？

二.数据依赖

定义：给定函数 f f f 的 CFG G = ( V , E ) G = (V, E) G=(V,E)，以及2个结点 n i , n j n_i, n_j ni​,nj​（假定 j j j 在 i i i 后面），并且 i ≠ j i \neq j i​=j。CFG存在1个路径从 n i n_i ni​ 到 n j n_j nj​。如果 n i n_i ni​ 中计算得到的值在 n j n_j nj​ 中用到了，那么 n j n_j nj​ 数据依赖于 n i n_i ni​

比如:

S1: a = b;
S2: b = c + d;
S3: e = a + d;
S4: b = 3;
S5: f = b * 2;

那么存在数据依赖边

S1 -> S3 (S1 def a, S3 use a)
S4 -> S5 (S4 def b, S5 use b)

虽然S2也def了b，但是并没有被使用。

上述数据依赖计算过程：

• 只考虑了 = 赋值情况，没有考虑指针地址（scanf）或者函数调用引用赋值的情况。

• 没有考虑指针变量别名的情况。

一般数据依赖分析之前都需要指针分析，以方便别名分析，不过这样开销太大。