Consider translating

s = y
if (x < 0) {
  res = - x
  s = s -1
} else {
  res = x
  s = s + 1
}
p = res * s

We could rename each block:

s0 = y
if (x < 0) {
  res0 = - x
  s1 = s0 -1
} else {
  res1 = x
  s2 = s0 + 1
}
p = res? * s?

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.

Translate

m(res,s)

into

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?)

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