Higher-Order and Symbolic Computation, 18(1/2)
Transformational Derivation of an Improved Alias Analysis AlgorithmDeepak Goyal, Calypto Design Systems, Inc.
| Abstract: In this paper we use a program transformational approach to obtain an asymptotically improved may-alias analysis algorithm. We derive an O(N^3) time algorithm for computing an intra-procedural flow sensitive may-alias analysis, where N denotes the number of edges in the program control flow graph (CFG). Our algorithm improves the previous O(N^5) time algorithm by Hind et al. (1999). Our time complexity improvement comes without any deterioration in space complexity. We also show that for a large subclass of programs in which the in-degree and out-degree of all CFG nodes is bounded by a constant, our algorithm is linear in the sum of the number of edges in the CFG of the program and the size of the output, i.e., the size of the computed alias information, and is therefore asymptotically optimal. Our transformational algorithm derivation technique also leads to a simplified yet precise analysis of time complexity. |
This article is not yet available.
![[picture of journal cover]](../LISP.JPG)