ON THE SEQUENTIAL NATURE OF INTERPROCEDURAL PROGRAM-ANALYSIS PROBLEMS

In this paper, we study two interprocedural program-analysis problems- interprocedural slicing and interprocedural dataflow analysis-and pres ent the following results: Interprocedural slicing is log-space comple te for P. The problem of obtaining ''meet-over-all-valid-paths'' solut ions to interprocedural versions of distributive dataflow-analysis pro blems is P-hard. Obtaining ''meet-over-all-valid-paths'' solutions to interprocedural versions of distributive dataflow-analysis problems th at involve finite sets of dataflow facts (such as the classical ''gen/ kill'' problems) is log-space complete for P. These results provide ev idence that there do not exist fast (Nl-class) parallel algorithms for interprocedural slicing and precise interprocedural dataflow analysis (unless P = Nl). That is, it is unlikely that there are algorithms fo r interprocedural slicing and precise interprocedural dataflow analysi s 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 ar e limitations on the ability to use parallelism to overcome compiler b ottlenecks due to expensive interprocedural-analysis computations.