Key points are not available for this paper at this time.
Escape analysis is an abstract interpretation technique for statically optimizing storage management devised by Park & Goldberg 30. The main application of escape analysis is the optimization of storage management and data locality in garbage-collected languages such as ML or JAVA.We improve the previously known exponential complexity bound of Park & Goldberg: we show that first-order escape analysis (EA1) can be solved in almost linear time, and that second-order escape analysis (EA2) is DEXPTIME-hard. We exhibit a fast, equational, path-compression based abstract interpretation algorithm for EA1. We prove that it is sound and complete, and that its time complexity is O(n log2 n).We sketch an extension of the analysis to higher-order functions and imperative operations that is approximate. Finally we briefly present some experimental evidence that escape analysis may be useful in practice.
Alain Deutsch (Wed,) studied this question.