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

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>

Hello Jakob,

I think I've found something interesting that may help you get a better
idea of what's going on.

While looking at the debug info I noticed that the coalescer was removing
lots of copies that could help the allocator make more cross class copies.
As a test, I disabled the join-liveintervals option in the coalescer which
gave me the surprise of  making the regalloc succeed. To show what I mean,
I'm attaching two text files that show the debug info generated when this
option is enabled and disabled for my target.

To push things a bit further, I wrote a dirty hack in
RegisterCoalescer::joinCopy() to return false when the dest regclass is too
constrained. This allowed me executing the coalescer without crashing the
regalloc. Obviously the generated code is not optimal at all, because there
are many useless copies around. I'm pretty sure this is not the right fix
at all, but it can give you a hint incase the problem is in the coalescer
and not in the regalloc.

Thanks!

2012/12/18 Borja Ferrer <borja.ferav at gmail.com>
> 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/20121219/605c97be/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dump.zip
Type: application/zip
Size: 17037 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121219/605c97be/attachment.zip>

On Dec 19, 2012, at 8:58 AM, Borja Ferrer <borja.ferav at gmail.com>
wrote:
> Hello Jakob,
> 
> I think I've found something interesting that may help you get a better
idea of what's going on.
> 
> While looking at the debug info I noticed that the coalescer was removing
lots of copies that could help the allocator make more cross class copies. As a
test, I disabled the join-liveintervals option in the coalescer which gave me
the surprise of  making the regalloc succeed. To show what I mean, I'm
attaching two text files that show the debug info generated when this option is
enabled and disabled for my target.
> 
> To push things a bit further, I wrote a dirty hack in
RegisterCoalescer::joinCopy() to return false when the dest regclass is too
constrained. This allowed me executing the coalescer without crashing the
regalloc. Obviously the generated code is not optimal at all, because there are
many useless copies around. I'm pretty sure this is not the right fix at
all, but it can give you a hint incase the problem is in the coalescer and not
in the regalloc.
We did something like this back when the register allocator couldn't split
live ranges.

The problem is that any heuristic you can come up with only makes the problem
less likely to happen. It doesn't actually fix it.

/jakob