【大学课件】数据流分析

1、第第2章章 数据流分析数据流分析 内容概述内容概述 数据流分析推导的是数据沿着程序数据流分析推导的是数据沿着程序 执行路径流动的信息执行路径流动的信息 过程内的分析：可用表达式分析、到达定过程内的分析：可用表达式分析、到达定 值分析等值分析等 过程间分析过程间分析 Shape分析分析 理论根底理论根底 数据流方程的求解数据流方程的求解 第第2章章 数据流分析数据流分析 数据流分析的用途数据流分析的用途 编译优化、程序维护编译优化、程序维护 程序平安性的检查程序平安性的检查 和编译原理课程的区别和编译原理课程的区别 基于源代码的结构化分析方法，而不是基于基于源代码的结构化分析方法，而不是基于 根

2、本块和程序流图的分析根本块和程序流图的分析 从过程内讨论到过程间从过程内讨论到过程间 强调理论根底强调理论根底 第第2章章 数据流分析数据流分析 数据流分析的正确性数据流分析的正确性 数据流分析所得结论同程序运行时的情况一数据流分析所得结论同程序运行时的情况一 致致 需要定义机器模型和操作语义，证明所得结需要定义机器模型和操作语义，证明所得结 论对操作语义可靠论对操作语义可靠 由于数据流分析收集的信息同根本块和控制由于数据流分析收集的信息同根本块和控制 流有关，通常和变量值无关，因此不同于一流有关，通常和变量值无关，因此不同于一 般的可靠性证明，例如般的可靠性证明，例如HoareHoare逻辑

3、的赋值公逻辑的赋值公 理是可靠的理是可靠的 x = 1 x := x + 1 x = 2x = 1 x := x + 1 x = 2 活泼变量分析活泼变量分析 活泼变量分析的正确性活泼变量分析的正确性 需要将该正确性概念形式地表达出来需要将该正确性概念形式地表达出来 在活泼变量的初值相同的不同格局下在活泼变量的初值相同的不同格局下S, S, 1 1 和和S, S, 2 2执行程序执行程序S S的结果应该的结果应该 是一样的是一样的 再细化一下，程序每执行一步，得到的不同再细化一下，程序每执行一步，得到的不同 格局格局S S, , 1 1 和和S S, , 2 2 中，活泼变量的值都相同中，活泼

4、变量的值都相同 第第2章章 数据流分析数据流分析 数据流分析的根底数据流分析的根底 把各种数据流模式作为一个整体来抽象地把各种数据流模式作为一个整体来抽象地 研究，然后可以形式地答复数据流算法的以研究，然后可以形式地答复数据流算法的以 下几个根本问题：下几个根本问题： 在什么情况下数据流分析中使用的迭代算法在什么情况下数据流分析中使用的迭代算法 是正确的？是正确的？ 该迭代算法所得解的精度如何？该迭代算法所得解的精度如何？ 该迭代算法是否收敛？该迭代算法是否收敛？ 数据流方程的解的含义是什么？数据流方程的解的含义是什么？ 第第2章章 数据流分析数据流分析 为一类数据流模式建一个共同理论框架为一

5、类数据流模式建一个共同理论框架 总结已讨论过的四种数据流分析模式总结已讨论过的四种数据流分析模式 整理出该框架的一些根本特征或原那么整理出该框架的一些根本特征或原那么 标准框架中的性质空间要满足的特征标准框架中的性质空间要满足的特征 标准框架中迁移函数要满足的性质标准框架中迁移函数要满足的性质 给出框架的定义给出框架的定义 区分单调框架和分配框架的区别区分单调框架和分配框架的区别 常量传播数据流模式不是分配的常量传播数据流模式不是分配的 第第2章章 数据流分析数据流分析 位向量框架位向量框架Bit vector framework Single-bit representation of ea

6、ch 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 第第2章章 数据流分析数据流分析 分配性蕴涵单调性的证明分配性蕴涵单调性的证明 l1 l2 并且并且f(l1 l2) = f(l1) f(l2) 蕴涵蕴涵 f(l1) f(l2) 证明

7、证明 因为因为f(l2) = f(l1 l2) = f(l1) f(l2) 所以所以 f(l1) f(l2) 第第2章章 数据流分析数据流分析 常量传播框架的非分配性常量传播框架的非分配性 说明常量传播框架没有分配性的例子说明常量传播框架没有分配性的例子 B1 EXIT z = x + y x = 2 y = 3 B3 B2x = 3 y = 2 第第2章章 数据流分析数据流分析 整数格整数格 表示没有任何信息可用表示没有任何信息可用 表示可能不是常量表示可能不是常量 3 2 1 0 1 2 3 第第2章章 数据流分析数据流分析 用集合之间的包含关系来定义局部函数之间用集合之间的包含关系来定义

8、局部函数之间 的偏序的偏序 0,1 , 1,1 , 2,1 常函数常函数1阶乘函数阶乘函数 0,1 , 1,1 , 2,2 0,1 , 1,1 0,1 0,5 . . . . . . . . . . . . . . . . . . . . 第第2章章 数据流分析数据流分析 数据流方程的求解数据流方程的求解 IDEAL，基于程序所有可能执行路径的解，基于程序所有可能执行路径的解， 它少于或等于流图上的执行路径它少于或等于流图上的执行路径 Meet Over all Paths(MOP)，不仅聚集了所，不仅聚集了所 有可能路径的数据流值，而且还包括了那些有可能路径的数据流值，而且还包括了那些 不可

9、能被执行路径的数据流值不可能被执行路径的数据流值 Maximum Fixed Point(MFP)，由迭代算法得，由迭代算法得 到的解到的解 迭代算法得到的迭代算法得到的MFP解总是平安的解总是平安的 MFP MOP IDEAL 第第2章章 数据流分析数据流分析 MOP和和MFP的比较的比较 由由MOP的定义，有的定义，有 MOPoB4 = (fB3 fB1) (fB3 fB2) (vENTRY) 在迭代算法在迭代算法(MFP)中，中， 如果按如果按B1，B2，B3和和B4的次序的次序 访问结点，那么访问结点，那么 MFPoB4 = fB3(fB1(vENTRY) fB2(vENTRY) 说明

10、路径上较早说明路径上较早 集合之影响的流图集合之影响的流图 B1 ENTRY B4 B3 B2 第第2章章 数据流分析数据流分析 敏感性分析敏感性分析 路径敏感分析路径敏感分析 根据条件分支语句中的谓词来计算不同路径上的根据条件分支语句中的谓词来计算不同路径上的 信息，它能够区分控制流图上不同路径的信息信息，它能够区分控制流图上不同路径的信息 路径不敏感分析路径不敏感分析 先前讨论的都是路径不敏感分析先前讨论的都是路径不敏感分析 流不敏感分析流不敏感分析 语句的执行次序对分析来说无关紧要，语句的执行次序对分析来说无关紧要，S1; S2和和 S2; S1的分析结果肯定一样的分析结果肯定一样 流敏感分析流敏感分析 先前讨论的都是流敏感分析先前讨论的都是流敏感分析 第第2章章 数据流分析数据流分析 敏感性分析敏感性分析 上下文不敏感分析上下文不敏感分析 组合所有调用点的状态信息，对过程体仅分析一组合所有调用点的状态信息，对过程体仅分析一 次，返回状态集合的信息用于所有的返回点次，返回状态集合的信息用于所有的返回点 上下文敏感分析上下文敏感分析 区分带不同上下文信息的不同调用区分带不同上下文信息的不同调用 第第2章章 数据流分析数据流