Gated Single Assignment [Was: Online explanation of Dijkstra's Guarded Command Language]

Vidar is quite right that there's near no connection between Dijkstra's
guards and the guards of GSA.


Vidar Hokstad wrote:
> If you're looking for approaches to do code optimisation by doing
> tranformations on the compiler internal code representation, on the
> other hand, Brandis is a concise overview of a very interesting
> approach based on single assignment.


Brandis thesis is nicely written, but he didn't invent the GSA form.
AFAIK, Ballance, Maccabe, and Ottenstein introduced the GSA as /gated
single-assignment form/ in "The Program Dependence Web: A Representation
Supporting Control-, Data-, and Demand-Driven Interpretation of
Imperative Languages". Thus, Chris might want to consult to original
text for a gentler introduction.


> Guarded single assignment is simply a variation on SSA where
> statements may be "guarded" by a condition controlling it's execution
> or a "merge" (representing the joing of two control paths). It's been
> too long since I read Brandis thesis to remember whether this presents
> any particular benefits over other SSA representations, or whether it
> is just meant as a convenient way to implement SSA for Brandis'
> project.


It has huge advantages IMO. The SSA-form merge nodes (phi node) aren't
referentially transparent and don't even have local semantics, which in
practice means that congruences across basic blocks is requires a global
analysis. The GSA form incorporates the structure of the flow graph
directly leading to very simple and elegant algorithms for incremental
constant propagation, GCSE, constant folding, strength reduction, etc.


For good motivation see the "Value Dependence Graph: Representation
without Taxation" (VDG is very close to TGSA, which is close to GSA) or
Havlak's Thesis http://hgsc.bcm.tmc.edu/~havlak/thesis/thesis.html (a
great read).


Note, GSA is restricted to structured programs, TGSA to reducible flow
graphs, and VDG has no restrictions. Not surprisingly the complexity
grows as you move left to right.


Tommy

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