SSA without phi
20 Apr 2007 10:25:01 -0400

          From comp.compilers

Related articles
SSA without phi (2007-04-20)
Re: SSA without phi (Tommy Thorn) (2007-04-23)
Re: SSA without phi (2007-04-23)
SSA without phi (Inderaj Bains) (2007-04-23)
Re: SSA without phi (Chris F Clark) (2007-04-23)
Re: SSA without phi find@my.address.elsewhere (Matthias Blume) (2007-04-26)
Re: SSA without phi (2007-04-29)
[5 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 20 Apr 2007 10:25:01 -0400
Organization: Compilers Central
Keywords: analysis, SSA, question
Posted-Date: 20 Apr 2007 10:25:01 EDT

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.