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.

Article Semantic models and abstract interpretation techniques for inductive data structures and pointers Share on Author: Alain Deutsch INRIA Rocquencourt, 78153 Le Chesnay Cedex, France INRIA Rocquencourt, 78153 Le Chesnay Cedex, FranceView Profile Authors Info & Claims PEPM '95: Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationJune 1995 Pages 226–229https://doi.org/10.1145/215465.215594Online:23 June 1995Publication History 21citation564DownloadsMetricsTotal Citations21Total Downloads564Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store-based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. Although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by Jones and Muchnick a decade ago. As a result, optimizing, verifying and parallelizing programs with pointers has remained difficult.We present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. The key idea is to represent alias information by pairs of symbolic access paths which are qualified by symbolic descriptions of the positions for which the alias pair holds.Based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [CWZ90, He90, LR92, CBC93].

We present a static analysis method for determining aliasing and lifetime of dynamically allocated data in lexically scoped, higher-order, strict and polymorphic languages with first class continuations. The goal is validate program transformations that introduce imperative constructs such as destructive updatings, stack allocations and explicit deallocations in order to reduce the run-time memory management overhead. Our method is based on an operational model of higher order functional programs from which we construct statically computable abstractions using the abstract interpretation framework. Our method provides a solution to a problem left open [Hudak 86]: determining isolation of data in the case of higher order languages with structured data.