[LLVMdev] Register pairing in PBQP

[Lang Hames]

Hi Jakob,

The PBQP allocator should have no problem representing this. Between each
pair of address/modification registers that are used together in a
post-modification instruction you'll need to add the following cost matrix:

    sp  r0  r1  r2  r3  r4  r5  r6  r7  r8  r9 r10 r11 r12 r13 r14 r15
sp  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
m0  0   0   0   0   0   i   i   i   i   i   i   i   i   i   i   i   i
m1  0   i   i   i   i   0   0   0   0   i   i   i   i   i   i   i   i
m2  0   i   i   i   i   i   i   i   i   0   0   0   0   i   i   i   i
m3  0   i   i   i   i   i   i   i   i   i   i   i   i   0   0   0   0

I have been busy with my thesis write-up recently and haven't had time to
keep up with progress in the CodeGen framework. Last time I checked it
didn't model this kind of constraint. If that's still the case (i.e. it
still isn't modeled) then you'll have to derive your own PBQPBuilder in your
target and set PBQP to be the default allocator for your system. If the
CodeGen framework can represent this kind of pairing constraint now you
could add your new PBQPBuilder to  CodeGen so that other target writers can
benefit from it.

See lib/CodeGen/RegAllocPBQP.cpp for examples of how to write PBQPBuilders,
and I'm happy to answer any questions, time permitting. :)

Cheers,
Lang.


On Wed, Apr 27, 2011 at 5:59 PM, Jakob Stengård <jakobste at kth.se> wrote:

> >Can you describe your pairing constraint in more detail? I've seen a few
> different kinds of "pairing", and the approach to supporting them can vary.
>
> The stuff im currently looking at is a constraint between address-registers
> and modification-registers.
> For example, post modification of r12-r15 can only be done with
> modification register m3.
> The instruction mv *r14++m, a4l must use modification register m3.
>
> They map like this:
>
> r0-r3    : m0
> r4-r7    : m1
> r8-r11  : m2
> r12-r15 : m3
>
> /J
>
>
>
>
> On Wed, Apr 27, 2011 at 2:06 AM, Lang Hames <lhames at gmail.com> wrote:
>
>> Hi Jakob,
>>
>> You're correct: Register pairing is not implemented in PBQP yet.
>>
>> Can you describe your pairing constraint in more detail? I've seen a few
>> different kinds of "pairing", and the approach to supporting them can vary.
>>
>> As a starting point I would look at the PBQPBuilder class and its
>> derivatives (see include/llvm/CodeGen/RegAllocPBQP.h,
>> lib/CodeGen/RegAllocPBQP.cpp). You probably need to derive a new
>> PBQPBuilder and have it add matrices representing the pairing constraints.
>> An overview of this is given in
>> http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-September/034781.html.
>>
>> Cheers,
>> Lang.
>>
>> On Tue, Apr 26, 2011 at 10:03 PM, Jakob Stengård <jakobste at kth.se> wrote:
>>
>>> Hi.
>>> Im currently investigating LLVM's implementation of PBQP as a part of a
>>> bachelors thesis im doing on register allocation for regular architectures.
>>> In particullar, im looking at the possibility for improving the spill
>>> rate of PBQP for a particular DSP architecture, by using register pairing.
>>>
>>> From reading the source code of lib/CodeGen/RegAllocPBQP.cpp  i conclude
>>> that support for register paring is not yet implemented (correct me if im
>>> wrong here).
>>> However this feature was mentioned as a future goal in a slide i found
>>> (http://llvm.org/devmtg/2009-10/RegisterAllocationFutureWorks.pdf<http://llvm.org/devmtg/2009-10/RegisterAllocationFutureWorks.pdf>
>>> ).
>>>
>>> So im just wondering what the status on this is.
>>> Would be interesting from the dev-teams perspective, to get this
>>> implemented?
>>> Anny ideas on what would be the best way to do that, in case someone
>>> (like me) would be interested in doing that?
>>>
>>> Best Regards
>>> Jakob Stengård.
>>> _______________________________________________
>>> 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/20110427/0a4d257e/attachment.html>