[LLVMdev] "Ran out of registers during register allocation" bug affecting ffmpeg

Eli Friedman eli.friedman at gmail.com
Mon Aug 30 19:38:07 PDT 2010


On Mon, Aug 30, 2010 at 5:52 PM, Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote:
>
> On Aug 21, 2010, at 5:27 PM, Eli Friedman wrote:
>
>> See http://llvm.org/bugs/show_bug.cgi?id=4668 and
>> http://llvm.org/bugs/show_bug.cgi?id=5010.  The basic description of
>> the issue (from http://llvm.org/bugs/show_bug.cgi?id=4668#c5): "The
>> fundamental problem is we can't spill a register once it's fixed to a
>> physical register."
>>
>>> From discussion on IRC:
>>
>> [17:14]       <_sabre_>       efriedma: sounds like a RA bug in linscan
>> [17:14]       <_sabre_>       unfortunately, it is a fairly well known bug that is
>> difficult to fix
>> [17:14]       <_sabre_>       it would be worth bringing up on llvmdev, there may
>> be a good approach since I stopped looking at the regalloc
>> [17:14]       <_sabre_>       in any case, its worth surfacing the issue so that
>> Jakob can keep it in mind as he's building the new RA infrastructure
>
>
> I am not sure I completely understand the problem here since the PRs don't reproduce on TOT, but it sounds like a physical register is live across an inline asm that needs all the registers.

I've uploaded a re-reduced testcase to PR4668; your guess appears to
be correct, or at least close.

> This can happen if the register coalescer decides to coalesce a physreg with a virtreg that is live across the inline asm. This is not easy to detect without a bad compile time regression.
>
> I suppose something similar could happen for calls. For instance, some calls clobber all XMM registers, so a physical XMM register coalesced to be live across a call would be unspillable.
>
> What can I say? Physreg coalescing is evil ;-)
>
> I want to remove physreg coalescing entirely, but it requires the register allocator to be really good at taking hints. We are not quite there yet.

I measure a 1.7% increase in code-size compiling gcc with
-disable-physical-join vs. normal compilation on x86-64.  That's
pretty substantial.  Looking over the generated code, it looks like
we're missing a lot of cases which seem like they should be easy, like
not putting an immediately returned PHI node into eax, or calculating
a value and immediately moving it into another register for a call.
The difference isn't so bad on x86-32, only 0.25%.  I think that means
the primary issue with using -disable-physical-join is that we're
doing a really bad job of putting the arguments to calls in the right
register.

Is the issue that the correct hints aren't there, or that the
allocation algorithm isn't using them well?

> A quick fix would be to disable physreg coalescing for functions containing inline asm.

On x86-32, that probably wouldn't be such a big deal, but the effect
looks really bad for x86-64, and probably other architectures that
pass arguments in registers.

-Eli




More information about the llvm-dev mailing list