Master Theses
Diplomarbeit
Diplomarbeit:
Run-time byte code compilation, optimization, and interpretation for Alice
Christian Müller
Advisor: Guido Tack
Responsible Professor: Gert Smolka
On this page you can find some information about my Diplom thesis. The
following picture shortly approximates the topic of my work. Read
below for a more detailed description.
State
- 30.05.2005 Antrittsvortrag
- 29.07.2005 I included a first working prototype of the byte code jitter into
the alice CVS. Although it performs only slight optimizations it is already relatively fast.
It is completely platform independent and tested on MacOS X and AMD 64bit architcture. You can
find the CVS access under
http://www.ps.uni-saarland.de/alice/download.html
- 02.09.2005 I added several small improvements and bug fixes to the prototype and it is now included into the official release of Alice 1.2
- 10.10.2005 I added an experimental version of inlining of small functions and I am now going to benchmark it and to further improve inlining.
- 30.11.2005 Improved self tail calls and translated them into real loops; enhanced inlining so that no superfluous register move is needed on procedure entry or exit; introduced a hot spot architecture that allows more flexible compilation decision than the existing lazy compilation scheme; some more minor performance improvements
- 10.02.2006 Added several specialized instructions; changed the layout of some instructions; improved calling convention conversion after non-tailcalls; first time that the byte code system bootstraps slightly faster than the native code jitter :-)
- 16.02.2006 Abschlussvortrag
- 30.03.2006 Thesis;
Diplomarbeit officially finished
Conceptual Formulation
Title
Run-time byte code compilation, optimization and interpretation for Alice
Abstract
Alice is a functional
programming language based on Standard ML,
extended with support for concurrent, distributed, and constraint
programming. It is implemented as a full-featured, open-source
programming system based on a generic virtual machine library called
Seam. One key feature of
the system is that code is communicated in a
high-level platform independent format, called the Alice Abstract
Code. The system ensures efficient execution by providing run-time
compilation to native code.
Run-time compilation (often called just-in-time or JIT compilation)
is particularly well-suited for Alice: A static compiler can only apply
moderate optimizations because components are linked dynamically. A
run-time compiler can be reflective and take advantage of its greater
knowledge of the current state of the system. For instance, an
application of a primitive integer addition can be inlined as soon as
it is known that the identifier + actually represents integer addition.
Run-time compilation to native code, on the other hand, has three severe
drawbacks: Debugging of the system becomes much more complicated,
porting the system to other platforms is difficult, and generating
efficient code requires deep knowledge of the underlying platform. The
goal of this project is hence to develop a run-time compiler that
generates byte code instead of native code, and to implement a highly
optimized interpreter for that byte code.
The project involves three major work packages:
- Design of the byte code
- Design and implementation of a run-time compiler
- Design and implementation of a byte code interpreter
The design of the byte code should be concise, well-documented and
leave room for run-time optimizations. Both run-time compiler and
interpreter will be implemented using the Seam architecture, which
provides all the low-level services for a virtual machine as well as
mechanisms for plugging in run-time compilers and interpreters.
The criteria of success are
- A well-documented and well-understood byte code for Alice
- An efficient, optimizing run-time compiler
- An efficient, optimized byte code interpreter
We would like to confirm our hypothesis that, given these three
criteria, the resulting performance of the system will at least
equal the current architecture that is based on native code. Our hope
is that thanks to a clear design, a lot of optimizations can be
applied at run time that allow for even better performance.
A possible direction for future work, whether within this project or
as a follow-up, could be to investigate the borderline between
interpreted byte code and native code. A different backend for the
run-time compiler could be used to generate simple native code by
inlining calls to the byte code interpreter. It should be interesting
to see how different degrees of inlining affect the system
performance.
Downloads
- Thesis: my thesis can be retrieved from the paper database
- Byte code unit: the project is officially included in the Alice project
Christian Müller, 03.04.2006