Static single-assignment form: Difference between revisions

Revision as of 16:05, 20 November 2003

Revision as of 00:57, 23 November 2003

Line 1:

In [[compilers]], '''static single assignment form''', more often abbreviated '''SSA form''' or just '''SSA''', is an [[intermediate representation]] in which every variable is assigned exactly once. Existing variables in the original IR are split into <i>versions</i>, new variables typically indicated by the original name with a subscript, so that every definition gets its own version. In SSA form, [[use-def chains]] are explicit and each contain a single element.

SSA was developed by researchers at [[International Business Machines|IBM]] in the 80's.

=== Benefits of SSA ===

The primary usefulness of SSA comes from how it simultaneously simplifies and improves the results of a variety of optimizations, by simplifying the properties of variables. For example, consider this piece of code:

y := 1<br>

y := 2<br>

x := y<br>

As humans, we can see that the first assignment isn't necessary, and that the value of <code>y</code> being used in the third line comes from the second assignment of <code>y</code>. A program would have to perform [[reaching definition|reaching definition analysis]] to determine this. But if the program is in SSA form, both of these are immediate:

y₁ := 1

y₂ := 2

x₁ := y₁

Algorithms which are either permitted or strongly enhanced by the use of SSA include:

*[[constant propagation]]

*[[dead code elimination]]

*[[global value numbering]]

*[[partial redundancy elimination]]

*[[register allocation]]

*[[sparse conditional constant propagation]]

=== Converting to SSA ===

<i>More needed here describing need for phi functions, the dominance-frontier based algorithm for computing "minimal" SSA, and other things.</i>

See also: [[Compiler optimization]]

This article is a [[Wikipedia:Perfect stub article|stub]]. You can help Wikipedia by [[Wikipedia:Find or fix a stub|fixing it]].