Abstract

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.

 

Keywords

Java, Alias Analysis, Reference-Set, Exception, Propagation Rules

 

Introduction

 

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.

 

References

[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.