[LLVMdev] Some questions about live intervals

[Fernando Magno Quintao Pereira]

Hi, Roman,

     we have an implementation of an allocator for LLVM that, like 
Sarkar's, allows to split live ranges at any program point. You can find 
its description here:

http://compilers.cs.ucla.edu/fernando/publications/drafts/long_PereiraPalsberg07.pdf

We handle register classes using an abstraction called puzzles. Also, we 
perform register allocation while the program is still in SSA-form. This 
requires breaking critical edges before RA, and removing phi-functions 
while taking register assignment in consideration, once RA is done. We 
have the code implemented in LLVM 2.1, and it passes all the tests that I 
have tried.
     If you need help testing and debugging your allocator, I can help you. 
We have a debugger that was very useful when trying to find errors in our 
implementation. Also, to implement Sarkar's ELS, you will need to swap 
live ranges at the boundaries of basic blocks. This is a little tricky 
once you have registers of different size, and I can help you with it.

all the best,

Fernando

>
> Yes. I plan to contribute it to the public LLVM repository. The
> skeleton implementation of this algorithm is alsmost done, though I
> still have some small problems mentioned in my original email. But to
> make the algorithm really usable, it should be extended to support
> register classes, since Sarkar's algorithm cannot handle it. I'm going
> to try out an approach based on Smith's paper about graph coloring
> register allocation. Hopefully this would solve this issue.
>
> - Roman