閻萍++藍立毅

摘要：針對生成程序系統(tǒng)依賴圖時語句頂點之間的流依賴和def-order依賴計算問題，給出了定義清晰的路徑以及到達定義集的概念，描述了利用到達定義集進行計算的方法步驟，有助于確立語句之間的流依賴和def-order依賴關(guān)系。

關(guān)鍵詞：C語言；到達定義集；流依賴；def-order依賴

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2016）36-0001-03

Using Reaching Definition Set To Compute Flow Dependence and Def-Order Dependence

YAN Ping， LAN Li-yi

（Department of Math and Computer Science，Gannan Normal University， Gannan 341000， China）

Abstract：Aiming at the computation problem of flow dependence and def-order dependence between sentences vertexes when building programs system dependence， the concept about the clear definition path and the reaching definition set is giving， the calculating method and step of using reaching definition set is described.It is helpful for building the dependence relation of flow dependence and def-order dependence types between sentences vertexes.

Key words： C-language；reaching definition set；flow dependence； def-order dependence

程序系統(tǒng)依賴圖的建立包括控制依賴、數(shù)據(jù)依賴以及transitive依賴關(guān)系的建立，而數(shù)據(jù)依賴包含流依賴和def-order依賴，本文以C語言程序為實例討論如何利用到達定義集對流依賴和def-order依賴進行計算。

1 相關(guān)概念與算法步驟描述

程序系統(tǒng)依賴圖的建立，需要以程序的函數(shù)為單位計算流依賴和def-order依賴，然后再建立函數(shù)之間的連接關(guān)系，為此需要用到2個輔助集合def集和use集，引入定義清晰的路徑和到達定義集概念，區(qū)分單點路徑和多點路徑。

函數(shù)內(nèi)數(shù)據(jù)依賴關(guān)系按如下步驟計算：

1.1 處理調(diào)用和被調(diào)用關(guān)系，給出函數(shù)的控制流圖

對于多函數(shù)程序，由于存在函數(shù)調(diào)用關(guān)系，在給出控制流圖時需要①處理函數(shù)內(nèi)的調(diào)用頂點，②處理被調(diào)函數(shù)的參數(shù)和返回值，為此需要引入新的變量。函數(shù)參數(shù)分為引用參數(shù)和引用后結(jié)果會被修改的參數(shù)兩種情況。依據(jù)文獻[1]在系統(tǒng)依賴圖生成中參數(shù)的處理方法有： 假設(shè)函數(shù)P調(diào)用函數(shù)Q，e為P中調(diào)用點call-site處實參，r為Q的形參，在P的調(diào)用點有：①Actual_in頂點，對應(yīng)賦值：r_in=e。②Actual_out頂點，對應(yīng)賦值：a=r_out，其中a為實參是個變量。關(guān)系：實參a對應(yīng)形參r。具有r_in和r_out形式的變量為新引入的變量。對Q的形參r，Q的依賴圖中包含①一個Formal_in頂點，對應(yīng)賦值：r=r_in。②一個 Formal_out頂點，對應(yīng)賦值：r_out=r。每個參數(shù)包含Actual_in和Formal_in頂點，若參數(shù)屬于引用后結(jié)果會被修改的參數(shù)，則還包含F(xiàn)ormal_out和Actual_out頂點。在系統(tǒng)依賴圖中，Actual_in和Actual_out頂點控制依賴于P內(nèi)的call_site點，F(xiàn)ormal_in和Formal_out頂點控制依賴于Q的ENTRY頂點。Q中形式為return（S）的語句引入新變量S_out后被處理為賦值頂點： S_out=S控制依賴于Q的ENTRY頂點。P中函數(shù)有返回值時，返回值為S_out，P中有對返回值進行加工處理的語句如賦值語句等，處理為控制依賴于P中調(diào)用點call-site。

1.2 計算函數(shù)中各語句S的def集和use集

def（S）是S中定義的變量集合，use（S）是S中使用的變量集合，根據(jù)變量是出現(xiàn)在賦值的左邊還是右邊來確定。

