第 2 章 数据流分析

第 2 章 数据流分析

第2章 数据流分析 章 内容概述 数据流分析推导的是数据沿着程序执行路 径流动的信息– 过程内的分析：可用表达式分析、到达-定值分 过程内的分析：可用表达式分析、到达- 析等 – 过程间分析 – Shape分析 分析 – 理论基础 – 数据流方程的求解

第 2 章 数据流分析

第2章 数据流分析 章 数据流分析的用途– 编译优化、程序维护 编译优化、 – 程序安全性的检查

和编译原理课程的区别–基于源代码的结构化分析方法，而不是基于基 基于源代码的结构化分析方法， 基于源代码的结构化分析方法 本块和程序流图的分析 –从过程内讨论到过程间 从过程内讨论到过程间 –强调理论基础 强调理论基础

第 2 章 数据流分析

第2章 数据流分析 章 数据流分析的正确性数据流分析所得结论同程序运行时的情况一致

–需要定义机器模型和操作语义，证明所得结论 需要定义机器模型和操作语义， 需要定义机器模型和操作语义 对操作语义可靠

–由于数据流分析收集的信息同基本块和控制流 由于数据流分析收集的信息同基本块和控制流 有关，通常和变量值无关， 有关，通常和变量值无关，因此不同于一般的可 靠性证明，例如Hoare逻辑的赋值公理是可靠的 靠性证明，例如 逻辑的赋值公理是可靠的 {x = 1} x := x + 1 {x = 2}

第 2 章 数据流分析

活跃变量分析 活跃变量分析的正确性–需要将该正确性概念形式地表达出来 需要将该正确性概念形式地表达出来 –在活跃变量的初值相同的不同格局下 S, σ1 和 在活跃变量的初值相同的不同格局下 在活跃变量的初值相同的不同格局下 执行程序S的结果应该是一样的 S, σ2 执行程序 的结果应该是一样的 –再细化一下，程序每执行一步，得到的不同格 再细化一下，程序每执行一步， 再细化一下 局 S′, σ1′ 和 S′, σ2′ 中，活跃变量的值都相同 ′ ′

第 2 章 数据流分析

第2章 数据流分析 章 数据流分析的基础 把各种数据流模式作为一个整体来抽象地研 究，然后可以形式地回答数据流算法的下列 几个基本问题： 几个基本问题：– 在什么情况下数据流分析中使用的迭代算法是正 确的？ 确的？ – 该迭代算法所得解的精度如何？ 该迭代算法所得解的精度如何？ – 该迭代算法是否收敛？ 该迭代算法是否收敛？ – 数据流方程的解的含义是什么？ 数据流方程的解的含义是什么？

第 2 章 数据流分析

第2章 数据流分析 章 为一类数据流模式建一个共同理论框架– 总结已讨论过的四种数据流分析模式 –整理出该框架的一些基本特征或原则 整理出该框架的一些基本特征或原则 –规范框架中的性质空间要满足的特征 规范框架中的性质空间要满足的特征 –规范框架中

迁移函数要满足的性质 规范框架中迁移函数要满足的性质 –给出框架的定义 给出框架的定义 –区分单调框架和分配框架的区别 区分单调框架和分配框架的区别 –常量传播数据流模式不是分配的 常量传播数据流模式不是分配的

第 2 章 数据流分析

第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

第 2 章 数据流分析

第2章 数据流分析 章 分配性蕴涵单调性的证明l1  l2 并且 1 ∫ l2) = f(l1) ∫ f(l2) 蕴涵 f(l1)  f(l2) 并且f(l

证明因为 所以 f(l2) = f(l1 ∫ l2) = f(l1) ∫ f(l2) f(l1)  f(l2)

第 2 章 数据流分析

第2章 数据流分析 章 常量传播框架的非分配性

x=2 y=3

B1

x=3 y=2

B2

z = x + y B3 EXIT 说明常量传播框架没有分配性的例子

第 2 章 数据流分析

第2章 数据流分析 章 整数格– ⊥表示没有任何信息可用 – 表示可能不是常量

… 3 2

1

0 ⊥

1

2

3

…

第 2 章 数据流分析

第2章 数据流分析 章 用集合之间的包含关系来定义部分函数之间 的偏序常函数1 常函数 阶乘函数 { 0,1 , 1,1 , 2,1 } { 0,1 , 1,1 , 2,2 } ... ... ... { 0,1 , 1,1 } ... ... { 0,1 } { 0,5 } ... ... ...

第 2 章 数据流分析

第2章 数据流分析 章 数据流方程的求解– IDEAL,基于程序所有可能执行路径的解，它 ，基于程序所有可能执行路径的解， 少于或等于流图上的执行路径 – Meet Over all Paths(MOP),不仅汇集了所有可 ， 能路径的数据流值， 能路径的数据流值，而且还包括了那些不可能被 执行路径的数据流值 – Maximum Fixed Point(MFP),由迭代算法得到 ， 的解 – 迭代算法得到的 迭代算法得到的MFP解总是安全的 解总是安全的 MFP MOP IDEAL

第 2 章 数据流分析

第2章 数据流分析 章 MOP和MFP的比较 和 的比较ENTRY

– 由MOP的定义，有 的定义， 的定义 B1 B2 MOPo[B4] = ((fB3 fB1) ∫ (fB3 fB2)) (vENTRY) – 在迭代算法 在迭代算法(MFP)中， 中 B3 如果按B1, , 和 的次序 如果按 ，B2,B3和B4的次序 访问结点， 访问结点，那么 B4 MFPo[B4] = fB3(fB1(vENTRY) ∫ fB2(vENTRY)) 说 明 路 径上 较早 汇合之影响的流图

第 2 章 数据流分析

第2章 数据流分析 章 敏感性分析– 路径敏感分析 根据条件分支语句中的谓词来计算不同路径上的 信息， 信息，它能够区分控制流图上不同路径的信息 – 路径不敏感分析 先前讨论的都是路径不敏感分析 – 流不敏感分析 语句的执行次序对分析来说无关紧要， 语句的执行次序对分析来说无关紧要，S1; S2和 S2; S1的分析结果肯定

一样 – 流敏感分析 先前讨论的都是流敏感分析

第 2 章 数据流分析

第2章 数据流分析 章 敏感性分析– 上下文不敏感分析 组合所有调用点的状态信息，对过程体仅分析一 组合所有调用点的状态信息， 次，返回状态集合的信息用于所有的返回点 – 上下文敏感分析 区分带不同上下文信息的不同调用

第 2 章 数据流分析

第2章 数据流分析 章 过程间分析的关注点– 上下文敏感分析 要注意调用和返回的匹配，注意上下文信息的传 要注意调用和返回的匹配， 递 – 参数传递的方式 仅考虑传值和传结果方式 其他如传引用， 其他如传引用，会引起别名 – 过程作为参数 在此不考虑