Re: SSA without phi

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

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

On Apr 20, 7:25 am, Nicolas.Cap...@gmail.com 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


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


you'd have


B0:
    ...
    jump B2(v.0)


B1:
    ...
    jump B1(v.1)


B2(v.2):
    ...


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


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


Tommy


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



Post a followup to this message

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