[LLVMdev] Some questions about live intervals

[Roman Levenstein]

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