|SSA without phi Nicolas.Capens@gmail.com (2007-04-20)|
|Re: SSA without phi firstname.lastname@example.org (Tommy Thorn) (2007-04-23)|
|Re: SSA without phi email@example.com (2007-04-23)|
|SSA without phi firstname.lastname@example.org (Inderaj Bains) (2007-04-23)|
|Re: SSA without phi cfc@shell01.TheWorld.com (Chris F Clark) (2007-04-23)|
|Re: SSA without phi email@example.com (Matthias Blume) (2007-04-26)|
|Re: SSA without phi Nicolas.Capens@gmail.com (2007-04-29)|
|Re: SSA without phi firstname.lastname@example.org (Tommy Thorn) (2007-05-04)|
|Re: SSA without phi email@example.com (2007-05-04)|
|[3 later articles]|
|From:||firstname.lastname@example.org (Jason Lee Eckhardt)|
|Date:||23 Apr 2007 07:51:13 -0400|
|Organization:||Rice University, Houston, TX|
|Posted-Date:||23 Apr 2007 07:51:12 EDT|
>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
Search the comp.compilers archives again.