After doing some transformations on control-flow graph, we may wish to revert back to trees

In SSA form, for each variable we can look up its definition, which makes finding appropriate trees easy

Suppose we do this recursively, but do not look up definitions that involve Phi nodes and loads from memory

We obtain a graph, which we can view as a tree

We can also omit “copy” definitions of the form

x = y

Example: in the following code

y0 = 0
x0 = a
x1 = x0 + y0
y1 = y0 + x1
x2 = y1 * b

for the definitions we obtain the following trees

y0 = 0
x0 = a
x1 = x0 + y0 // a + 0
y1 = y0 + x1 // 0 + (a + 0)
x2 = y1 * b  // (0 + (a + 0)) * b

So, for each assignment to variable we can compute the expression that the right-hand side denotes

If the expressions are equal, we can avoid re-computation (common subexpression elimination)

• this can be done recursively, so we avoid comparing big expressions
• maintain invariant: if two variables denote the same expression, map one to the other

x = a     // a
y = b     // b
z = x + b // a+b
u = a + y // a+b --> z
p = z + 1 // z + 1
q = u + 1 // z + 1 --> p

We can also do simplification on trees (folding 0)

We can obtain maximally shared directed graphs, or we can obtain trees