[LLVMdev] GSoC 2009 application

[Nick Lewycky]

Benoit Boissinot wrote:
> 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.


Hm, this sounds like something I was thinking about recently. I hadn't 
heard of SSI before, but I was trying to decide how I would implement 
GCC's VRP algorithm in LLVM in a sensible fashion, and the above is 
pretty much what I came up with.

GCC's "assert_expr" instructions would become PHI nodes like this with 
the actual ranges stored in a map<Value*, Range>, and that would provide 
path-sensitivity.

The actual VRP pass would use the SparsePropagationFramework to do the 
propagation with no knowledge of path-sensitivity, so long as we've 
transformed the graph this way in advance.

You could run this transform once then do the VRP and possibly any other 
passes (such as keeping track of whether a float may be NAN or may be 
-0.0 for example) on this form of SSA, in one batch, then let 
instcombine clean it up.

Nick

>> 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).