Answers are grounded in this paper and cite their sources.
At each program point, points-to analysis for statically typed object oriented programming languages (e.g., Java, C++) determines those objects to which a reference may refer (or a pointer may point) during execution. Points-to analysis is necessary for any semantics based software tools for object oriented systems. Our new complexity results for points-to analysis distinguish the difficulty of intraprocedural and interprocedural points-to analyses for languages with combinations of single-level types (i.e., types with data members only of primitive type), exceptions with or without subtyping, and dynamic dispatch. Our results include: 1) the first polynomial-time algorithm for points-to analysis in the presence of exceptions that handles a robust subset of Java without threads and can be applied to C++; 2) proof that the above algorithm is safe, in general, and provably precise on programs with single-level types and exceptions without subtyping, but not dynamic dispatch, thus, this case is in P; 3) proof that an interprocedural points-to analysis problem with single-level types and exceptions with subtyping, but without dynamic dispatch, is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of points-to analysis in programs without exceptions are presented, including an algorithm with worst-case bound of O(n/sup 5/), which improves over the O(n/sup 7/) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991).
No takes yet. Share an insight, caveat, or question.
Chatterjee et al. (2001) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: