利用到达定义集计算流依赖和def—order依赖

阎萍++蓝立毅

摘要：针对生成程序系统依赖图时语句顶点之间的流依赖和def-order依赖计算问题，给出了定义清晰的路径以及到达定义集的概念，描述了利用到达定义集进行计算的方法步骤，有助于确立语句之间的流依赖和def-order依赖关系。

关键词：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

程序系统依赖图的建立包括控制依赖、数据依赖以及transitive依赖关系的建立，而数据依赖包含流依赖和def-order依赖，本文以C语言程序为实例讨论如何利用到达定义集对流依赖和def-order依赖进行计算。

1 相关概念与算法步骤描述

程序系统依赖图的建立，需要以程序的函数为单位计算流依赖和def-order依赖，然后再建立函数之间的连接关系，为此需要用到2个辅助集合def集和use集，引入定义清晰的路径和到达定义集概念，区分单点路径和多点路径。

函数内数据依赖关系按如下步骤计算：

1.1 处理调用和被调用关系，给出函数的控制流图

对于多函数程序，由于存在函数调用关系，在给出控制流图时需要①处理函数内的调用顶点，②处理被调函数的参数和返回值，为此需要引入新的变量。函数参数分为引用参数和引用后结果会被修改的参数两种情况。依据文献[1]在系统依赖图生成中参数的处理方法有： 假设函数P调用函数Q，e为P中调用点call-site处实参，r为Q的形参，在P的调用点有：①Actual_in顶点，对应赋值：r_in=e。②Actual_out顶点，对应赋值：a=r_out，其中a为实参是个变量。关系：实参a对应形参r。具有r_in和r_out形式的变量为新引入的变量。对Q的形参r，Q的依赖图中包含①一个Formal_in顶点，对应赋值：r=r_in。②一个 Formal_out顶点，对应赋值：r_out=r。每个参数包含Actual_in和Formal_in顶点，若参数属于引用后结果会被修改的参数，则还包含Formal_out和Actual_out顶点。在系统依赖图中，Actual_in和Actual_out顶点控制依赖于P内的call_site点，Formal_in和Formal_out顶点控制依赖于Q的ENTRY顶点。Q中形式为return（S）的语句引入新变量S_out后被处理为赋值顶点： S_out=S控制依赖于Q的ENTRY顶点。P中函数有返回值时，返回值为S_out，P中有对返回值进行加工处理的语句如赋值语句等，处理为控制依赖于P中调用点call-site。

1.2 计算函数中各语句S的def集和use集

def（S）是S中定义的变量集合，use（S）是S中使用的变量集合，根据变量是出现在赋值的左边还是右边来确定。

1.3 求出函数中每个语句顶点Z的到达定义集rd（Z）

方法是找出函数的语句顶点中所有对变量进行定义的顶点，根据流图，逐个判断该定义是否能经由一条定义清晰的路径到达当前顶点。一个语句顶点Z的到达定义集rd（Z） ={|v∈def（Y），且存在一条关于v从Y到Z的定义清晰的路径}。流图中的一条路径是一个顶点序列（n1，n2，…，nk）。如果k=1，是单点路径，无前驱和后继。当变量就在当前顶点S定义时，则存在定义清晰的单点路径（S）。如果k≥2，当1≤i

1.4 求出函数的DU对集，D是变量v的定义点，U是变量v的使用点

文献[1][2]给出了数据流依赖的定义。一个数据流依赖是一个三元组（D，U，v），满足v∈use（U），∈rd（U），v∈def（D），关于变量v在流图中从D到U有一条定义清晰的路径。通过对函数计算DU对的方法，计算出流依赖。

方法：对函数每一条语句顶点Sm检查其所含变量。每条语句中所含的定义变量为空（不存在）或者存在设为x，每条语句中所含的引用变量为空（不存在）或者存在设为y。①根据定义变量找后继。对变量x∈def（Sm），在函数的任意语句顶点Sn的到达定义集rd（Sn）中，根据定义变量x寻找变量顶点对。若找到，则关于变量x从Sm到Sn存在一条定义清晰的路径，且该路径为多点路径（Sm，…，Sn）、路径末端为Sn时，若x∈use（Sn），则D=Sm，U=Sn。找出所有这样的Sn顶点，形成若干个（D，U）对，D到U之间存在数据流依赖，U为D的后继。若找不到，或找到但只存在单点路径，或找到且存在定义清晰的多点路径但x[?]use（Sn），则Sn不是Sm的后继。②根据引用变量找前驱。对变量y∈use（Sm），在该语句顶点Sm的到达定义集rd（Sm）中寻找变量y的变量顶点对，确定顶点Sn具体是哪个语句顶点。若存在变量顶点对，并且因y∈def（Sn），则根据到达定义集的概念定义，关于变量y从Sn到Sm存在一条定义清晰的路径，且该路径是多点路径（Sn，…，Sm），该路径起点为Sn，则Sn是定义变量y的一个顶点，y∈def（Sn），y可能是该顶点Sn中定义的变量，于是U=Sm，D=Sn。在该rd（Sm）中找出所有这样的Sn，形成若干个（D，U）对，D到U之间存在数据流依赖，D是U的前驱。若不存在或者存在但只存在单点路径，则Sm无前驱。

逐条语句求出后继和前驱，结合顶点的前驱和后继才能完整地计算出顶点之间的数据流依赖关系，可用表格表示出来。

1.5 利用到达定义集结合def-order依赖定义计算出def-order依赖

文献[1][2]给出了def-order依赖的定义：一个程序依赖图关于变量x包含一个从顶点V1到顶点V2的def-order依赖边，记为[V1→do（V3）V2]，当且仅当下列所有满足：①V1和V2都是定义同样变量x的赋值语句；②V1和V2在任何包含两者的条件语句的同样分支里；③存在一个程序成分（语句）V3满足[V1→fV3]和[V2→fV3]；④在程序的抽象语法树里V1发生在V2的左边。这个定义说明：只有定义同样变量的赋值语句之间才有可能有def-order依赖边。

假设程序函数的语句为Si（i为整数），假设x∈use（Si），在到达定义集rd（Si）中去寻找变量x的变量顶点对对，其中“_”表示可能是任意的語句顶点。若存在两个变量顶点对和，根据变量顶点对的定义，这里说明Sj和Sk都是定义变量x的赋值语句，当在程序中，Sj，Sk同在包含二者的条件语句的同样分支中，并且在抽象语法树中Sj出现在Sk的左边时，则[Sj→do（Si）Sk]。

2 计算实例

第1个程序只有主函数，第2个程序由两个函数组成，两个程序均省去了#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）={b}，def（S5）={c}， def（S6）={c}，def（S7）={b}，use（S3）={b，a}，use（S4）={b}，use（S7）={b}，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）={，，，，}，顶点与后继和前驱的关系如表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函数的流图如图2和3所示，计算出顶点间后继和前驱关系表，可得系统依赖图4，其中不带文字和叉的虚线表示的是流依赖，M1和M13之间有两条def-order依赖边，其它依赖和连接边用文献[3][4][5]方法计算。

3 結束语

流依赖和def-order依赖的计算方法，有助于数据依赖的计算和系统依赖图的建立。

参考文献：

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