llvm dev - Jun 2006 - [LLVMdev] Code instruction selection based on SSA-graphs

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

> 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
> 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?
I undertook some preliminary work in this space for my undergraduate
honours project with Bernhard Scholz at the University of Sydney last
year. The basic implementation of an SSA based pattern matcher
generator (in the style of BURGs) was implemented in Java with
generators for Java & C++. No code generation was implemented, only
pattern matching to get some rough timing details. There's still a
fair bit of work to be done, but my work is at least open source if
anyone wants to take a look. (probably the best way is to contact
Bernhard directly for the latest code/information:
http://www.it.usyd.edu.au/about/people/staff/scholz.shtml ). If my
code's still around & anyone gets/uses it I'm happy to answer
questions.

David

>
> 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?
We have talked about whole function instruction selection but does  
not have immediate plan to implement it. If we were to implement it  
today, it would probably be done on DAGs with control flow between  
blocks being modeled as chain operands.

Implementing what is described in the paper would require boolean  
query system like PBQP. That's no trivial matter. We definitely  
welcome contribution in this area. :-) In additional to being  
required for the instruction selection algorithm described, it is  
also very useful for backends with predicated execution (e.g. IA64).

Evan

Evan Cheng wrote:
>>
>> 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?
> 
> We have talked about whole function instruction selection but does not 
> have immediate plan to implement it. If we were to implement it today, 
> it would probably be done on DAGs with control flow between blocks being 
> modeled as chain operands.
> Implementing what is described in the paper would require boolean query 
> system like PBQP. That's no trivial matter. We definitely welcome 
> contribution in this area. :-) In additional to being required for the 
> instruction selection algorithm described, it is also very useful for 
> backends with predicated execution (e.g. IA64).
Yes, PBQP is not a trivial matter. But some implementations exist 
already and can be used as a basis, i.e. the one from Scholz:
http://www.complang.tuwien.ac.at/scholz/pbqp.html

The researchers in Karlsruhe have probably developed their own 
implementation of it. Moreover, it seems that they are trying to 
implement both SSA-based approaches: code selection and register allocation.

Also, taking into account that there is a Google Summer of Code project 
(http://compilers.cs.ucla.edu/fernando/projects/soc/) trying to 
implement for LLVM the register allocation algorithm described in the 
paper "Register Allocation via Coloring of Chordal Graphs, Pereira and 
Palsberg, APLAS'05"[Pereira05], which also operates on the 
SSA-implementation, SSA-based code selection seems to be a very nicely 
  fitting complementary approach.

/Roman

Evan Cheng wrote:
>>
>> 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?
>
> We have talked about whole function instruction selection but does
not 
>have immediate plan to implement it. If we were to implement it today,
>it would probably be done on DAGs with control flow between blocks
being 
>modeled as chain operands.
> Implementing what is described in the paper would require boolean
query 
>system like PBQP. That's no trivial matter. We definitely welcome 
>contribution in this area. :-) In additional to being required for the
>instruction selection algorithm described, it is also very useful for 
>backends with predicated execution (e.g. IA64).
Yes, PBQP is not a trivial matter. But some implementations exist
already and can be used as a basis, i.e. the one from Scholz:
http://www.complang.tuwien.ac.at/scholz/pbqp.html

The researchers in Karlsruhe have probably developed their own
implementation of it. Moreover, it seems that they are trying to
implement both SSA-based approaches: code selection and register
allocation.

Also, taking into account that there is a Google Summer of Code project
(http://compilers.cs.ucla.edu/fernando/projects/soc/) trying to
implement for LLVM the register allocation algorithm described in the
paper "Register Allocation via Coloring of Chordal Graphs, Pereira and
Palsberg, APLAS'05"[Pereira05], which also operates on the
SSA-implementation, SSA-based code selection seems to be a very nicely 
fitting complementary approach.

/Roman



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