llvm dev - Oct 2007 - [LLVMdev] Supporting pre-allocated registers in LLVM

Hi there

i would like to ask a few questions to the developers responsible for the
register  allocator(s) design in LLVM (Fernando and other people).

First of all, congrats on providing more than one option for register
allocation.

Now to the questions:

1. I can see the standard algorithms (bigblock, linearscan -- good choice for
the JIT and for general use as well, and the other algorithms). Is it possible
to pre-allocate registers in your linearscan (or in another allocation engine)
for specific source-level or (better) intermediate code (bitcode) level
variables?

Ideally i would to pre-allocate hard registers for specific temporary variables
(and their aliases through out the entire lifetime in a program -- or at least
a single C function). The pre-allocation would take place early in the register
allocation.

I'm designing small-scale embedded systems and pre-allocation is very
meaningful
in this context.

2. Which are the new register allocation algorithms currently under design? Do
they support preallocation of registers (it is different to "fixing" a
register
in GCC parlance)?

3. Does LLVM work on PDGs (Program Dependence Graphs) as well? If yes, does the
register allocation take on PDGs?


Kind regards
Nikolaos Kavvadias

On Oct 4, 2007, at 10:40 PM, nkavv at physics.auth.gr wrote:
> Hi there
>
> i would like to ask a few questions to the developers responsible  
> for the
> register  allocator(s) design in LLVM (Fernando and other people).
>
> First of all, congrats on providing more than one option for register
> allocation.
>
> Now to the questions:
>
> 1. I can see the standard algorithms (bigblock, linearscan -- good  
> choice for
> the JIT and for general use as well, and the other algorithms). Is  
> it possible
> to pre-allocate registers in your linearscan (or in another  
> allocation engine)
> for specific source-level or (better) intermediate code (bitcode)  
> level
> variables?
Yes that's done at instruction selection time. If you specify an  
instruction definition must go to a physical register, the selector  
and scheduler will take care of it. Same for instructions that require  
its operands that must be in fixed registers.
>
>
> Ideally i would to pre-allocate hard registers for specific  
> temporary variables
> (and their aliases through out the entire lifetime in a program --  
> or at least
> a single C function). The pre-allocation would take place early in  
> the register
> allocation.
>
> I'm designing small-scale embedded systems and pre-allocation is  
> very meaningful
> in this context.
>
> 2. Which are the new register allocation algorithms currently under  
> design? Do
> they support preallocation of registers (it is different to
"fixing"
> a register
> in GCC parlance)?
I know of a number of allocators in development. They are not yet made  
available to the public yet. Perhaps their authors can chime in.
>
>
> 3. Does LLVM work on PDGs (Program Dependence Graphs) as well? If  
> yes, does the
> register allocation take on PDGs?
No it doesn't.

Evan
>
>
>
> Kind regards
> Nikolaos Kavvadias
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Oct 4, 2007, at 10:40 PM, nkavv at physics.auth.gr wrote:
> 2. Which are the new register allocation algorithms currently under  
> design? Do
> they support preallocation of registers (it is different to  
> "fixing" a register
> in GCC parlance)?
>
Hi Nikolaos,

I have an alpha version of Chow & Hennesey's priority-based graph  
coloring algorithm. It's suffering from some bit-rotting -- e.g.,  
there's some trouble with how it calculates "forbidden" registers.
You're welcome to the code, if you'd like to hack on it. I've been  
trying to refresh it in the past few days, but would love some help. :-)

-bw

Quoting Bill Wendling <isanbard at gmail.com>:
> Hi Nikolaos,
>
> I have an alpha version of Chow & Hennesey's priority-based graph
> coloring algorithm. It's suffering from some bit-rotting -- e.g.,
> there's some trouble with how it calculates "forbidden"
registers.
> You're welcome to the code, if you'd like to hack on it. I've
been
> trying to refresh it in the past few days, but would love some help. :-)
>
> -bw
Hi Bill

i would like to have a look to your register allocator. Is it on LLVM SVN? Or is
it something standalone?

BTW, my time is limited right now (writing up my Ph.D. as well as a processor
soft core) but i will dedicate some time (after all i do this for polishing my
Machine-SUIF passes, and there is no help there). LLVM has a community, really
working on advancing the compiler.

Nikolaos Kavvadias