Conversion to SSI

In my last post I described the approach I would take to convert to SSI. I didn't have much knowledge on LLVM intermediate representation when I wrote that. During this week I found that my approach was not valid, since there is no instruction like A=A. So it is not possible to break SSA the way I intended. But we can insert phi functions with only one operand as sigma functions, and we will have a virtual break of SSA, if we consider this sigma as a new declaration of the variable.

I changed a little bit because of this but not too much.

My approach is:
To translate to SSI we need to do 3 steps in this order

• Insert sigma functions
• Insert phi functions
• Rename variable uses

As our approach is on demand, the transformation will be done for all variables requested by a client. And we will convert only variables used in conditionals that are used in a branch on the end of a basic block. With this in mind for every variable, in the client's list, that is in a conditional branch, we create a sigma function on all basic blocks successors of this one. But only those BB that have only this BB as predecessor. We used phi functions with only one operand to implement sigma functions.

With all sigma functions inserted we can insert phi functions. The insertion of phi functions is the same as used for SSA conversion, with the remark that the created sigma functions are treated as declarations of the original variable, thus creating a virtual break of the original SSA, but not a real break of it. The algorithm we used is described by Appel in his book "Modern compiler implementation in Java".

The next step is to rename the uses. This step is also the same as the step for the SSA conversion and we used the algorithm from Appel also. We have only a few small remarks so it can work.

• Sigma functions are treated as new declarations of the original variable.
• SSI inserted phi functions are treated as a phi functions for the algorithm.
• SSA phi functions are treated as any other instruction.

So with this approach, the transformation for SSI is already implemented, now we need to do some testing and some code revisions.

The next step is to define how to store and use constraints for our clients.