MIR to Java compiler

[glegris]

Hi @vnmakarov,

I started writing a MIR to Java compiler in a fork named mir2j.

My goal is to make C applications/libraries or code that can be compiled with LLVM work in a JVM. There are already projects that do this:

• NestedVM or Cibyl : it works very well and the performance is good but you have to compile your code with GCC MIPS and then a translation is done from the MIPS binary to Java sources or Java bytecodes.
• LLJVM-translator (based on LLJVM by David Roberts)

I think it's possible to do the same thing with MIR but with a much smaller footprint.

I saw that mir2c is a good start point. At first, I thought it wasn't a good idea (for me) to start generating bytecodes because I needed to understand how MIR works and experiment with trial and error (and also because I haven't found a good bytecode manipulation library in pure c). So I decided to generate Java sources for now. Another advantage is that we could also easily generate sources for languages close to Java syntax like C# or Dart.

LLVM IR / C => MIR => Java Sources

Because there is no goto instruction at source level, the program flow is based on a loop with switch/case statements.

public void doSomething() {
  while(true) {
    switch(label) {
    case "L1":
     ....
    case "L2":
      label = "L1"; // goto L1;
      break;
    }
  }
}  

Switching on strings is not good for performance. To use integers instead of strings, I'll create an unique integer for each label string (currently "L1", "L2", ... with c2mir)

Memory is a giant byte array (byte[]) with this structure: DATA | STACK | HEAP. It seems to me than putting the heap at the end helps to minimize memory footprint when a program is not allocating on the heap.

The C Standard library will be implemented in two places : a Runtime class (only printf and alloca yet) and a single C file for the other common functions which don't require an interaction with the subsystem (like string manipulations)

Currently the code is in its early stages, but the sieve.c example can already be converted and works fine.

If you think this project could be a candidate for an integration in the main project at some point in the future, I'll be happy to do it.

[vnmakarov]

Sorry for delay with the answer.

And thank you for informing me about your project. As you probably saw on the picture in README file about possible future of MIR project, Java bytecode <-> MIR translation is definitely interesting for me. I think that we could integrate your work into MIR code base if everything is ok.

Translation of LLVM IR is much harder project as it support a lot of C extensions (as asm for example). I would like only add that MIR probably will be changed and will support some extensions in the future. I'd like to add some simplified asm insns to C2MIR and labels as values and corresponding MIR extensions. This probably will create some problems for your project. On the other hand, not all MIR code should be translated too Java and its bytecode.

[glegris]

Thanks for your answer,

I got preliminary results based on sieve.c example.

Benchmark	Description	Execution time (s)	Slowdown factor
1	Original C code (gcc -O3)	1,6	1
2	Original C code (c2m -el)	2,1	1,3
3	Java (port of sieve.c by hand)	2,7	1,7
4	Java (mir2j)	66	41
5	Java (mir2j modified by hand: integer labels)	34	21
6	Java (mir2j modified by hand: integer labels, no long cast)	20	12
7	Java (mir2j modified by hand: integer labels, no long cast, memory access inlined)	15	9
8	Optimized mir2j code converted by hand to C (gcc -O3)	26	16
9	Optimized mir2j code converted by hand to C (c2m -eg)	26	16
10	Optimized mir2j code converted by hand to C with goto instead of switch (gcc -O3)	1,6	1
11	Optimized mir2j code converted by hand to C with goto instead of switch (c2m -el)	2,5	1,5

As expected, we can see a big improvement with integer labels (x2, benchmark 5). More surprisingly, the systematic widening to long (local variables are declared as long) entails a strong penalty (benchmarks 5 vs 6).

We can see that using while/switch statements instead of goto causes x16 slowdown in C (benchmarks 10 vs 8). We could expect an improvement of the same factor when we emit bytecodes (where jump instructions are available) instead of Java sources. Slowdown factor of generated Java bytecodes could be close to x2 at the end.

[vnmakarov]

Thanks for sharing the info. The data are interesting and shows what can be achieved by translating MIR to the bytecode.

By the way analogous problem exists for translation of C code containing setjmp/longjmp into webassembler. It is possible (although quite non-trivial) but the slowdown can achieve factor 3 for such C code (a language interpreter with exceptions implemented by setjmp/longjmp).

[glegris]

Some news: I managed to convert non-trivial code like the whole raylib library in Java

The main problems encountered are:

• c2mir sometimes generates unreachable code (2 consecutive jumps or ret/jmp). It's not a problem if we emit low-level code but it is for higher-level code because there are checks that make the code uncompilable. The mir to Java conversion is therefore done in two passes to detect these problems.

• Instruction va_end is never emitted

• When calling functions passing structures by value, I observed the following behavior:

If the size of the structure is less than 16 bytes, then c2mir generates functions which return 2 values ​​of 8 bytes to avoid allocating a block of memory on the stack.
If the size of the structure is greater than 16 bytes, c2mir allocates a memory block on the stack in which the values ​​of the structure are written.

I haven't found a real solution to force c2mir not to generate functions that return two values, which cannot be converted to Java. In the meantime, I modified the source code of the raylib library so that structures are always larger than 16 bytes (ugly). @vnmakarov, do you see a solution to prevent it?