3.1.4 求相关变量集和相关变量闭包
1.相关变量
变量相关又称变量间的依赖。变量a依赖于变量b记作:b→a。变量a直接依赖于b记作:b→Dir Dep a。DInfluence(a)表示直接影响变量a的变量的集合。在CTS中,如果两个变量a和b出现在同一个表达式中,那么就认为a和b是相关的。例如,有一个表达式a+b＞0,可以知道a依赖于b(b→Dir Dep a)和b依赖于a(a→Dir Dep b)。变量相关包括如下几种情况。
(1)由变量间的赋值运算直接引起的变量间的依赖关系
对于一个赋值表示式,左边是一个变量,右边是一个表达式,右边表达式中每一项都对左边唯一变量的取值有贡献,这样就有了依赖关系,即左边的唯一变量依赖于右边表达式中的变量。
(2)由变量间的赋值运算间接引起的变量间的依赖关系
在一个程序的执行过程中,如果从变量x到变量y的信息流中观察到变量x在某一点的取值变化导致在该点之后的某一点变量y的取值发生变化,我们就说变量y依赖于变量x。例如,顺序执行语句“z=x/2;y=z-1;”会引起一个从x到y的信息流,因为y的最终值是x/2-1,我们可以知道变量y依赖于变量x;顺序执行语句“z=x/2;z=0;y=z-1;”却不能引起从x到y的信息流。
定义3-4 有n(n≥2)个连续的程序动作(语句执行)a 1,a 2,…,a n,变量x被a 1使用,变量y由a n定义,并且对于i=1,2,…,n-1,ai+1动态数据依赖或者动态控制依赖于ai,我们就说变量y依赖于变量x。
(3)由关系运算引起的变量间的依赖关系
关系运算表达式左边表达式的取值受到右边表达式的取值影响,即关系运算表达式中,关系运算符左部的变量依赖关系运算符右部的变量。
(4)由复杂运算引起的变量间的依赖关系
假如关系表达式中有复杂运算(取模运算就是一种复杂运算,如a%b),并且参加复杂运算的参数都是变量,就会引入变量间的依赖关系。例如,对于复杂运算表达式a%b,参与运算的参数a和b都是变量,那就有变量a依赖于变量b,这是因为只有先知道了变量b的值才能确定表达式a%b的取值范围,而先知道变量a的值并不能确定表达式a%b的取值范围。
以上前两种变量之间的依赖关系可以通过符号分析技术得到,而本书所用算法主要关心后面两种变量之间的关系。这就要利用前面提取的表达式集合explist(实际上是含有表达式的控制流图节点集)和变量集合symlist来确定symlist中所有变量的直接相关变量集。该算法的流程如图3-4所示,具体描述如下。
①如果symlist为空,则算法结束;否则转去执行②。
②如果symlist中还有未被访问的变量,则依次取symlist中的一个变量var,转去执行③;否则,返回symlist,算法结束。
③若explist中还有未被访问的节点,则依次取explist中的一个控制流图节点node,转去执行④;否则转去执行②。
④若node的表达式中含有变量var,则将node的表达式中除变量var之外的所有其他变量都添加到变量var的直接相关变量集(∪→Dir Depvarvar)中,转去执行③;否则,转去执行③。(https://www.daowen.com)
图3-4 直接相关变量算法流程图
2.相关变量闭包
变量a的直接相关变量集的闭包是变量a的直接相关变量集中每一个变量的相关变量集的并集,即
变量的直接相关变量集通过“直接相关变量确定算法”可以获得。求直接相关变量集闭包的算法流程如图3-5所示,算法描述如下。
①如果symlist为空,则算法结束;否则转去执行②。
②如果symlist中还有未被访问的变量,那么依次取出symlist中的一个变量var,转去执行③;否则,返回symlist,算法结束。
③获取var的直接相关变量集DInfluence(var)。
④若DInfluence(var)不为空,转去执行⑤;否则,转去执行②。
⑤若DInfluence(var)中还有未被访问的变量,则依次取DInfluence(var)中的一个变量var_ref,转去执行⑥;否则,转去执行②。
⑥获取var_ref的直接相关变量集DInfluence(var_ref)。
⑦若DInfluence(var_ref)为空,转去执行⑤;若DInfluence(var_ref)不为空,则将DInfluence(var_ref)并入DInfluence(var)中,转去执行⑤。
图3-5 求解直接相关变量集的闭包算法流程图
