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?
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?
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.
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.
The code isn't in SVN right now. Here is the code (put BitMatrix.h in include/llvm/ADT and RegAllocGraphColoring.cpp in lib/CodeGen). There's a few problems with it. For one, when calculating the "forbidden registers", it's getting confused because LLVM marks registers that are killed by a call as having a live interval. These interfere with the live intervals that the RA is handling, resulting in a large number of intervals that are uncolorable. I think I know a way around this, but haven't tried it yet.
After that's finished, the next thing will be to have a better heuristic for selecting a physical register for a live interval. The one it uses now is *really* dumb.
Take a look and let me know what you think or if you have any improvements!
