SSA Based Compiler Design

The simplest, least constrained, definition of SSA can be given using the following
informal prose:
“ A program is defined to be in SSA form if each variable is a target of exactly one assignment
statement in the program text. ”
However there are various, more specialized, varieties of SSA, which impose
further constraints on programs. Such constraints may relate to graph-theoretic
properties of variable definitions and uses, or the encapsulation of specific
control-flow or data-flow information. Each distinct SSA variety has specific
characteristics. Basic varieties of SSA are discussed in Chapter 2. Part III of this
book presents more complex extensions.
One important property that holds for all varieties of SSA, including the simplest
definition above, is referential transparency?: i.e., since there is only a single
definition for each variable in the program text, a variable’s value is independent
of its position in the program. We may refine our knowledge about a particular
variable based on branching conditions, e.g. we know the value of x in the conditionally
executed block following an if statement beginning:
if (x == 0)
however the underlying value of x does not change at this if statement. Programs
written in pure functional languages are referentially transparent. Referentially
transparent programs are more amenable to formal methods and mathematical
reasoning, since the meaning of an expression depends only on the
meaning of its subexpressions and not on the order of evaluation or side-effects
of other expressions. For a referentially opaque program, consider the following
code fragment.
x = 1;
y = x +1;
x = 2;
z = x +1;
A naive (and incorrect) analysis may assume that the values of y and z are equal,
since they have identical definitions of (x + 1). However the value of variable
x depends on whether the current code position is before or after the second
definition of x , i.e., variable values depend on their context. When a compiler
transforms this program fragment to SSA code, it becomes referentially transparent.
The translation process involves renaming to eliminate multiple assignment
statements for the same variable.Nowit is apparent that y and z are equal
if and only if x1 and x2 are equal.