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

[Jakob Stoklund Olesen]

On Aug 30, 2010, at 7:38 PM, Eli Friedman wrote:

> I've uploaded a re-reduced testcase to PR4668

Thanks!

[...]

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

Yes. There are also some runtime performance regressions.

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

Interesting.

When spilling a virtual register, a bunch of new registers are created for all the uses. These registers don't currently get hints, but they could. See the bottom of SplitEditor::rewrite() in SplitKit.cpp.

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

Yes, function arguments and return registers are the primary source of copies to and from physregs. It makes sense that x86 has less.

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

The latter. I moved hinting to CalcSpillWeights.cpp and all relevant registers should be getting good hints.

The RA uses the hint as a first guess, but it doesn't try to avoid allocating registers that are used as hints for interfering virtual registers. The hints are also cleared when backtracking.

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

I agree.

/jakob