[LLVMdev] Code instruction selection based on SSA-graphs

[Roman Levenstein]

Hi,

LLVM already uses dynamic-programming based optimal pattern matching
selectors for some of the target architectures. But as far as I know,
the code is first converted out of the SSA form, before the selection
process takes place. The same approach is used by many other compilers.

But there is an article from Erik Eckstein, where a different method is
proposed. In the described approach, the code is generated directly
from the SSA-form. The tree grammar is extended accordingly to support
such SSA-constructs like PHI-nodes. The pattern matching problem is
mapped to a partitioned boolean quadratic optimization problem
(PBQP).Authors report that "experiments have shown that the performance
gain of a SSA-graph matcher compared to a tree pattern matcher is
significant (up to 82%) in comparison to classical tree matching
methods. These results were obtained without modifying the grammar.
Though the overhead of the PBQP solver is higher than tree matching
methods, the compile time overhead is in acceptable bounds". And this
is quite impressive. 

Here is a link to the paper:
Erik Eckstein, Oliver König, Bernhard Scholz: Code Instruction
Selection Based on SSA-Graphs. SCOPES 2003: 49-65
http://www.cs.usyd.edu.au/~scholz/publications/scopes03.pdf

Some people at the University of Karlsruhe, Germany have already done
some implementations along the lines of the proposed method:
http://www.info.uni-karlsruhe.de/theses.php/id=180
http://www.info.uni-karlsruhe.de/papers/da_jakschitsch.pdf

It might be interesting for LLVM to investigate this approach, since
LLVM is heavily SSA-based anyway. Besides improved code quality, it
might also eliminate a need for out-of-SSA pass.

What do you think about this approach? Whould it be interesting to
implement something like that for LLVM? May be you already have
considered something like that? Are there any plans to it?

Best Regards,
 Roman

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com