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.

Potential Solutions

In order to make these libraries available, we searched for a way to translate C/C++ code into Java code.

Source-To-Source Translators

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:

GCC Backends

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.

Binary-To-Binary Translation

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.

Binary-To-Source Translation

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.

Architecture Choice

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.

Architecture Representation

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.

Sample Program

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



    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;
                // ...

Future Optimizations

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.

More Information

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