-\documentclass[a4paper,twoside]{book}
+\documentclass[10pt,a4paper,twoside]{book}
\usepackage{latexsym}
%\pagestyle{myheadings} \footheight 12pt \footskip 72pt
\author{Andreas Krall et al.}
\date{}
-\includeonly{loader}
-
\begin{document}
\maketitle
\tableofcontents
+%\listoffigures
+%\listoftables
+
\include{intro}
\include{overview}
\bibliographystyle{alpha}
\end{document}
-
}
@INPROCEEDINGS{OgKoNa02,
- AUTHOR = {Takeshi Ogasawara and Hideaki Komatsu and Toshio Nakatani},
- TITLE = {{Optimizing Precision Overhead for x86 Processors}},
- BOOKTITLE = {2nd Java Virtual Machine Research and Technology Symposium (JVM '02)},
- PAGES = {41--50},
- VOLUME = {August 1--2},
- YEAR = 2003
+ AUTHOR = {Takeshi Ogasawara and Hideaki Komatsu and Toshio Nakatani},
+ TITLE = {{Optimizing Precision Overhead for x86 Processors}},
+ BOOKTITLE = {2nd Java Virtual Machine Research and Technology Symposium (JVM '02)},
+ PAGES = {41--50},
+ VOLUME = {August 1--2},
+ YEAR = 2003
}
@misc{AMD,
@misc{Blackdown,
KEY = {Blackdown},
- TITLE = {{Blackdown.org}},
+ TITLE = {Blackdown.org},
HOWPUBLISHED = {\texttt{http://www.blackdown.org/}},
YEAR = 2003
}
@misc{GCJ,
KEY = {GCJ},
- TITLE = {{The GNU Compiler for the Java Programming Language}},
+ TITLE = {The {GNU} Compiler for the {J}ava Programming Language},
HOWPUBLISHED = {\texttt{http://gcc.gnu.org/java/}},
YEAR = 2004
}
@misc{Sun,
KEY = {SUN},
- TITLE = {{Sun Microsystems}},
+ TITLE = {Sun {M}icrosystems},
HOWPUBLISHED = {\texttt{http://www.sun.com/}},
YEAR = 2004
}
+@misc{SunJVM,
+ KEY = {SunJVM},
+ TITLE = {Sun {M}icrosystems {J}ava {V}irtual {M}achine},
+ HOWPUBLISHED = {\texttt{http://java.sun.com/j2se/}},
+ YEAR = 2004
+}
+
+@misc{IBMJVM,
+ KEY = {IBMJVM},
+ TITLE = {{IBM} {J}ava {V}irtual {M}achine},
+ HOWPUBLISHED = {\texttt{http://www-106.ibm.com/developerworks/java/jdk/}},
+ YEAR = 2004
+}
+
@misc{SUSE,
KEY = {SUSE},
- TITLE = {{SUSE Linux}},
+ TITLE = {{SUSE} {L}inux},
HOWPUBLISHED = {\texttt{http://www.suse.com/}},
YEAR = 2004
}
+
+@manual{IA32vol1,
+ TITLE = {IA-32 Intel Architecture Software Developer's Manual Volume 1: Basic Architecture},
+ ORGANIZATION = {Intel Cooperation},
+ ADDRESS = {P.O. Box 7641 Mt. Prospect IL 60056-7641},
+ NOTE = {{Order Number: 245470-009}},
+ YEAR = 2002
+}
+
+@manual{IA32opt,
+ TITLE = {IA-32 Intel Architecture Optimization Reference Manual},
+ ORGANIZATION = {Intel Cooperation},
+ ADDRESS = {\texttt{http://developer.intel.com}},
+ NOTE = {{Order Number: 248966-009}},
+ YEAR = 2003
+}
+
+@manual{AMDopt,
+ TITLE = {AMD Athlon Processor x86 Code Optimization Guide},
+ ORGANIZATION = {Advanced Micro Devices, Inc.},
+ NOTE = {{Publication No. 22007}},
+ MONTH = {February},
+ YEAR = 2002
+}
+
+@MISC{KJC,
+ KEY = {KJC},
+ TITLE = {{KJC} {K}opi {J}ava {C}ompiler},
+ HOWPUBLISHED = {\texttt{http://www.dms.at/kopi/}},
+ YEAR = 2004
+}
+
+@MASTERSTHESIS{Lackner2001,
+ AUTHOR = {Martin Lackner},
+ TITLE = {Extending {J}ava},
+ SCHOOL = {Technische Universit\"at Wien},
+ MONTH = {May},
+ YEAR = 2001
+}
+
+@InProceedings{1998:iccl:jensen,
+ author = "T. Jensen and D. Le M{\'e}tayer and T. Thorn",
+ title = "Security and Dynamic Class Loading in {J}ava: {A}
+ Formalisation",
+ booktitle = "Proceedings of the 1998 International Conference on
+ Computer Languages",
+ publisher = "IEEE Computer Society Press",
+ year = "1998",
+ ISBN = "0-780-35005-7, 0-8186-8454-2, 0-8186-8456-9",
+ pages = "4--15",
+}
+
+@Misc{oai:CiteSeerPSU:523425,
+ title = "Dynamic Class Loading in the Java",
+ author = "Gilad Bracha and Sheng Liang",
+ year = "1999",
+ month = sep # "~26",
+ annote = "The Pennsylvania State University CiteSeer Archives",
+ language = "en",
+ oai = "oai:CiteSeerPSU:523425",
+ rights = "unrestricted",
+ subject = "Gilad Bracha,Sheng Liang Dynamic Class Loading in the
+ Java",
+ URL = "http://citeseer.ist.psu.edu/523425.html;
+ http://www.cs.utah.edu/~gary/classloaders.ps",
+}
+
+@Article{Norton:2000:DCL,
+ author = "James Norton",
+ title = "Dynamic Class Loading in {C++}",
+ journal = "Linux Journal",
+ volume = "73",
+ pages = "??--??",
+ month = may,
+ year = "2000",
+ CODEN = "LIJOFX",
+ ISSN = "1075-3583",
+ bibdate = "Thu Sep 21 07:44:12 MDT 2000",
+ URL = "http://noframes.linuxjournal.com/lj-issues/issue73/3687.html",
+ acknowledgement = ack-nhfb,
+}
+
+@InProceedings{alpe02,
+ title = "Experiences Porting the {J}ikes {RVM} to
+ {L}inux/{IA}32",
+ author = "Bowen Alpern and Maria Butrico and Anthony Cocchi and
+ Julian Dolby and Stephen Fink and David Grove and Ngo
+ Ngo",
+ booktitle = "Usenix Java Virtual Machine Research and Technology
+ Symposium ({JVM} '02)",
+ address = "San Francisco, CA",
+ month = aug,
+ year = "2002",
+ URL = "http://www.research.ibm.com/people/d/dgrove/papers/jvm02.pdf"
+}
+
+@Article{Alpern:2000:JAV,
+ author = "B. Alpern and C. R. Attanasio and J. J. Barton and Burke
+ Burke and P. Cheng and J.-D. Choi and A. Cocchi and
+ S. J. Fink and D. Grove and M. Hind and S. F. Hummel
+ and D. Lieber and V. Litvinov and M. F. Mergen and Ngo
+ Ngo and J. R. Russell and V. Sarkar and M. J. Serrano
+ and J. C. Shepherd and S. E. Smith and V. C. Sreedhar
+ and H. Srinivasan and J. Whaley",
+ title = "The {Jalape{\~n}o} virtual machine",
+ journal = "IBM Systems Journal",
+ volume = "39",
+ number = "1",
+ pages = "211--238",
+ month = "????",
+ year = "2000",
+ CODEN = "IBMSA7",
+ ISSN = "0018-8670",
+ bibdate = "Mon Apr 24 15:43:02 MDT 2000",
+ URL = "http://www.research.ibm.com/journal/sj/391/alpern.html",
+ acknowledgement = ack-nhfb,
+ keywords = "Java",
+ ordernumber = "G321-0137",
+}
\chapter{The Just-In-Time Compiler}
+
\section{Introduction}
-\section{The Java Virtual Machine}
+A Java Virtual Machine can implement four different approaches of
+executing Java byte code:
-\label{chapjvm}
+\begin{itemize}
+\item Interpreter
+\item Ahead-Of-Time Compiler
+\item Just-In-Time Compiler
+\item Mixed Mode
+\end{itemize}
+
+An \textit{Interpreter} interprets every single virtual machine
+instruction in the language the Java Virtual Machine is written in,
+mainly C. Due to this fact an interpreter based Java Virtual Machine
+is easily portable, but the execution speed is very slow, up to ten
+times slower than a current Just-In-Time Compilers or similar code
+written in C.
+
+An \textit{Ahead-Of-Time Compiler} compiles every Java method of a
+class when the class is loaded. This reduces the compiler overhead
+since the compilation of the class methods is done in one step and at
+runtime the method called can be executed immediately. The drawback of
+this approach is the fact that every single method is compiled, even
+if it's not needed. This can use a serious amount of memory and time
+since the java libraries contain a lot of methods.
+
+A \textit{Just-In-Time Compiler} is the solution to the memory and
+compilation time problem. This compiler only compiles a method when it
+is called the first time. The only drawback of this approach is the
+deferred execution of the called method since it must be compiled
+before, but a Just-In-Time Compiler can save much of compilation time.
+
+The \textit{Mixed Mode} is mostly a mixture of an Interpreter and a
+Just-In-Time Compiler. Normally the code is interpreted, but code
+parts which are frequently executed are compiled to native machine
+code with an Just-In-Time Compiler. This technique is used by Sun's
+and IBM's JVM.
+
+CACAO only implements a \textit{Just-In-Time Compiler} and has no
+Interpreter. The main target of CACAO was to build a fast executing
+Java Virtual Machine with short compilation times. Thus the CACAO
+development team decided to only implement a fast compiling
+Just-In-Time Compiler. So every single Java method executed is
+compiled to native machine code.
+
+The following sections decribe some basics of byte code to machine
+code compilation and how the CACAO Just-In-Time Compiler works in
+detail.
+
+
+\section{The Java Virtual Machine}
The JavaVM is a typed stack architecture \cite{javavm96}. There are
different instructions for integer, long integer, floating point and
some important JavaVM instructions and how a Java program is represented by
these instructions.
-\begin{tabular}{ll}
-{\tt iload n}& load contents of local variable n \\
-{\tt istore n}& store stack top in local variable n \\
-{\tt imul }& product of 2 topmost stack elements \\
-{\tt isub }& difference of 2 topmost stack elements \\
-\end{tabular}
+\begin{verbatim}
+ iload n ; load contents of local variable n
+ istore n ; store stack top in local variable n
+ imul ; product of 2 topmost stack elements
+ isub ; difference of 2 topmost stack elements
+\end{verbatim}
The Java assignment statement {\tt a = b - c * d} is translated into
-\begin{tabular}{ll}
-{\tt iload b }& load contents of variable b \\
-{\tt iload c }& load contents of variable c \\
-{\tt iload d }& load contents of variable d \\
-{\tt imul }& compute c * d \\
-{\tt isub }& compute b - (c * d) \\
-{\tt istore a}& store stack top in variable a \\
-\end{tabular}
+\begin{verbatim}
+ iload b ; load contents of variable b
+ iload c ; load contents of variable c
+ iload d ; load contents of variable d
+ imul ; compute c * d
+ isub ; compute b - (c * d)
+ istore a ; store stack top in variable a
+\end{verbatim}
Accessing the fields of objects is handled by the instructions {\tt
getfield} and {\tt putfield}. The instruction {\tt getfield} expects an
The index must be greater than or equal to zero and less than the array
length.
-There a special commands for method invocation. Each method has its own
+There are special commands for method invocation. Each method has its own
virtual stack and an area for local variables. After the method invocation,
the stack of the caller is empty and the arguments are copied into the
first local variables of the called method. After execution of a {\tt
\section{Translation of stack code to register code}
-\label{chaptranslation}
+The architecture of a RISC---\textit{Reduced Instruction Set Computer}
+or CISC---\textit{Complex Instruction Set Computer}---processor is
+completely different from the stack architecture of the Java Virtual
+Machine.
+
+RISC processors have large sets of registers. The Alpha architecture
+has 32 integer registers and 32 floating point registers which are
+both 64-bits wide. They execute arithmetic and logic operations only
+on values which are held in registers. RISC machines are a load-store
+architecture, this means load and store instructions are provided to
+move data between memory and registers. Local variables of methods
+usually reside in registers and are saved in memory only during a
+method call or if there are too few registers. The use of registers
+for parameter passing is defined by calling conventions.
+
+CISC processors have a relatively small set of registers, like the
+IA32 architecture with 8 integer general purpose registers or the
+AMD64 architecture with 16 integer general purpose registers. But, as
+the name implies, CISC processors have a large and complex machine
+instruction set. Unlike the load-store architecture of RISC machines,
+CISC instructions can operate on operands residing in registers and in
+memory locations. Local variables of methods should reside in
+registers, but due to the limited number of registers this very rare
+and most local variables are stored on the stack. Detailed information
+of the IA32 and AMD64 architecture can be found in section
+\ref{sectionia32codegenerator} and section
+\ref{sectionamd64codegenerator} respectively.
-The architecture of a RISC processor is completely different from the stack
-architecture of the JavaVM. RISC processors have large sets of registers.
-(The Alpha has 32 integer registers and 32 floating point registers which
-are both 64 bits wide.) They execute arithmetic and logic operations only
-on values which are held in registers. Load and store instructions are
-provided to move data between memory and registers. Local variables of
-methods usually reside in registers and are saved in memory only during a
-method call or if there are too few registers. The use of registers for
-parameter passing is defined by calling conventions.
\subsection{Machine code translation examples}
by an optimizing C compiler to the following two Alpha instructions (the
variables {\tt a}, {\tt b}, {\tt c} and {\tt d} reside in registers):
-\begin{quote}
-\begin{tabular}{ll}
-{\tt MULL c,d,tmp0 }&{\tt ; tmp0 = c * d }\\
-{\tt SUBL b,tmp0,a }&{\tt ; a = b - tmp0 }\\
-\end{tabular}
-\end{quote}
+\begin{verbatim}
+ MULL c,d,tmp0 ; tmp0 = c * d
+ SUBL b,tmp0,a ; a = b - tmp0
+\end{verbatim}
If JavaVM code is translated to machine code, the stack is eliminated and
the stack slots are represented by temporary variables usually residing in
registers. A naive translation of the previous example would result in the
following Alpha instructions:
-\begin{quote}
-\begin{tabular}{ll}
-{\tt MOVE b,t0 }&{\tt ; iload b } \\
-{\tt MOVE c,t1 }&{\tt ; iload c } \\
-{\tt MOVE d,t2 }&{\tt ; iload d } \\
-{\tt MULL t1,t2,t1}&{\tt ; imul } \\
-{\tt SUBL t0,t1,t0}&{\tt ; isub } \\
-{\tt MOVE t0,a }&{\tt ; istore a} \\
-\end{tabular}
-\end{quote}
+\begin{verbatim}
+ MOVE b,t0 ; iload b
+ MOVE c,t1 ; iload c
+ MOVE d,t2 ; iload d
+ MULL t1,t2,t1 ; imul
+ SUBL t0,t1,t0 ; isub
+ MOVE t0,a ; istore a
+\end{verbatim}
The problems of translating JavaVM code to machine code are primarily the
elimination of the unnecessary copy instructions and finding an efficient
The new compiler computes the exact number of objects needed or computes an
upper bound and allocates the memory for the necessary temporary data
-structures in three big blocks (the basic block array, the instruction
-array and the stack array). Eliminating all the double linked lists also
+structures in three big blocks: the basic block array, the instruction
+array and the stack array. Eliminating all the double linked lists also
reduced the memory requirements by a factor of five.
\subsection{Copy elimination}
-To eliminate unnecessary copies the loading of values is delayed until the
+To eliminate unnecessary copies, the loading of values is delayed until the
instruction is reached which consumes the value. To compute the information
-a the run time stack is simulated at compile time. Instead of values the
+the run time stack is simulated at compile time. Instead of values the
compile time stack contains the type of the value, if a local variable was
loaded to a stack location and similar information. Adl-Tabatabai
\cite{Taba+98} used a dynamic stack which is changed at every instruction.
instructions to later instructions. We use a static stack structure which
enables information flow in both directions.
-Fig.~\ref{Trans1} shows our instruction and stack representation. An
+Figure~\ref{Trans1} shows our instruction and stack representation. An
instruction has a reference to the stack before the instruction and the
stack after the instruction. The stack is represented as a linked list. The
two stacks can be seen as the source and destination operands of an
element not only contains the type of the stack slot but also the local
variable number of which it is a copy, the argument number if it is an
argument, the interface register number if it is an interface. Load (push
-the content of a variable onto the stack) and store store instructions do
+the content of a variable onto the stack) and store instructions do
no generate a copy machine instruction if the stack slot contains the same
local variable. Generated machine instructions for arithmetic operations
directly use the local variables as their operands.
There are some pitfalls with this scheme. Take the example of
-fig.~\ref{Trans2}. The stack bottom contains the local variable {\tt a}.
+figure~\ref{Trans2}. The stack bottom contains the local variable {\tt a}.
The instruction {\tt istore a} will write a new value for {\tt a} and will
make a later use of this variable invalid. To avoid this we have to copy
the local variable to a stack variable. An important decision is at which
case a {\tt store} not only can conflict with copies of a local variable
which result from {\tt load} instructions before the creator of the value,
but also with {\tt load} and {\tt store} instructions which exist between
-the creation of value and the {\tt store}. In fig.~\ref{Trans3} the {\tt
+the creation of value and the {\tt store}. In figure~\ref{Trans3} the {\tt
iload a} instruction conflicts with the {\tt istore a} instruction.
\begin{figure}[htb]
gives the distribution of the distance between the creation of the value
and the corresponding store. In 86\% of the cases the distance is one.
+The output dependences are checked by storing the instruction number of the
+last store in each local variable. If a store conflicts due to dependences
+the creator places the value in a stack register. Additional dependences
+arise because of exceptions. The exception mechanism in Java is precise.
+Therefore {\tt store} instructions are not allowed to be executed before
+an exception raising instruction. This is checked easily be remembering
+the last instruction which could raise an exception. In methods which contain
+no exception handler this conflict can be safely ignored because no
+exception handler can have access to these variables.
+
+
+\subsection{Register allocator}
+
+he current register allocator of CACAO is a very simple,
+straightforward allocator. It simply assigns free registers with a
+\textit{first-come-first-serve} based algorithm. This is mostly
+suitable for RISC architectures with large register sets like Alpha or
+MIPS with 32 integer registers and 32 floating-point registers. For
+these architectures the current register allocator was designed for.
+
+Basically the allocation passes of the register allocator are:
+
+\begin{itemize}
+ \item interface register allocation
+ \item scratch register allocation
+ \item local register allocation
+\end{itemize}
+
+The \texttt{javac} compiler also supports this simple
+\textit{first-come-first-serve} approach CACAO uses and does a
+coloring of the local variables and assigns the same number to
+variables which are not active at the same time. The stack variables
+have implicitly encoded their live ranges. When a value is pushed, the
+live range start. When a value is popped, the live range ends.
+
+Complications arise only with stack manipulation instructions like {\tt dup}
+and {\tt swap}. We flag therefore the first creation of a stack variable and
+mark a duplicated one as a copy. The register used for this variable can
+be reused only after the last copy is popped.
+
+During stack analysis stack variables are marked which have to survive a
+method invocation. These stack variables and local variables are assigned
+to callee saved registers. If there are not enough registers available,
+these variables are allocated in memory.
+
+Efficient implementation of method invocation is crucial to the performance
+of Java. Therefore, we preallocate the argument registers and the return
+value in a similar way as we handle store instructions. Input arguments (in
+Java input arguments are the first variables) for leaf procedures (and
+input arguments for processors with register windows) are preassigned, too.
+
+Since CACAO has now also been ported to CISC architectures like IA32
+and AMD64, the \textit{first-come-first-serve} register allocator has
+hit it's limits. The results produced for an architecture with 8
+integer general purpose registers like IA32 or 16 integer general
+purpose registers like AMD64, is far from perfect. Further details to
+register allocation of these architectures can be found in section
+\ref{sectionia32registerallocation} and section
+\ref{sectionamd64registerallocation} respectively.
+
+The CACAO development team is currently working on a new register
+allocator based on a \textit{linear scan} algorithm. This allocator
+should produce much better results on CISC machines than the current
+register allocator.
+
+
+\subsection{Instruction combining}
+
+Together with stack analysis we combine constant loading instructions
+with selected instructions which are following immediately. In the
+class of combinable instructions are add, subtract, multiply and
+divide instructions, logical and shift instructions, compare/branch
+and array store instructions.
+
+These combined immediate instructions are:
+
+\begin{itemize}
+ \item \texttt{ICMD\_IADDCONST}, \texttt{ICMD\_ISUBCONST},
+ \texttt{ICMD\_IMULCONST}, \texttt{ICMD\_IDIVPOW2},
+ \texttt{ICMD\_IREMPOW2}
+
+ \item \texttt{ICMD\_LADDCONST}, \texttt{ICMD\_LSUBCONST},
+ \texttt{ICMD\_LMULCONST}, \texttt{ICMD\_LDIVPOW2},
+ \texttt{ICMD\_LREMPOW2}
+
+ \item \texttt{ICMD\_IANDCONST}, \texttt{ICMD\_IORCONST},
+ \texttt{ICMD\_IXORCONST}
+
+ \item \texttt{ICMD\_LANDCONST}, \texttt{ICMD\_LORCONST},
+ \texttt{ICMD\_LXORCONST}
+
+ \item \texttt{ICMD\_ISHLCONST}, \texttt{ICMD\_ISHRCONST},
+ \texttt{ICMD\_IUSHRCONST}
+
+ \item \texttt{ICMD\_LSHLCONST}, \texttt{ICMD\_LSHRCONST},
+ \texttt{ICMD\_LUSHRCONST}
+
+ \item \texttt{ICMD\_IFxx}
+
+ \item \texttt{ICMD\_IF\_Lxx}
+
+ \item \texttt{ICMD\_xASTORECONST}
+\end{itemize}
+
+During code generation the constant is checked if it lies in the range
+for immediate operands of the target architecture and appropriate code
+is generated.
+
+Arithmetic and logical instructions are processed straightforward. The
+intermediate command opcode of the current instruction is changed and
+the immediate value from the previous instruction is stored in the
+current instruction. The register pressure is always reduced by one
+register by this optimization.
+
+\texttt{ICMD\_IDIV} and \texttt{ICMD\_IREM} divisions by a constant
+which is a power of two are handled in a special way. They are
+converted into \texttt{ICMD\_IDIVPOW2} and \texttt{ICMD\_IREMPOW2}
+respectively. For \texttt{ICMD\_IDIVPOW2} an immediate value is
+assigned which represents the left shift amount of \texttt{0x1} to get
+the divisor value. In the code generation pass a very fast shift-based
+machine code can be generated for this instruction. For
+\texttt{ICMD\_IREMPOW2} the intermediate value gets one
+subtracted. The generated machine code consists of logical
+\texttt{and}'s, \texttt{neg}'s and a conditional jump. For both
+instructions the generated machine code is much fast than an integer
+division. \texttt{ICMD\_LDIV} and \texttt{ICMD\_LREM} intermediate
+commands are handled respectively.
+
+\texttt{ICMD\_IxSHx} instructions by a constant value are converted
+to \texttt{ICMD\_IxSHxCONST} instructions. Nearly every architecture
+has machine shift instructions by a constant value. This optimization
+always reduces the register pressure by one
+register. \texttt{ICMD\_LxSHx} intermediate commands are converted to
+\texttt{ICMD\_LxSHxCONST} commands respectively.
+
+\texttt{ICMD\_IF\_ICMPxx} intermediate commands are converted to
+\texttt{ICMD\_IFxx} commands. This commands compare the source
+operand directly with an immediate value if possible. The generated
+machine code depends on the architecture. On the IA32 or AMD64
+architecture the immediate value can always be inlined. On RISC
+architectures the immediate value range is limited, like the Alpha
+architecture where the immediate value may be between 0 and 255. On
+architectures which support conditional branches on a source register,
+like Alpha or MIPS, the compare with 0 is optimized to a single
+instruction. This optimization can reduce the register pressure by one
+register. \texttt{ICMD\_IF\_Lxx} intermediate commands are handled
+respectively.
+
+The \texttt{ICMD\_xASTORE} optimization was actually implemented for
+the IA32 and AMD64 architecture. These architectures can handle inline
+immediate values up to their address pointer size, this means 32-bit
+for IA32 and 64-bit for AMD64 respectively. For RISC architectures
+which have a \texttt{REG\_ZERO}---a register which always contains the
+values zero---this array store optimization can be used only for zero
+values. Address array stores---\texttt{ICMD\_AASTORE}---can only be
+optimized in the \texttt{null} pointer case because of the dynamic
+type check. In this case the optimization not only reduces the
+register pressure by one register, but the dynamic type check
+subroutine call can be eliminated.
+
+
+\subsection{Complexity of the algorithm}
+
+The complexity of the algorithm is mostly linear with respect to the number
+of instructions and the number of local variables plus the number of stack
+slots. There are only a small number of spots where it is not linear.
+
+\begin{itemize}
+\item At the begin of a basic block the stack has to be copied to separate
+ the stacks of different basic blocks. Table \ref{tab-1} shows that
+ the stack at the boundary of a basic block is in most cases zero.
+ Therefore, this copying does not influence the linear performance of
+ the algorithm.
+\item A store has to check for a later use of the same variable. Table
+ \ref{tab-2} shows that this is not a problem, too.
+\item A store additionally has to check for the previous use of the same
+ variable between creation of the value and the store. The distances
+ between the creation and the use are small (in most case only 1) as
+ shown by table \ref{tab-3}.
+\end{itemize}
+
+Compiling {\tt javac} 29\% of the compile time are spent in parsing and
+basic block determination, 18\% are spent in stack analysis, 16\% are spent
+in register allocation and 37\% are spent in machine code generation.
+
+
+\subsection{Example}
+
+Figure \ref{IntermediateStack} shows the intermediate representation and
+stack information as produced by the compiler for debugging purposes. The
+{\tt Local Table} gives the types and register assignment for the local
+variables. The Java compiler reuses the same local variable slot for
+different local variables if there life ranges do not overlap. In this
+example the variable slot 3 is even used for local variables of different
+types (integer and address). The JIT-compiler assigned the saved register
+12 to this variable.
+
+One interface register is used in this example entering the basic block
+with label {\tt L004}. At the entry of the basic block the interface
+register has to be copied to the argument register {\tt A00}. This is one
+of the rare cases where a more sophisticated coalescing algorithm could
+have allocated an argument register for the interface.
+
+At instruction 2 and 3 you can see the combining of a constant with an
+arithmetic instruction. Since the instructions are allocated in an array
+the empty slot has to be filled with a {\tt NOP} instruction. The {\tt
+ADDCONSTANT} instruction already has the local variable {\tt L02} as
+destination, an information which comes from the later {\tt ISTORE} at
+number 4. Similarly the {\tt INVOKESTATIC} at number 31 has marked all its
+operands as arguments. In this example all copy (beside the one to the
+interface register) have been eliminated.
+
\begin{figure*}[htb]
\begin{center}
-%\small
\begin{verbatim}
java.io.ByteArrayOutputStream.write (int)void
\end{center}
\end{figure*}
-The output dependences are checked by storing the instruction number of the
-last store in each local variable. If a store conflicts due to dependences
-the creator places the value in a stack register. Additional dependences
-arise because of exceptions. The exception mechanism in Java is precise.
-Therefore {\tt store} instructions are not allowed to be executed before
-an exception raising instruction. This is checked easily be remembering
-the last instruction which could raise an exception. In methods which contain
-no exception handler this conflict can be safely ignored because no
-exception handler can have access to these variables.
+\section{Compiling a Java method}
-\subsection{Register allocation}
+The CACAO JIT compiler is invoked via the
-Expensive register allocation algorithms are neither suitable nor necessary.
-The {\tt javac} compiler does a coloring of the local variables and assigns
-the same number to variables which are not active at the same time. The
-stack variables have implicitly encoded their live ranges. When a value is
-pushed, the live range start. When a value is popped, the live range ends.
+\begin{verbatim}
+ methodptr jit_compile(methodinfo *m);
+\end{verbatim}
-Complications arise only with stack manipulation instructions like {\tt dup}
-and {\tt swap}. We flag therefore the first creation of a stack variable and
-mark a duplicated one as a copy. The register used for this variable can
-be reused only after the last copy is popped.
+function call. This function is just a wrapper function to the
+internal compiler function
-During stack analysis stack variables are marked which have to survive a
-method invocation. These stack variables and local variables are assigned
-callee saved registers. If there are not enough registers available,
-these variables are allocated in memory.
+\begin{verbatim}
+ static methodptr jit_compile_intern(methodinfo *m);
+\end{verbatim}
-Efficient implementation of method invocation is crucial to the performance
-of Java. Therefore, we preallocate the argument registers and the return
-value in a similar way as we handle store instructions. Input arguments (in
-Java input arguments are the first variables) for leaf procedures (and
-input arguments for processors with register windows) are preassigned, too.
+The argument of the compiler function is a pointer to a
+\texttt{methodinfo} structure (see figure \ref{methodinfostructure})
+allocated by the system class loader. This function should not be
+called directly and thus is declared \texttt{static} because the
+wrapper function has to ensure some conditions:
+\begin{itemize}
+ \item enter a monitor on the \texttt{methodinfo} structure to make
+ sure that only one thread can compile the same Java method at the
+ same time
-\subsection{Instruction combining}
+ \item check if the method already has a \texttt{entrypoint}, if so
+ the monitor is left and the entrypoint is returned
-Together with stack analysis we combine constant loading instructions with
-selected instructions which are following immediately. In the class of
-combinable instructions are add, subtract, multiply and divide instructions,
-logical and shift instructions and compare/branch instructions. During code
-generation the constant is checked if it lies in the range for immediate
-operands of the target architecture and appropriate code is generated.
+ \item measure the compiling time if requested
-The old translator did for some complex instructions an expansion in
-multiple instructions to avoid complex instructions in the later passes.
-One of such instructions was the expansion of the {\tt lookup} instruction
-in a series of load constant and compare and branch instructions. Since
-the constants are usually quite small this unnecessarily increased the
-size of the intermediate representation and the final code. The new
-compiler delays the expansion into multiple instructions to the code
-generation pass which reduces all representations and speeds up the
-compilation.
+ \item call the internal compiler function
+ \item leave the monitor and return the functions' \texttt{entrypoint}
+\end{itemize}
-\subsection{Example}
+The internal compiler function \texttt{jit\_compile\_intern} does the
+actual compilation of the Java method. It calls the different passes
+of the JIT compiler.
-Fig. \ref{IntermediateStack} shows the intermediate representation and
-stack information as produced by the compiler for debugging purposes. The
-{\tt Local Table} gives the types and register assignment for the local
-variables. The Java compiler reuses the same local variable slot for
-different local variables if there life ranges do not overlap. In this
-example the variable slot 3 is even used for local variables of different
-types (integer and address). The JIT-compiler assigned the saved register
-12 to this variable.
+If the passed Java method does not have a \textit{Code Attribute} (see
+\ref{sectionmethodloading}) a \texttt{methodptr} to a
+\texttt{do\_nothing\_function} is returned.
-One interface register is used in this example entering the basic block
-with label {\tt L004}. At the entry of the basic block the interface
-register has to be copied to the argument register {\tt A00}. This is one
-of the rare cases where a more sophisticated coalescing algorithm could
-have allocated an argument register for the interface.
+If the method has the \texttt{ACC\_STATIC} flag bit set and the
+methods' class is not yet initialized, \texttt{class\_init} is called
+with the methods' class as argument
-At instruction 2 and 3 you can see the combining of a constant with an
-arithmetic instruction. Since the instructions are allocated in an array
-the empty slot has to be filled with a {\tt NOP} instruction. The {\tt
-ADDCONSTANT} instruction already has the local variable {\tt L02} as
-destination, an information which comes from the later {\tt ISTORE} at
-number 4. Similarly the {\tt INVOKESTATIC} at number 31 has marked all its
-operands as arguments. In this example all copy (beside the one to the
-interface register) have been eliminated.
+Then the compiler passes are called:
+\begin{enumerate}
-\subsection{Complexity of the algorithm}
+ \item \texttt{reg\_init}: initializes the register allocator
-The complexity of the algorithm is mostly linear with respect to the number
-of instructions and the number of local variables plus the number of stack
-slots. There are only a small number of spots where it is not linear.
+ \begin{itemize}
-\begin{itemize}
-\item At the begin of a basic block the stack has to be copied to separate
- the stacks of different basic blocks. Table \ref{tab-1} shows that
- the stack at the boundary of a basic block is in most cases zero.
- Therefore, this copying does not influence the linear performance of
- the algorithm.
-\item A store has to check for a later use of the same variable. Table
- \ref{tab-2} shows that this is not a problem, too.
-\item A store additionally has to check for the previous use of the same
- variable between creation of the value and the store. The distances
- between the creation and the use are small (in most case only 1) as
- shown by table \ref{tab-3}.
-\end{itemize}
+ \item allocates the \texttt{registerdata} structure
-Compiling {\tt javac} 29\% of the compile time are spent in parsing and
-basic block determination, 18\% are spent in stack analysis, 16\% are spent
-in register allocation and 37\% are spent in machine code generation.
+ \item calculate the number of callee saved, temporary and argument
+ registers
+
+ \end{itemize}
+
+ \item \texttt{reg\_setup}: sets up the register allocator data which
+ is changed in every compiler run
+
+ \item \texttt{codegen\_setup}: initializes the code generator
+
+ \begin{itemize}
+
+ \item allocates the \texttt{codegendata} structure
+
+ \item allocate code and data memory
+
+ \end{itemize}
+
+ \item \texttt{parse}: parse pass
+
+ \begin{itemize}
+
+ \item parse the Java Virtual Machine instructions and convert them
+ into CACAO intermediate commands
+
+ \item determine basic blocks
+
+ \end{itemize}
+
+ \item \texttt{analyse\_stack}: analyse stack pass
+
+ \item \texttt{regalloc}: register allocation pass
+
+ \item \texttt{codegen}: code generation pass
+
+ \item \texttt{reg\_close}: release all allocated register allocator
+ memory
+
+ \item \texttt{codegen\_close}: release all allocated code generator
+ memory
+
+\end{enumerate}
+After all compiler passes were run and no exception or error occured,
+the \texttt{entrypoint} of the compiled method is returned.
+The CACAO JIT compiler is designed to be reentrant. This design
+decision was taken to easily support exception throwing during one of
+the compiler passes and to support concurrent compilation in different
+threads running. Concurrent compilation can speed up startup and run
+time especially on multi processor machines.
This wrapper function is required to ensure some requirements:
\begin{itemize}
- \item enter a monitor on the \texttt{classinfo} structure, so that
- only one thread can load the same class or interface at the same time
+ \item enter a monitor on the \texttt{classinfo} structure to make
+ sure that only one thread can load the same class or interface at the
+ same time
\item check if the class or interface is \texttt{loaded}, if it is
\texttt{true}, leave the monitor and return immediately
\subsection{Method loading}
+\label{sectionmethodloading}
As for the fields, the number of the class or interface methods is read from
the binary representation as \texttt{u2} value. For each method the function
\section{Run time type checking}
+\label{sectionruntimetypechecking}
Since type tests for trees are more (space) efficient than type tests for
DAGs, a possible solution is to split a DAG into a tree part and the
\section{IA32 (x86, i386) code generator}
+\label{sectionia32codegenerator}
-Porting to the famous x86 platform was more effort than
+
+\subsection{Introduction}
+
+The IA32 architecture is the most important architecture on the
+desktop market. Since the current IA32 processors are getting faster
+and more powerful, the IA32 architecture also becomes more important
+in the low-end and mid-end server market. Major Java Virtual Machine
+vendors, like Sun or IBM, have highly optimized IA32 ports of their
+Virtual Machines, so it's fairly important for an Open Source Java
+Virtual Machine to have a good IA32 performance.
+
+Porting CACAO to the IA32 platform was more effort than
expected. CACAO was designed to run on RISC machines from ground up,
so the whole code generation part has to be adapted. The first
-approach was to replace the simple RISC macros with x86 code, but this
-turned out to be not successful. So new x86 code generation macros
-were written, with no respect to the old RISC macros.
+approach was to replace the simple RISC macros with IA32 code, but
+this turned out to be not successful. So new IA32 code generation
+macros were written, with no respect to the old RISC macros.
-Some smaller problems occured since the x86 port was the first 32 bit
+Some smaller problems occured since the IA32 port was the first 32 bit
target platform, like segmentation faults due to heap corruption,
which turned out to be a simple \texttt{for} loop bug only hit on 32
bit systems. Most of the CACAO system already was
\subsection{Code generation}
One big difference in writing the new code generation macros was, that
-the x86 architecture is not a \textit{load-store architecture} like
+the IA32 architecture is not a \textit{load-store architecture} like
the RISC machines, but the \textit{machine instructions} can handle
both \textit{memory operands} and \textit{register operands}. This led
to a much more complicated handling of the various ICMDs. The typical
register}, do the calculation and store the result to memory, if the
destination variable resides in memory. If all operands are assigned
to registers, only the calculation is done. This design also works on
-x86 machines but leads to much bigger code size, reduces decoding
+IA32 machines but leads to much bigger code size, reduces decoding
bandwith and increases register pressure in the processor itself,
-which results in lower performance \ref{}. Thus we use all kinds of
-instruction types that are available and decide which one we have to
-use in some \texttt{if} statements:
+which results in lower performance~\cite{IA32opt}. Thus CACAO uses all
+kinds of instruction types that are available and decide which one is
+used in some \texttt{if} statements:
\begin{verbatim}
if (IS_INMEMORY(iptr->dst)) {
}
\end{verbatim}
-For most ICMDs we can further optimize the generated code when one
+For most ICMDs the generated code can be further optimized when one
source variable and the destination variable share the same local
variable.
To be backward compatible, mostly in respect of embedded systems, all
-generated code can be run on i386 systems.
-
-Another problem was the access to the functions data segment. Since
-RISC platforms like ALPHA and MIPS have a procedure pointer register,
-for the x86 platform there had to be implemented a special handling
-for accesses to the data segment, like \texttt{PUTSTATIC} and
-\texttt{GETSTATIC} instructions. The solution is like the handling of
-\textit{jump references} or \textit{check cast references}, which also
-have to be code patched, when the code and data segment are
-relocated. This means, there has to be an extra
+generated code can be run on i386 compatible systems.
+
+Another problem was the access to the functions' data segment. Since
+RISC platforms like Alpha and MIPS have a procedure vector register,
+for the IA32 platform there had to be implemented a special handling
+for accesses to the data segment, like \texttt{ICMD\_PUTSTATIC} and
+\texttt{ICMD\_GETSTATIC} instructions. The solution is like the
+handling of \textit{jump references} or \textit{check cast
+references}, which also have to be code patched, when the code and
+data segment are relocated. This means, there has to be an extra
\textit{immediate-to-register} move (\texttt{i386\_mov\_imm\_reg()})
-before every \texttt{PUT}/\texttt{GETSTATIC} instruction, which moves
-the start address of the procedure, and thus the start address of the
-data segment, in one of the temporary registers (code snippet from
-\texttt{PUTSTATIC}):
+before every \texttt{ICMD\_PUTSTATIC}/\texttt{ICMD\_GETSTATIC}
+instruction, which moves the start address of the procedure, and thus
+the start address of the data segment, in one of the temporary
+registers (code snippet from \texttt{ICMD\_PUTSTATIC}):
\begin{verbatim}
i386_mov_imm_reg(0, REG_ITMP2);
\subsection{Constant handling}
-Unlike RISC machines the x86 architecture has \textit{immediate move}
+Unlike RISC machines the IA32 architecture has \textit{immediate move}
instructions which can handle the maximum bitsize of the
-registers. Thus we don't have to load big constants indirect from the
-data segment, which means a \textit{memory load} instruction, but we
-can move 32 bit constants \textit{inline} into their destination
-registers.
+registers. Thus the IA32 port of CACAO does not have to load big
+constants indirect from the data segment, which means a \textit{memory
+load} instruction, but can move 32 bit constants \textit{inline} into
+their destination registers.
\begin{verbatim}
i386_mov_imm_reg(0xcafebabe, REG_ITMP1);
\subsection{Calling conventions}
-The normal calling convention of the x86 processor is passing all
-function arguments on the stack. The store size depends on the data
-type (the following types reflect the JAVA data types):
+The normal calling conventions of the IA32 processor is passing all
+function arguments on the stack~\cite{IA32vol1}. The store size on the
+stack depends on the data type (see table
+\ref{ia32callingconventionstackstoresizes}).
-\begin{itemize}
- \item \texttt{boolean}, \texttt{byte}, \texttt{char}, \texttt{short}, \texttt{int},
- \texttt{float}, \texttt{void} --- 4 bytes
- \item \texttt{long}, \texttt{double} --- 8 bytes
-\end{itemize}
+\begin{table}
+\begin{center}
+\begin{tabular}[b]{|l|c|}
+\hline
+JAVA Data Type & Bytes \\ \hline
+\texttt{boolean} & \\
+\texttt{byte} & \\
+\texttt{char} & \\
+\texttt{short} & 4 \\
+\texttt{int} & \\
+\texttt{void} & \\
+\texttt{float} & \\ \hline
+\texttt{long} & \\
+\texttt{double} & 8 \\ \hline
+\end{tabular}
+\caption{IA32 calling convention stack store sizes}
+\label{ia32callingconventionstackstoresizes}
+\end{center}
+\end{table}
-We changed this convention for CACAO in a way, that we are using
-always 8 bytes on the stack for each datatype. After calling the function
+This convention has been changed for CACAO in a way, that each
+datatype uses always 8 bytes on the stack. due to this fact after
+calling the function
\begin{verbatim}
void sub(int i, long l, float f, double d);
\end{verbatim}
-we have a stack layout like in figure \ref{stacklayout}.
+the stack layout looks like in figure \ref{stacklayout}.
\begin{figure}[htb]
\begin{center}
\put(30,3){\makebox(24,6){\textit{+4 bytes}}}
\put(30,-3){\makebox(24,6){\textit{stack pointer}}}
-\put(0,45){\makebox(24,6){\textit{double value}}}
+\put(0,45){\makebox(24,6){\texttt{d}}}
\put(0,36){\makebox(24,6){\textit{unused}}}
-\put(0,30){\makebox(24,6){\textit{float value}}}
-\put(0,21){\makebox(24,6){\textit{long value}}}
+\put(0,30){\makebox(24,6){\texttt{f}}}
+\put(0,21){\makebox(24,6){\texttt{l}}}
\put(0,12){\makebox(24,6){\textit{unused}}}
-\put(0,6){\makebox(24,6){\textit{int value}}}
-\put(0,0){\makebox(24,6){\textit{return address}}}
+\put(0,6){\makebox(24,6){\texttt{i}}}
+\put(0,0){\makebox(24,6){return address}}
\end{picture}
-\caption{CACAO x86 stack layout after function call}
+\caption{CACAO IA32 stack layout after function call}
\label{stacklayout}
\end{center}
\end{figure}
-If we pass a 32 bit variable, we just push 4 bytes onto the stack and
-leave the remaining 4 bytes untouched. This makes no problems since we
-do not read a 64 bit value from a 32 bit location. Passing a 64 bit
-value is straightforward.
+If the function passes a 32-bit variable, CACAO just push 4 bytes onto
+the stack and leave the remaining 4 bytes untouched. This does not
+make any problems since CACAO does not read a 64-bit value from a
+32-bit location. Passing a 64-bit value is straightforward.
-With this adaptation, it was possible to use the \textit{stack space
+With this adaptation, it is possible to use the \textit{stack space
allocation algorithm} without any changes. The drawback of this
-decision was, that we have to copy all arguments of a native function
-call into a new stack frame and we have a slightly bigger memory
-footprint.
+decision is, that all arguments of a native function calls have to be
+copied into a new stack frame and the memory footprint is slightly
+bigger.
But calling a native function always means a stack manipulation,
-because you have to put the \textit{JNI environment}, and additionally
-for \texttt{static} functions the \textit{class pointer}, in front of
-the function parameters. So this negligible.
+because the \textit{JNI environment}, and additionally for
+\texttt{static} functions the \textit{class pointer}, have to be
+stored in front of the function parameters. So this negligible.
-For some \texttt{BUILTIN} functions there had to be written
-\texttt{asm\_} counterparts, which copy the 8 byte parameters in their
-correct size in a new stack frame. But this only affected
-\texttt{BUILTIN} functions with more than 1 function parameter. To be
-exactly, 2 functions, namely \texttt{arrayinstanceof} and
-\texttt{newarray}. So this is not a big speed impact.
+For some \texttt{BUILTIN} functions there are assembler function
+counterparts, which copy the 8 byte parameters in their correct size
+in a new stack frame. But this only affects \texttt{BUILTIN} functions
+with more than one function parameter. To be precise, two functions,
+namely \texttt{arrayinstanceof} and \texttt{newarray}. So this is not
+a big speed impact.
Return parameters are stored in different places, this depends on the
return type of the function:
\item \texttt{long}: return value is split up onto the register pair
\texttt{\%edx:\%eax}
- (\texttt{REG\_RESULT2:REG\_RESULT}, high 32 bit in
- \texttt{\%edx}, low 32 bit in \texttt{\%eax})
+ (\texttt{REG\_RESULT2:REG\_RESULT}, high 32-bit in
+ \texttt{\%edx}, low 32-bit in \texttt{\%eax})
\item \texttt{float}, \texttt{double}: return value resides in the
\textit{top of stack} element of the \textit{floating point unit}
- stack (\texttt{st(0)}, described in detail later)
+ stack (\texttt{st(0)}, described in more detail in section
+ \ref{ia32floatingpointarithmetic})
\end{itemize}
-\subsection{Register allocator}
-
-Register usage was another problem in porting the CACAO to x86. An x86
-processor has 8 genernal purpose registers (GPR), of which one is the
-\textit{stack pointer} (SP) and thus it can not be used for arithmetic
-instructions. From the remaining 7 registers, in \textit{worst-case
-instructions} like \texttt{CHECKCAST} or \texttt{INSTANCEOF}, we need
-to reserve 3 temporary registers. So we have 4 registers available.
+\subsection{Register allocation}
+\label{sectionia32registerallocation}
-We use \texttt{\%ebp}, \texttt{\%esi}, \texttt{\%edi} as callee saved
-registers (which are callee saved registers in the x86 ABI) and
-\texttt{\%ebx} as scratch register (which is also a callee saved
-register in the x86 ABI, but we need some scratch registers). So we
-have a lack of scratch registers. But for most ICMD instructions, we
-do not need all, or sometimes none, of the temporary registers.
+Register usage was another problem in porting the CACAO to IA32. An
+IA32 processor has 8 integer general-purpose registers (GPR), of which
+one is the \textit{stack pointer} (SP) and thus can not be used for
+arithmetic instructions. From the remaining 7 registers, in
+\textit{worst-case instructions} like \texttt{CHECKCAST} or
+\texttt{INSTANCEOF}, 3 temporary registers need to be reserved for
+storing temporary values. Due to this fact there are 4 integer
+registers available for arithmetic operations.
-This fact we use in the \texttt{analyse\_stack()} pass. We try to use
-\texttt{\%edx} (which is \texttt{REG\_ITMP3}) and \texttt{\%ecx} (which
-is \texttt{REG\_ITMP2}) as scratch registers for the register
-allocator if certain ICMD instructions are not used in the compiled
-method. So for \textit{best-case situations} CACAO has 3
-\textit{callee saved} and 3 \textit{scratch} registers.
-
-This analysis should be changed from \textit{method level} to
-\textit{basic-block level}, so CACAO could emit better code on x86.
+CACAO uses \texttt{\%ebp}, \texttt{\%esi}, \texttt{\%edi} as callee
+saved registers, which are callee saved registers in the IA32 ABI and
+\texttt{\%ebx} as scratch register, which is also a callee saved
+register in the IA32 ABI. The remaining \texttt{\%eax}, \texttt{\%ecx}
+and \texttt{\%edx} registers are used as the previously mentioned
+temporary registers.
The register allocator itself is very straightforward, this means, it
does neither \textit{linear scan} nor any other analyse of the methods
variables, but allocates registers for the local variables in order as
-they are defined. This may result in good code on RISC machines, as
-there are almost always enough registers available, with 32 registers,
-but can produce really bad code on x86 processors.
+they are defined---\textit{first-come-first-serve}. This may result in
+a fairly good register allocation on RISC machines, as there are
+almost always enough registers available for the functions local
+variables, but can result in a really bad allocation on IA32
+processors.
-So the first step to make the x86 port more competitive with SUN's or
+So the first step to make the IA32 port more competitive with Sun's or
IBM's JVM would be to rewrite the register allocator.
-Basically the allocation order of the register allocator is as
-follows:
-
-\begin{itemize}
- \item interface register allocation
- \item scratch register allocation
- \item local register allocation
-\end{itemize}
+Only small register allocator changes were necessary for the IA32
+port. Since CACAO---on the IA32 architecture---stores all
+\texttt{long} variables, because of lack of integer general-purpose
+registers, in memory locations (described in more detail in section
+\ref{sectionia32longarithmetic}) the register allocator has to be
+adapted to support this feature. This means all \texttt{long}
+variables are assigned to stack locations and tagged with the
+\texttt{INMEMORY} flag.
-The only change which had to be made to all allocator passes, was the
-handling of \texttt{long} variables, because they are all spilled to
-memory (described in more detail in \ref{LongArithmetic}).
+\subsection{Long arithmetic}
+\label{sectionia32longarithmetic}
-\subsection{Long arithmetic}\label{LongArithmetic}
-
-Unlike the PowerPC port, we cannot put \texttt{long}'s in two 32 bit
-integer registers, since we have to little of them. Maybe this could
-bring a speedup, if the register allocator would be more intelligent
-or in leaf functions which have only \texttt{long} variables. But this
-is not implemented yet. So, the current approach is to store all
-\texttt{long}'s in memory, this means they are always spilled.
+Unlike the PowerPC port, the IA32 port cannot easily store
+\texttt{long}'s in two 32-bit integer registers, since there are too
+little of them. Maybe this could bring a speedup, if the register
+allocator would be more intelligent or in leaf functions which have
+only \texttt{long} variables. But this is not implemented yet. So, the
+current approach is to store all \texttt{long}'s in memory, this means
+they are always spilled.
Nearly all \texttt{long} instructions are inline, except two of them:
-\texttt{LDIV} and \texttt{LREM}. These two are computed via
-\texttt{BUILTIN} calls. It would be definitely possible to also
-inline them, but the code size is too big and the latency is so high,
-that the function calls are negligible.
+\texttt{ICMD\_LDIV} and \texttt{ICMD\_LREM}. These two are computed
+via \texttt{BUILTIN} calls. It would also be possible to inline them,
+but the code size would be too big and the latency of the
+\texttt{idiv} machine instruction is so high, that the function calls
+are negligible.
-The x86 processor has some machine instructions which are specifically
-designed for 64 bit operations. Some of them are
+The IA32 processor has some machine instructions which are
+specifically designed for 64-bit operations. With them several 64-bit
+integer arithemtic operations can be implemented very
+efficiently~\cite{AMDopt}. Some of them are
\begin{itemize}
\item \texttt{cltd} --- Convert Signed Long to Signed Double Long
\item \texttt{sbb} --- Integer Subtraction With Borrow
\end{itemize}
-Thus some of the 64 bit calculations like \texttt{LADD} or
-\texttt{LSUB} could be executed in two instructions, if both
+Thus some of the 64-bit calculations like \texttt{ICMD\_LADD} or
+\texttt{ICMD\_LSUB} could be executed in two instructions, if both
operand would reside in registers. But this does not apply to CACAO,
yet.
-All of the \texttt{long} instructions operate on 64 bit, even if it is
-not necessary. The dependency information that would be needed to just
-operate on the lower or upper half of the \texttt{long} variable, is
-not generated by CACAO.
+The generated machine code of intermediate commands which operate on
+\texttt{long} variables instructions always operate on 64-bit, even if
+it is not necessary. The dependency information that would be required
+to just operate on the lower or upper half of the \texttt{long}
+variable, is not generated by CACAO.
\subsection{Floating point arithmetic}
+\label{ia32floatingpointarithmetic}
-Since the i386, with it's i387 counterpart or the i486, the x86
+Since the i386, with it's i387 extension or the i486, the IA32
processor has a \textit{floating point unit} (FPU). This FPU is
implemented as a stack with 8 elements (see table \ref{FPUStack}).
the TOS is executed and decreased for a store from the TOS.
At first sight, the stack design of the FPU is perfect for the stack
-based design of a \textit{java virtual machine} (JVM). But there is a
-big problem. The JVM stack has no fixed size, so it can grow up to
-much more than 8 elements and we get an stack wrap around and thus an
-stack overflow. For this reason we need to implement an
+based design of a Java Virtual Machine. But there is one problem. The
+JVM stack has no fixed size, so it can grow up to much more than 8
+elements and this simply results in an stack wrap around and thus an
+stack overflow. For this reason it it necessary to implement an
\textit{stack-element-to-register-mapping}.
A very basic design idea, is to define a pointer to the current TOS
-offset (\texttt{fpu\_st\_offset}). With this offset we can determine
-the current register position in the FPU stack of an arbitrary
-register. From the 8 stack elements we need to reserve the last two
-ones (\texttt{st(6), st(7)}), so we can load two memory operands onto
-the stack and do the arithmetic on them. Most x86 floating point
-arithmetic operations have an \textit{do arithmetic and pop one
-element} version of the instruction, that means the float arithmetic
-is done and the TOS element is poped off. The remaining stack element
-has the result of the calculation. On the example of the \texttt{FADD}
-ICMD with two memory operands, it looks like this:
+offset (\texttt{fpu\_st\_offset}). With this offset the current
+register position in the FPU stack of an arbitrary register can
+determined. From the 8 stack elements the last two ones
+(\texttt{st(6), st(7)}) are reserved, so two memory operands can be
+loaded onto the stack and to preform an arithmetic operation. Most
+IA32 floating point arithmetic operations have an \textit{do
+arithmetic and pop one element} version of the instruction, that means
+the float arithmetic is done and the TOS element is poped off. The
+remaining stack element has the result of the calculation. On the
+example of the \texttt{ICMD\_FADD} intermediate command with two
+memory operands, it looks like this:
\begin{verbatim}
var_to_reg_flt(s1, src->prev, REG_FTMP1); /* load 1st operand in st(0), increase
This mapping works very good with \textit{scratch registers}
only. Defining \textit{callee saved float registers} makes some
-problemes since the x86 ABI has no callee saved float registers. This
+problemes since the IA32 ABI has no callee saved float registers. This
would need a special handling in the \textit{native stub} of a native
function, namely saving the registers and cleaning the whole FPU
stack, because a C function expects a clear FPU stack.
-Basically the x86 FPU can handle 3 float data types:
+Basically the IA32 FPU can handle 3 float data types:
\begin{itemize}
\item single-precision (32 bit)
The internal data type used by the FPU is always the \textit{double
extended-precision} (80 bit) format. Therefore implementing a IEEE 754
-compliant floating point code on x86 processors is not trivial.
+compliant floating point code on IA32 processors is not trivial.
Correct rounding to \textit{single-precision} or
\textit{double-precision} is only done if the value is stored into
-memory. This means for certain instructions, like \texttt{FMUL} or
-\texttt{FDIV}, a special technique called \textit{store-reload}, has
-to be implemented. This technique is in fact very simple but takes two
-memory accesses more for this instruction.
+memory. This means for certain instructions, like \texttt{ICMD\_FMUL}
+or \texttt{ICMD\_FDIV}, a special technique called
+\textit{store-load}, has to be implemented~\cite{OgKoNa02}. This
+technique is in fact very simple but takes two memory accesses more
+for this instruction.
-For single-precision floats the \textit{store-reload} code could looks
+For single-precision floats the \textit{store-load} code could looks
like this:
\begin{verbatim}
Another technique which has to be implemented to be IEEE 754
compliant, is \textit{precision mode switching}. Mode switching on the
-x86 processor is made with the \texttt{fldcw} (load control word)
-instruction. A \texttt{fldcw} instruction has a quite large overhead,
-so frequently mode switches should be avoided. For this technique
-there are two different approaches:
+IA32 processor is made with the \texttt{fldcw}---load control
+word---instruction. A \texttt{fldcw} instruction has a quite large
+overhead, so frequently mode switches should be avoided. For this
+technique there are two different approaches:
\begin{itemize}
\item \textbf{Mode switch on float arithmetic} --- switch the FPU on
initialization in one precision mode, mostly \textit{double-precision
mode} because \texttt{double} arithmetic is more common. With this
- setting \texttt{doubles} are calculated correctly. To handle
- \texttt{floats} in this approach, the FPU has to be switched into
+ setting \texttt{double}s are calculated correctly. To handle
+ \texttt{float}s in this approach, the FPU has to be switched into
\textit{single-precision mode} before each \texttt{float} instruction
and switched back afterwards. Needless to say, that this is only
useful, if \texttt{float} arithmetic is sparse. For a simple
\textit{double-precision mode}. But the difference on this approach
is, that the precision mode is only switched if the float data type
is changed. That means if your calculation switches from
- \texttt{double} arithmetic to \texttt{float} or backwards. This
- technique makes much sense due to the fact that there are always a
- bunch of instructions of the same data type in one row in a normal
- program. Now the same example as before with this approach:
+ \texttt{double} arithmetic to \texttt{float} arithmetic or
+ backwards. This technique makes much sense due to the fact that there
+ are always a bunch of instructions of the same data type in one row
+ in a normal program. Now the same example as before with this
+ approach:
\begin{verbatim}
...
After this code sequence the FPU is in \textit{single-precision mode}
and if a function return would occur, the caller function would not
- know in which mode the FPU is currently. One solution would be to
- reset the FPU to \textit{double-precision} on a function return, if
+ know which FPU mode is currently set. One solution would be to reset
+ the FPU to \textit{double-precision mode} on a function return, if
the actual mode is \textit{single-precision}.
\end{itemize}
-These techniques and further researches into optimizations which could
-be done, are described in \cite{OgKoNa02}.
-
-All of these described FPU techniques have been implemented in CACAO's
-x86 port, but the results were not completly IEEE 754 compliant. So
-the CACAO developer team decided to be on the safe side and to store
-all float variables in memory, until we have found a solution which is
-fast and 100\% compliant.
+Each of these FPU techniques described have been implemented in
+CACAO's IA32 port, but the results were not completly IEEE 754
+compliant. So the CACAO developer team decided to be on the safe side
+and to store all float variables in memory, until we have found a
+solution which is fast and 100\% compliant.
\subsection{Exception handling}
-The exception handling for the x86 architecture is implemented as
+The exception handling for the IA32 architecture is implemented as
intended to be for CACAO. To handle the common and unexpected, but
-often checked, \texttt{NullPointerException} very fast, we use
-\textit{hardware null-pointer checking}. That means we install a
-signal handler for the \texttt{SIGSEGV} operating system signal and in
-the handler we forward the exception to CACAO's internal exception
-handling system. So if an instruction tries to access the memory at
-address \texttt{0x0}, a \texttt{SIGSEGV} signal is raised because the
-memory page is not read or writeable. After the signal is hit, we have
-to reinstall the handler, so we can catch further exceptions and this
-is done in the handler itself.
-
-The \texttt{SIGSEGV} handler is used on any architecture to which
-CACAO has been ported. Additionally we install a handler for the
-\texttt{SIGFPE} on the x86 architecture. With this handler we can
-catch \texttt{ArithmeticException}'s for integer \textit{/ by zero} in
-hardware and there is no need to write a helper function which checks
-the operands, as it has to be done for the ALPHA or MIPS port.
+often checked, \texttt{java.lang.NullPointerException} very fast,
+CACAO uses \textit{hardware null-pointer checking}. That means a
+signal handler for the \texttt{SIGSEGV} operating system signal is
+installed. If the signal is hit, the CACAO signal handler forwards the
+exception to CACAO's internal exception handling system. So if an
+instruction tries to access the memory at address \texttt{0x0}, a
+\texttt{SIGSEGV} signal is raised because the memory page is not read
+or writeable. After the signal is hit, the handler has to be
+reinstalled, so that further exceptions can be catched. This is done
+in the handler itself.
+
+The \texttt{SIGSEGV} handler is used on any architecture CACAO has
+been ported to. Additionally on the IA32 architecture a handler for
+the \texttt{SIGFPE} signal is installed. With this handler a
+\texttt{java.lang.ArithmeticException}'s for integer \textit{/ by
+zero} can be catched in hardware and there is no need to write helper
+functions, like \texttt{asm\_builtin\_idiv}, which check the division
+operands as this is done for the Alpha or MIPS port.
\section{AMD64 (x86\_64) code generator}
+\label{sectionamd64codegenerator}
+
\subsection{Introduction}
and the upcoming memory address space problem on IA32 high-end
servers, led to a special design decision by AMD. Unlike Intel, with
it's completely new designed 64-bit architecture---IA64---AMD decided
-to extend the IA32 instruction set with new a 64-bit instruction mode.
+to extend the IA32 instruction set with a new 64-bit instruction mode.
Due to the fact that the IA32 instructions have no fixed length, like
this is the fact on RISC machines, it was easy for AMD to introduce a
-new \textit{prefix byte} called \texttt{REX}. The \textit{REX prefix}
-enables the 64-bit operation mode of the following instruction in the
-new \textit{64-bit mode} of the processor.
+new \textit{prefix byte} called \texttt{tablerexprefixbytefields}. The
+\textit{REX prefix} enables the 64-bit operation mode of the following
+instruction in the new \textit{64-bit mode} of the processor.
-A processor of the AMD64 architecture has two main operating modes:
+A processor which implements the AMD64 architecture has two main
+operating modes:
\begin{itemize}
\item Long Mode
accessible registers by 1 bit. This means in \textit{64-bit Mode} 16
general-purpose registers are available. The value of a \textit{REX
prefix} is in the range \texttt{40h} through \texttt{4Fh}, depending
-on the particular bits used (see table \ref{REX}).
+on the particular bits used (see table
+\ref{tablerexprefixbytefields}).
\begin{table}
\begin{center}
& & permitting access to 16 registers. \\ \hline
\end{tabular}
\caption{REX Prefix Byte Fields}
-\label{REX}
+\label{tablerexprefixbytefields}
\end{center}
\end{table}
\end{verbatim}
to emit this byte. The names of the arguments are respective to their
-usage in the \textit{REX prefix} itself (see table \ref{REX}).
+usage in the \textit{REX prefix} itself (see table
+\ref{tablerexprefixbytefields}).
The AMD64 architecture introduces also a new addressing method called
\textit{RIP-relative addressing}. In 64-bit mode, addressing relative
analysis and some changes in the code generator itself.
-\subsection{Register allocator}
+\subsection{Register allocation}
+\label{sectionamd64registerallocation}
As mentioned in the introduction, the AMD64 architecture has 16
-general-purpose registers and 16 floating-point registers. One
-general-purpose register is reserved for the \textit{stack
+integer general-purpose registers and 16 floating-point registers. One
+integer general-purpose register is reserved for the \textit{stack
pointer}---namely \texttt{\%rsp}---and thus cannot be used for
arithmetic instructions. The register usage as used in CACAO is shown
in table \ref{amd64registerusage}.
\texttt{\%rdi} & 1$^{\rm st}$ argument register & no \\
\texttt{\%r8} & 5$^{\rm th}$ argument register & no \\
\texttt{\%r9} & 6$^{\rm th}$ argument register & no \\
-\texttt{\%r10}-\texttt{\%r11} & reserved for code generator & no \\
-\texttt{\%r12}-\texttt{\%r15} & callee-saved register & yes \\
+\texttt{\%r10} - \texttt{\%r11} & reserved for code generator & no \\
+\texttt{\%r12} - \texttt{\%r15} & callee-saved register & yes \\
\texttt{\%xmm0} & 1$^{\rm st}$ argument register, return register & no \\
-\texttt{\%xmm1}-\texttt{\%xmm7} & argument registers & no \\
-\texttt{\%xmm8}-\texttt{\%xmm10} & reserved for code generator & no \\
-\texttt{\%xmm11}-\texttt{\%xmm15} & temporary registers & no \\
+\texttt{\%xmm1} - \texttt{\%xmm7} & argument registers & no \\
+\texttt{\%xmm8} - \texttt{\%xmm10} & reserved for code generator & no \\
+\texttt{\%xmm11} - \texttt{\%xmm15} & temporary registers & no \\
\end{tabular}
\caption{AMD64 Register usage in CACAO}
\label{amd64registerusage}
\texttt{-softnull}. On the RISC ports only the \textit{null-pointer
exception} is checked in software when using this switch, but on IA32
and AMD64 both are checked, \texttt{SIGSEGV} and \texttt{SIGFPE}.
-
-
-\subsection{Related work}
-
-The AMD64 architecture is a reasonably young architecture, released in
-April 2003. At the writing of this document the only available 64-bit
-operating systems for AMD64 are GNU/Linux---from different
-distributors---, FreeBSD, NetBSD and OpenBSD. Microsoft Windows is not
-available yet, although it was announced to be released in the first
-half of 2004.
-
-The first available 64-bit JVM for the AMD64 architecture was GCC's
-GCJ---The GNU Compiler for the Java Programming
-Language~\cite{GCJ}. \texttt{gcj} itself is a portable, optimizing,
-ahead-of-time compiler for the JAVA Programming Language, which can
-compile:
-
-\begin{itemize}
-\item JAVA source code directly to native machine code
-\item JAVA source code to JAVA bytecode (class files)
-\item JAVA bytecode to native machine code
-\end{itemize}
-
-One part of the GCJ is \texttt{gij}, which is the JVM
-interpreter. Much of the porting effort for the \textit{GNU Compiler
-Collection} to the AMD64 architecture was done by people working at
-SUSE~\cite{SUSE}.
-
-Long time no AMD64 JIT was available, till Sun~\cite{Sun} released
-their AMD64 version of J2SE 1.4.2-rc1 for GNU/Linux by
-Blackdown~\cite{Blackdown} in December 2003. At this time our AMD64
-JIT was already working for months, but we were not able to release
-CACAO, because of the common status of CACAO to be a compliant
-JVM. The Sun JVM uses the HotSpot Server VM by default, the HotSpot
-Client VM is not available for AMD64 at this time.
-
-The Kaffe~\cite{Wilkinson:97} JVM has ported their interpreter to the
-AMD64 architecture for GNU/Linux, but they still have no plans to port
-their JIT.
projects / cacao.git / commitdiff