Java教程

程序分析-对程序依赖图(PDG)的理解

本文主要是介绍程序分析-对程序依赖图(PDG)的理解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

程序依赖图

  • 一.控制依赖
    • 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中,可以看到 S1C1END 的2条路径都经过了 S5,S6,因此S5,S6 post-dominate C1。但是S2,S3,S4不post-dominate C1S1

对于路径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

在这里插入图片描述

重点看 C1S2 S3 的关系。C1->S2->S3S3不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 -> C1C1 -> 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)或者函数调用引用赋值的情况。

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

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

这篇关于程序分析-对程序依赖图(PDG)的理解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!