基于格理论的数据流分析

高级软件工程第十讲基于格理论的数据流分析基于格理论的数据流分析2/49高级软件工程内容一、控制流图二、活性分析三、可用表达式四、很忙表达式五、可达定义六、初始化变量七、符号分析八、常量分析九、区间分析基于格理论的数据流分析3/49高级软件工程一、控制流图（ControlFlowGraph：CFG）类型分析主要通过语法树进行是流不敏感的(flowinsensitive)S1;S2的分析结果与S2;S1的结果相同深入的分析是流敏感的(flowsensitive)需要结束控制流图基于格理论的数据流分析4/49高级软件工程一个控制流图是一个有向图结点对应于程序中的点（语句）边对应与可能的控制流一个CFG有单个的入口和单个的出口如果v是一个CFG中的一个点，则：pred(v)是指该点直接前面点的集合succ(v)是指该点直接后面点的集合基于格理论的数据流分析5/49高级软件工程数据流分析与格传统的数据流分析(我们要讨论的内容)从一个CFG和一个具有有限高度的格L开始对于CFG中的每个点v,我们赋予一个变量[v]，其取值范围是L中的元素.对于编程语言中的每个构造块，我们定义一个数据流约束（dataflowconstraint）该约束反映了一个点与其它点(特别是邻居)之间值的关系基于格理论的数据流分析6/49高级软件工程对于一个CFG，我们可以抽取变量的约束的集合如果所有的约束刚好是等式或者不等式（右边单调）我们就可以利用不动点算法求唯一的最小解如果所有的解对应于程序的正确信息，则数据流约束是“确定的”（sound）因为解可能或多或少地不精确，所以分析是“保守”的(conservative)但计算最小解将获得最大的精确度基于格理论的数据流分析7/49高级软件工程不动点算法如果一个CFG具有点V={v1,v2,...,vn},我们可以这样构造格Ln假定点vi产生数据流等式[vi]=Fi([v1],...,[vn])我们构造联合函数F:Ln→LnF(x1,...,xn)=(F1(x1,...,xn),...,Fn(x1,...,xn))基于格理论的数据流分析8/49高级软件工程x=(⊥,...,⊥);do{t=x;x=F(x);}while(xt);计算不动点x的直观算法:x1=⊥;...;xn=⊥;do{t1=x1;...;tn=xn;x1=F1(x1,...,xn);...xn=Fn(x1,...,xn);}while(x1t1∨...∨xntn);每个语句未利用以前语句的结果X1:第i个结点结束时的值集合迭代时重复计算量大许多等式已经不变！改进:利用以前语句的结果基于格理论的数据流分析9/49高级软件工程x1=⊥;...;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);xi=y;}}实际使用的算法:dep(vi)是被Vi影响的点的集合基于格理论的数据流分析10/49高级软件工程二、活性（Liveness）分析一个变量在程序的某个点是活跃的，如果：它的当前值在后面程序执行时可能被读取我们的分析借助于一个幂集格(powersetlattice)其元素是程序中的变量基于格理论的数据流分析11/49高级软件工程varx,y,z;x=input;while(x1){y=x/2;if(y3)x=x-y;z=x-4;if(z0)x=x/2;z=z-1;}outputx;考虑如下的程序:构造格:L=(2{x,y,z},⊆)What’sthemeaning?{x,y,z}{x,y}{x,z}{y,z}{x}{y}{z}{}基于格理论的数据流分析12/49高级软件工程对任何一个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中的变量“\”表示减去：原来的值不再起作用这些约束明显是单调的（为什么？）F(x1,...,xn)基于格理论的数据流分析13/49高级软件工程[varx,y,z;]=[x=input]\{x,y,z}[x=input]=[x1]\{x}[x1]=([y=x/2]∪[outputx])∪{x}[y=x/2]=([y3]\{y})∪{x}[y3]=[x=x-y]∪[z=x-4]∪{y}[x=x-y]=([z=x-4]\{x})∪{x,y}[z=x-4]=([z0]\{z})∪{x}[z0]=[x=x/2]∪[z=z-1]∪{z}[x=x/2]=([z=z-1]\{x})∪{x}[z=z-1]=([x1]\{z})∪{z}[outputx]=[exit]∪{x}[exit]={}varx,y,z;x=input;while(x1){y=x/2;if(y3)x=x-y;z=x-4;if(z0)x=x/2;z=z-1;}outputx;ProgramConstraints基于格理论的数据流分析14/49高级软件工程[varx,y,z;]=[x=input]\{x,y,z}[x=input]=[x1]\{x}[x1]=([y=x/2]∪[outputx])∪{x}[y=x/2]=([y3]\{y})∪{x}[y3]=[x=x-y]∪[z=x-4]∪{y}[x=x-y]=([z=x-4]\{x})∪{x,y}[z=x-4]=([z0]\{z})∪{x}[z0]=[x=x/2]∪[z=z-1]∪{z}[x=x/2]=([z=z-1]\{x})∪{x}[z=z-1]=([x1]\{z})∪{z}[outputx]=[exit]∪{x}[exit]={}Constraints[entry]={}[varx,y,z;]={}[x=input]={}[x1]={x}[y=x/2]={x}[y3]={x,y}[x=x-y]={x,y}[z=x-4]={x}[z0]={x,z}[x=x/2]={x,z}[z=z-1]={z}[outputx]={x}[exit]={}[entry]={}[varx,y,z;]={}[x=input]={}[x1]={}[y=x/2]={}[y3]={}[x=x-y]={}[z=x-4]={}[z0]={}[x=x/2]={}[z=z-1]={}[outputx]={}[exit]={}第一次迭代结果基于格理论的数据流分析15/49高级软件工程[entry]={}[varx,y,z;]={}[x=input]={}[x1]={x}[y=x/2]={x}[y3]={x,y}[x=x-y]={x,y}[z=x-4]={x}[z0]={x,z}[x=x/2]={x,z}[z=z-1]={x,z}[outputx]={x}[exit]={}[entry]={}[varx,y,z;]={}[x=input]={}[x1]={x}[y=x/2]={x}[y3]={x,y}[x=x-y]={x,y}[z=x-4]={x}[z0]={x,z}[x=x/2]={x,z}[z=z-1]={z}[outputx]={x}[exit]={}第一次迭代结果[varx,y,z;]=[x=input]\{x,y,z}[x=input]=[x1]\{x}[x1]=([y=x/2]∪[outputx])∪{x}[y=x/2]=([y3]\{y})∪{x}[y3]=[x=x-y]∪[z=x-4]∪{y}[x=x-y]=([z=x-4]\{x})∪{x,y}[z=x-4]=([z0]\{z})∪{x}[z0]=[x=x/2]∪[z=z-1]∪{z}[x=x/2]=([z=z-1]\{x})∪{x}[z=z-1]=([x1]\{z})∪{z}[outputx]=[exit]∪{x}[exit]={}Constraints第二次迭代结果基于格理论的数据流分析16/49高级软件工程[entry]={}[varx,y,z;]={}[x=input]={}[x1]={x}[y=x/2]={x}[y3]={x,y}[x=x-y]={x,y}[z=x-4]={x}[z0]={x,z}[x=x/2]={x,z}[z=z-1]={x,z}[outputx]={x}[exit]={}[entry]={}[varx,y,z;]={}[x=input]={}[x1]={x}[y=x/2]={x}[y3]={x,y}[x=x-y]={x,y}[z=x-4]={x}[z0]={x,z}[x=x/2]={x,z}[z=z-1]={x,z}[outputx]={x}[exit]={}第二次迭代结果[varx,y,z;]=[x=input]\{x,y,z}[x=input]=[x1]\{x}[x1]=([y=x/2]∪[outputx])∪{x}[y=x/2]=([y3]\{y})∪{x}[y3]=[x=x-y]∪[z=x-4]∪{y}[x=x-y]=([z=x-4]\{x})∪{x,y}[z=x-4]=([z0]\{z})∪{x}[z0]=[x=x/2]∪[z=z-1]∪{z}[x=x/2]=([z=z-1]\{x})∪{x}[z=z-1]=([x1]\{z})∪{z}[outputx]=[exit]∪{x}[exit]={}Constraints第三次迭代结果基于格理论的数据流分析17/49高级软件工程从该信息，一个聪明的编译器可以发现y和z从来没有同时活跃，z=z-1中的赋值从未被用过。因此，该程序可以被优化：varx,y,z;x=input;while(x1){y=x/2;if(y3)x=x-y;z=x-4;if(z0)x=x/2;z=z-1;}outputx;节省了一个赋值语句！寄存器分配更合理！varx,yz;x=input;while(x1){yz=x/2;if(yz3)x=x-yz;yz=x-4;if(yz0)x=x/2;}outputx;冗余赋值！基于格理论的数据流分析18/49高级软件工程三、可用表达式（Availableexpression）一个重要的表达式是可用的，如果它的当前值已经计算过对应的幂集格，元素是程序中出现过的所有表达式比较关系是反的（“以前”：从上到下）程序例子：varx,y,z,a,b;z=a+b;y=a*b;while(ya+b){a=a+1;x=a+b;}基于格理论的数据流分析19/49高级软件工程其中含4个表达式，对应的格为：L=(2{a+b,a*b,ya+b,a+1},⊇)重要表达式基于格理论的数据流分析20/49高级软件工程定义:JOIN(v)=∩[w]w∈pred(v)对于入口，约束为：[entry]={}如果v包含一个条件表达式E,约束为：[v]=JOIN(v)∪exps(E)如果v包含输出语句E,约束为：[v]=JOIN(v)∪exps(E)如果v包含赋值语句id=E,约束为:[v]=(JOIN(v)∪exps(E))↓id↓id表示移除所有包含指向变量id的表达式对所有其它结点，约束为：[v]=JOIN(v)基于格理论的数据流分析21/49高级软件工程函数exps定义为:exps(intconst)=∅exps(id)=∅exps(input)=∅exps(E1opE2)={E1opE2}∪exps(E1)∪exps(E2)op是任何二元操作符[entry]={}[varx,y,z,a,b;]=[entry][z=a