How to eliminate phi instructions in transformed SSA?

Question

I am working on a homework compiler project and I have done the mem2reg pass and got some phi instructions in my LLVM IR.

However, I am confused about how to eliminate the phi nodes (phi destruction). After searching online and reading some chapters of Single Static Assignment Book and Data Flow Analysis, I know a few concepts and several method to eliminate the phi nodes.

• Critical Edge Spliting
• Lost of Copy Problem
• Swap Problem

Traditional ways to eliminate phi nodes can just be like this

block 1
//x3 = phi(x1,x2)

block 2
x1 = ...
move x3 x1

block 3
x2 = ...
move x3 x2

I know such way would cause the lost of copy problem (when copy propagation) and swap problem, and I found a way slightly different from this

block 1
x3 = x4
//x3 = phi(x1,x2)

block 2
x1 = ...
move x4 x1

block 3
x2 = ...
move x4 x2

Can this way of phi's elimination do a fully good job on transformed SSA ? Or in what condition this method would cause errors ?

May be it can not, because I always see "cirtical edges spliting" and I can't fully understand it.

When adding a empty block in a cirtical edge, the movement about phi's elimination seems to be the end of the empty block ? And I try to stimulate it, I found that it woundn't solve the swap problem.

Answer 1

After trying the several above methods and looking into some backend implementation in our lab, I guess the following explaination can solve my doubts.(It may not be strict and general, but it works)

split the critical edge

This procedure is for avoiding the lost of copy problem when doing copy propagation on LLVM IR.

When doing phi elimination, in the above image there is x3 = phi(x1,x2), we want move x1 and x2 to x3 respectively after executing the two predecessor blocks of phi inst. However, it's worthy to mention that, the exact place we want to insert phi is neither the beginning of the phi block nor the end of the predecessor block, we want to insert it in the edge, when the edge is not a critical edge(predesessor has only one successor and successor has only one predecessor), we can insert it casualy. But when there is a critical edge, the only way to implement this is add a special block for the critical edge.

For each phi create a temporary register to store the result

That is

bb1:
x3 = x4
//x3 = phi(x1,x2)

bb2:
x1 = ...
move x4 x1

bb3:
x2 = ...
move x4 x2

This way can also solve the lost of copy problem, as the new temporary register can be viewed as a implict path to pass the result.

Moreover, this way can avoid swap problem too.

When several phi instructions need to be execute in parallel, in the traditional move method, there can be circles in the copy graph, that is, a phi's rs is another phi's rd. For each phi creating a distinct temporary register can avoid this perfectly.

Two ways to do Phi elmination

• Just create a new temporary register for each phi
• Split the critical edge first, and for the cricles in the copy graph when eliminating phi, break the circles, insert just one new register for each circle, then move the registers in reverse toplogical order.

The above two images are from Data Flow Analysis : Theory and Practice

If there is any mistakes, plase point it out, thanks!