llvm dev - Oct 2009 - [LLVMdev] request for help writing a register allocator

I'm using LLVM for a compiler course, and I'd like to have my students 
implement a graph-coloring register allocator.  I'm having a lot of 
trouble figuring out how this should be done.

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?

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

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


Susan Horwitz

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.

I'm no expert on the LLVM register allocation interfaces, so I'll  
defer to those who are regarding the specifics of your questions.

-Jim

On Oct 19, 2009, at 5:20 PM, Susan Horwitz wrote:
> I'm using LLVM for a compiler course, and I'd like to have my
students
> implement a graph-coloring register allocator.  I'm having a lot of
> trouble figuring out how this should be done.
>
> 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?
>
> - How do I know which operands of a Machine Instruction are candidates
>   for (simple) register allocation (e.g., are of type int)?
>
> - 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?
>
>
> Susan Horwitz
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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>