一种增量式数据流分析方法
AN INCREMENTAL METHOD OF DATA-FLOW ANALYSIS
-
摘要: 数据流分析是编译器中的重要部分 ,而增量式分析在程序开发环境和过程间优化编译器中有着相当实用的价值 .当程序发生变化时 ,它可以增量式地维护数据流信息 ,而不致因程序的任何小改动都重新进行数据流分析 .给出了一种增量式的消去数据流算法 ,它基于路径简化算法 ,具有和路径简化算法同样的复杂度 ,同样的通用性 (适用于不可归约流图和流函数不完备的情况 ) ,而且能方便地在程序发生变化时维护现有的数据流信息Abstract: Data flow analysis is an important part in a compiler and incremental analysis is very useful in the compilers with interprocedure analysis and optimization or in the programming developing environment. When a program is modified a little or is optimized, incremental analysis can maintain the data flow information, which can avoid recomputing the data flow information of the whole procedure because of a little change. Here, an incremental elimination algorithm of data flow analysis is given. The algorithm is based on a non incremental algorithm-Tarjan’s fast path algorithm. It has fairly good complexity and universality (it can be used in irreducible control flow graph and incomplete flow function set). What’s more, it can maintain data flow information fast and conveniently when a change happens.
下载: