SSA without phi

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

Relevant Pages

  • Re: SSA without phi
    ... SSA by using it only per basic block. ... complexity of phi functions. ... Which part of the complexity? ...
    (comp.compilers)
  • SSA without phi
    ... these you can get trivially in a basic block without ssa also ... You will lose most advantages that actually come with SSA: ... to behave in a way that a programmer would optimize code ... The problem with phi functions is that they're not executable. ...
    (comp.compilers)
  • Re: SSA without phi
    ... SSA by using it only per basic block. ... The problem with phi functions is that they're not executable. ... There is also reason to believe some global algorithms operating on SSA ...
    (comp.compilers)
  • Re: SSA without phi
    ... SSA by using it only per basic block. ... I'm not sure why you "fear" phi functions, ... If you generate assignments at the places where the ...
    (comp.compilers)