include/llvm/fernando which contains header files, and
lib/CodeGen which contains the implementation. In order
to add the register allocator to LLVM, you must follow the instructions
in this link.
Recent research results have demonstrated that the register allocation problem has a polynomial solution when restricted to programs in the Single Static Assignment (SSA) form. Although the proposed algorithms are theoretically optimal, the idiosyncrasies of a real architecture may hinder their optimality and elegance. This project consists in designing a new register allocation algorithm. Our algorithm detaches from previous works in the way that we handle the SSA elimination phase, liveness analysis and the resolution of conflicts with pre-colored registers. The main objective of our algorithm is to be simple, while still competitive with other register allocators. In order to validate the proposed algorithm, we have implemented it for the PowerPC platform using the LLVM compiler framework. The code produced by our implementation has performance similar to the code produced by LLVM's algorithm, although our implementation does not iterates in the presence of spills.
This project was supported by the google's Summer of Code initiative. Fernando Pereira is funded by CAPES under process number 218603-9. We thank Dan Berlin and Chris Lattner for their invaluable assistance (and patience:).
The Summer of Code initiative is something remarkably "cool": it allows young students to get in touch with open software, to make money, to know the people in the community, and, of course, it gives a mentor. I really appreciate what those guys in google are doing. If you are thinking about applying for it, you can check my research proposal.
The complete code of our implementation is available
here.
If you want to run it, you will need to download and install
LLVM, what, by the way,
is super easy. This gz file that we provide is divided in two main directories:
include/llvm/fernando which contains header files, and
lib/CodeGen which contains the implementation. In order
to add the register allocator to LLVM, you must follow the instructions
in this link.
Also, there is a diary describing the progress during the implementation phase of the register allocator. If LLVM is new to you, maybe you will find some nice hints about how to use this framework in that diary.
This table shows results
of some well
know benchmarks compiled with the proposed algorithm. Besides this
programs, we have also being able to compile programs in the spec-cpu
2000 benchmark suite. For a comparison, we provide the results of other
register allocators. In this table you have the same programs compiled with LLVM's
default algorithm. This is a
version of linear scan with many improvements. Indeed, it executes some
iterations in the presence of spills. This
table
contains the results of the local allocator: an algorithm that tries to
keep data in registers inside basic blocks. Finally, this
table contains the
results of the naive allocator, an algorithm that spills everything.
|
|
This file contains the latest stable version of my implementation of a
SSA-based register allocator.
This implementation does not contain the super-ultra-fast coalescing algorithm;
this one is based on the interference graph, and it is super-ultra-slow.
If you want the fast one, write me and e-mail.
If you want to run it, you will need to download and install
LLVM, what, by the way,
is super easy. This gz file that we provide is divided in two main directories:
include/llvm/fernando which contains header files, and
lib/CodeGen which contains the implementation. In order
to add the register allocator to LLVM, you must follow the instructions
in this link.
|
|
|
This file contains a report describing the implementation of the SSA-based allocator. It contains a description of each of the main passes necessary to produce running code, and also it brings running time measurements of the code produced by the compiler. |
|
|
This file is a shorter version of the report available at the link above. |
