Java Reference
In-Depth Information
In the discussion that follows, we call an assignment to
x
a
def
(short for
definition
)of
x
. Any other reference to
x
is called a
use
of
x
. SSA Form was
developed as an intermediate representation for programs written in any lan-
guage. The single assignment rule is relaxed to apply
statically
: assignment to
a given name can appear only once in a source program. Once SSA Form is
achieved, the value supplied for any given use of a name such as
x
can be as-
sociated with exactly one def of
x
. This property allows algebraic substitution
of program analysis information that flows from a def to each use.
SSA Form allows a statement such as
a
←
b
+
1 to execute multiple times,
but that statement can be the only one that defines
a
. Algorithms that compute
and use SSA Form are covered in Chapter 14. We describe the approach more
informally here, so that SSA Form can be computed by hand. We consider
monolithic programs (no procedure calls) that reference only scalar variables
(no arrays) and constants. Extensions are considered in the Exercises 13, 14,
and 15.
10.3.1 Renaming and
φ
-functions
The first step in obtaining SSA Form is to
rename
the defs of a program so that
each is unique. A simple approach that leaves the program relatively intact is
to rename each def using an integer subscript. This task can be done separately
for each name in the original program, as shown below for
v
:
v
←
v
1
←
4
←
v
1
4
←
v
+
+
5
5
v
2
←
6
←
v
2
v
←
6
←
v
+
7
+
7
When the program on the right is obtained,
v
1
and
v
2
are treated as distinct
names. They are renamed in this way only to show that their original name
was
v
. For code without branches, renaming su
ces to compute SSA Form.
In other cases, special care must be taken to manage the confluence of values
flowing from multiple defs of the same name:
if
p
then
v
←
if
p
then
v
1
←
4
4
else
v
←
6
else
v
2
←
6
v
3
←φ
(
v
1
,
v
2
)
←
v
+
5
←
v
3
+
5
←
v
3
+
7
←
v
+
7
The
(
v
1
,
v
2
) function articulates the point in the program where
v
1
and
v
2
converge. Without the
φ
-function, both defs would reach each of the uses that
follow. The introduction of the new assignment to
v
3
prevents such behavior.
Conceptually,
φ
φ
-functions could be placed anywhere in a program.
If
placed at point
p
in a program, then the
φ
-function would have a parameter
