Publications JKU

h1. Publications of the Johannes Kepler University

In close collaboration with Sun Microsystems, several research projects of the [Institute for System Software|http://ssw.jku.at] at the [Johannes Kepler University Linz (JKU)|http://www.jku.at] are based on the Java HotSpot™ VM. Parts of the research are already included in the product version of the VM. This page lists all publications that describe the research projects. Some of them might be of general interest because they describe the current production version, especially of the client compiler. The publications of the projects are ordered by relevance, i.e. the most complete and most recent publications are first.

h3. SSA Form and Register Allocation for the Client Compiler

We changed the high-level intermediate representation of the client compiler to use static single assignment (SSA) form, which simplifies global optimizations. Additionally, we implemented a global register allocator that uses the linear scan algorithm. This work is part of the production version since Java 6.
* Thomas Kotzmann, [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM], Thomas Rodriguez, Kenneth Russell, David Cox: _[_Design of the Java HotSpot™ Client Compiler for Java 6_|http://ssw.jku.at/Research/Papers/Ko08/]_. In _ACM Transactions on Architecture and Code Optimization_, volume 5, issue 1, article 7. ACM Press, 2008. [doi:10.1145/1369396.1370017|http://dx.doi.org/10.1145/1369396.1370017]
Explains the structure of the client compiler, its intermediate representations, and the optimization algorithms. It describes the client compiler of the Java HotSpot™ VM of Java 6. Java 7 and OpenJDK contain no significant changes, so all information up-to-date.

* [Christian Wimmer|http://www.christianwimmer.at]: _[_Linear Scan Register Allocation for the Java HotSpot™ Client Compiler_|http://ssw.jku.at/Research/Papers/Wimmer04Master/]_. Master's thesis, Institute for System Software, Johannes Kepler University Linz, 2004.
Extended description of the client compiler, with a focus on the register allocator. Read Chapter 4 for if you are interested in the details of the compiler and the intermediate representations. The term "research compiler" in this thesis refers to the product version of Java 6 (which was not released at the time of writing).

* [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Optimized Interval Splitting in a Linear Scan Register Allocator_|http://ssw.jku.at/Research/Papers/Wimmer05/]_. In _Proceedings of the ACM/USENIX International Conference on Virtual Execution Environments_, pages 132-141. ACM Press, 2005. [doi:10.1145/1064979.1064998|http://dx.doi.org/10.1145/1064979.1064998]
Description of the register allocation algorithm of the current client compiler.

* [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM], Michael Pfeiffer: _[_Linear Scan Register Allocation in the Context of SSA Form and Register Constraints_|http://ssw.jku.at/Research/Papers/Moe02.html]_. In _Proceedings of the International Conference on Compiler Construction_, LNCS 2304, pages 229-246. Springer-Verlag, 2002.
Describes an early version of the work, so it does not reflect the current product version.

* [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Adding Static Single Assignment Form and a Graph Coloring Register Allocator to the Java HotSpot™ Client Compiler_|http://ssw.jku.at/Research/Reports/Report15.html]_. Technical Report 15, Institute for Practical Computer Science, Johannes Kepler University Linz, 2000.
Describes an early version of the work, so it does not reflect the current product version. The graph coloring register allocator was later replaced by the linear scan register allocator.

h3. Client Compiler Visualizer

Visualization tool for the internal data structures of the Java HotSpot™ client compiler. The tool shows the high-level and the low-level intermediate representations as well as the lifetime intervals used for register allocation. Additionally, the bytecodes of the compiled methods can be shown. Both textual and graphical views are available. The tool uses information emitted by the debug version of the Java HotSpot™ VM, starting with Java 6.
* Homepage of the Java HotSpot™ Client Compiler Visualizer: [https://c1visualizer.dev.java.net/]
The homepage contains the binary download, the source code repository, and the documentation (several bachelor theses and master's theses).

h3. Ideal Graph Visualizer
{anchor:IdealGraphVisualizer}

The Java HotSpot™ server compiler uses a single intermediate representation in all compiler phases, called _ideal graph_. The tool saves snapshots of the graph during the compilation. It displays the graphs and provides filtering mechanisms based on customizable JavaScript code and regular expressions. High performance and sophisticated navigation possibilities enable the tool to handle large graphs with thousands of nodes. The tool will be part of the OpenJDK soon, but there is no release available yet.
* Thomas Würthinger: _[_Visualization of Program Dependence Graphs_|http://ssw.jku.at/Research/Papers/Wuerthinger07Master/]_. Master's thesis, Institute for System Software, Johannes Kepler University Linz, 2007.
This thesis describes the architecture and implementation of the tool and also contains a user guide. It does not describe the final version, but is still up-to-date.

* Thomas Würthinger, [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Visualization of Program Dependence Graphs_|http://ssw.jku.at/Research/Papers/Wuerthinger08/]_. In _Proceedings of the International Conference on Compiler Construction_, LNCS 4959, pages 193-196. Springer-Verlag, 2008. [doi:10.1007/978-3-540-78791-4_13|http://dx.doi.org/10.1007/978-3-540-78791-4_13]
A short tool demonstration paper that briefly sketches the purpose and structure of the application.

h3. Array Bounds Check Elimination for the Client Compiler

We added a fast algorithm for array bounds check elimination to the client compiler that optimizes frequently used patterns of array accesses and uses the deoptimization facilities of the Java HotSpot™ VM. This is a research project, but the algorithm could be part of a future product version.

* Thomas Würthinger, [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Array Bounds Check Elimination in the Context of Deoptimization_|http://www.christianwimmer.at/Publications/Wuerthinger09a/]_. In Science of Computer Programming, volume 74, issue 5-6, pages 279-295. Elsevier, 2009. [doi:10.1016/j.scico.2009.01.002|http://dx.doi.org/10.1016/j.scico.2009.01.002]
Journal paper that describes the optimization process. It shows how deoptimization is used, compares the algorithm with the server compiler, and contains an extensive evaluation.

* Thomas Würthinger, [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Array Bounds Check Elimination for the Java HotSpot™ Client Compiler_|http://ssw.jku.at/Research/Papers/Wuerthinger07/]_. In _Proceedings of the International Conference on Principles and Practice of Programming in Java_, pages 125-133. ACM Press, 2007. [doi:10.1145/1294325.1294343|http://dx.doi.org/10.1145/1294325.1294343]
Conference paper that describes the optimization process, with a focus on the usage of deoptimization to avoid code duplication.

h3. Optimization of Strings
{anchor:StringOpt}

We implemented an optimization that fuses the string object with its character array that holds the actual content. New bytecodes access the characters and allocate the strings. Nevertheless, the optimization is implemented completely inside the VM. The necessary bytecode rewriting is performed by the class loader. Optimized string objects are significantly smaller than the old string and its character array. This eliminates field loads, reduces the memory pressure, and the time necessary for garbage collection. It is a research project, but could show up in a future product version because it has a high impact on the performance.
* Christian Häubl, [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Optimized Strings for the Java HotSpot™ Virtual Machine_|http://www.christianwimmer.at/Publications/Haeubl08a/]_. In _Proceedings of the International Conference on Principles and Practice of Programming in Java_, pages 105-114. ACM Press, 2008. [doi:10.1145/1411732.1411747|http://dx.doi.org/10.1145/1411732.1411747]

* Christian Häubl: _[_Optimized Strings for the Java HotSpot™ Virtual Machine_|http://ssw.jku.at/Research/Papers/Haeubl08Master/]_. Master's thesis, Institute for System Software, Johannes Kepler University Linz, 2008.
This thesis describes the complete architecture and implementation of the optimization, together with a comprehensive evaluation.


h3. Tail Calls

Tail calls are necessary when compiling functional languages, like Scheme, to Java bytecodes. It guarantees that no stack frame is created for recursive calls and thus no stack overflow occurs. Tail calls are supported in the interpreter, the client compiler, and the server compiler. The source code is available from the [Da Vinci Machine|http://openjdk.java.net/projects/mlvm/] project.

* Arnold Schwaighofer: _[_Tail Call Optimization in the Java HotSpot™ VM_|http://ssw.jku.at/Research/Papers/Schwaighofer09Master/]_. Master's thesis, Institute for System Software, Johannes Kepler University Linz, 2009.
This thesis describes the complete architecture and implementation of the virtual machine changes, together with a comprehensive evaluation.

h3. Continuations

Continuations, or 'the rest of the computation', are a concept that is most often used in the context of functional and dynamic programming languages. Our implementation of continuations in the Java virtual machine uses a lazy or on-demand approach. Our system imposes zero run-time overhead as long as no activations need to be saved and restored and performs well when continuations are used.

h3. Escape Analysis for the Client Compiler

In this research project, we implemented a fast algorithm for escape analysis. It detects objects that are accessible only by a single method or thread. Its results are used to replace fields of objects with scalar variables, to allocate objects on the stack instead of the heap, and to remove synchronization. The produced machine code is smaller and executes faster because fewer objects are allocated on the heap and the garbage collector runs less frequently. Deoptimization is used to handle dynamic class loading. There are currently no plans to integrate this work into the product version, however it influenced the implementation of escape analysis for the server compiler.
* Thomas Kotzmann: _[_Escape Analysis in the Context of Dynamic Compilation and Deoptimization_|http://ssw.jku.at/Research/Papers/Ko05b/]_. PhD thesis, Institute for System Software, Johannes Kepler University Linz, 2005.
Describes the details of all algorithms and contains an extensive evaluation as well as a survey of related work.

* Thomas Kotzmann, [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Run-Time Support for Optimizations Based on Escape Analysis_|http://ssw.jku.at/Research/Papers/Ko07/]_. In _Proceedings of the International Symposium on Code Generation and Optimization_, pages 49-60. IEEE Computer Society, 2007. [doi:10.1109/CGO.2007.34|http://dx.doi.org/10.1109/CGO.2007.34]
Conference paper that describes the support necessary in the runtime system, the garbage collector, and the deoptimization framework.

* Thomas Kotzmann, [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Escape Analysis in the Context of Dynamic Compilation and Deoptimization_|http://ssw.jku.at/Research/Papers/Ko05/]_. In _Proceedings of the ACM/USENIX International Conference on Virtual Execution Environments_, pages 111-120. ACM Press, 2005. [doi:10.1145/1064979.1064996|http://dx.doi.org/10.1145/1064979.1064996]
Conference paper that describes the core algorithm for escape analysis that is integrated into the client compiler.

h3. Automatic Object Inlining

We designed a feedback-directed optimization system for object inlining and array inlining that utilizes the just-in-time compiler and the garbage collector. _Object inlining_ reduces the costs of field accesses by combining referenced objects with their referencing object. The order of objects on the heap is changed by the garbage collector so that they are placed next to each other. Then their offset is fixed, i.e. the objects are _colocated_. This allows field loads to be replaced by address arithmetic using the just-in-time compiler. _Array inlining_ expands the concepts of object inlining to arrays, which are frequently used for the implementation of dynamic data structures. There are currently no plans to integrate this work into the product version.
* [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Feedback-Directed Object Inlining and Array Inlining_|http://www.christianwimmer.at/Publications/Wimmer08x/]_. Technical Report, Institute for System Software, Johannes Kepler University Linz, 2008.
Summary report that covers all parts of the optimization, but does not describe the algorithmic details. Read this if you want to get familiar with the topic.

* [Christian Wimmer|http://www.christianwimmer.at]: _[_Automatic Object Inlining in a Java Virtual Machine_|http://www.christianwimmer.at/Publications/Wimmer08b/]_. PhD thesis, Institute for System Software, Johannes Kepler University Linz, 2008.
Describes the details of all algorithms and contains an extensive evaluation as well as a survey of related work. Read this if you are interested in the implementation details.

* [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Automatic Array Inlining in Java Virtual Machines_|http://www.christianwimmer.at/Publications/Wimmer08a/]_. In _Proceedings of the International Symposium on Code Generation and Optimization_, pages 14-23. ACM Press, 2008. [doi:10.1145/1356058.1356061|http://dx.doi.org/10.1145/1356058.1356061]
Conference paper that covers only the array inlining part of the optimization system.

* [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Automatic Feedback-Directed Object Inlining in the Java HotSpot™ Virtual Machine_|http://www.christianwimmer.at/Publications/Wimmer07a/]_. In _Proceedings of the ACM/USENIX International Conference on Virtual Execution Environments_, pages 12-21. ACM Press, 2007. [doi:10.1145/1254810.1254813|http://dx.doi.org/10.1145/1254810.1254813]
Conference paper that covers only the object inlining part of the optimization system.

* [Christian Wimmer|http://www.christianwimmer.at], [Hanspeter Mössenböck|http://ssw.jku.at/General/Staff/HM]: _[_Automatic Object Colocation Based on Read Barriers_|http://www.christianwimmer.at/Publications/Wimmer06a/]_. In _Proceedings of the Joint Modular Languages Conference_, LNCS 4228, pages 326-345. Springer-Verlag, 2006. [doi:10.1007/11860990_20|http://dx.doi.org/10.1007/11860990_20]
Conference paper that covers only the object colocation part. It describes an early version of the work, so it does not fully reflect the final version.