[LLVMdev] Register Allocation: Interference graph

[David Greene]

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

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