[LLVMdev] Code instruction selection based on SSA-graphs

[Roman Levenstein]

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