David Greene wrote:> On Saturday 01 May 2010 08:34:50 Josef Eisl wrote:
>> Hello,
>>
>> 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 :).
>
> Welcome!
>
>> 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?
>
> http://llvm.org/docs/CodeGenerator.html
> http://llvm.org/docs/CodeGenerator.html#regalloc
>
> 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,
> of course.
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
>> something similar?
>
> Not in trunk. Here's a message I looked at when I did mine:
>
> http://www.mail-archive.com/llvm-commits at cs.uiuc.edu/msg10962.html
>
> 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
promising :).
>
>> - 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
> about it.
>
> -Dave
>
>
Many thanks your reply. I Really appreciate your help.
Josef