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

Tommy Thorn <>
14 Jun 2004 17:46:58 -0400

          From comp.compilers

Related articles
Online explanation of Dijkstra's Guarded Command Language (2004-05-30)
Re: Online explanation of Dijkstra's Guarded Command Language (2004-06-06)
Gated Single Assignment [Was: Online explanation of Dijkstra's Guarded (Tommy Thorn) (2004-06-14)
| List of all articles for this month |

From: Tommy Thorn <>
Newsgroups: comp.compilers
Date: 14 Jun 2004 17:46:58 -0400
Organization: Compilers Central
References: 04-05-101 04-06-013
Keywords: analysis
Posted-Date: 14 Jun 2004 17:46:58 EDT

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


Post a followup to this message

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