On the Sequential Nature of Interprocedural Program-Analysis Problems

Thomas Reps
University of Wisconsin

In this paper, we study two interprocedural program-analysis problems --- interprocedural slicing and interprocedural dataflow analysis --- and present the following results:

  • 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 PTIME-hard.
  • 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.
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.

(Click here to access the paper: PostScript, PDF.)