利用到達(dá)定義集計(jì)算流依賴和def—order依賴

閻萍++藍(lán)立毅

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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語(yǔ)言程序?yàn)閷?shí)例討論如何利用到達(dá)定義集對(duì)流依賴和def-order依賴進(jìn)行計(jì)算。

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

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

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

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

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

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

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

1.3 求出函數(shù)中每個(gè)語(yǔ)句頂點(diǎn)Z的到達(dá)定義集rd（Z）

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

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

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

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

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

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

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

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

2 計(jì)算實(shí)例

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

程序1的 C語(yǔ)言代碼為：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）；}程序流程見(jiàn)圖1，各語(yǔ)句編號(hào)為Si（i=1，…，8），各頂點(diǎn)定義和使用變量集：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）=?。程序中語(yǔ)句S1，S2，S5，S6，S7是對(duì)不同變量進(jìn)行定義的語(yǔ)句。各語(yǔ)句頂點(diǎn)的到達(dá)定義集為：rd（S1）={}，rd（S2）={， }，rd（S3）={，，，，}，rd（S4）={，，，，}，rd（S5）={，，，，}，rd（S6）={，，， ，}，rd（S7）={，，，，}，rd（S8）={，，，，}，頂點(diǎn)與后繼和前驅(qū)的關(guān)系如表1所示，存在三條def-order依賴邊[S2→do（S3）S7]，[S2→do（S4）S7]和[S2→do（S7）S7]。

程序2的C語(yǔ)言代碼為：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所示，計(jì)算出頂點(diǎn)間后繼和前驅(qū)關(guān)系表，可得系統(tǒng)依賴圖4，其中不帶文字和叉的虛線表示的是流依賴，M1和M13之間有兩條def-order依賴邊，其它依賴和連接邊用文獻(xiàn)[3][4][5]方法計(jì)算。

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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].