[發(fā)明專利]一種無損壓縮系統(tǒng)依賴圖的方法及裝置

有效

• 申請?zhí)枺?/td>: 201210584770.6
• 申請日: 2012-12-28
• 公開（公告）號: CN103902273B
• 公開（公告）日: 2017-07-07
• 發(fā)明（設計）人: 李豐;霍瑋;陳聰明;衷璐潔;張兆慶;馮曉兵
• 申請（專利權）人: 華為技術有限公司;中國科學院計算技術研究所
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京中博世達專利商標代理有限公司11274
• 代理人: 申健

技術領域

本發(fā)明涉及計算機領域，尤其涉及一種無損壓縮系統(tǒng)依賴圖的方法及裝置。

背景技術

程序靜態(tài)切片是一種重要的程序分析技術，廣泛應用于程序理解、測試、調試、驗證、維護，能夠幫助程序員提取所關注代碼，降低程序分析、錯誤驗證、維護等領域。目前，主流的切片工具均采用基于系統(tǒng)依賴圖的圖可達算法。

系統(tǒng)依賴圖(System Dependence Graph，SDG)是一個有向圖，是對程序依賴圖(Program Dependence Graph，PDG)的擴展。以系統(tǒng)依賴圖為基礎的程序切片算法，是通過遍歷系統(tǒng)依賴圖，從中提取出可能影響某個變量在程序中某個位置上的取值的程序代碼。但是現(xiàn)有的切片算法開銷與精度都無法滿足大規(guī)模使用程序的需求。

因此，為了解決上述問題，現(xiàn)有技術通常采用的技術包括：一、通過提高別名分析精度降低SDG的規(guī)模，因為SDG的規(guī)模不僅決定其自身的計算與存儲的時空開銷，還直接影響切片的效率。其中，別名分析，也稱指針分析，是一種識別程序中可能用兩種以上的方法訪問的存儲位置的靜態(tài)分析技術。別名分析所得出的結果是基于SDG的程序切片技術中用于創(chuàng)建系統(tǒng)依賴圖時所需的輸入之一。二、通過限制切片算法的上下文敏感性(Context Sensitivity)來減少切片算法遍歷SDG的開銷。

在實現(xiàn)上述降低SDG規(guī)模和減少切片算法的時空開銷的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術中至少存在如下問題：

提高指針分析的精度雖然可以適度降低SDG的規(guī)模，但高精度的指針分析算法本身不僅需要高昂的時空開銷，也幾乎無助于切片精度的提高。而采用限制切片算法的上下文敏感性來緩解遍歷SDG的開銷，會使切片的精度降低。

發(fā)明內容

本發(fā)明的實施例提供一種無損壓縮系統(tǒng)依賴圖的方法及裝置，能夠實現(xiàn)系統(tǒng)依賴圖的無損壓縮，并降低系統(tǒng)依賴圖的規(guī)模，從而降低以系統(tǒng)依賴圖為基礎的切片算法的開銷。

為達到上述目的，本發(fā)明的實施例采用如下技術方案：

第一方面，提供一種無損壓縮系統(tǒng)依賴圖的方法，包括：

根據別名分析信息獲取程序中所有變量間的等價關系，并根據所述等價關系將所有變量分為不同的等價類，其中，所述別名分析信息是根據別名分析算法得到的；

根據系統(tǒng)依賴圖中的各個節(jié)點所代表的變量所屬的等價類為所述系統(tǒng)依賴圖中的各個節(jié)點設置鍵值；

根據所述系統(tǒng)依賴圖中的各個節(jié)點的鍵值對所述系統(tǒng)依賴圖進行壓縮。

在第一種可能的實現(xiàn)方式中，結合第一方面，所述根據別名分析信息獲取程序中所有變量間的等價關系，并根據所述等價關系將所有變量分為不同的等價類包括：

根據所述別名分析信息建立從第一變量集合到指向所述變量集合中每個變量的指針集合的冪集的映射f，所述第一變量集合為程序中所有變量的集合；

根據所述映射f建立從所述指針集合的冪集到第二變量集合的映射f′，以將所有變量分為不同的等價類；所述第二變量集合為被同一組指針所指向的變量的集合。

在第二種可能的實現(xiàn)方式中，結合第一方面或第一方面的第一種可能的實現(xiàn)方式，所述根據所述別名分析信息建立從第一變量集合到指向所述變量集合中每個變量的指針集合的冪集的映射f包括：

為程序中的每個指針變量建立一個由該指針變量所指向的變量構成的指向集，為所有指向集中出現(xiàn)的每個變量建立一個空集合；

將每個指針變量添加到該指針變量所指向的變量對應的空集合中，以得到所述映射f。

在第三種可能的實現(xiàn)方式中，結合第一方面或第一方面的第一種可能的實現(xiàn)方式或第一方面的第二種可能的實現(xiàn)方式，根據所述映射f建立從所述指針集合的冪集到第二變量集合的映射f′，以將所有變量分為不同的等價類包括：

建立第i個空集合，將所述映射f的定義域中一個變量var，以及所有被映射到f(var)的變量添加到所述第i個空集合中，得到第i個等價類，并對所述第i個等價類設置唯一的編號，并從所述映射f的定義域中刪除添加到所述第i個空集合中的變量，直至映射f的定義域中的變量個數(shù)為0；其中，i的起始值為1，所述變量var表示映射f的定義域中的任意一個變量。

在第四種可能的實現(xiàn)方式中，結合第一方面或第一方面的第一種可能的實現(xiàn)方式至第一方面的第三種可能的實現(xiàn)方式，所述根據系統(tǒng)依賴圖中的各個節(jié)點所代表的變量所屬的等價類為所述系統(tǒng)依賴圖中的各個節(jié)點設置鍵值包括：

將所述系統(tǒng)依賴圖上的各個節(jié)點所代表的變量所屬的等價類的編號對應設置為所述各個節(jié)點的鍵值。