1.3 求出函數(shù)中每個語句頂點Z的到達定義集rd（Z）

方法是找出函數(shù)的語句頂點中所有對變量進行定義的頂點，根據(jù)流圖，逐個判斷該定義是否能經(jīng)由一條定義清晰的路徑到達當前頂點。一個語句頂點Z的到達定義集rd（Z） ={|v∈def（Y），且存在一條關(guān)于v從Y到Z的定義清晰的路徑}。流圖中的一條路徑是一個頂點序列（n1，n2，…，nk）。如果k=1，是單點路徑，無前驅(qū)和后繼。當變量就在當前頂點S定義時，則存在定義清晰的單點路徑（S）。如果k≥2，當1≤i

1.4 求出函數(shù)的DU對集，D是變量v的定義點，U是變量v的使用點

文獻[1][2]給出了數(shù)據(jù)流依賴的定義。一個數(shù)據(jù)流依賴是一個三元組（D，U，v），滿足v∈use（U），∈rd（U），v∈def（D），關(guān)于變量v在流圖中從D到U有一條定義清晰的路徑。通過對函數(shù)計算DU對的方法，計算出流依賴。

方法：對函數(shù)每一條語句頂點Sm檢查其所含變量。每條語句中所含的定義變量為空（不存在）或者存在設(shè)為x，每條語句中所含的引用變量為空（不存在）或者存在設(shè)為y。①根據(jù)定義變量找后繼。對變量x∈def（Sm），在函數(shù)的任意語句頂點Sn的到達定義集rd（Sn）中，根據(jù)定義變量x尋找變量頂點對。若找到，則關(guān)于變量x從Sm到Sn存在一條定義清晰的路徑，且該路徑為多點路徑（Sm，…，Sn）、路徑末端為Sn時，若x∈use（Sn），則D=Sm，U=Sn。找出所有這樣的Sn頂點，形成若干個（D，U）對，D到U之間存在數(shù)據(jù)流依賴，U為D的后繼。若找不到，或找到但只存在單點路徑，或找到且存在定義清晰的多點路徑但x[?]use（Sn），則Sn不是Sm的后繼。②根據(jù)引用變量找前驅(qū)。對變量y∈use（Sm），在該語句頂點Sm的到達定義集rd（Sm）中尋找變量y的變量頂點對，確定頂點Sn具體是哪個語句頂點。若存在變量頂點對，并且因y∈def（Sn），則根據(jù)到達定義集的概念定義，關(guān)于變量y從Sn到Sm存在一條定義清晰的路徑，且該路徑是多點路徑（Sn，…，Sm），該路徑起點為Sn，則Sn是定義變量y的一個頂點，y∈def（Sn），y可能是該頂點Sn中定義的變量，于是U=Sm，D=Sn。在該rd（Sm）中找出所有這樣的Sn，形成若干個（D，U）對，D到U之間存在數(shù)據(jù)流依賴，D是U的前驅(qū)。若不存在或者存在但只存在單點路徑，則Sm無前驅(qū)。

逐條語句求出后繼和前驅(qū)，結(jié)合頂點的前驅(qū)和后繼才能完整地計算出頂點之間的數(shù)據(jù)流依賴關(guān)系，可用表格表示出來。

1.5 利用到達定義集結(jié)合def-order依賴定義計算出def-order依賴

文獻[1][2]給出了def-order依賴的定義：一個程序依賴圖關(guān)于變量x包含一個從頂點V1到頂點V2的def-order依賴邊，記為[V1→do（V3）V2]，當且僅當下列所有滿足：①V1和V2都是定義同樣變量x的賦值語句；②V1和V2在任何包含兩者的條件語句的同樣分支里；③存在一個程序成分（語句）V3滿足[V1→fV3]和[V2→fV3]；④在程序的抽象語法樹里V1發(fā)生在V2的左邊。這個定義說明：只有定義同樣變量的賦值語句之間才有可能有def-order依賴邊。

