程序依賴圖

• 一.控制依賴
• • 1.1.示例1
  • 1.2.示例2
  • 1.3.示例3
  • 求CPG
• 二.數據依賴

程序依賴圖，主要包括控制依賴圖（CDG）和數據依賴圖（DDG），在做程序切片時有重要作用。這里對它們的定義引用SySeVR論文中的話。

一.控制依賴

定義：（這里我對它的表達進行了一些簡化，這里考慮的是一個函數內的情況）：給定函數 $f$ 的 CFG $G=(V,E)$，以及2個結點 $n_i,n_j$（假定 $j$ 在 $i$ 后面），并且 $i=j$。

• 如果CFG中所有從 $n_i$ 開始到 end 結點的路徑都經過 $n_j$，那么稱 $n_j$ post-dominate $n_i$（后面的支配前面的）。

• 如果存在CFG中存在一個從 $n_i$ 到 $n_j$ 的路徑，并且滿足 $n_j$ post-dominate 這個路徑上除了 $n_i$ 和 $n_j$ 之外的所有結點并且不post-dominate $n_i$。那么 $n_j$ 控制依賴于 $n_i$。

1.1.示例1

以下面偽代碼為例（$S_i$ 表示statement i， $C_i$ 表示condition i）：

S1; if (C1){S2;S3; } elseS4; 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; } elseS4; 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$ 的 CFG $G=(V,E)$，以及2個結點 $n_i,n_j$（假定 $j$ 在 $i$ 后面），并且 $i=j$。CFG存在1個路徑從 $n_i$ 到 $n_j$。如果 $n_i$ 中計算得到的值在 $n_j$ 中用到了，那么 $n_j$ 數據依賴于 $n_i$

比如:

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）的理解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。