More programs compiled!

Today I got more programscompiled correctly. One of the problems that was happening was that I was not saving the caller save registers. I have discovered this after talking to my mentor and to Mr. Lattner. Now I am trying not to use the caller save registers to allocate data. This allows me to compile correctly the programs in the test directory. Check them out. They include the famous "Hello, world!", and many of its variations, such as "Hello, there!" and "Hello, darling". The last one was this one here. Thank you, Daniel, and Chris. But, up to know, my register allocator does not spill, nor destroy phi functions. This means that I only can compile strait line code, and the register pressure cannot be very high. I will address spilling and phi elimination in the coming days. PHI elimination will come first.

Serious issue

Because X86 is quite annoying, I have decided to install the Power PC version of LLVM. Because it needed GCC 4.1, I had to install Tiger. I was very reluctant to install Tiger, because I really liked Panther. Surprisingly, the installation went quite smoothly. After that, I discover that Tiger only comes with GCC 4.0.0, which did not compile LLVM correctly. So, go and download the XDeveloper 2.3, which also installs quite easily (those people from MacOS deserve some candies). Everything put together, go to install LLVM. Oh, God, it took me a long while to figure the class path out, now that I had two versions of llvm in the same computer. Anyways, now it is working, and I am using the PowerPC version of LLVM, be it for good, or be it for bad. But there is now one quite serious issue: in the way LLVM is implemented, it requires that the first and second operand of a three address code instruction be the same. The pass used to put the program in this format breaks SSA. I am not sure yet how to solve this. Go and talk to the LLVM guys...

First program compiled!

Nothing like gdb! I have used it today to debug my register allocation pass. To the guy who coded gdb: I love you! To use gdb in LLVM is the same as in any other application. First gdb llc. After that, try run -f hello.bc -o result.s. The problem of my pass was that I was not setting the vector that marks the physical registers used. In my opinion, LLVM should assert that the size of this vector is the size of the number of physical registers that need to be used. Maybe I can ask this for the LLVM guys. To compile a program, I am using this sequence of commands:

llvm-gcc file.c -o file
llc -f file.bc -o chordal.s
gcc chordal.s -o file.exe
./file.exe [params]

To make life easier, I have this script. I will be storing the files that I can compile correctly in this directory. I still have to remove some pesky move instructions. The code generated by linear scan, or local allocation (built in in LLVM) does not have those instructions. I think it is because they are using this "Two address instruction pass".

First program compiled!

Nothing like gdb! I have used it today to debug my register allocation pass. To the guy who coded gdb: I love you! To use gdb in LLVM is the same as in any other application. First gdb llc. After that, try run -f hello.bc -o result.s. The problem of my pass was that I was not setting the vector that marks the physical registers used. In my opinion, LLVM should assert that the size of this vector is the size of the number of physical registers that need to be used. Maybe I can ask this for the LLVM guys. To compile a program, I am using this sequence of commands:

llvm-gcc file.c -o file
llc -f file.bc -o chordal.s
gcc chordal.s -o file.exe
./file.exe [params]

To make life easier, I have this script. I will be storing the files that I can compile correctly in this directory. I still have to remove some pesky move instructions. The code generated by linear scan, or local allocation (built in in LLVM) does not have those instructions. I think it is because they are using this "Two address instruction pass".

Annoying error...

Good and bad news. The good news is that I am already trying to run the register allocator in real programs. The bad news is that it crashes. The error is something like this. I sent this e-mail to the discussion list, and I will try to solve this problem also by myself.

Assembling the knights

Today I "learned" X86 assembly language. I am studying X86 to see how I must insert xor instructions in order to eliminate phi functions. This program here, for example, prints "Black knight" if the number of command line arguments is exactly 2, and prints "White knight" otherwise. The pointer to the string that must be printed, and the string size, are stored in registers. Xor instructions are used to eliminate the phi function in edge B2-B3, and move instructions are used to eliminate the phi function in edge B1-B3.

Midterm evaluation

The midterm evaluation is approaching, and I decided to post the code that I have already implemented. The code is here. The implementation, up to now, consist of 3.700 lines of code. It contains one application that generates the control flow graph of .c programs, some data types, and the skeleton of the register allocation algorithm. The RA is producing a map between virtual and physical registers that seems to be correct. For instance, for this program here (.c), it produces this map. Tomorrow I will be studying X86 assembly code, so, there will be no new code. I hope to start coding again by Friday.

Updating LLVM

