llvm dev - Dec 2012 - [LLVMdev] LLVM ERROR: ran out of registers during register allocation

Hello,

I'm getting the "LLVM ERROR: ran out of registers during register
allocation" error message for an out of tree target I'm developing.
This is
happening for the following piece of C code:

struct ss
{
  int a;
  int b;
  int c;
};
void loop(struct ss *x, struct ss **y, int z)
{
  int i;
  for (i=0; i<z; ++i)
  {
    x->c += y[i]->b;
  }
}

The problem relies in the register classes for the load and store with
displacement instructions:
- load DREGS:$dst, PTR:$p
- store DREGS:$src, PTR:$p
where DREGS is a regclass composed of 16 registers and PTR is a regclass
composed of 2 registers, but the key point here is that PTR is a subset of
DREGS, so cross class copies are perfectly allowed.
One of the 2 registers in the PTR regclass is reserved for the frame
pointer, leaving only one register to access both x and y[i] in the code
above, which seems to confuse the regalloc. Implementing
getLargestLegalSuperClass() sort of helped for simpler functions, but not
for this one.
This code can be register-allocted if the addresses of both x and y[i] are
cross class copied to DREGS registers to temporarily store these values and
then when required copied back to the the register in PTR to access them in
memory.

Any help for a solution or a workaround will be greatly appreciated since
this problem is severily limiting the complexity of the programs that I can
currently compile.

Thanks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121217/95a82097/attachment.html>

On Dec 17, 2012, at 8:38 AM, Borja Ferrer <borja.ferav at gmail.com>
wrote:
> Hello, 
> 
> I'm getting the "LLVM ERROR: ran out of registers during register
allocation" error message for an out of tree target I'm developing.
This is happening for the following piece of C code:
> 
> struct ss
> {
>   int a;
>   int b;
>   int c;
> };
> void loop(struct ss *x, struct ss **y, int z)
> {
>   int i;
>   for (i=0; i<z; ++i)
>   {
>     x->c += y[i]->b;
>   }
> }
> 
> The problem relies in the register classes for the load and store with
displacement instructions:
> - load DREGS:$dst, PTR:$p
> - store DREGS:$src, PTR:$p
> where DREGS is a regclass composed of 16 registers and PTR is a regclass
composed of 2 registers, but the key point here is that PTR is a subset of
DREGS, so cross class copies are perfectly allowed.
> One of the 2 registers in the PTR regclass is reserved for the frame
pointer, leaving only one register to access both x and y[i] in the code above,
which seems to confuse the regalloc. Implementing getLargestLegalSuperClass()
sort of helped for simpler functions, but not for this one.
> This code can be register-allocted if the addresses of both x and y[i] are
cross class copied to DREGS registers to temporarily store these values and then
when required copied back to the the register in PTR to access them in memory.
> 
> Any help for a solution or a workaround will be greatly appreciated since
this problem is severily limiting the complexity of the programs that I can
currently compile.
Those are some severe constraints on register allocation, but it ought to be
possible anyway.

You may wan't to investigate how RAGreedy::canEvictInterference() is
behaving.

/jakob

Hello Jakob,

> Those are some severe constraints on register allocation, but it ought to
> be possible anyway.
>
Indeed, these constraints aren't playing very well with the register
allocator :\

>
> You may wan't to investigate how RAGreedy::canEvictInterference() is
> behaving.
>
Ok, this is what I've noticed, not sure if it makes sense at all but,
regalloc fails with the following sequence:

1) directly assign the physreg in PTR RC to a virtX.
2) for a virtY which also belongs to the PTR RC, try to evict: call
canEvictInterference() for virtY which interferes with virtX, returns true.
evict and unassign virtX and assign physreg to virtY.
3) for a virtZ which also belongs to the PTR RC, try to evict: call
canEvictInterference() for virtZ which interferes with virtY, both
VirtReg.isSpillable() and Intf->isSpillable() return false, can't evict,
wait for a second round and queue new interval.
4) do some work unrelated to these vregs.
5) when selectOrSplit is called again for virtZ it falls through down to
the return ~0u line and fails.


This issue can be very easily reproduced with the Thumb2 target by doing
the following few changes:

1) declare a PTRRC regclass in ARMRegisterInfo.td with only one physreg:
def PTRRC : RegisterClass<"ARM", [i32], 32, (add R6)>;

2) modify the RC used in the addr_offset_none addressing mode in
ARMInstrInfo.td around line 947 to:
  let MIOperandInfo = (ops PTRRC:$base);
(this is used by the t2LDR_POST instruction)

3) and likewise modify the t2addrmode_imm12 addressing mode in
ARMInstrThumb2.td around line 151 to:
let MIOperandInfo = (ops PTRRC:$base, i32imm:$offsimm);
(used by the load/store instructions)

then compile with -O3 and done :)

In addition, I've attached the debugging info generated by the regalloc for
the Thumb2 target. The main difference of the debug output using my target
is that I didn't get any spill code like Thumb2 has, probably because i
have far more free regs available.

Thanks for your help.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121218/84986328/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dbg
Type: application/octet-stream
Size: 131017 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121218/84986328/attachment.obj>