Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2019/1/31, 数据流分析,数据流分析的用途,编译优化、程序维护,程序安全性的检查,和编译原理课程的区别,基于源代码的结构化分析方法，而不是基于基本块和程序流图的分析,从过程内讨论到过程间,强调理论基础, 数据流分析数据流分析的用途http:/www.d,1,第,2,章 数据流分析,数据流分析的正确性,数据流分析所得结论同程序运行时的情况一致,需要定义机器模型和操作语义，证明所得结论对操作语义可靠,由于数据流分析收集的信息同基本块和控制流有关，通常和变量值无关，因此不同于一般的可靠性证明，例如,Hoare,逻辑的赋值公理是可靠的,x = 1,x := x + 1,x = 2, 数据流分析数据流分析的正确性http:/www.,2,活跃变量分析,活跃变量分析的正确性,需要将该正确性概念形式地表达出来,在活跃变量的初值相同的不同格局下,S,1,和,S,2,执行程序,S,的结果应该是一样的,再细化一下，程序每执行一步，得到的不同格局,S,1,和,S,2,中，活跃变量的值都相同, 数据流分析,数据流分析的基础,把各种数据流模式作为一个整体来抽象地研究，然后可以形式地回答数据流算法的下列几个基本问题：,在什么情况下数据流分析中使用的迭代算法是正确的？,该迭代算法所得解的精度如何？,该迭代算法是否收敛？,数据流方程的解的含义是什么？, 数据流分析数据流分析的基础http:/www.d,4,第,2,章 数据流分析,为一类数据流模式建一个共同理论框架,总结已讨论过的四种数据流分析模式,整理出该框架的一些基本特征或原则,规范框架中的性质空间要满足的特征,规范框架中迁移函数要满足的性质,给出框架的定义,区分单调框架和分配框架的区别,常量传播数据流模式不是分配的, 数据流分析为一类数据流模式建一个共同理论框架htt,5,第,2,章 数据流分析,位向量框架（,Bit vector framework,）,Single-bit representation of each data flow property,Separability of solution,Data flow properties can be evaluated,independently,Merge operation is a bitwise AND or OR,operation,Monotonic bit function,A bit function cannot negate any bit, 数据流分析位向量框架（Bit vector fra,6,第,2,章 数据流分析,分配性蕴涵单调性的证明,l,1,l,2,并且,f,(,l,1,l,2,) =,f,(,l,1,),f,(,l,2,),蕴涵,f,(,l,1,),f,(,l,2,),证明,因为,f,(,l,2,) =,f,(,l,1,l,2,) =,f,(,l,1,),f,(,l,2,),所以,f,(,l,1,),f,(,l,2,), 数据流分析分配性蕴涵单调性的证明http:/ww,7,第,2,章 数据流分析,常量传播框架的非分配性,说明常量传播框架没有分配性的例子,B,1,EXIT,z = x + y,x = 2,y = 3,B,3,B,2,x = 3,y = 2, 数据流分析常量传播框架的非分配性说明常量传播框架,8,第,2,章 数据流分析,整数格,表示没有任何信息可用,表示可能不是常量,3,2,1 0 1 2 3 , 数据流分析整数格 3 2,9,第,2,章 数据流分析,用集合之间的包含关系来定义部分函数之间的偏序,0,1,1,1,2,1,常函数1,阶乘函数,0,1,1,1,2,2,0,1,1,1,0,1,0,5,. . .,. . .,. . .,. . .,. . .,. . .,. . .,. . ., 数据流分析用集合之间的包含关系来定义部分函数之间的,10,第,2,章 数据流分析,数据流方程的求解,IDEAL,，基于程序所有可能执行路径的解，它少于或等于流图上的执行路径,Meet Over all Paths(MOP),，不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值,Maximum Fixed Point(MFP),，由迭代算法得到的解,迭代算法得到的,MFP,解总是安全的,MFP,MOP,IDEAL, 数据流分析数据流方程的求解http:/www.d,11,第,2,章 数据流分析,MOP,和,MFP,的比较,由,MOP,的定义，有,MOP,o,B,4 =,(,f,B,3,f,B,1,),(,f,B,3,f,B,2,) (,v,ENTRY,),在迭代算法,(MFP),中，,如果按,B,1,，,B,2,，,B,3,和,B,4,的次序,访问结点，那么,MFP,o,B,4 =,f,B,3,(,f,B,1,(,v,ENTRY,),f,B,2,(,v,ENTRY,),说明路径上较早汇合之影响的流图,B,1,ENTRY,B,4,B,3,B,2, 数据流分析MOP和MFP的比较 说明,12,第,2,章 数据流分析,敏感性分析,路径敏感分析,根据条件分支语句中的谓词来计算不同路径上的信息，它能够区分控制流图上不同路径的信息,路径不敏感分析,先前讨论的都是路径不敏感分析,流不敏感分析,语句的执行次序对分析来说无关紧要，,S,1,; S,2,和,S,2,; S,1,的分析结果肯定一样,流敏感分析,先前讨论的都是流敏感分析, 数据流分析敏感性分析http:/www.doci,13,第,2,章 数据流分析,敏感性分析,上下文不敏感分析,组合所有调用点的状态信息，对过程体仅分析一次，返回状态集合的信息用于所有的返回点,上下文敏感分析,区分带不同上下文信息的不同调用, 数据流分析敏感性分析http:/www.doci,14,第,2,章 数据流分析,过程间分析的关注点,上下文敏感分析,要注意调用和返回的匹配，注意上下文信息的传递,参数传递的方式,仅考虑传值和传结果方式,其他如传引用，会引起别名,过程作为参数,在此不考虑, 数据流分析过程间分析的关注点http:/www.,15,