[發明專利]一種無損壓縮系統依賴圖的方法及裝置

有效

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

1.一種無損壓縮系統依賴圖的方法，其特征在于，包括：

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

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

根據所述系統依賴圖中的各個節點的鍵值對所述系統依賴圖進行壓縮。

2.根據權利要求1所述的無損壓縮系統依賴圖的方法，其特征在于，所述根據別名分析信息獲取程序中所有變量間的等價關系，并根據所述等價關系將所有變量分為不同的等價類包括：

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

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

3.根據權利要求2所述的無損壓縮系統依賴圖的方法，其特征在于，所述根據所述別名分析信息建立從第一變量集合到指向所述變量集合中每個變量的指針集合的冪集的映射f包括：

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

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

4.根據權利要求2所述的無損壓縮系統依賴圖的方法，其特征在于，根據所述映射f建立從所述指針集合的冪集到第二變量集合的映射f'，將所有變量分為不同的等價類包括：

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

5.根據權利要求1至4任意一項所述的無損壓縮系統依賴圖的方法，其特征在于，所述根據系統依賴圖中的各個節點所代表的變量所屬的等價類為所述系統依賴圖中的各個節點設置鍵值包括：

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

6.根據權利要求1至4任意一項所述的無損壓縮系統依賴圖的方法，其特征在于，所述根據所述系統依賴圖中的各個節點的鍵值對所述系統依賴圖進行壓縮包括：

若所述系統依賴圖上的任意一個節點的前驅節點集合或者后繼節點集合中的任意兩個節點擁有相同的鍵值，并且所述任意兩個節點中有一個是副作用節點，則將所述任意兩個節點中的副作用節點的出入邊依次轉化為所述任意兩個節點中另外一個節點的出入邊；

刪除所述系統依賴圖中所有孤立的節點；

合并所述系統依賴圖上具有相同的源點和匯點的有向邊。

7.一種系統依賴圖無損壓縮裝置，其特征在于，包括：

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

鍵值設置模塊，用于根據系統依賴圖中的各個節點所代表的變量所屬的等價類為所述系統依賴圖中的各個節點設置鍵值；

依賴圖壓縮模塊，用于根據所述系統依賴圖中的各個節點的鍵值對所述系統依賴圖進行壓縮。

8.根據權利要求7所述的系統依賴圖無損壓縮裝置，其特征在于，所述等價類獲取模塊包括：

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

等價類獲取子模塊，用于根據所述映射f建立從所述指針集合的冪集到第二變量集合的映射f'，所述第二變量集合為被同一組指針所指向的變量的集合。