基于格理论的数据流分析.ppt

《基于格理论的数据流分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十讲基于格理论的数据流分析内容一、控制流图二、活性分析三、可用表达式四、很忙表达式五、可达定义六、初始化变量七、符号分析八、常量分析九、区间分析2一、控制流图（ControlFlowGraph：CFG）类型分析主要通过语法树进行是流不敏感的(flowinsensitive)S1;S2的分析结果与S2;S1的结果相同深入的分析是流敏感的(flowsensitive)需要结束控制流图3一个控制流图是一个有向图结点对应于程序中的点（语句）边对应与可能的控制流一个CFG有单个的入口和单个的出口如果v是一个CFG中的一个点，则：pred(

2、v)是指该点直接前面点的集合succ(v)是指该点直接后面点的集合4数据流分析与格传统的数据流分析(我们要讨论的内容)从一个CFG和一个具有有限高度的格L开始对于CFG中的每个点v,我们赋予一个变量[v]，其取值范围是L中的元素.对于编程语言中的每个构造块，我们定义一个数据流约束（dataflowconstraint）该约束反映了一个点与其它点(特别是邻居)之间值的关系5对于一个CFG，我们可以抽取变量的约束的集合如果所有的约束刚好是等式或者不等式（右边单调）我们就可以利用不动点算法求唯一的最小解如果所有的解对应于程序的正确信息，

3、则数据流约束是“确定的”（sound）因为解可能或多或少地不精确，所以分析是“保守”的(conservative)但计算最小解将获得最大的精确度6不动点算法如果一个CFG具有点V={v1,v2,...,vn},我们可以这样构造格Ln假定点vi产生数据流等式[vi]=Fi([v1],...,[vn])我们构造联合函数F:Ln→LnF(x1,...,xn)=(F1(x1,...,xn),...,Fn(x1,...,xn))7x=(⊥,...,⊥);do{t=x;x=F(x);}while(xt);计算不动点x的直观算法:x1=⊥;.

4、..;xn=⊥;do{t1=x1;...;tn=xn;x1=F1(x1,...,xn);...xn=Fn(x1,...,xn);}while(x1t1∨...∨xntn);每个语句未利用以前语句的结果X1:第i个结点结束时的值集合迭代时重复计算量大许多等式已经不变！改进:利用以前语句的结果8x1=⊥;...;xn=⊥;q=[v1,...,vn];while(q[]){assumeq=[vi,...];y=Fi(x1,...,xn);q=q.tail();if(yxi){for(v∈dep(vi))q.append(v);x

5、i=y;}}实际使用的算法:dep(vi)是被Vi影响的点的集合9二、活性（Liveness）分析一个变量在程序的某个点是活跃的，如果：它的当前值在后面程序执行时可能被读取我们的分析借助于一个幂集格(powersetlattice)其元素是程序中的变量10varx,y,z;x=input;while(x>1){y=x/2;if(y>3)x=x-y;z=x-4;if(z>0)x=x/2;z=z-1;}outputx;考虑如下的程序:构造格:L=(2{x,y,z},⊆)What’sthemeaning?{x,y,z}{x,y}{x,z

6、}{y,z}{x}{y}{z}{}11对任何一个CFG结点v，我们引入一个约束变量[v][v]代表在该结点前活跃的程序变量集我们引入一个辅助定义:JOIN(v)=∪[w]w∈succ(v)对于退出结点，约束为：[exit]={}对“条件”和“输出”语句，约束为:[v]=JOIN(v)∪vars(E)对于赋值语句，约束为:[v]=JOIN(v){id}∪vars(E)对于变量声明，约束为:[v]=JOIN(v){id1,...,idn}最后，对所有其它结点，约束为:[v]=JOIN(v)其中：vars(E)表示出现在E中的变量“

7、”表示减去：原来的值不再起作用这些约束明显是单调的（为什么？）F(x1,...,xn)12[varx,y,z;]=[x=input]{x,y,z}[x=input]=[x>1]{x}[x>1]=([y=x/2]∪[outputx])∪{x}[y=x/2]=([y>3]{y})∪{x}[y>3]=[x=x-y]∪[z=x-4]∪{y}[x=x-y]=([z=x-4]{x})∪{x,y}[z=x-4]=([z>0]{z})∪{x}[z>0]=[x=x/2]∪[z=z-1]∪{z}[x=x/2]=([z=z-1]{x})∪

8、{x}[z=z-1]=([x>1]{z})∪{z}[outputx]=[exit]∪{x}[exit]={}varx,y,z;x=input;while(x>1){y=x/2;if(y>3)x=x-y;z=x-4;if(z>0)x=x/2;z=z