[LLVMdev] Re gister Allocation: Interference graph

Sat Apr 21 10:14:06 PDT 2012

I am working on a similar project on register allocation using graph coloring 
and as part of it, I need to generate the register interference graph. The 
interference graph will be an input to my analysis program in another 
programming language, so a generic graph representation is required (nodes
and 
edges). I see that you have come up with some conflict graph output and I
assume 
this is the register interference graph. Can you please post your pass code?

Josef Eisl wrote:
> 
> 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
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 

-- 
View this message in context: http://old.nabble.com/Register-Allocation%3A-Interference-graph-tp28420851p33726089.html
Sent from the LLVM - Dev mailing list archive at Nabble.com.