Today I got the updated version of LLVM. It was not hard to recompile everything, but the code of RegAlloc* has changed. Anyways, I will be using this very simple program in the next experiments (Loop.c). The control flow graph is quite easy to follow. To get the updated version of LLVM, go to the root directory (/llvm), and run cvs update.

Correct mapping.

I think the mapping between virtual registers and physical registers is working correctly. Thus, if the program does not produces spill, I believe that the assignment of machine registers to temporaries is right. I have implemented part of the spill code, but I still have to debug it. I have not touched the phi deconstruction algorithm yet.

Crab walk

Today I decided to change some of the interfaces that I had already coded. It will make the code more uniform. I also changed some parts of the general algorithm (but very little). I have a lot of implementation done, but will not post it here, because the code cannot yet be tested. I hope to have good progress tomorrow.

Tacking spills

I am working in the implementation of the register allocation algorithm now. I will not post code, because the program is not completely ready yet. I have already coded the algorithm to choose the best register candidate to be spilled.
Also, I finished implementing a simple algorithm that goes over the cliques and search points where the register pressure is high. Tomorrow I will be testing and debugging the program.

Def/Use sites

Today I finished coding a class that maps each virtual register to all the instructions where they are used, (and defined). This class will be useful during register allocation. It will allow to place load and store instructions efficiently, and, most important, it will allow to compute the spilling factor of each virtual. I call spilling factor a number that determines which virtual is the best candidate to be spilled. The heuristics I am using takes into consideration how many times the register has been used, and the nesting depth of the using (and defining) instructions. For this example control flow graph here, the dump() function will produce this output. Check the .h and the .cpp classes.

Cliques of Registers

Today I finished the implementation of the build_list_of_cliques algorithm. The code is here. It uses liveness analysis information to find all the cliques in a basic block. By clique I mean a set of physical and virtual registers whose live ranges overlap. If a clique contains more than K elements, where K is the number of machine registers available for register allocation, then some virtual registers must be spilled. Now I am implementing a mapping between virtual registers and the instructions where they are defined or used.

Finished describing algorithm

Today I finished fully describing the register allocation algorithm. Also, I discovered a little bug in the liveness analysis implementation. I will try to fix it tonight, or tomorrow morning. There is still one problem: which is the best way of coping with pre-colored registers?

Getting loop information

The register allocation algorithm must provide heuristics to select good registers to spill, when spilling is unavoidable. Normally, the usage frequency of instructions is used as a utility function. The best candidate for eviction is a temporary that minimizes the frequency of execution of load and store instruction. Such frequency can be approximated by taking into consideration the loop depth of each basic block. In order to obtain this information in LLVM, one can use the following code:

#include "llvm/Analysis/LoopInfo.h"
AU.addRequired<LoopInfo>(); // in getAnalysisUsage
const LoopInfo *loopInfo;
loopInfo = &getAnalysis<LoopInfo>();
// MBB is MachineBasicBlock
const BasicBlock *BB = MBB.getBasicBlock();
unsigned loopDepth = loopInfo->getLoopDepth(BB);


Types of Registers

Today, I got this explanation from Chris Lattner. Very clarifying:

Before register allocation, there are three types of registers:

1. Virtual registers. These are in SSA form, and follow all the normal SSA properties. These can be live across blocks.
2. Unallocatable physical registers (e.g. ESP). These can be live anywhere and can be used/modified in ways the register allocator is not required to understand.
3. Allocatable physregs (e.g. EAX). These are required to only be live within a machine basic block. This restriction is primarily to simplify/speed up the compiler (at no loss of generality because vregs can always be used). The live ranges of allocatable physregs should be short, e.g. an instruction selector may emit:


EAX = vreg1234
EDX = vreg4567
div vreg1928
vreg8910 = EAX


The set of allocatable physregs can be obtained with
MRegisterInfo::getAllocatableSet.

Critical Nasty Edges

Today I spent a very nice time trying to remove the critical edges from the control flow graph. Well, I can use the opt tool to remove these mischievous edges, but I could not make it automatic. When the hope is about to die, ask some LLVM guy... by the way:
opt -break-crit-edges < oldFile.bc > newFile.bc
llc -f -regalloc=simple Base1Sum.bc -o simple.s

Check the visualizer

I have a nice prototype of the visualizing tools that I am coding. The code for the pass is here. It is practically done. The only thing that is missing is the liveness information for physical registers. I will try to fix this on the comming days. But it outputs nicely the liveness information for all the virtual registers. For a function like this one, it renders a dataflow graph like this. Hum... actually it only renders the dot description of the data flow graph. In order to see the graphic output, you must use something like Graphviz, that, by the way, is free.