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).
Reasonably Related Threads
- [LLVMdev] GSoC 2009 application
- [LLVMdev] GSoC 2009 application
- [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg.
- [LLVMdev] A new project proposal for LLVM and calling help from a chinese student
- [LLVMdev] A new project proposal for LLVM and calling help from a chinese student