Complexity of points-to analysis of Java in the presence of exceptions

At each program point, points-fo analysis for statically typed object-orien ted programming languages (e.g., Java, C++) determines those objects to whi ch 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 disting uish the difficulty of intraprocedural and interprocedural points-to analys es 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 al gorithm 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 progr ams with single-level types and exceptions without subtyping, but not dynam ic dispatch. thus, this case is in P; 3) proof that an interprocedural poin ts-to analysis problem with single-level types and exceptions with subtypin g, 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 algori thm with worst-case bound of O(n(5)), which improves over the O(n(7)) worst -case bound achievable from previous approaches of Reps et al. [53] and Lan di and Ryder [42].