[LLVMdev] GSoC 2009 application

[Benoit Boissinot]

2009/3/29 Misha Brukman <brukman at gmail.com>:
> 2009/3/27 Andre Tavares <andrelct at dcc.ufmg.br>
>>
>> I'm a Computer Science master student at UFMG, Brasil. I'm interested in
>> taking part on Google Summer of Codes 2009. My idea is not on the LLVM list,
>> but I have written a project description to make my intentions clear. My
>> project is attached as a pdf file.
>
> By changing LLVM IR from SSA to SSI, you propose to make a
> non-backwards-compatible change which will break all existing passes,
> optimizers, analyses, as well as instruction selectors and register
> allocations.  It's particularly troublesome because the SSI sigma
> instruction defines multiple variables, whereas the SSA form instructions
> can only define a single value (in fact, LLVM's Instruction class is an
> indirect subclass of the Value class), and this assumption is ingrained in
> LLVM.

While it is not described in the litterature, I don't think you need
to introduce a new
function:
      x0 = ...
  x1, x2 = \sigma (x0)
         |
    +----+------+
    |           |
    v           v
  ... = x1    ... = x2

Can be transformed to:

         x0 = ...
            |
    +-------+------+
    |              |
    v              v
 x1 = \phi(x0)  x2 = \phi(x0)

This comes from the fact that the sigma function, like the phi, function has
the semantic that the copies are done on the edges.

>
> It doesn't sound like you're prepared to update the entire LLVM codebase to
> be built on SSI -- you want to make SSI an offshoot of the SSA form, and
> that's hard to accomodate as that means every pass will have to know about
> and support SSI form, not just the ones you write.

That would just be SSA with some other properties (like there could be
a pass to transform SSA into Conventional SSA, ie CSSA, a pass could be
added to transform into SSI).
>
> Does SSI bring anything to SSA that cannot be expressed in a structure
> outside of the SSA encoding, if your goal is to implement the  two
> applications of bitwidth analysis and array bounds-checking elimination?

You should in any case be aware that SSI papers suffer from imprecisions and
errors. Those errors are not encountered in practice because people usually
use a very constraint SSI form (with more split than required, that's what
Fernando or the PyPy people are doing).

regards,

Benoit