Phi Functions in SSA Form
We could rename each block:
We need to express somehow that either res0 or res1 can be used in m, and similarly either s1 or s2. We use functions for this purpose.
res2 = phi(res0,res1) s3 = phi(s1,s2) p = res2 * s3
This denotes that the value of res2 will be res0 when the control comes from one branch and res1 if it comes from another branch. Similarly for s.
(Suppose we have a loop around this. What is the resulting CFG with phi nodes?)
For Which Variables to Insert Phi Functions
If a variable is not assigned on some path, we need not insert a phi function for it
We insert phi function for variable 'a' in the “first” node z where paths from different assignments to 'a' merge, i.e.
- there is a definition of 'a' in two different nodes, x, y, with two non-empty paths Pxz, Pyz
- the paths Pxz, Pyz have no node in common except z
- in at least one of Pxz,Pyz z appears only as the last node
Inserted phi function becomes a new assignment, so we need to apply the criterion again (until we reach fixpoint)
Most efficient algorithms (nearly linear) for SSA form use dominator nodes in graphs