-\section{X86 code generator}
+\section{x86 code generator}
+
+Porting to the famous x86 platform was more effort than
+expected. CACAO was designed to run on RISC machines from ground up,
+so the code generation part hat 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 where written,
+with no respect to the old RISC macros. One big difference in writing
+the new code generation macros was, that the x86 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 handling of an ICMD on RISC
+machines looks like this (on the example of the integer add ICMD):
+
+\begin{verbatim}
+ case ICMD_IADD:
+ var_to_reg_int(s1, src->prev, REG_ITMP1);
+ var_to_reg_int(s2, src, REG_ITMP2);
+ d = reg_of_var(iptr->dst, REG_ITMP3);
+ M_IADD(s1, s2, d);
+ store_reg_to_var_int(iptr->dst, d);
+ break;
+\end{verbatim}
+
+This means loading the two \textit{source operands} from memory to
+temporary registers, if necessary, getting a \textit{destination
+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
+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:
+
+\begin{verbatim}
+ if (IS_INMEMORY(iptr->dst)) {
+ if (IS_INMEMORY(src) && IS_INMEMORY(src->prev)) {
+ ...
+ } else if (IS_INMEMORY(src) && !IS_INMEMORY(src->prev)) {
+ ...
+ } else if (!IS_INMEMORY(src) && IS_INMEMORY(src->prev)) {
+ ...
+ } else {
+ ...
+ }
+ } else {
+ if (IS_INMEMORY(src) && IS_INMEMORY(src->prev)) {
+ ...
+ } else if (IS_INMEMORY(src) && !IS_INMEMORY(src->prev)) {
+ ...
+ } else if (!IS_INMEMORY(src) && IS_INMEMORY(src->prev)) {
+ ...
+ } else {
+ ...
+ }
+ }
+\end{verbatim}
+
+For most ICMDs we can further optimize the generated code 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.
+
+Some smaller problems occured since the x86 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
+\textit{32-bit-ready}, namely an architecture dependent
+\texttt{types.h} with definitions of the used datatypes and some
+feature flags, which features the processor itself natively
+supports. Most noticeable change was the \texttt{s8} and \texttt{u8}
+datatype from \texttt{long} to \texttt{long long} to support 64 bit
+calculations.
+
+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
+\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}):
+
+\begin{verbatim}
+ i386_mov_imm_reg(0, REG_ITMP2);
+ dseg_adddata(mcodeptr);
+\end{verbatim}
+
+The \texttt{dseg\_adddata()} call inserts the current postion of the
+code generation pointer into a datastructure which is later processed
+by \texttt{codegen\_finish()}, where the final address of the data
+segment is patched.
+
+
+\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):
+
+\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}
+
+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
+
+\begin{verbatim}
+ void sub(int i, long l, float f, double d);
+\end{verbatim}
+
+we have a stack layout like in figure \ref{stacklayout}.
+
+\begin{figure}[htb]
+\begin{center}
+\setlength{\unitlength}{1mm}
+\begin{picture}(50,54)
+\thicklines
+\put(0,0){\framebox(24,54){}}
+\put(0,42){\line(1,0){24}}
+\put(0,36){\line(1,0){24}}
+\put(0,30){\line(1,0){24}}
+\put(0,18){\line(1,0){24}}
+\put(0,12){\line(1,0){24}}
+\put(0,6){\line(1,0){24}}
+\put(30,0){\vector(-1,0){6}}
+\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,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,12){\makebox(24,6){\textit{unused}}}
+\put(0,6){\makebox(24,6){\textit{int value}}}
+\put(0,0){\makebox(24,6){\textit{return address}}}
+\end{picture}
+\caption{CACAO x86 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.
+
+With this adaptation, it was 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.
+
+But calling a native function always means a stack manipulation,
+because you have to put the \textit{JNI environment}, and for
+\texttt{static} functions the \textit{class pointer}, 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.
+
+Return parameters are stored in different places, this depends on the
+return type of the function:
+
+\begin{itemize}
+ \item \texttt{boolean}, \texttt{byte}, \texttt{char}, \texttt{short},
+ \texttt{int}, \texttt{void}: return value resides in \texttt{\%eax}
+ (\texttt{REG\_RESULT})
+
+ \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})
+
+ \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)
+\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.
+
+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.
+
+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.
+
+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.
+
+So the first step to make the x86 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}
+
+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{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.
+
+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.
+
+The x86 processor has some machine instructions which are specifically
+designed for 64 bit operations like \texttt{cltd} --- Convert Signed
+Long to Signed Double Long, \texttt{adc} --- Integer Add With Carry or
+\texttt{sbb} --- Integer Subtraction With Borrow. So some of the 64
+bit calculations like \texttt{LADD} or \texttt{LSUB} can be exceuted
+in two instructions.
+
+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.
+
+
+\subsection{Floating point arithmetic}
+
+Since the i386, with it's i387 counterpart or the i486, the x86
+processor has an \textit{floating point unit} (FPU). This FPU is
+implemented as a stack with 8 elements (see table \ref{FPUStack}).
+
+\begin{table*}
+\begin{center}
+\begin{tabular}[b]{|l|l|}
+\hline
+st(x) & FPU Data Register Stack \\ \hline
+0 & TOS (Top Of Stack) \\ \hline
+1 & \\ \hline
+2 & \\ \hline
+3 & \\ \hline
+4 & \\ \hline
+5 & \\ \hline
+6 & \\ \hline
+7 & \\ \hline
+\end{tabular}
+\caption{x87 FPU Data Register Stack}
+\label{FPUStack}
+\end{center}
+\end{table*}
+
+This stack is designed to wrap around if values are loaded to the
+\textit{top of stack} (TOS). For this reason, it has a special register which
+points to the TOS. This pointer is increased if a load instruction to
+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
+\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:
+
+\begin{verbatim}
+var_to_reg_flt(s1, src->prev, REG_FTMP1); /* load 1st operand in st(0), increase
+ fpu_st_offset */
+var_to_reg_flt(s2, src, REG_FTMP2); /* load 2nd operand in st(0), increase
+ fpu_st_offset */
+i386_faddp(); /* add 2 upper most elements st(1) = st(1) + st(0) -- pop st(0) */
+fpu_st_offset--; /* decrease fpu_st_offset from previous pop */
+store_reg_to_var_flt(iptr->dst, d); /* store result -- decrease fpu_st_offset */
+\end{verbatim}
+
+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
+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:
+
+\begin{itemize}
+ \item single-precision (32 bit)
+ \item double-precision (64 bit)
+ \item double extended-precision (80 bit)
+\end{itemize}
+
+The FPU has a 16 bit \textit{control register} which has a
+\textit{precision control field} (PC) and a \textit{rounding control
+field} (RC), each of 2 bit length (see table \ref{PCField} and
+\ref{RCField}).
+
+\begin{table*}
+\begin{center}
+\begin{tabular}[b]{|l|c|}
+\hline
+Precision & PC Field \\ \hline
+single-precision (32 bit) & 00B \\ \hline
+reserved & 01B \\ \hline
+double-precision (64 bit) & 10B \\ \hline
+double extended-precision (80 bit) & 11B \\ \hline
+\end{tabular}
+\caption{Precision Control Field (PC)}
+\label{PCField}
+\end{center}
+\end{table*}
+
+\begin{table*}
+\begin{center}
+\begin{tabular}[b]{|l|c|}
+\hline
+Rounding Mode & RC Field \\ \hline
+round to nearest (even) & 00B \\ \hline
+round down (toward -$\infty$) & 01B \\ \hline
+round up (toward +$\infty$) & 10B \\ \hline
+round toward zero (truncate) & 11B \\ \hline
+\end{tabular}
+\caption{Rounding Control Field (RC)}
+\label{RCField}
+\end{center}
+\end{table*}
+
+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.
+
+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.
+
+For single-precision floats the \textit{store-reload} code could looks
+like this:
+
+\begin{verbatim}
+i386_fstps_membase(REG_SP, 0); /* store single-precision float to stack */
+i386_flds_membase(REG_SP, 0); /* load single-precision float from stack */
+\end{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:
+
+\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
+ \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
+ calculation like
+
+ \begin{verbatim}
+ float f = 1.234F;
+ float g = 2.345F;
+ float e = f * f + g * g;
+ \end{verbatim}
+
+ the generated ICMD's look like this (with comments where precision
+ mode switches take place):
+
+ \begin{verbatim}
+ ...
+ <fpu in double-precision mode>
+ FLOAD 1
+ FLOAD 1
+ <switch fpu to single-precision mode>
+ FMUL
+ <switch fpu to double-precision mode>
+ FLOAD 2
+ FLOAD 2
+ <switch fpu to single-precision mode>
+ FMUL
+ <switch fpu to double-precision mode>
+ <switch fpu to single-precision mode>
+ FADD
+ <switch fpu to double-precision mode>
+ FSTORE 3
+ ...
+ \end{verbatim}
+
+ For this corner case situation the mode switches are extrem, but the
+ example should demonstrate how this technique works.
+
+ \item \textbf{Mode switch on float data type change} --- switch the
+ FPU on initialization in on precision mode, like before, in
+ \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:
+
+ \begin{verbatim}
+ ...
+ <fpu in double-precision mode>
+ FLOAD 1
+ FLOAD 1
+ <switch fpu to single-precision mode>
+ FMUL
+ FLOAD 2
+ FLOAD 2
+ FMUL
+ FADD
+ FSTORE 3
+ ...
+ \end{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
+ 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.
projects / cacao.git / blobdiff