Re: SSA without phi

  <Nicolas.Capens@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.


    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.

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