[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