An interval-based approach to exhaustive and incremental interprocedural data-flow analysis
- 1 July 1990
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 12 (3), 341-395
- https://doi.org/10.1145/78969.78963
Abstract
We reformulate interval analysis so that it can he applied to any monotone data-flow problem, including the nonfast problems of flow-insensitive interprocedural analysis. We then develop an incremental interval analysis technique that can be applied to the same class of problems. When applied to flow-insensitive interprocedural data-flow problems, the resulting algorithms are simple, practical, and efficient. With a single update, the incremental algorithm can accommodate any sequence of program changes that does not alter the structure of the program call graph. It can also accommodate a large class of structural changes. For alias analysis, we develop an incremental algorithm that obtains the exact solution as computed by an exhaustive algorithm. Finally, we develop a transitive closure algorithm that is particularly well suited to the very sparse matrices associated with the problems we address.Keywords
This publication has 30 references indexed in Scilit:
- A critical analysis of incremental iterative data flow analysis algorithmsIEEE Transactions on Software Engineering, 1990
- Incremental data flow analysis via dominator and attribute updatePublished by Association for Computing Machinery (ACM) ,1988
- The impact of interprocedural analysis and optimization in the R n programming environmentACM Transactions on Programming Languages and Systems, 1986
- Experience with the SETL OptimizerACM Transactions on Programming Languages and Systems, 1983
- The Experimental Compiling SystemIBM Journal of Research and Development, 1980
- A practical interprocedural data flow analysis algorithmCommunications of the ACM, 1978
- On computing the transitive closure of a relationActa Informatica, 1977
- A program data flow analysis procedureCommunications of the ACM, 1976
- A Fast and Usually Linear Algorithm for Global Flow AnalysisJournal of the ACM, 1976
- Flow Graph ReducibilitySIAM Journal on Computing, 1972