林 姗，郑朝霞

(湖北工业大学计算机学院，湖北 武汉 430068)

随着软件技术的发展，程序结构和程序中数据间的关联日益复杂。数据流分析在分析程序复杂性的基础上，为编译器的各类优化提供全局的和准确的信息分析。现在它也广泛地应用于软件测试、程序验证并行、向量化和并行编程环境等领域。另外，通过数据流分析，不必实际运行程序就能够发现程序运行时的行为，这样可以帮助人们理解程序。格框架为数据流分析提供了统一的、可复用的理论分析框架。笔者在研究数据流分析技术相关理论和基于格的框架基础上，以“未定值先使用变量”的到达定值问题为实例，提出了一种基于格的数据流分析方案。

1 数据流分析的理论基础

数据流分析是一组用以收集程序相关信息的算法。不同的应用其具体实现不同，如对于常量传播的分析，要判断在程序的每个点上，程序使用的各个变量是否具有唯一的常量值，如果是则可以把对变量的引用替换为常数值;而对于活跃变量分析则是确定在程序的每个点上，在某个变量中存放的值是否一定会在读取之前被覆盖掉，如果是则不需要在寄存器或内存中保留该值。但对于程序中的每个指令，数据流分析的结果都描述了该指令每次执行时必然成立的一些性质[1]。

常见的数据流问题有到达定值、活跃变量分析和可用子表达式等。利用这些数据流分析的结果，可以实现编译器的各种优化，如消除公共子表达式、常量折叠、复制传播和清除死代码等。……