Sat, 01 Jan 2011

LLVM Backend for DDC : Very Nearly Done.

The LLVM backend for DDC that I've been working on sporadically since June is basically done. When compiling via the LLVM backend, all but three of 100+ tests in the DDC test suite pass. The tests that pass when going via the C backend but fail via the LLVM backend are of two kinds:

  1. Use DDC's foreign import construct to name a C macro to perform a type cast where the macro is defined in one of C header files.
  2. Use static inline functions in the C backend to do peek and poke operations on arrays of unboxed values.

In both of these cases, DDC is using features of the C language to make code generation easier. Obviously, the LLVM backend needs to do something else to get the same effect.

Fixing the type casting problem should be relatively simple. Ben is currently working on making type casts a primitive of the Core language so that both the C and LLVM backends can easily generate code for them.

The array peek and poke problem is little more complex. I suspect that it too will require the addition of new Core language primitive operations. This is a much more complex problem than the type casting one and I've only just begun to start thinking about it.

Now that the backend is nearly done, its not unreasonable to look at its performance. The following table shows the compile and run times of a couple of tests in the DDC test suite compiling via the C and the LLVM backend.

Test name C Build Time LLVM Build Time C Run Time LLVM Run Time
93-Graphics/Circle 3.124s 3.260s 1.701s 1.536s
93-Graphics/N-Body/Boxed 6.126s 6.526s 7.649s 4.899s
93-Graphics/N-Body/UnBoxed 3.559s 4.017s 9.843s 6.162s
93-Graphics/RayTracer 12.890s 13.102s 13.465s 8.973s
93-Graphics/SquareSpin 2.699s 2.889s 1.609s 1.604s
93-Graphics/Styrene 13.685s 14.349s 11.312s 8.527s

Although there is a small increase in compile times when compiling via LLVM, the LLVM run times are significantly reduced. The conceptual complexity of the LLVM backend is also low (the line count is about 4500 lines, which will probably fall with re-factoring) and thanks to LLVM's type checking being significantly better than C's, I think its reasonable to be more confident in the quality of the LLVM backend than the existing C backend. Finally, implementing things like proper tail call optimisation will be far easier in LLVM backend than in C.

All in all, I think doing this LLVM backend has been an interesting challenge and will definitely pay off in the long run.

Posted at: 13:54 | Category: CodeHacking/DDC | Permalink