Precise interprocedural dataflow analysis via graph reachability
Thomas Reps, Susan Horwitz, Mooly Sagiv · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1995
The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)—e.g., reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables.
Cited by 1,170 works. doi:10.1145/199448.199462
Authors
References
- The Design and Analysis of Computer Algorithms
- Abstract interpretation
- A unified approach to global program optimization
- Interprocedural slicing using dependence graphs
- Two approaches to interprocedural data flow analysis
- An Algorithm for Structuring Flowgraphs
- RATFOR—a preprocessor for a rational fortran
- Code generation using tree matching and dynamic programming
- Interprocedural constant propagation
- Pointer-induced aliasing: a problem taxonomy