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

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>

Å correction:

> You could re-write it in place (using
> MachineRegisterOperand::setReg(<reg>)...
>
That should have been MachineOperand::setReg(<reg>)...

And a disclaimer:
I wrote the PBQP allocator, so I might be biased. I think it's easier to
follow than linear scan though.

- Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091019/1d315fc9/attachment.html>

On Oct 19, 2009, at 7:28 PM, Lang Hames wrote:
> 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.
Other advice: if you're looking to simplify this for students, I'd  
recommend staying away from X86 or ARM, which use subregs heavily.  If  
you work with (e.g.) the sparc backend, you can avoid them completely,  
simplifying the problem.

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091019/d3cb91f1/attachment.html>

On Oct 20, 2009, at 7:22 AM, Susan Horwitz wrote:
> On Mon, 19 Oct 2009, Chris Lattner wrote:
>
>> Other advice: if you're looking to simplify this for students,
I'd
>> recommend staying away from X86 or ARM, which use subregs heavily.   
>> If you work with (e.g.) the sparc backend, you can avoid them  
>> completely, simplifying the problem.
>
> Chris -
>
> Thanks for your reply!  But I'm confused about the above.  In  
> particular, another reply said the following:
>
>> 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.
>
> If I can get the appropriate physical register for each virtual one  
> this way, then how does X86's use of sub-registers complicate my  
> register-allocation code?
Each virtual register has an assigned register class.  However,  
register classes relate to each other, and the machine IR also has  
subreg references.  For example, this is how X86 handles AL/AX/EAX/RAX  
all aliasing each other.  In the Sparc backend, the only aliases are  
in the FPU, and it doesn't use subregs to model them at this point.

-Chris

<ccing llvmdev>

On Oct 20, 2009, at 12:46 PM, Susan Horwitz wrote:
> On Tue, 20 Oct 2009, Chris Lattner wrote:
>
>> Each virtual register has an assigned register class.  However,  
>> register classes relate to each other, and the machine IR also has  
>> subreg references. For example, this is how X86 handles AL/AX/EAX/ 
>> RAX all aliasing each other. In the Sparc backend, the only aliases  
>> are in the FPU, and it doesn't use subregs to model them at this  
>> point.
>
> So if AL is a sub-register of EAX (assume this is true even if not),  
> then will getAliasSet(AL) include EAX, and will getAliasSet(EAX)  
> include AL? If yes, then I think I'm OK.
Yes, I believe so.

-Chris

>
> > So if AL is a sub-register of EAX (assume this is true even if not),
> > then will getAliasSet(AL) include EAX, and will getAliasSet(EAX)
> > include AL? If yes, then I think I'm OK.
>
> Yes, I believe so.

Yep - that's correct. Watch out for a potential gotcha though:
getAliasSet(EAX) does not include EAX itself (and in general physregs do not
appear in their alias sets).



> -Chris
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091020/fff0c121/attachment.html>

Lang -

I've made some progress writing my register allocator, but now I'm
stuck.

I have 2 questions for you:

1. I tried running the PBQP allocator (as a dynamic pass), but that didn't
    work.  When I type this:

 	llc -f -load Debug/lib/regalloc.so -regalloc=pbqp simple.bc

   I get the following error:

   llc:
/afs/cs.wisc.edu/p/course/cs701-horwitz/public/llvm-root/llvm/include/llvm/Support/CommandLine.h:483:
void llvm::cl::parser<DataType>::addLiteralOption(const char*, const
DT&, const char*) [with DT = llvm::FunctionPass* (*)(), DataType =
llvm::FunctionPass* (*)()]: Assertion `findOption(Name) == Values.size()
&& "Option already exists!"' failed.

   Can you tell from this what I'm doing wrong?


2. I tried writing a very simple register allocator.  It works as follows:

Step 1: Find out which physical registers are already used. Do this by 
iterating over all instructions and testing each operand.  Store results 
(including aliases) in a set.

Step 2: For each target reg class, save one (unused) physical register to 
be used for spills.  (Some classes have no unused physical registers. 
This would be detected in Step 3 if there were a virtual register in that 
class, but it hasn't happened for my tests so far.)

Step 3: Iterate over all instructions again allocating virtual registers 
to available physical ones (in the appropriate class) or, if no such 
physical reg is available, allocate the virtual register both to the 
saved "spill" register for its class and to a stack slot.  Keep track
of
the set of virtual registers already processed so none is processed twice. 
When a physical register is allocated, add it (and any aliases) to the set 
of used physical registers.

Step 4: Run the spiller.


This allocator works on very simple C code, but fails (with an 
uninformative segmentation fault) as soon as I include a call to scanf, or 
a loop, or an if-else.

Do you see any obvious errors in the approach outlined above?

If not, can you suggest a way to find out what is going wrong?

Thanks for any help you can give me!!

Susan Horwitz

Hi Susan,
> 1. I tried running the PBQP allocator (as a dynamic pass), but that
didn't
>   work....


 Can you tell from this what I'm doing wrong?
>
The PBQP allocator is built into the LLVM CodeGen library, so the
"-regalloc=pbqp" option is already available in llc. If you've
built a copy
of the PBQP allocator in a separate library it will try to re-register that
same option, triggering the assertion you're seeing. You can probably get
around this by just changing the option in your copy to "pbqp2".

2. I tried writing a very simple register allocator.  It works as follows...


<snip>

> This allocator works on very simple C code, but fails (with an
> uninformative segmentation fault) as soon as I include a call to scanf, or
a
> loop, or an if-else.
>
There are any number of things that can go wrong in register allocation, so
it's hard for me to guess without seeing your code.

Possible issues:

1) Some machine instructions have implicit register operands. If you are not
including these in your calculations you will probably have some errors. My
apologies for not mentioning this earlier.

You can find the set of implicit uses and defs by querying the
TargetInstDesc object for each MachineInstr (call MachineInstr::getDesc() to
get it, and then the TargetInstrDesc::getImplicitUses() and
TargetInstrDesc::getImplicitDefs() methods to find the regs used/definied by
this instr).

2) How are you making sure that interfering virtregs never receive the same
physreg? If you're using the LiveIntervals analysis (and the
LiveInterval::overlaps(LiveInterval &) test) you should be ok, since it gets
a lot of testing (though bugs are not unheard of). If you've written your
own liveness analysis that would be one of the first places I'd check for
correctness.

> Do you see any obvious errors in the approach outlined above?
>
No obvious errors. My concern would be the liveness issue mentioned above.
In addition, what do you do if/when you encounter an instruction with two or
more operands (in the same class) that have been spilled?

> If not, can you suggest a way to find out what is going wrong?
>
The LLVM bugpoint tool is very handy if your allocator itself is crashing.
It sounds like your allocator is running fine though, but miscompiling
programs. Unfortunately in this case there aren't many tools to help you
(that I know of). I usually just work by inspection. Add some debugging
output to your allocator, or fire llc up under gdb and dump information
(many objects in LLVM have a handy "dump()" method to print out their
state). Try to find a minimal failing test case (if it breaks on if tests
then that's a great start), and just look to see where the allocation goes
wrong.

> Thanks for any help you can give me!!

No problem at all. Writing allocators is non-trivial (took me quite a while
to get my first one going). If you get really stuck try posting your
allocator and a failing test case.

Good luck!

- Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091021/28be3dc1/attachment.html>