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