[LLVMdev] request for help writing a register allocator

[Lang Hames]

Hi Susan,

> You may find the PBQP allocator implementation useful as a reference
> to what's involved in adding a new allocator to LLVM. It's located in
> lib/CodeGen/RegAllocPBQP.cpp, with supporting files in the lib/CodeGen/
> PBQP directory.
>

Yes - as far as working allocators go PBQP is pretty simple. If you're just
interested in LLVM API details you can focus on the lower half of the
RegAllocPBQP.cpp source file (everything
from PBQPRegAlloc::findVRegIntervalsToAlloc()). The rest of the source
(class declaration at the top of RegAllocPBQP.cpp aside) is mostly concerned
with PBQP algorithm specifics, such as constructing cost matrices, or
carrying out the PBQP graph reduction algorithm.


> > Is there anyone who has written an LLVM register allocator who would
> > be
> > willing to help me understand the basic ideas?  I understand the
> > algorithm, it's LLVM that I don't understand.  For example:
> >
> > - When allocating registers, how do I know which register class to
> > use,
> >   and which registers of that class are available?
>

For each virtual register the MachineRegisterInfo::getRegClass(<vreg>)
method will give you a TargetRegisterClass. You can use the
allocation_order_begin/allocation_order_end methods to iterate over the
allocable physregs in that class.


> > - How do I know which operands of a Machine Instruction are candidates
> >   for (simple) register allocation (e.g., are of type int)?
>

Each operand of a MachineInstr has a corresponding MachineOperand object.
You can query this object using the "isReg()" method to check if an operand
is a register. You'd then have to use
"TargetRegisterInfo::isVirtualRegister(<reg>)" to test whether the operand
is virtual, and from there perform your allocation.

I've attached a demo allocator that'll get you started with the above APIs.

LLVM's CodeGen library is target independent though, and the register
allocator is expected to be able to allocate for _all_ virtregs, regardless
of their class (and to handle things like register aliasing). There's no
built-in distinction of "simple" candidates, as opposed to trickier ones.

If it helps you could hard code a test for your chosen platform (presumably
something nice and clean) at the start of the allocator, and from there on
work on the assumption that you're dealing with that platform. Then it'd be
up to you to decide which classes the students would have to allocate for.
You'd still need a way to allocate any "hard" classes though if you want a
working program.


> > - How do I replace a virtual register with a physical one?
>
> - Do I need to generate spill code to handle virtual registers that
>
>   cannot be replaced with physical ones, and if so, how?
>

You could re-write it in place (using MachineRegisterOperand::setReg(<reg>)
if you want to manipulate the code yourself, or you can store the mapping in
a VirtRegMap object and have the LLVM VirtRegRewriter apply the changes for
you. The latter would have to be used in conjunction with the other LLVM
regalloc components. You'd get liveness (LiveIntervals) and spilling
(LiveIntervals/VirtRegRewriter) for free, at the cost of some extra work to
understand their somewhat curious APIs. Looking at RegAllocPBQP.cpp is
probably the best way to get your head around how those components are used
by register allocation.


Regards,
Lang Hames.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091019/732ab805/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RegAllocDemo.cpp
Type: application/octet-stream
Size: 5744 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091019/732ab805/attachment.obj>