On the Sequential Nature of Interprocedural Program-Analysis Problems
University of Wisconsin
In this paper, we study two interprocedural program-analysis problems
--- interprocedural slicing and interprocedural dataflow analysis ---
and present the following results:
These results provide evidence that there do not exist fast
(NC-class) parallel algorithms for interprocedural slicing
and precise interprocedural dataflow analysis (unless PTIME =
NC). That is, it is unlikely that there are algorithms for
interprocedural slicing and precise interprocedural dataflow analysis
for which the number of processors is bounded by a polynomial in the
size of the input, and whose running time is bounded by a polynomial
in the logarithm of the size of the input. This suggests that there
are limitations on the ability to use parallelism to overcome compiler
bottlenecks due to expensive interprocedural-analysis computations.
Interprocedural slicing is log-space complete for PTIME.
The problem of obtaining "meet-over-all-valid-paths" solutions to
interprocedural versions of distributive dataflow-analysis problems is
Obtaining "meet-over-all-valid-paths" solutions to interprocedural
versions of distributive dataflow-analysis problems that involve
finite sets of dataflow facts (such as the classical "gen/kill"
problems) is log-space complete for PTIME.
(Click here to access the paper: