《数据流分析PPT课件》由会员分享，可在线阅读，更多相关《数据流分析PPT课件（16页珍藏版）》请在金锄头文库上搜索。
1、第第2章章 数据流分析数据流分析内容概述内容概述数据流分析推导的是数据沿着程序执行路数据流分析推导的是数据沿着程序执行路径流动的信息径流动的信息过程内的分析：可用表达式分析、到达定值分过程内的分析：可用表达式分析、到达定值分析等析等过程间分析过程间分析Shape分析分析理论基础理论基础数据流方程的求解数据流方程的求解第第2章章 数据流分析数据流分析数据流分析的用途数据流分析的用途编译优化、程序维护编译优化、程序维护程序安全性的检查程序安全性的检查和编译原理课程的区别和编译原理课程的区别基于源代基于源代码的的结构化分析方法，而不是基于基本构化分析方法，而不是基于基本块和程序流和程序流图的分析的分
2、析从从过程内程内讨论到到过程程间强强调理理论基基础第第2章章 数据流分析数据流分析数据流分析的正确性数据流分析的正确性数据流分析所得数据流分析所得结论同程序运行同程序运行时的情况一致的情况一致需要定需要定义机器模型和操作机器模型和操作语义，证明所得明所得结论对操作操作语义可靠可靠由于数据流分析收集的信息同基本由于数据流分析收集的信息同基本块和控制流有和控制流有关，通常和关，通常和变量量值无关，因此不同于一般的可靠无关，因此不同于一般的可靠性性证明，例如明，例如Hoare逻辑的的赋值公理是可靠的公理是可靠的x = 1 x := x + 1 x = 2活跃变量分析活跃变量分析活跃变量分析的正确性活
3、跃变量分析的正确性需要将需要将该正确性概念形式地表达出来正确性概念形式地表达出来在活在活跃变量的初量的初值相同的不同格局下相同的不同格局下 S, 1 和和 S, 2 执行程序行程序S的的结果果应该是一是一样的的再再细化一下，程序每化一下，程序每执行一步，得到的不同格行一步，得到的不同格局局 S , 1 和和 S , 2 中，活中，活跃变量的量的值都相同都相同第第2章章 数据流分析数据流分析数据流分析的基础数据流分析的基础 把各种数据流模式作为一个整体来抽象地研把各种数据流模式作为一个整体来抽象地研究，然后可以形式地回答数据流算法的下列究，然后可以形式地回答数据流算法的下列几个基本问题：几个基本
4、问题：在什么情况下数据流分析中使用的迭代算法是正在什么情况下数据流分析中使用的迭代算法是正确的？确的？该迭代算法所得解的精度如何？该迭代算法所得解的精度如何？该迭代算法是否收敛？该迭代算法是否收敛？数据流方程的解的含义是什么？数据流方程的解的含义是什么？第第2章章 数据流分析数据流分析为一类数据流模式建一个共同理论框架为一类数据流模式建一个共同理论框架总结已讨论过的四种数据流分析模式总结已讨论过的四种数据流分析模式 整理出整理出该框架的一些基本特征或原框架的一些基本特征或原则规范框架中的性范框架中的性质空空间要要满足的特征足的特征规范框架中迁移函数要范框架中迁移函数要满足的性足的性质给出框架的
5、定出框架的定义区分区分单调框架和分配框架的区框架和分配框架的区别常量常量传播数据流模式不是分配的播数据流模式不是分配的第第2章章 数据流分析数据流分析位向量框架（位向量框架（Bit vector framework）Single-bit representation of each data flow propertySeparability of solution Data flow properties can be evaluated independently Merge operation is a bitwise AND or OR operationMonotonic bit f
6、unction A bit function cannot negate any bit第第2章章 数据流分析数据流分析分配性蕴涵单调性的证明分配性蕴涵单调性的证明l1 l2 并且并且f(l1 l2) = f(l1) f(l2) 蕴涵蕴涵 f(l1) f(l2)证明证明 因为因为f(l2) = f(l1 l2) = f(l1) f(l2) 所以所以 f(l1) f(l2)第第2章章 数据流分析数据流分析常量传播框架的非分配性常量传播框架的非分配性说明常量传播框架没有分配性的例子说明常量传播框架没有分配性的例子B1EXITz = x + yx = 2y = 3B3B2x = 3 y = 2第第2
7、章章 数据流分析数据流分析整数格整数格 表示没有任何信息可用表示没有任何信息可用表示可能不是常量表示可能不是常量 3 2 1 0 1 2 3 第第2章章 数据流分析数据流分析用集合之间的包含关系来定义部分函数之间用集合之间的包含关系来定义部分函数之间的偏序的偏序 0,1 , 1,1 , 2,1 常函数常函数1阶乘函数阶乘函数 0,1 , 1,1 , 2,2 0,1 , 1,1 0,1 0,5 . . . . . . . . . . . . . . . . .第第2章章 数据流分析数据流分析数据流方程的求解数据流方程的求解IDEAL，基于程序所有可能执行路径的解，它少，基于程序所有可能执行路径的
8、解，它少于或等于流图上的执行路径于或等于流图上的执行路径Meet Over all Paths(MOP)，不仅汇集了所有可，不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值执行路径的数据流值Maximum Fixed Point(MFP)，由迭代算法得到，由迭代算法得到的解的解迭代算法得到的迭代算法得到的MFP解总是安全的解总是安全的 MFP MOP IDEAL第第2章章 数据流分析数据流分析MOP和和MFP的比较的比较由由MOP的定义，有的定义，有MOPoB4 = (fB3fB1) (fB3fB2) (vENTRY)在迭代
9、算法在迭代算法(MFP)中，中，如果按如果按B1，B2，B3和和B4的次序的次序访问结点，那么访问结点，那么MFPoB4 = fB3(fB1(vENTRY) fB2(vENTRY) 说说明明路路径径上上较较早早汇合之影响的流图汇合之影响的流图B1ENTRYB4B3B2第第2章章 数据流分析数据流分析敏感性分析敏感性分析路径敏感分析路径敏感分析根据条件分支语句中的谓词来计算不同路径上的根据条件分支语句中的谓词来计算不同路径上的信息，它能够区分控制流图上不同路径的信息信息，它能够区分控制流图上不同路径的信息路径不敏感分析路径不敏感分析先前讨论的都是路径不敏感分析先前讨论的都是路径不敏感分析流不敏感
10、分析流不敏感分析语句的执行次序对分析来说无关紧要，语句的执行次序对分析来说无关紧要，S1; S2和和S2; S1的分析结果肯定一样的分析结果肯定一样流敏感分析流敏感分析先前讨论的都是流敏感分析先前讨论的都是流敏感分析第第2章章 数据流分析数据流分析敏感性分析敏感性分析上下文不敏感分析上下文不敏感分析组合所有调用点的状态信息，对过程体仅分析一组合所有调用点的状态信息，对过程体仅分析一次，返回状态集合的信息用于所有的返回点次，返回状态集合的信息用于所有的返回点上下文敏感分析上下文敏感分析区分带不同上下文信息的不同调用区分带不同上下文信息的不同调用第第2章章 数据流分析数据流分析过程间分析的关注点过程间分析的关注点上下文敏感分析上下文敏感分析要注意调用和返回的匹配，注意上下文信息的传要注意调用和返回的匹配，注意上下文信息的传递递参数传递的方式参数传递的方式仅考虑传值和传结果方式仅考虑传值和传结果方式其他如传引用，会引起别名其他如传引用，会引起别名过程作为参数过程作为参数在此不考虑在此不考虑
