数据流抽象(1) ·程序点 三地址语句之前或之后的位置 基本块内部:一个语句之后的程序点等于下一个语 句之前的程序点 如果流图中有B1到B的边,那么B的第一个语句之 前的点可能紧跟在B1的最后语句之后的点后面执行 从p1到p2的执行路径:p1,p2,…,pn 要么p是一个语旬之前的点,且pi是该语旬之后 的点 要么p是某个基本块的结尾,且pi+1是该基本块的 某个后继的开头
数据流抽象（1） • 程序点 – 三地址语句之前或之后的位置 – 基本块内部：一个语句之后的程序点等于下一个语 句之前的程序点 – 如果流图中有B1到B2的边，那么B2的第一个语句之 前的点可能紧跟在B1的最后语句之后的点后面执行； • 从p1到p2的执行路径：p1 , p2 , …, pn – 要么pi是一个语句之前的点，且pi+1是该语句之后 的点 – 要么pi是某个基本块的结尾，且pi+1是该基本块的 某个后继的开头
数据流抽象(2) 出现在某个程序点的程序状态 在某个运行时刻,当指令指针指向这个程序点时, 各个变量和动态内存中存放的值 指令指针可能多次指向同一个程序点 因此一个程序点可能对应多个程序状态 ·数据流分析把可能出现在某个程序点上的程序 状态集合总结为一些特性 不管程序怎么运行,当它到达某个程序点时,程序 状态总是满足分析得到的特性; 不同的分析技术关心不同的信息; 为了高效、自动地进行数据流分析,通常要求 这些特性能够被高效地表示和求解
数据流抽象（2） • 出现在某个程序点的程序状态： – 在某个运行时刻，当指令指针指向这个程序点时， 各个变量和动态内存中存放的值 – 指令指针可能多次指向同一个程序点 • 因此一个程序点可能对应多个程序状态 • 数据流分析把可能出现在某个程序点上的程序 状态集合总结为一些特性； – 不管程序怎么运行，当它到达某个程序点时，程序 状态总是满足分析得到的特性； – 不同的分析技术关心不同的信息； • 为了高效、自动地进行数据流分析，通常要求 这些特性能够被高效地表示和求解；
例子(1 ·路径 (1) B -123.4.9 12.3.4.5.6.7.8.9 (3) if read()<=0 goto B B 第一次到达(5),a=1; 第二次到达(5),a=243; d: b 且之后都是243。 (7)“3:a=243 goto B2 ·我们可以说: 点(5)具有特性a=1or B a=243。 表示成为<a2{1,243}>图9-12说明数据流抽象的例子程序
例子（1） • 路径 – 1,2,3,4,9 – 1,2,3,4,5,6,7,8,9 – … • 第一次到达(5)，a=1； 第二次到达(5)，a=243； 且之后都是243。 • 我们可以说： – 点(5)具有特性a=1 or a=243。 – 表示成为<a,{1,243}>
性质和算法 根据不同的需要来设置不同的性质集合:然后设讣 分析算法 ·程序点上的性质被表示成为数据流值:求解这些数 据流值的过程实际上就是推导这些性质的过程 例子 如果要求出变量在某个点上的值可能在哪里定值,可 以使用到达定值( reaching definition) ·性质形式:X由dl定值 一如果希望实现常量折叠优化。我们关心的是某个点上 变量X的值是否总是由某个特定的常量赋值语句赋予的。 性质形式:X=C,以及X=NAC 分析得到的性质集合应该是一个安全的佔计值 即根据这些性质进行优化不会改变程序的语义
性质和算法 • 根据不同的需要来设置不同的性质集合；然后设计 分析算法 • 程序点上的性质被表示成为数据流值；求解这些数 据流值的过程实际上就是推导这些性质的过程 • 例子 – 如果要求出变量在某个点上的值可能在哪里定值，可 以使用到达定值(reaching definition) • 性质形式：x由d1定值 – 如果希望实现常量折叠优化，我们关心的是某个点上 变量x的值是否总是由某个特定的常量赋值语句赋予的。 • 性质形式：x=c，以及x=NAC • 分析得到的性质集合应该是一个安全的估计值 – 即根据这些性质进行优化不会改变程序的语义
数据流分析模式 ·数据流分析中,程序点和数据流值关联起来 数据流值表示了程序点具有的性质; 和某个程序点关联的数据流值:程序远行中经过这 个点时必然满足的这个条件: 域 所有可能的数据流值的集合称为这个数据流值的域 不同的应用选用不同的域;比如到达定值: 目标是分析在某个点上,各个变量的值由哪些语旬定值; 因此数据流值是定值(即三地址语旬)的集合,表明集 合中的定值对某个变量定值了
数据流分析模式 • 数据流分析中，程序点和数据流值关联起来 – 数据流值表示了程序点具有的性质； – 和某个程序点关联的数据流值：程序运行中经过这 个点时必然满足的这个条件； • 域 – 所有可能的数据流值的集合称为这个数据流值的域 – 不同的应用选用不同的域；比如到达定值： • 目标是分析在某个点上，各个变量的值由哪些语句定值； • 因此数据流值是定值（即三地址语句）的集合，表明集 合中的定值对某个变量定值了