Abstract
This paper attempts to address the question of why certain dataflow analysis problems can be solved efficiently, but not others. We focus on flow-sensitive analyses, and give a simple and general result that shows that analyses that require the use of relational attributes for precision must be PSPACE-hard in general. We then show that if the language constructs are slightly strengthened to allow a computation to maintain a very limited summary of what happens along an execution path, inter-procedural analyses become EXPTIME-hard. We discuss applications of our results to a variety of analyses discussed in the literature. Our work elucidates the reasons behind the complexity results given by a number of authors, improves on a number of such complexity results, and exposes conceptual commonalities underlying such results that are not readily apparent otherwise.
Original language | English (US) |
---|---|
Pages (from-to) | 67-80 |
Number of pages | 14 |
Journal | Conference Record of the Annual ACM Symposium on Principles of Programming Languages |
DOIs | |
State | Published - 2000 |
Externally published | Yes |
Event | POPL'00 - The 27th ACM SIGPLAN-SIGACT Symposium on Principles og Programming Languages - Boston, MA, USA Duration: Jan 19 2000 → Jan 21 2000 |
ASJC Scopus subject areas
- Software