The complexity of copy constant detection in parallel programs
Despite of the well-known state-explosion problem, certain simple but important data-flow analysis problems known as gen/kill problems can be solved efficiently and completely for parallel programs with a shared state. This paper shows that, in all probability, these surprising results cannot be generalized to significantly larger classes of data-flow analysis problems. More specifically, we study the complexity of detecting copy constants in parallel programs, a problem that may be seen as representing the next level of difficulty of data-flow problems beyond gen/kill problems. We show that already the intraprocedural problem for loop-free parallel programs is co-NP-complete and that the interprocedural problem is even PSPACE-hard. For the entire collection see [Zbl 0958.00036].
- Precise interprocedural dependence analysis of parallel programs
- On the sequential nature of interprocedural program-analysis problems
- Constraint-based inter-procedural analysis of parallel programs
- Precise interprocedural dataflow analysis with applications to constant propagation
- On the complexity of flow-sensitive dataflow analyses
- Precise interprocedural dependence analysis of parallel programs
- On the computational complexity of data flow analysis over finite bounded meet semilattices
- Complexity of data dependence problems for program schemas with concurrency
- Fast Detection of Stable and Count Predicates in Parallel Computations
- Program-Conflict-Analysis
- Constraint-based inter-procedural analysis of parallel programs
This page was built for publication: The complexity of copy constant detection in parallel programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762527)