XWT needs two rather crucial open source (typically Linux-related) libraries which are written in C/C++: libjpeg (for non-JVM and J2ME platforms) and Freetype2. A crucial design decision which has kept XWT so portable is that it must not use any code which cannot compile under jdk1.1, and must not use any classes outside of the java.lang, java.text, java.net, java.io, and java.util packages.
In order to make these libraries available, we searched for a way to translate C/C++ code into Java code.
There are a few packages that purport to translate C/C++ source into Java source: c2j (commercial, closed-source), Jazillian (closed-source, web service), and c2java (closed source).
These projects are unacceptable for three reasons:
None of these packages offers complete support for the C language (notably pointer arithmetic).
The output from all of these programs requires substantial hand-tweaking. The problem here is that FreeType is a rapidly changing project, gaining new features every day. It is absolutely crucial that XWT can import new versions of FreeType and automatically rebuild without human intervention; if special human tweaks are necessary, and the project were to lose the person who knew how to perform those tweaks, we would be unable to upgrade our embedded copy of FreeType.
Finally, each of these packages takes the place of a C compiler. This means that a substantial amount of work is required in order to get the Freetype/libjpeg build processes to use the translator instead of gcc.
The old egcs project had a Java Bytecode Backend. Unfortunately, it is highly experimental and has not been ported to newer versions of gcc. It shares all the flaws above except for the last one.
One approach that has been overlooked thus far is to run the C/C++ code through gcc (which will work flawlessly since the code is designed for a full-blown C/C++ compiler) and translate the resulting binary code into Java bytecode. This approach is attractive, but would require learing the Java Bytecode language details as well as reimplementing a lot of the static optimizations (like 2+2=>4) that are aleady implemented in Java compilers such as Jikes.
This is the solution we finally settled on.
MipsToJava is a small Java program that takes a target class name and a statically linked MIPS R200 ELF binary on the command line, and emits equivalent Java code on stdout. We recommend linking against newlib, which provides an implementation of libc and libm. GCC can be compiled with --target=mips to produce a compiler that generates MIPS binaries.
We searched for a target CPU that closely resembles the JVM, and found the MIPS R2000 to be an excellent match. The most important factor is that MIPS does not allow nonaligned memory accesses, and never interacts with main memory except to load and store single 32-bit words, one at a time. This is crucial -- it means that pointer arithmetic gets converted to array accesses, something that source-to-source translators cannot accomplish, since converting struct-member accesses to word-level reads and writes cannot be done without undergoing compilation.
Conveniently, we can represent main memory as a Java int[][], which allows efficient accesses so long as they are aligned, 32-bit-word-at-a-time accesses. The first index is the top 16 bits of the address; the second index is the lower 16 bits. This allows us to allocate Java memory to the MIPS emulator in 64kb slabs.
The only performance lost here is array bounds checking; however, we can safely turn off array bounds checking here (either on the JVM command line or in GCJ) since all but the bottom 16 bits of each address are masked off before it is used as an index; hence an ArrayIndexOutOfBoundsException is impossible. We hope that in the future, JVMs will notice this sequence of instructions and statically remove the bounds check.
Reads and writes are performed via different members; if a page is write protected, the write member will contain a null. This allows us to use the JVM's null-detection to do memory protection operations. Since most JVMs catch sigsegv in order to detect null dereferences, and since sigsegv is implemented in hardware (in the CPU's MMU), we can effectively use the host CPU's MMU to emulate the MIPS MMU at no performance cost.
The 32 MIPS registers are represented as 32 int members (r0 is marked final). Instructions are compiled into a gigantic switch(pc) block, which jumps to the case arm corresponding to the appropriate program counter value. If the instruction is not a jump, then there will be no break in the case arm, and program flow will fall through to the next instruction.
Since Java places a very restrictive limit on the maximum length of a method, the MIPS .text segment is broken up into blocks of 0x100 (256) instructions, each of which is compiled into a method. A simple trampoline() method sits in a while() loop and dispatches control to the appropriate method based on the top 24 bits of the program counter. Jumps are implemented by changing the pc value and returning to the trampoline method.
Jumping to the special address 0xdeadbeef indicates that the program should exit normally. The .data segment is translated into a method which allocates and populates a region of memory with constant values.
Here is a sample skeleton program:
// This file was generated by MipsToJava
package org.xwt.imp;
public class Freetype {
public Freetype() { }
// memory
public int mem_read[][] = new int[65535][];
// same as mem_read unless a page is write-protected
public int mem_write[][] = new int[65535][];
// program counter
int pc = 0;
// temporary
int tmp = 0;
// MIPS multiply/divide subsystem; 64-bit result
long hilo = 0;
// General Purpose registers
final int r0 = 0;
int r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0, r6 = 0, r7 = 0,
r8 = 0, r9 = 0, r10 = 0, r11 = 0, r12 = 0, r13 = 0, r14 = 0, r15 = 0,
r16 = 0, r17 = 0, r18 = 0, r19 = 0, r20 = 0, r21 = 0, r22 = 0, r23 = 0,
r24 = 0, r25 = 0, r26 = 0, r27 = 0, r28 = 0, r29 = 0, r30 = 0, r31 = 0;
// section ".text" #1; file offset 0x1000, vma 0xa0020000, size 0x306cc
private void run_a0020000() {
switch(pc) {
/* 27bdffe0 */ case 0xa0020000: r29 = r29 + -32; pc = 0xa0020004;
/* afbf0014 */ case 0xa0020004: mem_write[(r29 + 20)>>>16][(r29 + 20) & 0xffff] = r31; pc = 0xa0020008;
/* 04110001 */ case 0xa0020008: /* NOP */; pc = 0xa002000c;
/* 00000000 */ case 0xa002000c: /* NOP */; pc = 0xa0020010;
// ...
}
}
public static void main(String[] s) { new Freetype().main(); }
public void main() {
// allocate the stack
mem_read[1] = mem_write[1] = new int[65535];
// set the stack pointer
r29 = 0x0001ff00;
// set the "return address" from _start to point at the "magic exit address" (0xdeadbeef)
r31 = 0xdeadbeef;
// read in the .data segment
initData();
trampoline(0xa0050440);
}
public void trampoline(int pc) {
this.pc = pc;
while(true) {
switch(this.pc & 0xffffff00) {
case 0xdeadbe00: System.out.println("exiting with return value " + r2); System.exit(r2); continue;
case 0xa0020000: run_a0020000(); continue;
// ...
}
}
}
Ideally, we would like to infer the pc value statically; it should not be necessary to compute it at each instruction. It should be passed as the sole argument and return value for each of the methods which trampoline() calls.
It would also be nice to remove the switch block and simply recompile every code path starting at a potential jump target and ending at a jump instruction. In the case of the jr instruction (jump to register), we cannot infer the set of possible jump targets, so a runtime MIPS-to-Java converter would need to be present (using ClassLoader.fromBytes() to load the bytecode). Doing this would open up more optimization and reordering opportunities for the compiler.
Jumps within a method should use continue rather than return.
Floating point instructions are not yet implemented, mainly because neither libjpeg nor freetype2 uses floating point math. In the future, it should be very easy to use the JVM's double and float types to efficiently emulate the MIPS FPU.
The 32 MIPS registers should be implemented as method-local variables; this will cause them to (probably) be compiled into register accesses rather than memory accesses by the JIT. Unfortunately this means that we must save/restore them every time we use the trampoline.
Mips2Java is licensed under the GNU GPL; however this places no restrictions upon what kinds of programs you can provide as input to Mips2Java, nor does it place any restrictions or incumberences upon the code emitted as output.
The source code for Mips2Java is in src/org/xwt/imp/MIPS.java in the XWT CVS Repository.
A syntax-highlighted, HTMLized copy of the source code is here