三四者都属于数据流分析, 都是使用传递函数, 基于流图分析
IN[B]: B之前的数据流, 哪些[…对象]在该基本块的开始处[…满足条件]
OUT[B]: B之后的数据流, 哪些[…对象]在该基本块的结束处[…满足条件]
| 概念 | 到达定值 | 活跃变量 | 可用表达式 | 支配节点 |
|---|---|---|---|---|
| 目标 | 表达式(表达式的被赋值对象) | 变量 | 表达式(表达式的计算式) | 节点(基本块) |
| 定义 | 如果存在一条从紧跟在x的定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被杀死(如果在此路径上有对变量x的其它定值d’，则称定值d被定值d’杀死了)，则称定值d到达程序点p | 对于变量x和程序点p，如果在流图中沿着从p开始的某条路径会引用变量x在p点的值，则称变量x在点p是活跃的,否则称变量x在点p不活跃(dead) | 如果从流图的首节点到达程序点p的每条路径都对表达式x op y进行计算，并且从最后一个这样的计算到点p之间没有再次对x或y定值，那么表达式x op y在点p是可用的 | 如果从流图的入口结点到结点n的每条路径都经过d，则称结点d支配(dominate)结点n，记为d dom n |
| 直观理解 | 定值d对变量x赋的值在p处还可以使用 | x在p点之后还有用没(活不活跃) | 在p点被计算过,不需要再次计算 | 要经过n一定要经过d, n被d控制了 |
| 传递函数 | gen(B), kill(B) f: 加上生成的, 减去杀死的 | use(B): 引用了B,使用之前没有对B定值 def(B): 定义了B,定义之后没有对B引用 | e_gen(B), e_kill(B) 计算e_gen时先加再减,计算e_kill先减再加 | |
| 生成杀死定义 | a = b + c 生成了定值a, 并杀死了a的其他所有定值(在其他任何基本块内) | a = b + c 定义了a, 引用了b, c a = a + b 定义了a, 但没有引用a | a = b + c 先生成了表达式b + c, 然后杀死了所有给b和c复制的表达式 先生成再杀死, 也可以认为杀死优先于生成 | |
| 相关链 | 引用定值链: 可能到达某一次引用的所有定值 | 定值引用链: 某一个定值能到达的所有引用 | ||
| 正/逆 | 正 | 逆 | 正 | 逆 |
| 并/交 | 并 | 并 | 交 | 交 |
| 初值 | 空集 | 空集 | 全集 | 入口 (每个节点一定被入口节点支配) |
正/逆: 正向数据流还是逆向数据流
并/交: 计算时是前置数据流的并还是交
初值: 算法将每个数据流的初值规定成什么
举例
到达定值:
活跃变量:
版权声明：本文为xiaoyouyouaaa原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。