Content deleted Content added
m Added link |
Added lots of explanation, especially of phi functions |
||
Line 27:
=== Converting to SSA ===
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]]:
<i>More needed here describing need for phi functions, the dominance-frontier based algorithm for computing "minimal" SSA, and other things.</i>▼
<center>
[[Image:SSA_example1.1.png|An example control flow graph, before conversion to SSA]]
</center>
Notice that we could change the name on the left side of "x <math>\leftarrow</math> x - 3", and change the following uses of <var>x</var> to use that new name, and the program would still do the same thing. We exploit this in SSA by create two new variables, <var>x</var><sub>1</sub> and <var>x</var><sub>2</sub>, each of which is assigned only once. We likewise give distinguishing subscripts to all the other variables, and we get this:
<center>
[[Image:SSA_example1.2.png|An example control flow graph, partially converted to SSA]]
</center>
We've figured out which definition each use is referring to, except for one thing: the uses of <var>y</var> in the bottom block could be referring to <i>either</i> <var>y</var><sub>1</sub> or <var>y</var><sub>2</sub>, depending on which way the control flow came from. So how do we know which one to use?
The answer is that we add a special statement, called a <i>φ function</i>, to the beginning of the last block. This statement will generate a new definition of <var>y</var>, <var>y</var><sub>3</sub>, by "choosing" either <var>y</var><sub>1</sub> or <var>y</var><sub>2</sub>, depending on which arrow control arrived from:
<center>
[[Image:SSA_example1.3.png|An example control flow graph, fully converted to SSA]]
</center>
Now, the uses of <var>y</var> in the last block can simply use <var>y</var><sub>3</sub>, and they'll obtain the correct value either way. You might ask at this point, do we need to add a phi function for <var>x</var> too? The answer is no; only one version of <var>x</var>, namely <var>x</var><sub>2</sub> is reaching this place, so there's no problem.
A more general question along the same lines is, given an arbitrary control flow graph, how can I tell where to insert φ 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>.
▲<i>More needed here describing
See also: [[Compiler optimization]]
| |||