Re: SSA without phi

Tommy Thorn <>
23 Apr 2007 07:50:56 -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)
Re: SSA without phi (Tommy Thorn) (2007-05-04)
[4 later articles]
| List of all articles for this month |

From: Tommy Thorn <>
Newsgroups: comp.compilers
Date: 23 Apr 2007 07:50:56 -0400
Organization: Compilers Central
References: 07-04-075
Keywords: SSA, analysis
Posted-Date: 23 Apr 2007 07:50:56 EDT

On Apr 20, 7:25 am, wrote:
> 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.

Which part of the complexity?

> The problem with phi functions is that they're not executable.

Sure they are(**). The "execution" just have to know how phi arguments
relate to the CFG edge and track where branches (and fall-through)
came from.

A common alternative representation of SSA distributes the arguments
into the predecessor blocks., ie instead of

    v.2 = phi(v.0, v.1)

you'd have

    jump B2(v.0)

    jump B1(v.1)


This is strictly isomorphic to the traditional representation, but can
be easier to work with.

Of course, you could also look into Gated Single-Assignment.

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

If you don't care about efficiency, reducing the number of phi-nodes
is pretty

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

What's "natural" is relative.

The alternative representation sketched above looks very much like
tail recursive function calls.


(**): SSA is wildly cited in literature as being "non-executable". Go

Post a followup to this message

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