数据流分析 对一组约東求解,得到各个点上数据流值。 ·约束分成两类:基于语句和基于控制流 ·基于语句语义的约東 一个语句之前和之后的数据流值受到该语句语义的约東 语句语义通常用传递函数表示,它把一个数据流值映射 为另一个数据流值; IN[S]=f(OUT[S) (逆向) OUTS=([SD (正向) ·基于控制流的约東 在基本块内部,一个语旬的输出和下一语旬的输入相同; 流图的控制流边也对应新的约束
数据流分析 • 对一组约束求解，得到各个点上数据流值。 • 约束分成两类：基于语句和基于控制流 • 基于语句语义的约束 – 一个语句之前和之后的数据流值受到该语句语义的约束； – 语句语义通常用传递函数表示，它把一个数据流值映射 为另一个数据流值； • IN[s]=fs (OUT[s]) （逆向） • OUT[s]=fs (IN[s]) （正向） • 基于控制流的约束 – 在基本块内部，一个语句的输出和下一语句的输入相同； – 流图的控制流边也对应新的约束
例子(1 ·假设我们考慮各个变量在某个程序点上是 否常量 s是语句x=3; 考處变量X,y,Z; iNS: X: NAC, 7;z 3 那么OUTs]就是:x:3;y:7;z:3 如果 s是xy+z,OUTS是 s是xx+y,OUTS是?
例子（1） • 假设我们考虑各个变量在某个程序点上是 否常量 – s是语句x=3； – 考虑变量x，y，z； – IN[s]：x:NAC; y:7; z:3 • 那么OUT[s]就是：x:3；y:7；z:3 • 如果 – s是x=y+z，OUT[s]是？ – s是x=x+y，OUT[s]是？
例子(1) 设有如右图的流图 X=4; y=4; 且数据流值 Z=a+b: OUT[SI: 3, y: 4, Z: NAC OUT[S2: X: 4, y: 3, Z: NAC s1:X=3 s2:y=3 iNS: X: NAC, y: NAC, Z: NAC S:2=X+y ·OUIS]是什么?能推出z7吗?
例子（1） • 设有如右图的流图 • 且数据流值 – OUT[s1]：x:3，y:4，z:NAC – OUT[s2]：x:4，y:3，z:NAC • 则 – IN[s]：x:NAC，y:NAC，z:NAC • OUT[s]是什么？能推出z:7吗? s1: x = 3 s2: y = 3 x = 4; y = 4; z = a+b; s: z = x+y
基本块上的数据流模式 ·基本块的控制流非常简单 从头到尾不会中断 没有分支 基本块的效果就是各个语句的效果的复合 ·可以预先处理基本块內部的数据流关系,给岀 基本块对应的传递函数; IN[B]=f(OUT[B])或者OUT[B]=fB(IN[B]) 设基本块包含语句S1,S2,,Sn; B sh
基本块上的数据流模式 • 基本块的控制流非常简单 – 从头到尾不会中断 – 没有分支 • 基本块的效果就是各个语句的效果的复合 • 可以预先处理基本块内部的数据流关系，给出 基本块对应的传递函数； IN[B] = fB (OUT[B]) 或者 OUT[B] = fB (IN[B]) • 设基本块包含语句s1,s2,…,sn； fB =fsn ◦…◦fs2◦fs1
基本坎之间的控制流约束 ·前向数据流问题 B的传递函数根据N[B]计 算得到OUTB]: N[B]和B的各前驱基本块 的OUT值之间具有约束关 系 B 逆向数据流问题 B的传递函数根据OUT1B假据流的例于: 前向 计算IN[B]; OUT[B1: X: 3 y: 4 Z: NAC OUTB和B的各后继基本OB2:x:3y:5z7 块的Ⅳ值之间具有约束关 OUt B3: X:3 4 7 则 系; INB]: X: 3 y: NAC Z: NAC
基本块之间的控制流约束 • 前向数据流问题 – B的传递函数根据IN[B]计 算得到OUT[B]； – IN[B]和B的各前驱基本块 的OUT值之间具有约束关 系； • 逆向数据流问题 – B的传递函数根据OUT[B] 计算IN[B]； – OUT[B]和B的各后继基本 块的IN值之间具有约束关 系； B1 B3 B B2 前向数据流的例子： 假如： OUT[B1]：x:3 y:4 z:NAC OUT[B2]：x:3 y:5 z:7 OUT[B3]：x:3 y:4 z:7 则： IN[B]： x:3 y:NAC z:NAC