[CST-2] OptComp: Single Static Assignment Form

[Phebe Mann]

On Sun, 20 May 2001, M.Y.W.Y. Becker wrote:

> OptComp
> CST 99/7/4
> Question (b):
>  "Given a program expressed in a language like C,
>  explain how one might deal with (non-address taken)
>  formal parameters and local variables so that the
>  resulting flowgraph is in SSA form."
>
> What is meant by "formal parameters" and "local variables"? Is that a
> question about the Phi-operator? In particular, what is the difference to
> question (a)?
>

Formal parameters
Formal parameters are dummy arguments in a function. They are the place
holders for values which will be supplied when the function is called. The
actual parameters provide the values to be substituted for the formal
parameter.
(*** not so sure about non-address taken ??***)

e.g function divide

divide(int x, int y)
	if y = 0 then return 0
	else return x/y

x and y are the formal parameters of the function

Local variables
A function may have local variables that are created on entry to the
function. Several invocations of the function may exist at the same time,
and each invocation has its own instantiations of local variables,

Yup, It is about Phi-function.

For variables defined by the programmer, e.g. as parameter to the
function, or as local variables, the compiler must split the variable into
temporaries, such that each temporary is only assigned to once. This can
be done with a counter for each variable that is prefixed to the variable.
Then the variable is assigned to the counter is increased, creating new
temporary.

v=3;  v=v+1; v=v+w; w = v*2;
becomes v1 = 3; v2=v1 + 1; v3 =2

and e.g.

{ if (p)
	{ v = v+1;
	  v = v + w;
	  }
	  else v = v-1;
	  }
	  w = v*2


{ if (p)
	{ v4 = v3 + 1
	  v5 = v4 + w
	  }
	  else v6 = v3 -1 ;
	  }
	  v7 = Phi (v5, v6); path merge
	  w = v7 * 2


has to be taken between basic blocks, if 2 basic blocks enter another ,
the current version of each variable is at the end of each basic block
must have made to match. This can be done in Phi-function between the
blocks, which takes the current versions from the previous blocks and
creates a new one.

for part (a) A new temporary must be used whenever a 3-address assignment
to a temporary is created. Normal form ?? Any thoughts ??

>
> And the last part:
> "Commonly SSA form is discussed only for temporaries and non-address-taken
> local variables. To what extent is it possible to arrange that accesses to
> address-taken locals or statically allocated global variables can be
> transformed into SSA form? What effect might such a transformation have on
> register allocation of such variables?"
>
> Any ideas?
>
> Mo
>
>
>
>
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2
>