LLVM-test

I'm on the process of testing my SSI conversion. In order to prepare my code for testing, I did the following.

• Create a method in your Pass called createPass()

FunctionPass *llvm::create<PassName>Pass() {
 return new <PassName>();
}

• Include the following line in the file llvm/include/llvm/LinkAllPasses.h and llvm/include/Transforms/Scalar.h

(void) llvm::create<PassName>Pass();

• Include the following line in the file llvm/include/llvm/Support/StandardPasses.h

PM->add(create<PassName>Pass());

With this I was able to run make TEST=nightly report.html on a folder and it returned fine.

Now I have to run this test on the hole LLVM-test folder. As this will take a lot of time, my plan for today (friday), is to set up a computer in my lab to run these tests.

It's been a while

It's been a while since I last wrote in my blog. The reason is that it was a holiday in Brazil, and I was away for the last 5 days. Now that I'm back, I'm preparing my SSI conversion to test it in llvm-tests, and as soon as it is working I will submit a patch.

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.

What to do next?

I'm now studying how to transform a representation from SSA to SSI. My approach will be to transform on demand. So not all the code will be in SSI, just the variables asked to be transformed by a client.

So a client will request to transform one variable, lets call it A. The Pass will run through each use of that variable A and will see if it is used in any branch. In case it is used in a branch, we will include a copy instruction like A = A in all basic blocks that succeeds the branch.

This approach will break the SSA IR for the moment. But now to construct SSI, we need to use the same SSA algorithm in variable A, thus changing all copy instructions inserted before to Ai = A, and inserting phi functions when necessary. This will bring the IR back to SSA, and variable A will be in SSI.