[LLVMdev] register allocation

[Jonas Paulsson]

 > On Jan 19, 2012, at 5:31 AM, Jonas Paulsson wrote:
 >  LLVM would have to be extended with an RegClass/register-attribute 'spillable'
>
 >
 > What exactly are you proposing? Why can't you do what the PowerPC and Hexagon targets do?

Yes, I can move a CR to a GPR and save it to the stack, but due to a very irregular register file this is about 10 times more expensive than saving/restoring an ordinary register. These registers should basically never
have to be spilled, at least not on -O3.

 > Spill-free register allocation sounds great, why not do it for all register classes?

Well, in this architecture, each GPR has its own CR, and I have made a super-register that includes the GPR and CR when the flag is needed. I need to write code like:

GPR_CR = cmp GPR, 0                                                            // GPR_CR def
<other code, possibly using just GPR's without setting the CR>
br #, GPR_CR                                                                         // GPR_CR use

Basically, I would like to make sure that the GPR_CR reg is not spilled before another GPR-only reg is spilled, as it would be idiotic. As the super-register is wider than the GPR I do not see why this happened, but at -O0
this happened for some reason or other.

I tried a method with simply handing out pregs as suitable in preRA. I would like to confirm with you if possible that this should work with PBQP and greedy/basic, which scans the LiveIntervals for pregs and remembers it.
What's more, setting the GPR_CR class to 'not-spillable' would probably do the trick here as we basically do not want to do this, and I would not have to pre-allocate. But there is probably a better way, or?

> , and a register allocator would have to implement register pairing. That would be PBQP, right?
 >
 > If by pairing you mean GCC's multiple-alternatives, then PBQP should be able to support that.
>
 > /jakob

I take it then that it is not possible to write operand-combinations as in GCC in LLVM so as to handle register pairing on a high level?

The PBQP algorithm as such supports register pairing per the article, but it was not implemented in RegAllocPBQP.cpp as far as I can see.

For my needs, I would like to say that whenever two registers are used in the same instruction, they must follow any register-pairing rule defined for any such occurence. Possibly, one could add a Constraint per instruction def
as well to indicate the use of the register pairing rule, and to allow instances where it does not apply.

PBQP extension (suggestion)
======================

Tablegen:

def regPair : registerPair<AddrReg0, OffsReg0>,
~or~
def regPair:  registerPairing<AddrReg0, [OffsReg0, OffsReg1, OffsReg2]>;
~or~
??

in the instruction such as a load:

ld dst, addrReg, offsReg

then PBQP must follow the rule and only allocate legal combinations of addrReg and offsReg.

I beleive this should work by setting the cost to infinity for illegal combinations. I supervised a bacheolor student here last year (Jakob Stengård), and as far as I recall, Lang was interested in helping him getting this implemented
then, although Jakob ran out of time. Has anything changed since then? What is your estimation on the amount of  work for this? Would anyone (Lang?) be willing to supervise it?

Jonas

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120120/1168d75f/attachment.html>