[LLVMdev] Register Allocation: Interference graph

[David Greene]

On Tuesday 04 May 2010 05:45:36 Josef Eisl wrote:


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

Which objects?  Iterating over blocks and instructions from MachineFunction
is pretty straightforward and getAnalysis<> is what you want for 
LiveIntervals.  I presume you know all this since you have LiveIntervals
dumping something.

What else do you need to get at?

> I didn't know Boost.Graph. Seems pretty cool, thank for the hint.

It's a bit unwieldy at times.  The interface is much more complex
than it needs to be, but people are working on that.  Slowly.  :(

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

Passes in llc are hard-coded in LLVMTargetMachine.cpp.  Does your
pass actually do register allocation, or will it?  If so, you want
to use the RegisterRegAlloc object.  Here is how linear scan uses it:

static RegisterRegAlloc
linearscanRegAlloc("linearscan", "linear scan register allocator",
                   createLinearScanRegisterAllocator);

Then createRegisterAllocator in CodeGen/Passes.cpp will pick up
your allocator and list it as an option under -regalloc=<allocator>.

If you pass is just doing some analysis and dumps you can either
add a invocation of it to LLVMTargetMachine.cpp or make some
other pass dependent on it.

                           -Dave