[LLVMdev] Register Allocation: Interference graph

[Josef Eisl]

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@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