David Greene wrote:
I want learn more about register allocation and do some analysis for a
current research project. After reading some papers (eg. Chaitin,
Briggs) I think its time to get my hands dirty :).
First I plan to (re)implement some of the classic approaches to get
familiar with the framework.
Before doing that, can you describe your research a bit? A number of
people (include me!) have done graph-coloring style register allocators
for LLVM/x86 and not found much benefit over the existing "linear scan"
scheme (in quotes because it's not actually linear scan anymore :)).
Maybe 'research' was not the appropriate term :). I am currently working
on an assignment for the undergraduate course 'algorithms and
data-structures' at our university and I want our attendee to see some
real world examples. The topic of the assignment is graph coloring and I
thought I can use LLVM to throw out some example input data. Maybe I'll
port some of the submissions to LLVM and see what happens...
Besides that, I am generally interested in all topics around compilation
techniques/code generation especially using LLVM. I've been working on a
back-end and recently implemented a tblgen pass to generate some
hardware description files out of .td files.
I am not planning to develop a highly efficient regalloc to compete with
'linear scan' ;). Just digging a little bit deeper into the topic.
It might be better to use your time to investigate other algorithms.
If all you want to do right now is get familiar with the framework, there
are simpler algorithms than graph coloring.
At the beginning the following questions came up:
- Is there some documentation about register allocation in LLVM?
These are essential to read. A lot of details are missing which requires
one to just get down into the code and start hacking but this document helps
with understanding the broad picture.
Thanks, I read these some time ago when I was starting the back-end
implementation. I'll see if there are some new infos in it.
- As far as I understand it, register allocators are implemented as
MachineFunctionPasses. Does a MachineFunction object contain all
information needed for a (classic) allocator?
It has the instructions, operands and dependencies among them. There's
a LiveInvervalAnalysis pass which you'll probably also need. That should
be enough to get going.
I was able to set up my own allocator that uses LiveIntervals and it is
currently printing out something that might become a conflict graph ;).
Would be nice if there was some documentation about how to get all these
objects out of the MachineFunction &MF parameter.
Maybe I'll summarize how I did it and write something up...
- Is there already a pass that prints interference graph (Chaitin et al.
1981) or something similar like opt -view-cfg prints a CFG? If not, is
it even possible with the current LLVM infrastructure?
There's not one in trunk. When I did this I used Boost.Graph as the
representation and relied on its ability to dump GraphViz files for
visualization. You can also specialize LLVM's GraphTraits for your
particular graph representation and get much the same thing. You'll
need to add your own command-line options to display pretty pictures,
I didn't know Boost.Graph. Seems pretty cool, thank for the hint.
There is another questions that came up: Can I somehow get the
PassManager to execute my MachineFunctionPass (loaded with llc -load)
before the RegAlloc? As I am currently only printing out some
LiveInterval infos so I don't need/want to implement a complete
allocator. But if there is no pass that depends on my analysis the pass
manager doesn't schedule my pass at all. I understand that that makes
sense but it would be nice to 'force' the pass manager the execute my
stuff before the allocator without changing the framework and only using
llc -load (and maybe some custom cmd switches). Something similar is
possible with opt but I can't figure it out with llc.
- Is there an LLVM register allocator that uses graph coloring or
Not in trunk. Here's a message I looked at when I did mine:
It's pretty stale at this point. It won't apply to trunk. Just
use it as a guide to get started.
Hm, first class definition 'Interference graph node'. This looks very
- Which LLVM allocator would you recommend to look into to get the basic
ideas how to use the framework?
LinearScan is the only one widely used, AFAIK. There are some simpler
allocators as well (local, simple). PBQP is cool but I don't know much
Many thanks your reply. I Really appreciate your help.