Re: SSA without phi

<Nicolas.Capens@xxxxxxxxx> wrote:

I'm wondering whether it is possible to get (part of) the benefits of
SSA by using it only per basic block.

Of course you may get some benefit-- this is the same as fully
renaming every value in the basic block, and was done long
before SSA became fashionable. For example, it was commonly
done to eliminate output- and anti-dependences in instruction
scheduling (among other things).

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.

I would disagree that phi insertion is "complex" and "convoluted"--
it is relatively straightforward, assuming one understands some
basic concepts, such as dominance. For a particularly nice (and
easy to understand) description of SSA construction, see the book:
Cooper & Torczon, "Engineering a Compiler".

As a point of reference, our compiler students at Rice University
implement SSA construction as just one of their lab assignments
during the semester.
This is after 1 or 2 lectures on the topic.

However, I would tend to agree that some of the early SSA papers were
perhaps less readable than current descriptions.

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?

As mentioned above, this has been done for many years, just under
different names, such as "renaming" or similar.

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?

An advantage of standard SSA is that it often enables simpler
formulations of algorithms operating over scopes larger than
basic blocks. "Simpler" can refer to both engineering ease as well
as operating efficiency.
There is also reason to believe some global algorithms operating on SSA
can be more effective in optimizing the code than a similar algorithm
operating on, say, standard use-def/def-use chains.
Read Engineering a Compiler (for example) for a more detailed discussion
about SSA and the benefits, uses, caveats, etc.

.

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)
  • SSA without phi
    ... SSA by using it only per basic block. ... The problem with phi functions is that they're not executable. ... could still benefit from the single-assignment property. ...
    (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)