代碼基本知識點

代碼基本塊

嚴格的來說，基本塊是滿足下列條件的一組連續指令代碼，程式的執行（控制流）只能從基本塊的第一條陳述句（入口陳述句）進入，從基本塊的最后一條陳述句離開，

int a,b;
a = getchar();
b = getchar();
if (a>b){
  a = a*b;
  print(a);
}
else {
  a = a/b;
  print(a);
}
### if/else

代碼5_6行與910行兩個代碼塊有不同的進入條件，下一個執行代碼塊的選擇取決于第4行的判斷條件

int a,b;
a = getchar();
b = getchar();
while (a>b){
  a = a*b;
  print(a);
}
# while

第4行代碼while陳述句包含第5行代碼，該行代碼與其他行代碼分開，執行條件是第4行的判斷陳述句

int a,b,c;
a = getchar();
b = getchar();
for (;a,b;a++){
  c = a+b;
}
print(c);
### for

第4行代碼for陳述句包含第5行代碼，該行代碼與其他行代碼分開，執行條件是第4行的判斷陳述句

控制流圖CFG

當程式被劃分為基本塊后，如果將基本塊視為一個基本單元節點，基本塊之間在程式執行流程上互為前驅和后繼的關系可以視為兩個基本塊村子一條邊，則整個程式可以轉換為一個有向圖，稱為控制流圖（Control Flow Graph）

int max(int x, int y){
  int tmp = 0;        -----0
  if (x>y){           -----0
    tmp =x;           -----1
  }
  else{
    tmp = y;          -----2
  }
  return tmp;         -----3
}

節點0是節點1和2的嚴格直接前必經節點，而節點3是節點1和2的嚴格直接后必經節點，

根據基本塊構造的有向圖G可以表示為四元組G = {V, E, Entry, Exit}，其中
V是基本塊節點的集合
E是基本塊之間邊的集合
Entry表示入口基本塊節點
Exit表示結束基本塊節點
程式執行時，從Entry代表的基本塊開始執行，沿著控制邊遍歷執行基本塊，最后到Exit代表的基本塊時執行結束，

資料流分析

到達與可到達

針對變數x的一個定義陳述句s，稱該陳述句對變數x的定義到達程式的某個代碼位置P，當且僅當在程式控制流圖(CFG)中存在從該定義對應的陳述句到位置P陳述句的一條路徑，并且該路徑上沒有變數x的其他定義，
稱陳述句s是代碼位置P的一個可到達定義，

第2條陳述句對變數b賦值，在該陳述句執行后變數b的值被算術運算式a+1的值所替代，
另外，每條陳述句前后都有對應的代碼位置標識，分別為P1, P2, P3, P4, P5, P6，程式執行時可能的路徑為<P1, P2, P3, P4, P5, P6>或者<P1, P2, P3, P4, P1, P2, P3, P4, P5, P6>，

第二條陳述句對變數b賦值，在該陳述句執行后變數b的值被算術運算式a+1的值所替代，

陳述句3對變數a進行定義，且陳述句4和5均未對變數a進行定義，那么，陳述句3就是代碼位置P4、P5和P6的一個可到達定義

簡單一點來說，一個賦值陳述句a在他的賦值被更改前運行的所有陳述句的有一個可到達定義a，

變數定義和參考概念

程式切片

程式切片通常包括3個步驟

1、程式依賴關系提取
主要是從程式中提取各類資訊，包括控制流和資料流資訊，形成程式依賴圖，
2、切片規則制定
主要是依據具體的程式分析需求設計切片準則，
3、切片生成
主要是依據切片準則選擇相應的程式切片方法，然后對提取的依賴關系進行分析處理，從而生成程式切片，

程式切片的分類

按照是否在切片中考慮程式的具體輸入，可以劃分為靜態切片和動態切片，
按照切片要提取的是對關注變數有影響的代碼片段還是被關注變數所影響，可以劃分為前向切片和后向切片，
按照提取的切片是否為可執行程式，可以劃分為可執行的切片和不可執行的切片等，

靜態切片

目前，靜態程式切片主要有兩種方法
基于資料流方程的切片方法
基于程式依賴圖可達性的切片方法
靜態程式切片方法均是利用資料依賴和控制依賴關系進行分析以獲得程式切片，

靜態程式切片方法
基于資料流方程的切片方法
基于圖可達性演算法的切片方法

基于資料流方程進行切片的方法主要是通過迭代計算控制流圖中每個節點的相關變數集合，迭代分析陳述句間的資料依賴關系和控制依賴關系，最侄訓得每條陳述句中與切片準則相關的變數的集合，

基于圖可達性演算法的切片方法

基于圖可達性進行切片的方法與圖遍歷方法基本相同，
首先需要計算出目標程式的控制依賴和資料依賴關系，構建程式依賴圖，
然后從切片準則所對應的節點出發，沿著資料依賴邊和控制依賴邊進行圖遍歷，所有遍歷可達的節點均加入到切片中

這邊其實最重要的一步是畫出程式依賴圖，這是靜態切片的關鍵：

int main(){
  int x=0, y, z;
  int i = 0;
  z = 0;
  y = getchar();
  for(;i<100;i++)
    if(i%2 == 1)
      x += y*i;
    else
      z += 1;
    print(x);
    print(z);
}

切片舉例：

基于依賴圖的靜態切片示例

