第五讲-数据流分析技术应用-程序分析技术-研究生课件.ppt

《第五讲-数据流分析技术应用-程序分析技术-研究生课件.ppt》由会员分享，可在线阅读，更多相关《第五讲-数据流分析技术应用-程序分析技术-研究生课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序分析技术程序分析技术第五讲：第五讲：数据流分析技术应用数据流分析技术应用一、检测数据流异常一、检测数据流异常1.1.数据流异常情况：数据流异常情况：1)1)变量无定值而使用；变量无定值而使用；2)2)变量重复定值；变量重复定值；3)3)变量定值无使用。变量定值无使用。检测方法（检测方法（a a）in_dB:in_dB:表示在表示在B B入口处所有定值的变量入口处所有定值的变量之集；之集；out_dB:out_dB:表示表示B B在出口处所有定值的变在出口处所有定值的变量之集；量之集；def_dB:def_dB:表示表示B B中所有定值的变量之集。中所有定值的变量之集。数据流方程（数据流方程

2、（a a）in_dB*=B*in_dB*=B*为入口块为入口块in_dBin_dB=（或（或）i=1,2ni=1,2n(out_dBi)(out_dBi)BiBi为为B B的前驱块的前驱块out_dB=def_dBin_dBout_dB=def_dBin_dB检测方法（检测方法（b b）in_ddBi:in_ddBi:表示块表示块B B入口处所有定值而未使用的变入口处所有定值而未使用的变 量之集；量之集；out_ddBi:out_ddBi:表示块表示块B B出口处所有定值而未使用的变出口处所有定值而未使用的变量之集；量之集；def_dd1Bi=def_dd1Bi=x|xx|x在（在（B,diB

3、,di）点定值，且从）点定值，且从（B,d1B,d1）.（B,diB,di）无）无x x的使用性出现。的使用性出现。def_dd2Bi=def_dd2Bi=x|xx|x在（在（B,diB,di）点定值，且从）点定值，且从（B,di+1B,di+1）到）到B B出口，无出口，无x x的使用性出现。的使用性出现。数据流方程（数据流方程（b b）in_ddB*=B*in_ddB*=B*为入口块为入口块 in_ddB=in_ddB=（或（或）out_ddB out_ddB out_ddB=def_dd2Bout_ddB=def_dd2B(in_ddB-useB)in_ddB-useB)数据流方程（数据

4、流方程（b b）结论：结论：1.1.若若in_ddBdef_dd1Bin_ddBdef_dd1B，则，则有变量重复定值有变量重复定值；若若in_ddB-in_liveBiin_ddB-in_liveBi，则有变量定值而未使用，或重，则有变量定值而未使用，或重复定值。复定值。2.2.若若out_ddB*out_ddB*，B*B*为出口块为出口块,则有变量定值而未使用。则有变量定值而未使用。定义：常量定值定义：常量定值若在块若在块B B中有中有x:=cx:=c，其中，其中c c是常数是常数,且该且该定值是向下暴露的，则称定值是向下暴露的，则称x x有一个有一个常量定值，记为常量定值，记为xcxc。

5、定义：定义：注销常量定值注销常量定值若有若有x:=Ex:=E，则称注销了，则称注销了x x的常量定值的常量定值。解决办法解决办法定义：定义：广义常量定值广义常量定值若块若块B B中有向下暴露的定值中有向下暴露的定值x:=Ex:=E，且且 E E的值可计算为一个常量的值可计算为一个常量c c，则，则称产生一个广义常量定值称产生一个广义常量定值xcxc。定义：定义：注销广义常量定值注销广义常量定值若有若有x=x=则称注销了广义常量则称注销了广义常量定值定值优化过程优化过程建立数据流方程建立数据流方程求解求解对每一基本块进入优化对每一基本块进入优化把把in-ac(B)in-ac(B)填入填入vvlv

6、vl按原方法优化按原方法优化in-acB1=in-acB1=out-acB1=x.1,y.2out-acB1=x.1,y.2in-acB2=x.1,y.2in-acB2=x.1,y.2out-acB2=x.1,y.2,z.3,b.4out-acB2=x.1,y.2,z.3,b.4in-acB3=x.1,y.2 in-acB3=x.1,y.2 out-acB3=x.1,y.2,z.3,b.4out-acB3=x.1,y.2,z.3,b.4in-acB4=x.1,y.2,z.3,b.4 in-acB4=x.1,y.2,z.3,b.4 out-acB4=out-acB4=x.1,y.2,z.3,b.

7、4,k.7,u.9,r.16 x.1,y.2,z.3,b.4,k.7,u.9,r.16 程序优化程序优化：公共子表达式节省公共子表达式节省定义：表达式定值定义：表达式定值在块在块B B中，若有中，若有d:x:=Ed:x:=E，则称有表达式，则称有表达式E E的的定值，定值，d d为定值点若从为定值点若从di+1di+1到到B B的出口没有的出口没有对表达式对表达式E E中变量的赋值，则称中变量的赋值，则称B B定值了表定值了表达式达式E E定义定义:注销表达式定值注销表达式定值若有若有 x:=E,x:=E,且且x x出现在表达式出现在表达式E E中，注销了中，注销了E E的定值。的定值。需要注

8、意的两个问题需要注意的两个问题形式相同的表达式未必能节省形式相同的表达式未必能节省（已解决）（已解决）形式不同的表达式也可能节省形式不同的表达式也可能节省（未解决）（未解决）定义：等式定值定义：等式定值 在块在块B B中，若有中，若有x:=yx:=y。且从。且从di+1di+1到到B B出口无对出口无对x x或或y y的赋值，则称的赋值，则称B B有了一个等式定值。即有了一个等式定值。即x=yx=yl 定义：注销等式定值定义：注销等式定值 若有对若有对x x的赋值的赋值x:=x:=，则称注销，则称注销了所有了所有x x的等式定值。的等式定值。数据流方程数据流方程in_eqB0=in_eqB0=B0B0为入口块为入口块out_eqBi=def_eqBiout_eqBi=def_eqBi(in_eqBi-kill_eqBi)(in_eqBi-kill_eqBi)in_eqBi=in_eqBi=BjBj pre(Bi)pre(Bi)out_eqBjout_eqBj 利用等式定值和表达式定值，利用等式定值和表达式定值，可以解决形式不相同但语义相同的可以解决形式不相同但语义相同的表达式节省问题。表达式节省问题。例如：例如：X:=A*B X:=A*B11 C:=A C:=A2 2 Y:=C*B Y:=C*B33 由由22可知可知1313等价等价