GSoC 2009 application

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,

SSI.pdf (114 KB)

2009/3/27 Andre Tavares <andrelct@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.

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

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)

This is assuming you run a pass like BreakCriticalEdges first? Looks
like it would work. My concern here would be performance...

-Eli

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:

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

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