針對切片準則<12, {z}>，切片計算從節點print(z);開始進行圖遍歷，
其中，以灰色填充的節點是遍歷得到的節點，節點旁邊的圓圈內的數字表示按照深度優先遍歷的順序，
最后得到的針對切片準則的后向切片為{3, 4, 6, 7, 10, 12}，

動態切片

動態切片是一種僅關注在給定某個輸入條件下對程式中某點的變數有影響的陳述句，
動態切片與靜態切片的最大差異在于是否考慮了程式輸入，
當考慮程式輸入時，程式中的某些路徑將不可達，從而能夠確定程式依賴圖的部分節點與切片準則不相關，可以從原始程式依賴圖中洗掉這些節點以縮小圖的規模，
與靜態切片相比，通常動態切片給出的結果更有針對性，切片規模更小而且精確，

代碼片段及其程式依賴圖示例

采用靜態切片方法中的基于圖可達性的切片方法計算其切片，只需要從切片準則對應的節點開始遍歷程式依賴圖，并提取所有可到達的節點對應的陳述句

代碼片段針對<10, {y}>的靜態切片示例
針對切片準則<10, {y}>，靜態切片包括節點1、2、3、5、6、8和10，
切片中節點3、6和8是給y賦值的陳述句，均資料依賴于節點1，分別控制依賴于節點2和5，而節點2和5均資料依賴于節點1，因此，節點1中x的取值至關重要，
假設給定節點1中的x值為1，則節點1、2、5、8可達，而節點3、6不可達，在遍歷程式依賴圖以獲取程式切片時可以忽略節點3和6，最終遍歷裁剪后的程式依賴圖獲得的程式切片為{1, 2, 5, 8, 10}，

動態程式切片方法
基于程式依賴圖的動態切片方法
基于動態依賴圖的動態切片方法

基于程式依賴圖的動態切片方法

基于程式依賴圖的動態切片方法是通過裁剪程式依賴圖來獲得動態切片，
動態切片除了要考慮切片準則以外，還要考慮程式的具體輸入，
當程式中某個未指定具體值的變數被賦予某個特定值時，程式運行能夠得到一條由執行指令構成的動態執行路徑，該執行路徑稱為執行歷史，
執行歷史示例
若給N指定一個具體值2，程式動態運行形成的執行歷史可以表示為節點編號的序列：<1, 2, 3, 4, 51, 61, 71, 81, 52, 62, 72, 82, 53, 9>，
其中，節點編號有上標表示該節點在執行歷史中不止一次出現，上標是其出現次數的遞增編號，例如53表示當前是第3次執行陳述句5，

N = getchar();
z = 0;
y = 0;
i = 1;
while(i<=N){
  z = f1(z,y);
  y = f2(y);
  i++;
}
print(z);

但上述動態切片方法存在的不足：產生的切片不夠精確，

任何一個節點(陳述句)可能依賴于多個其他節點，這些依賴關系需要通過執行歷史中的多條執行路徑來體現，因此，執行歷史中的執行路徑雖然無法覆寫該節點與依賴節點之間的全部執行路徑，但只要某個節點在執行歷史中，則該節點關聯的所有邊對于圖遍歷都是有效邊，仍然能夠通過遍歷執行歷史沒有覆寫的路徑，把不相關節點也加入到切片中，導致最侄訓得的切片過大，

動態依賴圖（DDG）

程式依賴圖是一種靜態表示，無法體現同一陳述句(節點)的不同次執行的區別，
動態依賴圖(Dynamic Dependence Graph, DDG)，不但能夠表示靜態程式依賴關系，同時也能表示程式的動態執行程序，

DDG的構造方法
遍歷執行歷史，依次為其中每個陳述句(節點)的每一次出現均創建一個新的節點；
同時，節點之間僅在因為程式執行而導致有實質的控制和依賴關系時才建立一條依賴邊，

N = getchar();
i = 1;
while(i <= N){
  x = getchar();
  if (x<0)
    y = f1(x);
  else
    y = f2(x);
  z = f3(y);
  print(z);
  i++;
}

當N=3，x依次取-4、3和-2時，執行歷史為<1, 2, 31, 41, 51, 61, 81, 91, 101, 32, 42, 52, 71, 82, 92, 102, 33, 43, 53, 62, 83, 93, 103, 34>，
在動態依賴圖中，3行節點對應于回圈的3次執行，重復編號代表該節點所在陳述句的多次執行，
在前兩次回圈中，節點8依賴的節點不同
第一次回圈時節點8參考的變數y是通過節點6的賦值陳述句定義的；
第二次回圈時是通過節點7的賦值陳述句定義的，

基于DDG的動態切片計算比較簡單，僅需要從切片準則對應的節點開始遍歷動態依賴圖，將所有可達到的節點都添加到切片中，
例如，針對上述代碼片段，當N值為3，x值為-4、3和-2的條件下，針對切片準則<9, {z}, I0>的動態切片為{1, 2, 3, 4, 5, 6, 8, 9, 10}，

切片準則包含兩個要素

• 切片的目標變數

• 開始切片的代碼位置 嚴格地說，程式P的切片準則是一個二元組<n, V>，其中n是程式中一條陳述句的編號，V是切片所關注的變數集合，該集合是P中變數的一個子集，

本文來自博客園，作者：ivanlee717，轉載請注明原文鏈接：https://www.cnblogs.com/ivanlee717/p/16798245.html

標籤：其他

上一篇：代碼塊+控制流圖+程式切片的學習

下一篇：百度ueditor工具列配置