[LLVMdev] A faster instruction selector?

[Nicolas Geoffray]

Hi Mark,

I don't know the internals of the instruction selection in LLVM (vburg 
and stuff), but I do know that work has been made to improve it. The 
"-fast" command line argument in lli and llc generates less optimized 
machine code quickly. You can also use the local register allocator 
which is faster than the default linear scan.

I did some benchmarks in vmkit (the project that encompass ladyvm) and 
compilation time is roughly 50% faster with both fast and local register 
allocator.

Nicolas

Mark Shannon wrote:
> 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.
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>