中间表示- 数据流分析
数据流分析往往与优化绑定在一起,如下图所示。
优化的一般模式
程序分析
(1)控制流分析、数据流分析、依赖分析等。
(2)得到被优化程序的静态保守信息,是对动态运行行为的近似。
程序重写
以上一步得到的信息制导对程序的重写。
静态保守
问题:能把上图中的y替换为3吗?如果能,这称之为“常量传播”优化。
实际上,我们在问在L_3处,y的值都有哪些?如果y的值就是一个单元素的集合{3},那么我们在这就可以做常量传播优化。通过静态观察程序的文本,来推断里面某一点上变量值是什么,这就是一个典型的数据流分析。
对程序进行分析的结果表明:只有L_0块中的y = 3能到达L_3。这种分析称为“到达定义”分析。
还是原来的问题:能把上图中的y替换为3吗?如果能,这称之为“常量传播”优化。
编译器需要证明:x == 1?
但若x是程序输入的话,运行时才能知道值。所以编译器只能采用静态能够获得的信息对程序做保守估计:“L_2可能会执行”。
还是原来的问题:能把上图中的y替换为3吗?如果能,这称之为“常量传播”优化。
编译器能够证明可能有L_1或L_2中的对y的赋值能够到达L_3。这同样只依赖于程序的静态结构得到的保守信息,实际只会有一个块能到达。所以真正得到的静态信息是y=2,这样的信息跟它动态的行为也是一样的。
这告诉我们,静态保守尽管往往得到的是程序的静态的近似行为,但是,通过非常仔细的研究它的性质以及设计相应的算法,我们往往可以让这两个集合之间的差别尽可能的小,也就是说,两者尽可能的接近,也就意味着静态时能够得到非常精确的程序将来动态行为的估计,有了精确的信息对于指导我们对程序做优化会更有帮助。
总结
(1)数据流分析通过对程序代码进行静态分析,得到关于程序数据相关的保守信息
- 必须保证程序分析的结果是安全的
(2)根据优化的目标不同,需要进行的数据流分析也不同
接下来我们将研究两种具体的数据流分析:到达定义分析,活性分析