Reviewer Name: Lori

Paper: Callahan 1988

Statement of the Problem/Goals:

This paper focuses on the problem of performing flow sensitive interprocedural side effect analysis. The goal, and the author's contribution, is to develop a solution that is practical enough to be used as part of an interactive tool.

Technical Approach:

The key insight is a novel program representation that allows the analysis to be done in a more efficient way. The author presents a new program representation called a program summary graph, which captures flow sensitive information through procedures, while avoiding the high space and analysis time costs of the supergraph. He formulates both the must-modify (KILL) and may-use-before-define (USE) flow sensitive problems over the program summary graph. Discussions of optimizing the analysis with the use of flow insensitive analysis and also the handling of global variables in the analysis is included.

Discussion/Critique:

To evaluate the approach, the author presents both a complexity analysis of the program summary graph size and the data flow analysis, as well as an empirical study of the size of the psg for a set of 9 numerical Fortran programs.

The conclusions: The data fow analysis runtime is proportional to the size of the psg, while the PSG restricted to formal parameters is proportional to program length, and the total PSG is proportional to progamlength times the number of global variables. His empirical data supports this analysis.

Useful Benefit: The program summary graph is a significant contribution towards enabling fast analysis of flow sensitive information flow across whole programs. Side effect analysis like this can significantly increase the precision of data flow information used for interactive tools as well as program optimization across call sites. As the author notes, the psg is useful for context-insensitive problems, because the complexity of these problems can be greatly reduced.

Author-noted Limitations: Interprocedural flow sensitive problems that are context sensitive like LIVE need other information to be handled correctly and with precision, such as alias information.

My additional noted Limitations: One threat to validity of the experimental results is the use of only 10 programs, of which all are Fortran and none are very large.

Some questions that remain unanswered are: Can the program summary graph be used to aid other analyses? Can the authors classify the kinds of problems that benefit from the psg? What are the issues involved in building a psg for other programming languages, such as object-oriented languages? How does the size of the psg grow for programs in other languages? How can context-sensitive problems utilize the psg in their analysis?

Presentation Comments:

The author clearly presents the problem, motivates the need to solve the problem, and presents a concise description of the solution. The use of examples is good. Including both complexity analysis and some empirical evidence is very good. The work is put into context with others quite well in the related work section.