To everyone who expressed interest in the work I did on the JIT compiler for Japhar: I decided to post this wide in the Japhar/JCL communities, since I think it might be helpful to whomever implements any sort of optimization framework for an OO language. Below are excerpts from a proposal I wrote to get funded for the project from Usenix (which was declined, BTW---one of the reasons I switched projects :) The proposal refers to articles, related work, etc that might be helpful to someone implementing optimizations. In addition, here are some projects you should definitely check out: - Self, self.sunlabs.com - Cecil/Vortex, http://www.cs.washington.edu/research/projects/cecil Here are some other articles I found interesting and possibly useful (I have electronic copies of some of these, if anyone is interested): "A Type System for Java Bytecode Subroutines" by Stata and Abadi, POPL'98 "Does Just in Time == Better Late Then Ever" by Pezbert and Cytron, POPL '97 "The Cartesian Product Algorithm" by Agesen, ECOOP'95 "Fast Interprocedural Class Analysis" by DeFouw, Grove and Chambers, POPL'98 "Points-to Analysis in Almost Linear Time" by Steensgaard, POPL'96 "Call Graph Construction in OO Languages" by Grove, DeFouw, Dean and Chambers, OOPSLA'97 "Optimization of OO Programs Using Static Class Hierarchy Analysis" by Dean Grove, and Chambers , ECOOP'95 Below are the excerpts from my proposal: =============================================================================== PROJECT DESCRIPTION 1. Background The strength of the Java language and its wide availability have quickly made it one of the major problem solving tools for the near future. The robustness and flexibility of this language specification are necessary to create distributed, platform independent solutions that were unheard of a short time ago. But Java cannot and is not standing still. Increased speed of execution, demanded by many new applications, is being addressed, in part, by just-in-time (JIT) compilers. In this regard, SUN's new Hot-Spot technology [1] is designed to optimize Java Virtual Machine (JVM) code in a platform-independent and dynamic way. Unfortunately, SUN's Hot-Spot technology must be purchased at high cost. This is incompatible with the current open environment in which Java coding has thrived, and is not tolerable in the current, swiftly advancing domain of computer science. Therefore, high quality, freely redistributable versions of Hot-Spot-like technology must be developed. However, such new, freely redistributable technology cannot exist in a void. Much of the current Java technology such as the JVM itself, the Java Compiler (javac) and the Java class libraries are proprietary products that commercial, academic, and non-profit users and developers alike must license from SUN Microsystems. Creation of freely redistributable Hot-Spot-like technology cannot be done without the availability of other freely redistributable pieces of the Java environment. Fortunately, such an infrastructure does already exists. Guavac [2], a javac replacement, is available under the General Public License (GPL). Similarly, two Java Virtual Machines exist, Kaffe [3] and Japhar [4], which are available under the GPL and the Library General Public License (LGPL), respectively. Finally, a recently started project, Java Class Libraries (JCL) [5], will create a clean-room implementation of the entire set of Java class libraries for release under the LGPL. Finally, Cygnus Solutions is working on a native compiler for Java [6] which will compile to the back-end representation used by gcc. The current plan is that Cygnus will release this software under a suitable free license [7]. Since these other projects are well underway, it is clear that a niche remains for a Hot-Spot-like, platform-independent JIT compiler. Kaffe does currently provides JIT compilers. However, these are more traditional JIT compilers that simply translate JVM code into native instructions for the machine. Clearly, traditional JIT compilers provide a very important feature that can produce a substantial speed-up in execution time. In contrast, any software that optimizes the JVM code directly (as Hot-Spot-like technology does) will also result in a substantial speed-up, and will give the added benefit of easy integration with traditional JIT compilers. This integration will produce a combined set of optimizations that will greatly increase the speed of JVM code execution. 2. Goals The primary goal of this project is to research, implement, benchmark, maintain, and possibly port GNU-Spot, a Hot-Spot-like, platform-independent JIT compiler for the JVM. The project began with a survey of the current academic literature concerning optimizations of dynamic object-oriented languages. Much work has been done on an academic level in this area. Unfortunately, only in rare occasions has this academic work been translated into viable products to benefit the larger user community. One of the goals of this research is to make that "technology transfer." In fact, this type of technology may be the best place to attempt such a "technology transfer." There are indications [8] that SUN used such academic research in the development of Hot-Spot technology. Since this academic work is, for the most part, in the public domain, there are no impediments to the development of GNU-Spot, which will incorporate these same research ideas. Upon completion of the survey of academic work, the second phase of this project will focus on the actual implementation of GNU-Spot. GNU-Spot will be written primarily in ANSI C, since ANSI C is highly portable and fast for implementation of system software like compilers. GNU-Spot will be built to run on as many Unix-like operating systems to which we can gain access for testing. This includes GNU/Linux, FreeBSD, Solaris, HPUX, and possibly others. GNU-Spot will be directly integrated with the development of the Japhar JVM. The Japhar JVM was chosen because it uses the latest techniques in Java development. For example, Japhar conforms to the Java Native Interface (JNI) specification from SUN. It is our hope that GNU-Spot can stay on the cutting edge, as Japhar is, with the latest Java technology. When a working version of GNU-Spot is stable, benchmark Java code will be collected. Extensive testing of GNU-Spot against Japhar without GNU-Spot and against Kaffe will be done to determine realistic numbers for the runtime effects that GNU-Spot has on JVM execution time. These numbers will be collected into a concise document and published. Once benchmark data have been collected, the project will focus on the composition of a Master's thesis, and derived from that work, at least two papers, that will be submitted for publication at USENIX-sponsored conferences. We feel that the USENIX community will benefit from published work that describes how the academic research was applied to create a usable product, how GNU-spot was implemented, and what results were found in the benchmark trials. Once GNU-Spot has been released, and if time remains, an effort will be made to port GNU-Spot to Kaffe and any other freely redistributable Java Virtual Machines that may have emerged by that point. It is important that GNU-Spot be available to users of many different environments. Kaffe is one very popular JVM environment, so it should not and will not be ignored by this project. 3. Related Work In the previous section, the status of the implementation of related Java system components was discussed. Also, it was inferred that there is much academic work done that can be applied to the implementation of GNU-Spot. This section briefly discusses some of the major optimization research for object-oriented languages that is applicable to GNU-Spot. Research into applicable academic work is ongoing, and a grant from USENIX will assist in the completion of this ongoing research. However, enough variety of optimization algorithms have already been found to make GNU-Spot a successful project, regardless of what additional optimizations are found later and subsequently implemented. Some of the most important work in the area of dynamic optimization of object-oriented languages has been concerning the Self language. Self is a pure, object-oriented language. A good deal of research has been done on optimizations for Self's run-time environment. There are many publications that concern optimizations of Self [10, 11, 12] that can be directly applied to the optimization of JVM code. In fact, Urs Hoelzle, one of the original architects of Self, has noted that SUN has used these optimization techniques as the foundation for their Hot-Spot technology [8]. There is no reason that the same techniques cannot be adapted to GNU-Spot, and this is our goal. We hope to incorporate these optimizations and others found in the literature to build a highly optimized, platform-independent, JIT compiler for the JVM. However, Self is not the only project that has sought to optimize object-oriented languages. The Cecil/Vortex project at the University of Washington [13] has similar goals. The group at the University of Washington has proposed many optimization algorithms, mostly dealing with interprocedural analysis. They have developed advanced methods for call graph construction for object-oriented languages [14], allowing more traditional interprocedural optimizations to work well with object-oriented languages. In addition, they have recently proposed a new framework for fast class analysis [15], which can be used to enable other interesting optimizations that rely on availability of class (i.e., type) information at method invocation. Our current work indicates that some of the static optimizations developed by the Cecil/Vortex Project and other researchers might be useful in GNU-Spot. Although such optimizations were designed to take place during a static compilation phase, some of these optimizations appear to run quickly enough for use in GNU-Spot. However, even if these optimizations prove too slow for dynamic use in GNU-Spot, we hope to contribute implementations of these optimizations back to Guavac, a static Java source to JVM code compiler. David Engberg, the author of Guavac, recently noted that Guavac has only a peep-hole optimizer, and does not implement any advanced optimization techniques [16]. In addition, Mr. Engberg has encouraged others to contribute to Guavac, since his available time to improve it is limited [17]. Clearly, there are many useful optimizations for object-oriented languages that have been published in the literature. However, most have only been implemented in research programming environments, if at all. The results of these optimizations have been promising, so much so that SUN has already used this research to develop their Hot-Spot technology. GNU-Spot draws upon these same sources and others in the academic community to collect, evaluate and implement these research optimizations into a viable, production quality, platform-independent JIT compiler for the JVM. NOTES [1] Griswold, David. "Breaking the Speed Barrier: The Future of Java Performance." JavaOne - SUN's 1997 Worldwide Java Developer's Conference. [Online] Available at http://java.sun.com/javaone/sessions/slides/TT06/title.htm. 25 May 1998. [2] Engberg, David. Guavac Home Page. [Online] Available at http://http.cs.berkeley.edu/~engberg/guavac. 25 May 1998. [3] Wilkinson, Tim. Kaffe - A Virtual Machine to Run Java Code. [Online] Available at http://www.kaffe.org. 25 May 1998. [4] Toshok, Christoph. Japhar - The Hungry Java Runtime. [Online] Available at http://www.hungry.com/products/japhar. 25 May 1998. [5] Jones, Brian. JCL - A free clean room implementation of the Java class libraries. [Online] Available at http://www.oryxsoft.com/projects/jcl. 25 May 1998. [6] Cygnus Solutions. Cygnus Implementation Plans for the Java Platform. [Online] Available at http://www.cygnus.com/product/javalang. 28 May 1998. [7] Bothner, Per. Electronic mail to the author. 22 March 1998. [8] Hoelzle, Urs. Urs Hoelzle. [Online] Available at http://www.cs.ucsb.edu/~urs. 25 May 1998. [10] Hoelzle, Urs and Ungar, David. "Reconciling Responsiveness with Performance in Pure Object-Oriented Languages." ACM Transactions on Programming Languages and Systems 18(4):355-400, 1996. [11] Hoelzle, Urs and Agesen, Ole. "Dynamic vs. Static Optimization Techniques for Object-Oriented Languages." Theory and Practice of Object Systems 1(3), 1996. [12] Hoelzle, Urs, Chambers, Craig, and Ungar, David. "Optimizing Dynamically-Typed Object-Oriented Programming Languages with Polymorphic Inline Caches." In ECOOP '91, Proceedings of the Fifth European Conference on Object-Oriented Programming. Geneva, Switzerland, July, 1991. [13] University of Washington Cecil/Vortex Project. [Online] Available at http://www.cs.washington.edu/research/projects/cecil. 27 May 1998. [14] Grove, David, et al. "Call Graph Construction in Object-Oriented Languages". In OOPSLA'97 Conference Proceedings. Atlanta, GA, October 1997. [15] DeFouw, Greg, Grove, David and Chambers, Craig. "Fast interprocedural class analysis". In Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. San Diego, CA, January 1998. [16] Engberg, David. Electronic mail to the author. 26 May 1998. [17] Engberg, David. Electronic mail to the author. 20 May 1998. [18] Rashid, Terri Watson. Electronic mail to the author. 20 May 1998. -- - [EMAIL PROTECTED] - Bradley M. Kuhn - [EMAIL PROTECTED] - http://www.ebb.org/bkuhn
