[LLVMdev] Whole-function isel

[Dietmar Ebner]

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.

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.

-
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