GSoC 2009 application

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

GSoC 2009 application

Andre Tavares
Dear LLVM Community,
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.

Regards,

--
Andre Tavares
Master Student in Computer Science - UFMG - Brasil
http://dcc.ufmg.br/~andrelct


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

SSI.pdf (156K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2009 application

Misha Brukman-3
2009/3/27 Andre Tavares <[hidden email]>
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.

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.

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?

Misha

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2009 application

Benoit Boissinot-4
2009/3/29 Misha Brukman <[hidden email]>:

> 2009/3/27 Andre Tavares <[hidden email]>
>>
>> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2009 application

Eli Friedman-2
On Sun, Mar 29, 2009 at 3:33 PM, Benoit Boissinot
<[hidden email]> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2009 application

Benoit Boissinot-4
On Mon, Mar 30, 2009 at 1:05 AM, Eli Friedman <[hidden email]> wrote:

> On Sun, Mar 29, 2009 at 3:33 PM, Benoit Boissinot
> <[hidden email]> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2009 application

Nick Lewycky
In reply to this post by Benoit Boissinot-4
Benoit Boissinot wrote:

> 2009/3/29 Misha Brukman <[hidden email]>:
>> 2009/3/27 Andre Tavares <[hidden email]>
>>> 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).


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2009 application

Eli Friedman-2
In reply to this post by Benoit Boissinot-4
On Sun, Mar 29, 2009 at 4:39 PM, Benoit Boissinot
<[hidden email]> wrote:
> 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.

The issue would be that the sigma output doesn't have a unique
identity... I'm not too familiar with algorithms using SSI, though, so
I don't know if that would be an issue.

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

The performance concern is all the new PHI nodes getting inserted...

-Eli
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev