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

Interprocedural slicing is logspace complete for PTIME.

The problem of obtaining "meetoverallvalidpaths" solutions to
interprocedural versions of distributive dataflowanalysis problems is
PTIMEhard.

Obtaining "meetoverallvalidpaths" solutions to interprocedural
versions of distributive dataflowanalysis problems that involve
finite sets of dataflow facts (such as the classical "gen/kill"
problems) is logspace complete for PTIME.
These results provide evidence that there do not exist fast
(NCclass) 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 interproceduralanalysis computations.
(Click here to access the paper:
PostScript,
PDF.)