llvm dev - Mar 2009 - [LLVMdev] GSoC 2009 application

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

On Sun, Mar 29, 2009 at 3:33 PM, Benoit Boissinot
<bboissin+llvm at gmail.com> wrote:
> 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.
This is assuming you run a pass like BreakCriticalEdges first?  Looks
like it would work.  My concern here would be performance...

-Eli

On Mon, Mar 30, 2009 at 1:05 AM, Eli Friedman <eli.friedman at gmail.com>
wrote:
> On Sun, Mar 29, 2009 at 3:33 PM, Benoit Boissinot
> <bboissin+llvm at gmail.com> wrote:
>> 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.
>
> This is assuming you run a pass like BreakCriticalEdges first?  Looks
> like it would work.  My concern here would be performance...
You don't need to break any edges, the copies are "semantically"
done on
the edge. When you have a critical edge, you can simply fold the sigma into
the following phi's.

Where is the performance a concern? Using phi's instead of sigma's? Or
all
the new variables introduced by SSI? (I think that's a real concern,
if I remember
correctly the numbers from Ananian and Singer).

regards,

Benoit

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