假設(shè)程序函數(shù)的語句為Si（i為整數(shù)），假設(shè)x∈use（Si），在到達定義集rd（Si）中去尋找變量x的變量頂點對對，其中“_”表示可能是任意的語句頂點。若存在兩個變量頂點對和，根據(jù)變量頂點對的定義，這里說明Sj和Sk都是定義變量x的賦值語句，當在程序中，Sj，Sk同在包含二者的條件語句的同樣分支中，并且在抽象語法樹中Sj出現(xiàn)在Sk的左邊時，則[Sj→do（Si）Sk]。

2 計算實例

第1個程序只有主函數(shù)，第2個程序由兩個函數(shù)組成，兩個程序均省去了#include"stdio.h".scanf語句看成賦值語句處理。

程序1的 C語言代碼為：void main（）{int a，b，c；scanf（“%d”，&a）；b=1； while（b<=a） {if（b/2！=0）c=1；else c=2； b=b+1；}printf （“c=%d＼n”，c）；}程序流程見圖1，各語句編號為Si（i=1，…，8），各頂點定義和使用變量集：def（S1）={a}，def（S2）=，def（S5）={c}， def（S6）={c}，def（S7）=，use（S3）={b，a}，use（S4）=，use（S7）=，use（S8）={c}，def（S3）=def（S4）=def（S8）=?，use（S1）=use（S2）=use（S5）=use（S6）=?。程序中語句S1，S2，S5，S6，S7是對不同變量進行定義的語句。各語句頂點的到達定義集為：rd（S1）={}，rd（S2）={， }，rd（S3）={，，，，}，rd（S4）={，，，，}，rd（S5）={，，，，}，rd（S6）={，，， ，}，rd（S7）={，，，，}，rd（S8）={，，，，}，頂點與后繼和前驅(qū)的關(guān)系如表1所示，存在三條def-order依賴邊[S2→do（S3）S7]，[S2→do（S4）S7]和[S2→do（S7）S7]。

程序2的C語言代碼為：float max3（float *x，float *y，float *z，float *sm）{float max=*x；if（*z>*y）{if（*z>*x）max=*z；}else{if（*y>*x）max=*y；}*sm=*sm+*x+*y+*z；return（max）；}void main（）{float a，b，c，max，sum；int i；i=1；sum=0；while（i<=5）{scanf （“%f%f%f%”，&a，&b，&c）；printf（“a=%f，b=%f，c=%f”，a，b，c）；max=max3（&a，&b，&c，&sum）； printf（“max=%f＼n”，max）；i=i+1；}printf（“sum=%f＼n”，sum）；}其中main和max3函數(shù)的流圖如圖2和3所示，計算出頂點間后繼和前驅(qū)關(guān)系表，可得系統(tǒng)依賴圖4，其中不帶文字和叉的虛線表示的是流依賴，M1和M13之間有兩條def-order依賴邊，其它依賴和連接邊用文獻[3][4][5]方法計算。

3 結(jié)束語

流依賴和def-order依賴的計算方法，有助于數(shù)據(jù)依賴的計算和系統(tǒng)依賴圖的建立。

參考文獻：

[1] SUSAN HORWITZ，THOMAS REPS，and DAVID BINKLEY.Interprocedural Slicing Using Dependence Graphs[J].ACM Transactions on Programminges and Systems，January 1990，12（1）：26-60.

[2] SUSAN HORWITZ，JAN PRINS，and THOMAS REPS.Integrating Non-Interfering Versions of Programs[J].ACM Transactions on Programming Languages and System.A preliminary version of this paper appeared in the Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages，{San Diego，Ca，January 13-15，1988}，ACM，New York，NY（1988），pp，133-145.

[3] JEANNE FERRANTE，IBM T.J.Watson Research Center，KARL J.OTTENSTEIN.The Program Dependence Graph and Its Use in Optimization[J].ACM Transactions on Programming Languages and Systems，July 1987， 9（3）：319-349.

[4] Panos E.Livadas Stephen Croll.Program Slicing[J]. http：//wenku.baidu.com/view/

[5] T homas Reps，Susan Horwitz，Mooly Sagiv，et al.Speeding up Slicing[J].