A flow-sensitive alias analysis algorithm is to compute safe and efficient alias sets in Java. For this, a references-set representation of aliased elements, with an accompanying type table, and set of propagation rules are constructed. Further, as an exception construct, we consider try/catch/finally blocks as well as potential exception statement nodes, and incorporate this into the construction of a control flow graph. Finally, to ensure safe alias computation on the control flow graph, we present a structural order traverse of each block and node.
Java, Alias Analysis, Reference-Set, Exception, Propagation Rules
The increasingly popularity Java currently enjoys is due largely to its platform independence, object oriíęented nature, and its usefulness for server site applications. Although the absence of pointer operations makes Java relatively easy to analyze statically, Java has other aspects such as exceptions and threads that can complicate analysis. In particular, objects are accessed by references in Java. Consequently, there is potential for a large numbers of aliases, where an object is referenced by more than one name in a typical Java program.
We propose an alias analysis algorithm that operates upon the reference-set representaíętion and that computes possible aliases. Further, this algorithm can be used in the notoriously complicated case where exception constructs are used. Previous research [BCC97, CBC93, CR97, CS95, EGH94, PR94, PR95, PR96, WWG00] has anaíęlyzed aliases statically for high performance computing such as parallelizing compiler as well as compiler optimization. Consequently, we have seen proposals for alias analysis methods for C/C++ that represent the alias relation with pointers and pointer-to-pointer objects. However, the representation of alias relations is not sufficiently optimized to apply to Java. Thus, we have proposed referred-set representation [WWG00] for Java. Although this method should reduce the alias computation, it may have an associated time penalty caused during usage of the computed alias information. Thus, in this paper, we present an alternative alias relation, reference-set representation in order to achieve a better efficiency and accuracy than in previous efforts, with no loss in safety.
With regards to the static analysis of exceptions in Java, Choi [CGH99] presented a model of excepíętions by analyzing exception instructions in a Java intermediate code. We present a Control Flow Graph (CFG) to compute aliases safely on exception constructs of source codes in Java. Based on these CFGs and propagation rules on reference-set representation, we propose a safe and efficient alias analysis algorithm.
[BCC97] M. Burke, P. Carini, and J. Choi. Interprocedural Pointer Alias Analysis. Research Report RC 21055, IBM T. J. Watson Research Center, December 1997.
[CBC93] J. Choi, M. Burke, and P. Carini. Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects. The 20th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 232-245, January 1993.
[CGHS99] J. Choi, D. Grove, M. Hind, and V. Sarkar. Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs. Proceedings of the ACM SIGPLAN SIGSOFT workshop on Program analysis for software tools and engineering September 6, 1999.
[CR97] R. Chatterjee and B. G. Ryder. Scalable, flow-sensitive type inference for statically typed object-oriented laníęguages. Technical Report DCS-TR-326, Rutgers University, August 1997.
[CS95] P. Carini and H. Srinivasan. Flow-Sensitive Type Analysis for C++. Research Report RC 20267, IBM T. J. Watson Research Center, November 1995.
[EGH94] M. Emami, R.Ghiya, and L. J. Hendren. Context-sensitive interprocedural point-to analysis in the presence of function pointers. SIGPLAN '94 Conference on Programming Language Design and Implementation, 242-256, SIGPLAN Notices, 29(6), 1994
[Flan97] David Flanagan, Java in a nutshell, 2nd Edition, Oí»REILLY, May 1997.
[Much97] S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Academic Press, July 1997.
[PR94] H. D. Pande and B. G. Ryder. Static Type Determination and Aliasing for C++. Technical Report LCSR-TR-236, Rutgers University, December 1994.
[PR95] H. D. Pande and B. G. Ryder. Static Type Determination and Aliasing for C++. Technical Report LCSR-TR-250-A, Rutgers University, October 1995.
[PR96] H. D. Pande and B. G. Ryder. Dat-flow Based Virtual Function Resolution. In LNCS 1145, Proceedings of the Third International Symposium on Static Analysis, 1996.
[WWG00] Jehak Woo, Jongwook Woo and Jean-Luc Gaudiot. Flow-Sensitive Alias Analysis with Referred-Set Repíęresentation for Java. The Fourth International Conference/Exhibition on High Performance Computing in Asia Pacific Region, May 2000.
Analysis for Java with Reference-Set Representation,
Jongwook Woo, Jehak Woo, Isabelle Attali, Denis Caromel, Jean-Luc Gaudiot, and Andrew L Wendelborn
International Conference on Parallel and Distributed Systems, ICPADS 2001, June 26-29, 2001.
Analysis On Type Inference For Class Hierarchy In Java,
Jongwook Woo, Isabelle Attali, Denis Caromel, Jean-Luc Gaudiot, and Andrew L Wendelborn
The 24th Australian Computer Science Conference, ACSC 2001, Jan 29-Feb 2, 2001.