[LLVMdev] Whole-function isel

[Evan Cheng]

On Mar 25, 2008, at 9:40 AM, Dietmar Ebner wrote:

> Chris,
>
> Chris Lattner wrote:
>> I would love to see any progress in this area.  It is clearly an
>> important thing to tackle, and it is blocking other interesting
>> improvements in the code generator.  It would also allow us to
>> eliminate a significant amount of weirdness that exists to hack  
>> around
>> this (e.g. switch lowering).
> we've been working on a whole-function instruction selector here at  
> the
> vienna university of technology in the recent past. our approach
> considers ssa graphs and is based on a problem transformation to a
> specialized quadratic assignment problem (pbqp). in contrast to  
> previous
> work [1], the technique is flexible enough to cope with general DAG
> patterns such as pre/postincrement or divmod patterns.
>
> the instruction selector is a drop-in replacement for the original
> implementation (llvm 2.1). we've used the ARM backend for evaluation  
> and
> obtained quite encouraging results: speedups are up to 10% for
> SPEC/Mibench and up to 57% for simple loop kernels. the compile time
> increase is about a factor of 2.

Very nice!

>
>
> the paper has been accepted for this year's LCTES conference (june
> 12-13, tucson, az). i'm afraid i cannot post it on the list but i'm
> happy to send a preliminary version to anybody who's interested.
>
> the implementation is not yet as efficient as it could be (e.g., we
> maintain an additional datastructure for the ssa graph along with the
> selection DAG) and i'm afraid there are licensing issues that do not
> allow me to directly post or contribute the code. however, i'm happy  
> to
> share further experimental results and discuss the approach in case
> somebody is interested.

That's unfortunate. What kind of licensing issues are there?

Evan

>
>
> -
> dietmar
>
>
> [1] Erik Eckstein, Oliver König and Bernhard Scholz
>     Code Instruction Selection Based on SSA-Graphs
>     SCOPES 2003
>     http://springerlink.metapress.com/content/83cj0ebgtm998hj8
>
> --
> ---------------------------------------------------------------------
> Dietmar Ebner
> CD Laboratory - Compilation Techniques for Embedded Processors
> Institut fuer Computersprachen  E: ebner at complang.tuwien.ac.at
> Technische Universitaet Wien    F: (+431) 58801-18598
> Argentinierstrasse 8 / E1851    T: (+431) 58801-58521
> 1040 Wien, Austria              W: www.complang.tuwien.ac.at/cd/ebner
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev