SSI Patch

Finally the patch containing SSI was incorporated into LLVM. It took a few weeks of discussion on the llvm list.

The link below shows the patch.

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090629/080114.html

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.

LLVM with Ada support

Our objective is to remove array bound checks. So we need a strongly typed language that will have array bound checks to remove all possible. Ada is an imperative language that is strongly typed.

This week I have been busy working out how to use LLVM to compile Ada. It was a little difficult on the beginning because I had to install an old version of the Ada compiler (GNAT), and I didn't realize it a first. But after that it went a little smother. I asked on the llvm-dev list for some help, and Duncan Sands helped me out. Below is a description of what I had to do to install llvm-gcc with support for Ada.

• The build requires having a compiler that supports Ada, C and C++. The Ada front-end is written in Ada so an Ada compiler is needed to build it. Compilers known to work with the LLVM 2.4 release are gcc-4.2 and the 2005, 2006 and 2007 versions of the GNAT GPL Edition.

• So first thing is to do is download GNAT 2007. Download it from here.

• Export the download in a folder. Lets call it ada_folder. Then install it into /build.

• Now we need to get llvm-gcc. Lest call llvm-gcc_folder the folder where llvm-gcc is downloaded.

svn co http://llvm.org/svn/llvm-project/llvm-gcc-4.2/trunk llvm-gcc_folder

• Make a build directory for llvm-gcc and make it the current directory:

cd
mkdir build
cd build

• Now we need to configure it.

export CC=/build/bin/gcc
export CXX=PATH_TO_C++_COMPILER

../configure --enable-languages=c,c++,fortran,ada --disable-bootstrap --disable-nls --disable-multilib --enable-checking --program-prefix=llvm- --prefix=/build --enable-llvm=

• Before we build the compiler we need to put gnat2007 in our classpath. Only while we build it, we can change it later.

export PATH=/build/bin:$PATH

• Build and install the compiler:

make -j2
make install

• Now we need to change the PATH:

export PATH=/build/bin:/build/libexec/gcc/i686-pc-linux-gnu/4.2.1:$PATH

GSoC 2009

Good Evening dear Readers,

I had a project accepted for Google Summer of Code 2009. I will be working with LLVM, which is a modern compiler. LLVM is very well modularized, which allows to be extended easily.

My first goal is to extend its intermediate representation from SSA to SSI. But it will only simulate SSI, because if I really changed to SSI, it would be necessary to make tons of changes in the core of the compiler.

Once my SSI simulated is done, it will allow me to implement the ABCD algorithm. Which is my second goal.

And the third goal is to create a bit-width analysis, using the algorithm described by Stephenson et al. It also depends on the SSI representation.

This is the first post of my blog, created specifically for this GSoC. I will be posting regularly as request.

More information on this project may be found at: http://homepages.dcc.ufmg.br/~andrelct/projects/gsoc_2009