llvm dev - Feb 2008 - [LLVMdev] Some questions about live intervals

Hi David,


--- David Greene <dag at cray.com> schrieb:
> On Thursday 31 January 2008 07:05, Roman Levenstein wrote:
> 
> > I already started work on the implementation of this algorithm and
> have
> > a few hopefully rather simple questions:
> 
> Roman,
> 
> I'm excited to hear that you are working on this algorithm.  Do you
> plan to contribute it to the public llvm repository?
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


      Lesen Sie Ihre E-Mails jetzt einfach von unterwegs.
www.yahoo.de/go

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

Hi Fernando,
> 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
> 
I've read your paper already. It is a very interesting approach!
But my impression was that it is rather complex solution and requires
quite some bits of implementation. I also looked at your sources. Looks
like they introduce a lot of new code into LLVM. 

IMHO, one of the attractive parts of Sarkar's algorithm is its
simplicity. It almost does not require any significant changes in the
LLVM code-base and is also conceptually a bit simpler.
>      we have an implementation of an allocator for LLVM that, like 
> Sarkar's, allows to split live ranges at any program point. 
Actually, Sarkar's algorithm can split only at block boundaries, as far
as I understand. This can be an obstacle for very long basic blocks.
One of the interesting ideas could be to introduce live-range splitting
into his algorithm.

BTW, since I was also working on Wimmer's linear scan algorithm (which
is sort of implemented, works on simple test-cases and requires a  lot
of code clean-up and refactoring), I also have the LiveInterval
splitting code in place and it can be done at any program point.
> We have the code implemented in LLVM 2.1, and it passes all the tests
> that I  have tried.
Cool! I'm not that far yet :-(
>      If you need help testing and debugging your allocator, I can
> help you. 
Thank you very much for offering this. I'll most likely come back to
you, once I'm that far.
> We have a debugger that was very useful when trying to find errors in
> our implementation. 
I've seen references to it on your page. But this debugger is in Java,
or? So, one has to dump the results of register allocation and input
problem and it would do some checks, or?
> 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.
Actually, I already implemented something very similar for Wimmer's
linear scan. The main issue was to order the copies in the right way
and to introduce stores/loads to handle circular dependencies. Or do
you say that register classes of different sizes introduce additional
problems?

Thanks,
  Roman


      Lesen Sie Ihre E-Mails auf dem Handy.
www.yahoo.de/go