[LLVMdev] A faster instruction selector?

[Mark Shannon]

Hi everyone,

llvm is great!

But there is one exception ;)
llvm components are generally fast, but instruction selection is slooow.

Let me explain.
I am developing a toolkit for building virtual machines which can automatically
generate a JIT compiler using the interpreter specification.
llvm does the hard work of machine code generation. (Thanks to you all)

I discovered that JIT compilation is taking much longer than had hoped.
Some profiling showed that is almost entirely due 
to the llvm instruction selector (The register allocator and optimisation passes are fast)

The split in execution time for JIT compilation being approximately:
(My) IR code generation:      1
(llvm) Register allocation:   1
(llvm) Instruction selection: 12 

The ladyvm JVM paper noted the same problem: 
http://vmkit.llvm.org/ladyvm.html

So I did a quick experiment with llvm and lcc (http://www.cs.princeton.edu/software/lcc), 
in order to see how much faster instruction selection could be. 
lcc uses a BURG-type (called lburg) instruction-selector.

The following is for x86/linux (ubuntu)
I am interested in JIT performance so I have only counted user+sys time.

Compiling a small test program (the dhrystone benchmark):
lcc (Fraser and Hanson) (after pre-processing): 4ms.
llc                                           : 16ms.
Incidentally, optimisation is respectably fast
opt -O3                                       : 16ms.

(My machine is quite slow)

Using -time-passes shows that almost all of the time spent by llc is in the DAG-to-DAG
instruction selection.

lcc does lexing, parsing, type-checking, IR code-generation, register allocation 
AND final code generation in much less time that llvm spends doing instruction selection.
Also, there is no way that instruction selection should take as long as -O3 optimisation.

It would seem that lcc's lburg instruction selector is at least ten times faster than
than llvm, possibly 20 times faster.

Does a fast instruction selector for llvm exist?

A BURG based instruction selector would improve the JIT compilation capabilities of llvm hugely,
and benefit the static compiler as well.
A fast compiler is really useful in the compile-test-debug cycle.

Sadly, I do not have the time to implement such an instruction selector myself.

Cheers,
Mark.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 3683 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081215/22b34198/attachment.bin>