SSA without phi

Nicolas.Capens@gmail.com
20 Apr 2007 10:25:01 -0400

          From comp.compilers

Related articles
SSA without phi Nicolas.Capens@gmail.com (2007-04-20)
Re: SSA without phi tommy.thorn@gmail.com (Tommy Thorn) (2007-04-23)
Re: SSA without phi jle@forest.owlnet.rice.edu (2007-04-23)
SSA without phi inderaj@gmail.com (Inderaj Bains) (2007-04-23)
Re: SSA without phi cfc@shell01.TheWorld.com (Chris F Clark) (2007-04-23)
Re: SSA without phi find@my.address.elsewhere (Matthias Blume) (2007-04-26)
Re: SSA without phi Nicolas.Capens@gmail.com (2007-04-29)
[5 later articles]
| List of all articles for this month |

From: Nicolas.Capens@gmail.com
Newsgroups: comp.compilers
Date: 20 Apr 2007 10:25:01 -0400
Organization: Compilers Central
Keywords: analysis, SSA, question

Hi all,


I'm wondering whether it is possible to get (part of) the benefits of
SSA by using it only per basic block. This way I could avoid all the
complexity of phi functions.


The problem with phi functions is that they're not executable. I would
prefer keeping my intermediate code executable at all time. This would
make it easier to reason about optimizations and follow every step
(*). It's also fairly complex (almost convoluted in my opinion) to
correctly compute where to insert phi functions, especially when
trying to keep their number low.


So what I propose is to have single-assignment per basic block, but
allow reassignment of the same variables in other basic blocks. Is
this a known technique that has been compared to full SSA before? I
believe that all optimizations that work per basic block would still
work correctly. Things like dead code elimination and copy propagation
could still benefit from the single-assignment property. And by simply
looking at uses and definitions per basic block it could still
optimize across basic blocks.


Does this "Block Single Assignment" make any sense or would I lose
some significant advantages of SSA with phi functions? Or is it
equivalent with a known technique that is proven to be less efficient?


Thanks for all insights,


Nicolas Capens


(*) This is also a bit of a philospohical opinion. I want my compiler
to behave in a way that a programmer would optimize code. SSA with phi
functions just isn't natural, while the idea of static assignment is
fundamental in functional programming and well understood.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.