![[ IBM Research ]](http://www.research.ibm.com/images/masthead.gif){kind=small}
![[ Find ]](http://www.ibm.com/i/v8/b/fi.gif){kind=small}
![[ News ]](http://www.ibm.com/i/v8/b/ne.gif){kind=small}
![[ Products ]](http://www.ibm.com/i/v8/b/pro.gif){kind=small}
![[ Support ]](http://www.ibm.com/i/v8/b/su.gif){kind=small}
![[ Business solutions ]](http://www.ibm.com/i/v8/b/so.gif){kind=small}
![[ Inside IBM ]](http://www.ibm.com/i/v8/b/ins_h.gif){kind=small}
![[ Interest groups ]](http://www.ibm.com/i/v8/b/int.gif){kind=small}
|
 |
Jikes RVM (Jalapeņo) Publications
Authors: B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P.Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley Journal: IBM System Journal, Vol 39, No 1, February 2000. Abstract: Jalapeņo is a virtual machine for Java™ servers written in the Java language. To be able to address the requirements of servers (performance and scalability in particular), Jalapeņo was designed “from scratch” to be as self-sufficient as possible. Jalapeņo's unique object model and memory layout allows a hardware null-pointer check as well as fast access to array elements, fields, and methods. Run-time services conventionally provided in native code are implemented primarily in Java. Java threads are multiplexed by virtual processors (implemented as operating system threads). A family of concurrent object allocators and parallel type-accurate garbage collectors is supported. Jalapeņo's interoperable compilers enable quasi-preemptive thread switching and precise location of object references. Jalapeņo's dynamic optimizing compiler is designed to obtain high quality code for methods that are observed to be frequently executed or computationally intensive. Download: PDF file (667K) Adaptive Optimization in the Jalapeņo JVM Authors: Matthew Arnold, Stephen Fink, David Grove, Michael Hind, and Peter F. Sweeney. Conference: 2000 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'00), Minneapolis, Minnesota, October 15-19, 2000. Abstract: Future high-performance virtual machines will improve performance through sophisticated online feedback-directed optimizations. This paper presents the architecture of the Jalapeņo adaptive optimization system, a system to support leading-edge virtual machine technology and enable ongoing research on online feedback-directed optimizations. We describe the extensible system architecture, based on a federation of threads with asynchronous communication. We present an implementation of the general architecture that supports adaptive multi-level optimization based purely on statistical sampling. We empirically demonstrate that this profiling technique has low overhead and can improve startup and steady-state performance, even without the presence of online feedback-directed optimizations. The paper also describes and evaluates an online feedback-directed inlining optimization based on statistical edge sampling. The system is written completely in the Java programming language, applying the described techniques not only to application code and standard libraries, but also to the virtual machine itself. Download: PDF file (649K) Adaptive Optimization in the Jalapeņo JVM: The Controller's Analytical Model Authors: Matthew Arnold, Stephen Fink, David Grove, Michael Hind, and Peter F. Sweeney. Conference: 200 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-3), Monterey, California, December 10, 2000. Abstract: This paper provides details of the component of the Jalapeņo adaptive optimization system that determines what methods to optimize. This component, called the controller, can choose from one of several optimization levels. In the current implementation, the controller uses a simple cost/benefit analysis to drive adaptive compilation decisions. It has been demonstrated that even this simple analytic model can achieve reasonable performance compared to various JIT compilation scenarios in both startup and steady-state program regimes. This paper outlines several open questions in developing a more accurate controller model. We present two experiments that study the effects of how the current model predicts future execution from the past, a limited experimental evaluation of stability of the current model across applications, and describe our ongoing efforts to improve the Jalapeņo controller. Download: Postscript file (305K) An Empirical Study of Selective Optimization Authors: Matthew Arnold, Michael Hind, and Barbara G. Ryder. Workshop: 13th International Workshop on Languages and Compilers for Parallel Computing, Yorktown Heights, New York, August 10-12, 2000. Abstract: This paper describes an empirical study of selective optimization using the Jalapeņo Java virtual machine. The goal of the study is to provide insight into the design and implementation of an adaptive system by investigating the performance potential of selective optimization and identifying the classes of applications for which this performance can be expected. Two types of offline profiling information are used to guide selective optimization, and several strategies for selecting the methods to optimize are compared. The results show that selective optimization can offer substantial improvement over an optimize-all-methods strategy for short-running applications, and for longer-running applications there is a significant range of methods that can be selectively optimized to achieve close to optimal performance. The results also show that a coarse-grained sampling system can provide enough accuracy to successfully guide selective optimization. Download: PostScript file (270K) Jalapeņo - a Compiler-supported Java Virtual Machine for Servers Authors:Bowen Alpern, Anthony Cocchi, Derek Lieber, Mark Mergen, Vivek Sarkar Conference: Workshop on Compiler Support for Software System (WCSSS 99), Atlanta, GA, May 1999, held in conjunction with PLDI 99 Abstract: In this paper, we give an overview of the Jalapeņo Virtual Machine research project at the IBM T. J. Watson Research Center. The goal of Jalapeņo is to expand the frontier of VM technologies for server machines. As reported in the paper, several of the design and implementation decisions in Jalapeņo depend heavily on compiler support. Two noteworthy features of Jalapeņo are as follows. First, Jalapeņo takes a compile-only approach to program execution. Instead of providing both an interpreter and a JIT compiler as in other systems, bytecodes are always translated to machine code before they are executed. Second, Jalapeņo is itself implemented in Java! This design choice brings with it several advantages as well as technical challenges. The Jalapeņo project was initiated in January 1998 and is work-in-progress. This paper summarizes our design decisions and early experiences in working towards our goal of building a high-performance VM for SMP server machines. Download: poscript
file (224K) The Jalapeņo Dynamic Optimizing Compiler for Java Authors: Michael Burke, Jong-Deok Choi, Stephen Fink, David Grove, Michael Hind, Vivek Sarkar, Mauricio Serrano, V.C. Sreedhar, Harini Srinivasan Conference: 1999 ACM Java Grande Conference, San Francisco, June 12-14, 1999 Abstract: The Jalapeņo Dynamic Optimizing Compiler is a key component of the Jalapeņo Virtual Machine, a new Virtual Machine for Java designed to support efficient and scalable execution of Java applications on SMP server machines. This paper describes the design of the Jalapeņo Optimizing Compiler, and the implementation results that we have obtained thus far. To the best of our knowledge, this is the first dynamic optimizing compiler for Java that is being used in a VM with a compile-only approach to program execution. Download: poscript
file (278K) Authors: Craig Chambers, Igor Pechtchanski, Vivek Sarkar, Mauricio Serrano, Harini Srinivasan Conference: 1999 Workshop on Languages and Compilers for Parallel Computing, La Jolla CA, August 4-6, 1999 Abstract: In this paper, we address the problem of data dependence analysis for Java in the presence of Java's ``non-traditional'' language features such as exceptions, synchronization, and memory consistency. We introduce new classes of edges in a dependence graph to model code motion constraints arising from these language features. We present a linear-time algorithm for constructing this augmented dependence graph using type-based alias analysis for Java. As motivation for dependence analysis, we discuss two phases of the Jalapeņo dynamic optimizing compiler, instruction selection and instruction scheduling, that use the data dependence graph and benefit from more precise dependence analysis. Download: poscript
file (208K) Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs Authors: Jong-Deok Choi, David Grove, Michael Hind, Vivek Sarkar Conference: 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'99), Toulouse, France, September 6, 1999. Abstract: The Factored Control Flow Graph, FCFG, is a novel representation of a program's intraprocedural control flow, which is designed to efficiently support the analysis of programs written in languages, such as Java, that have frequently occurring operations whose execution may result in exceptional control flow. The FCFG is more compact than traditional CFG representations for exceptional control flow, yet there is no loss of precision in using the FCFG. In this paper, we introduce the FCFG representation and outline how standard forward and backward data flow analysis algorithms can be adapted to work on this representation. We also present empirical measurements of FCFG sizes for a large number of methods obtained from a variety of Java programs, and compare these sizes with those of a traditional CFG representation. Download: poscript
file (274K) Escape Analysis for Java Authors: Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff Conference: 1999 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99), Denver, Colorado, November 1, 1999. Abstract: This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can be removed. We introduce a new program abstraction for escape analysis, the connection graph, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory. Download: poscript
file (274K) Implementing Jalapeņo in Java Authors: Bowen Alpern, Dick Attanasio, John J. Barton, Anthony Cocchi, Susan Flynn Hummel, Derek Lieber, Mark Mergen, Ton Ngo, Janice Shepherd, Stephen Smith Conference: 1999 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99), Denver, Colorado, November 1, 1999. Abstract: Jalapeņo is a virtual machine for Java servers written in Java. To be able to address the requirements of servers, performance and scalability in particular, Jalapeņo was designed from scratch to be as self-sufficient as possible. Jalapeņo's object model and memory layout allows a hardware null-pointer check as well as fast access to array elements and, virtual and static, fields and methods. Runtime services conventionally provided in native code are implemented in Java. Java threads are multiplexed by virtual processors (implemented as operating system threads). A family of concurrent object allocators and parallel type-accurate garbage collectors is supported. Three inter-operable compilers enable quasi-preemptive thread switching and precise location of object references. Jalapeņo's dynamic optimizing compiler is designed to obtain high quality code for methods that are observed to be frequently executed and/or computationally intensive. Download: postscript file (217K) Issues in High-Performance Programming in Java Authors: Bowen Alpern and Susan Flynn-Hummel Conference: High Performance Computing System, June 13th, 1999 (HPCS99 Tutorial) Abstract: Java is a modern object-oriented
type-safe programming language with automatic memory management. These features make it
attractive to anyone responsible for developing and maintaining a large software project.
Its multithreading support is a further inducement to those anxious to exploit parallel
processing hardware. To date, however, there has been a performance penulty for using the
language. For the vast majority of programming efforts, this is marginal concern at most.
But, for performance programming, any degradation in performance is a potential show
stopper. Download: postscript file Part 1 (764K), Part 2 (656K) Unified Analysis of Object And Array References in Strongly Typed Languages Authors: Stephen Fink, Kathleen Knobe, and Vivek Sarkar Conference: 2000 Static Analysis Symposium (SAS 2000), Santa Barbara, CA, June , 2000. Abstract: We present a simple, unified approach
for the analysis and optimization of object field and array element accesses in strongly
typed languages, that works in the presence of object references/pointers. This approach
builds on Array SSA form, a uniform representation for capturing control and data flow
properties at the level of array elements. The techniques presented here extend previous
analyses at the array element level to handle both array element and object field accesses
uniformly. Download: postscript file (240K) Optimizing Java Programs in the Presence of Exceptions Authors: Manish Gupta, Jong-Deok Choi, and Michael Hind Conference: 14th European Conference on Object-Oriented Programming (ECOOP 2000), Cannes, France, June 12-16, 2000. Abstract: The support for precise exceptions in Java, combined with frequent checks for runtime exceptions, leads to severe limitations on the compiler's ability to perform program optimizations that involve reordering of instructions. This paper presents a novel framework that allows a compiler to relax these constraints. We first present an algorithm using dynamic analysis, and a variant using static analysis, to identify the subset of program state that need not be preserved if an exception is thrown. This allows many spurious dependence constraints between potentially excepting instructions (PEIs) and writes into variables to be eliminated. Our dynamic algorithm is particularly suitable for dynamically dispatched methods in object-oriented languages, where static analysis may be quite conservative. We then present the first software-only solution that allows dependence constraints among PEIs to be completely ignored while applying program optimizations, with no need to execute any additional instructions if an exception is not thrown. With a preliminary implementation, we show that for many benchmark programs, a large percentage of methods can be optimized (while honoring the precise exception requirement) without any constraints imposed by frequent runtime exceptions. Finally, we show that relaxing these reordering constraints can lead to substantial improvements (up to a factor of 7 on small codes) in the performance of programs. Download: postscript file (265K) A Comparative Study of Static and Profile-Based Heuristics for Inlining Authors: Matthew Arnold, Stephen Fink,Vivek Sarkar, and Peter F. Sweeney Conference: 2000 ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (DYNAMO'00), Boston, Massachusetts, January 19-21, 2000 Abstract: In this paper, we present a comparative study of static and profile-based heuristics for inlining. Our motivation for this study is to use the results to design the best inlining algorithm that we can for the Jalapeņo dynamic optimizing compiler for Java. We use a well-known approximation algorithm for the knapsack problem as a common "meta-algorithm" for the inlining heuristics studied in this paper. We present performance results for an implementation of these inlining heuristics in the Jalapeņo dynamic optimizing compiler. Our performance results show that the inlining heuristics studied in this paper can lead to significant speedups in execution time (up to 1.68x) even with modest limits on code size expansion (at most 10%). Download: postscript file (247K) A Framework for Interprocedural Analysis and Optimization in the Presence of Dynamic Class Loading Authors: Vugranam C. Sreedhar, Michael Burke, and Jong-Deok Choi Conference: ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI 2000), Vancouver, British Columbia, Canada, June 17-21, 2000 Abstract: Dynamic class loading during program
execution in the JavaTM Programming Language is an impediment for generating code that is
as efficient as code generated using static whole-program analysis and optimization.
Whole-program analysis and optimization is possible for Download: postcript file (228K) Debugging by Remote Reflection Authors: Ton Ngo and John Barton Conference: Euro-Par 2000, Munich, Germany, August 27-September 1. Abstract: Reflection in an object-oriented system allows the structure of objects and classes to be queried at run-time and for data inside objects to be read and written using this structure. Reflection allows ``meta-object'' programming, including, for example, program debugging. Remote Reflection allows objects in one address space to reflect upon objects in a different address space. When applied to a program debugger, remote reflection makes available the full power of object-oriented reflection even when the object being examined is within a malfunctioning or terminated system. We have implemented remote reflection as an extension to an interpreter to create a very effective debugger for Jalapeņo, a research virtual machine for Java written in the Java programming language. Download: postcript file (236K) Linear Scan Register Allocation Authors: Massimiliano Poletto and Vivek Sarkar Journal: ACM Transactions on Programming Languages and Systems, Volume 21 , Issue 5 (Sept. 1999), pp 895-913. Abstract: We describe a new algorithm for fast global register allocation called linear scan. This algorithm is not based on graph coloring, but allocates registers to variables in a single linear-time scan of the variables' live ranges. The linear scan algorithm is considerably faster than algorithms based on graph coloring, is simple to implement, and results in code that is almost as efficient as that obtained using more complex and time-consuming register allocators based on graph coloring. The algorithm is of interest in applications where compile time is a concern, such as dynamic compilation systems, "just-in-time" compilers, and interactive development environments. Download: pdf file (225K) ABCD: Eliminating Array Bounds Checks on Demand Authors: Rastislav Bodik, Rajiv Gupta, and Vivek Sarkar Conference: ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI 2000), Vancouver, British Columbia, Canada, June 17-21, 2000 Abstract: To guarantee typesafe execution,
The Java programming language and other strongly typed languages require bounds checking of array accesses. Because
array-bounds checks may raise exceptions, they block code motion of instructions with side
effects, thus preventing many useful code optimizations, such as partial redundancy
elimination or instruction scheduling of memory operations. Furthermore, because it is not
expressible at bytecode level, the elimination of bounds checks can only be performed at
run time, after the bytecode program is loaded. Using existing powerful bounds-check
optimizers at run time is not feasible, however, because they are too heavyweight for the
dynamic compilation setting. Download: postscript file (244K) |
Java and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
For problems or questions regarding this web contact hind@watson.ibm.com