Static single-assignment form: Difference between revisions

Revision as of 23:35, 15 February 2005

Revision as of 23:36, 15 February 2005

Line 3:

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 [[compiler optimization]]s, by simplifying the properties of variables. For example, consider this piece of code:

Line 25:

*[[register allocation]]

=== Converting to SSA ===

==== Introduction ====

Converting ordinary code into SSA form is primarily a simple matter of replacing the target of each assignment with a new variable, and replacing each use of a variable with the "version" of the variable [[reaching definition|reaching]] that point. For example, consider the following [[control flow graph]]:

Line 53:

A more general question along the same lines is, given an arbitrary control flow graph, how can I tell where to insert &phi; functions, and for what variables? This is a difficult question, but one that has an efficient solution that can be computed using a concept called <i>dominance frontiers</i>.

==== Computing minimal SSA using dominance frontiers ====

First, we need the concept of a ''dominator'': we say that a node A ''strictly dominates'' a different node B in the control flow graph if it's impossible to reach B without passing through A first. This is useful, because if we ever reach B we know that any code in A has run. We say that A ''dominates'' B if either A strictly dominates B or A = B.

Line 71:

(Cambridge University Press, 2002). See the paper for more details.

=== Converting out of SSA form ===

<i>Simple copy insertion, algorithms to reduce copies, etc. If overlapping lifetimes are allowed (which is critical to SSA form) simply dropping the subscripts doesn't work. Pure SSA form doesn't really use subscripts anyway.</i>

=== Extensions to SSA form ===

<i>Many possible extensions to talk about. Probably the most important are ones involving memory, gated SSA form, and array SSA form.</i>

=== Compilers using SSA form ===

SSA form is a relatively recent development in the compiler community. As such, many older compilers only use SSA form for some part of compilation or optimization process, but most do not rely on it. Examples of compilers that rely heavily on SSA form include:

Line 93:

* Although not a compiler, [http://boomerang.sourceforge.net/ Boomerang] (a [[decompiler]]) uses SSA form in its internal representation. Applicability of various SSA algorithms to [[decompilation]] is an active area of SSA research.

=== See also: ===

* [[Compiler optimization]]