Register Allocation: Interference graph

Project Infrastructure LLVM Dev List Archives
#1

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 :).
First I plan to (re)implement some of the classic approaches to get
familiar with the framework.

At the beginning the following questions came up:

- Is there some documentation about register allocation in LLVM?

- As far as I understand it, register allocators are implemented as
MachineFunctionPasses. Does a MachineFunction object contain all
information needed for a (classic) allocator?

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

- Is there an LLVM register allocator that uses graph coloring or
something similar?

- Which LLVM allocator would you recommend to look into to get the basic
ideas how to use the framework?

Many thanks in advance!

Josef

#2

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

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.

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

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

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

- 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

#3

David Greene 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

#4

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

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

#5

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

After I've taken a second look at my code, I must admit, it is really
straight forward. Don't know why I didn't got it the first time.

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

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

Yes, I've done so. After my pass is finished with the 'dumping' it calls
runOnMachineFunction from another implemented RegAlloc until I implement
my own.

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.

Ok, thats what I expected. Would be nice to hook in a pass without
changing llc but I guess it wouldn't make any sense for 'real' passes.

Thanks again for your help!

Josef

#6

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?

#7

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: