数据流分析 数据流分析 用于获取数据沿着程序执行路径流动信息的相关技术 是优化的基础 例如 两个表达式是否一定计算得到相同的值？（公共子表达 式) 一个语句的计算结果是否可能被后续语句使用？（死代 码消除) 16
数据流分析 • 数据流分析 – 用于获取数据沿着程序执行路径流动信息的相关技术 – 是优化的基础 • 例如 – 两个表达式是否一定计算得到相同的值？(公共子表达 式) – 一个语句的计算结果是否可能被后续语句使用？(死代 码消除) 16 南大编译许畅
数据流抽象(1) 程序点 三地址语句之前或之后的位置 基本块内部：一个语句之后的程序点等于下一个语句 之前的程序点 如果流图中有B到B,的边，那么B,的第一个语句之前的 点可能紧跟在B,的最后语句之后的点后面执行 从p1到pn的执行路径：p1,p2pm 要么P;是一个语句之前的点，且p1是该语句之后的点 要么P:是某个基本块的结尾，且P+1是该基本块的某个 后继的开头 17
数据流抽象 (1) • 程序点 – 三地址语句之前或之后的位置 – 基本块内部：一个语句之后的程序点等于下一个语句 之前的程序点 – 如果流图中有B1到B2的边，那么B2的第一个语句之前的 点可能紧跟在B1的最后语句之后的点后面执行 • 从p1到pn的执行路径：p1 , p2 , …, pn – 要么pi是一个语句之前的点，且pi+1是该语句之后的点 – 要么pi是某个基本块的结尾，且pi+1是该基本块的某个 后继的开头 17 南大编译许畅
数据流抽象(2) 出现在某个程序点的程序状态 在某个运行时刻，当指令指针指向这个程序点时，各 个变量和动态内存中存放的值 指令指针可能多次指向同一个程序点，因此一个程序 点可能对应多个程序状态 数据流分析把可能出现在某个程序点上的程序状 态集合总结为一些特性 不管程序怎么运行，当它到达某个程序点时，程序状 态总是满足分析得到的特性 不同的分析技术关心不同的信息 18
数据流抽象 (2) • 出现在某个程序点的程序状态 – 在某个运行时刻，当指令指针指向这个程序点时，各 个变量和动态内存中存放的值 – 指令指针可能多次指向同一个程序点，因此一个程序 点可能对应多个程序状态 • 数据流分析把可能出现在某个程序点上的程序状 态集合总结为一些特性 – 不管程序怎么运行，当它到达某个程序点时，程序状 态总是满足分析得到的特性 – 不同的分析技术关心不同的信息 18 南大编译许畅
例子 ·路径 (1) 1,2,3,4,9 d1:a=1 B (2) -1,2,3,4,5,6,7,8,3,4,9 (3) 。 第一次到达(5)，a=1 if read()<=0 gotoB4 B2 (4) 第二次到达(5)，a=243 (5) 之后都是243 (6) 4:b=a B3 d4: a=243 (7) goto B2 ·我们可以说 (8) (5)具有特性a-1或a=243 (9) 表示成为<a,{1,243}> 图9-12 说明数据流抽象的例子程序 19
例子• 路径– 1, 2, 3, 4, 9 – 1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 9 • 第一次到达(5)，a = 1 • 第二次到达(5)，a = 243 – 之后都是243 • 我们可以说 – (5)具有特性a = 1或a = 243 – 表示成为<a, {1, 243}> 19 南大编译许畅
性质和算法 根据不同的需要来设置不同的性质集合，然后设 计分析算法 程序点上的性质被表示成为数据流值，求解这些数据 流值实际上就是推导这些性质的过程 例子 如果要求出变量在某个点上的值可能在哪里定值，可 以使用到达定值(Reaching Definition) 。性质形式：x由d定值 如果希望实现常量折叠优化，我们关心的是某个点上 变量x的值是否总是由某个常量赋值语句赋予 。性质形式：x=C,以及x=NAC 20
性质和算法 • 根据不同的需要来设置不同的性质集合，然后设 计分析算法 – 程序点上的性质被表示成为数据流值，求解这些数据 流值实际上就是推导这些性质的过程 • 例子 – 如果要求出变量在某个点上的值可能在哪里定值，可 以使用到达定值 (Reaching Definition) • 性质形式：x由d1定值 – 如果希望实现常量折叠优化，我们关心的是某个点上 变量x的值是否总是由某个常量赋值语句赋予 • 性质形式：x = c，以及x = NAC 20 南大编译许畅