[發明專利]一種基于樹優化的程序依賴關系分析方法及系統

有效

• 申請號: 201410055841.2
• 申請日: 2014-02-19
• 公開（公告）號: CN103793653A
• 公開（公告）日: 2014-05-14
• 發明（設計）人: 陳愷;趙險峰;張穎君
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F21/57
• 分類號: G06F21/57
• 代理公司: 北京輕創知識產權代理有限公司 11212
• 代理人: 楊立

1.一種基于樹優化的程序依賴關系分析方法，其特征在于，包括：

步驟1，以函數為基本單位進行程序依賴關系分析，將函數中的連續指令劃分為多個基本塊，且保證每個基本塊有單一入口和單一出口；

步驟2，針對每個基本塊構建相應的指令依賴樹和指令依賴森林；

步驟3，分析各基本塊的指令依賴樹和指令依賴森林，去除未改變原狀態的指令，去除依賴于特殊寄存器的指令依賴樹；

步驟4，分析各基本塊的指令依賴樹和指令依賴森林，從前一基本塊中去除在其后續各基本塊中有重復定義但未被使用的變量對應的指令依賴樹；

步驟5，根據步驟3和步驟4的處理結果，選取內存索引中不能靜態計算寄存器值的指令所在的位置，將該指令位置之前的位置作為動態插裝位置；

步驟6，在所有動態插裝位置上插裝統一化的影子指令，通過影子指令分析指令依賴樹和指令依賴森林。

2.根據權利要求1所述的程序依賴關系分析方法，其特征在于，所述步驟2中，若指令中定義的一個變量i沒出現在指令依賴樹的節點集合V中，則將該變量i增加到指令依賴樹的節點集合V中，并增加從該節點i到指令所用到的變量相應的邊。

3.根據權利要求1或2所述的程序依賴關系分析方法，其特征在于，所述步驟2中，若指令中定義的一個變量i出現在指令依賴樹的節點集合V中，且其是指令依賴森林的根節點，則刪除從節點i到其孩子節點的邊，并增加從i到指令所用到的變量集合相應的邊；若i是指令依賴森林的葉子節點，則i沒有在基本塊中重復定義，增加新的節點i₁，作為塊入口i的初始狀態，并用i₁取代i，增加從i到相應指令中使用變量的邊；否則，增加i的父節點到i的孩子節點的邊，并去掉i的父節點到i的邊及i到其孩子節點的邊。

4.根據權利要求1所述的程序依賴關系分析方法，其特征在于，所述步驟4具體包括：

步驟41，定義一個記錄在一個基本塊中被定義但未被使用的變量的集合S；

步驟42，分析函數的最后一個基本塊B，如果該基本塊的最后一個指令是一個函數調用指令，則清空S；

步驟43，若最后一個基本塊是一個分支塊，則重新定義S集合為兩個分支的定義集合的交集，若存在一個分支未被分析過，則返回分析該分支；

步驟44，如果基本塊的非葉節點存在于步驟43執行后的S中，則刪除該非葉節點；

步驟45，更新集合S，重復執行步驟41至步驟44，優化基本塊B前面的基本塊。

5.根據權利要求1所述的程序依賴關系分析方法，其特征在于，所述步驟5中，若在指令依賴森林中沒有間接內存地址，則動態插裝位置為基本塊中的任意位置。

6.根據權利要求1所述的程序依賴關系分析方法，其特征在于，所述步驟6中通過影子指令分析指令依賴森林具體包括：影子指令對指令依賴森林中每個根節點n和其孩子節點c_i，執行操作T(n)＝U_i＝[0,m]T(c_i)，其中T（x）表示返回x的依賴關系狀態，且孩子節點c_i中i=0,…,m。

7.一種基于樹優化的程序依賴關系分析系統，其特征在于，包括依次連接的基本塊劃分模塊、依賴關系構建模塊、基本塊內優化模塊、基本塊間優化模塊、插裝位置獲取模塊和影子指令生成模塊：

基本塊劃分模塊，其用于以函數為基本單位進行程序依賴關系分析，將函數中的連續指令劃分為多個基本塊，且保證每個基本塊有單一入口和單一出口；

依賴關系構建模塊，其用于針對每個基本塊構建相應的指令依賴樹和指令依賴森林；

基本塊內優化模塊，其用于分析各基本塊的指令依賴樹和指令依賴森林，去除未改變原狀態的指令，去除依賴于特殊寄存器的指令依賴樹；

基本塊間優化模塊，其用于分析各基本塊的指令依賴樹和指令依賴森林，從前一基本塊中去除在其后續各基本塊中有重復定義但未被使用的變量對應的指令依賴樹；

插裝位置獲取模塊，其用于根據基本塊內優化模塊和基本塊間優化模塊的處理結果，選取內存索引中不能靜態計算寄存器值的指令所在的位置，將該指令位置之前的位置作為動態插裝位置；

影子指令生成模塊，其用于在所有動態插裝位置上生成統一化的影子指令，通過影子指令分析指令依賴樹和指令依賴森林。