Re: SSA without phi

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.

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