Copy Propagation

Copy Propagation propagates the right argument of an assignment statement to the places where the left argument is used. This transformation is performed on the Scribble CFG while it is in SSA form. Our algorithm traverses the Scribble CFG looking for simple assignment statements on which to execute the transformation. At this time, we do not propagate copies if

the assignment is not a simple assignment to a variable,
if the right argument contains May-Use information indicating that it may be involved in an alias relationship, or
if either of the two arguments in the assignment are global variables.

Even in simple assignments we may not be able to perform the propagation successfully, if it is found that the variables aliased by the left argument and its use(s) have different SSA versions. In general, after the right argument of an assignment is propagated to all the uses of the left argument, the original assignment may be deleted. However, in our implementation, we found that removing the original assignment resulted in poorer code being generated. Specifically, the coalescing of variables, when coming out of SSA form, is hindered by overlapping lifetimes of different SSA versions of the same variable. Thus, in our implementation, the original assignment is left as is, and only gotten rid of during a phase of dead variable elimination.

For productions in the Scribble CFG of the form

   A = B

uses of A are replaced by B.

Return to Scale home page.
(Last changed: March 21, 2007.)