[LLVMdev] Possible bug in the linear scan register allocator

[Chris Lattner]

On Fri, 22 Dec 2006, Roman Levenstein wrote:
>> This is likely a bug, probably PR711.
>>
>> Unfortunately, this isn't super easy to fix, I don't have plans to do
>> so in the near future...
>
> OK. I looked at the PR711 at http://llvm.org/bugs/show_bug.cgi?id=711
> Indeed, it sounds as the same bug.
>
> Two questions:
> 1) At least, it would be better if LLVM would crash on an assertion
> instead of running for ever in such situations. I think this can be
> easily detected, since this is a case where nothing could be spilled.

Yes, this is certainly desirable.

> 2) You write in PR711:
>> This is due to the coallescer coallescing virtregs with both EAX and
>> EDX, which makes them unavailable to satisfy spills, causing the RA to
>> run out of registers.  We want to coallesce physregs when possible,
>> but we cannot pin them in the spiller:
>> we have to be able to >uncoallesce them.
>
> First of all, I totally agree with "we have to be able to uncoallesce
> them". Linear Scan already does a backtracking in some situations. I'm
> wondering, if it is very difficult to implement the logic,  where when
> it detects that it runs for ever (i.e. nothing can be spilled for some
> reason) it basically backtracks completely, does coallescing again but
> ignoring some selected virtual/physical registers (or any attempts to
> coalesce with physregs) and tries to allocate the whole function again?
> Alternatively, may be it would be possible to rerun the linear-scan
> pass without interval joining on a given function? This will probably
> produce a worse code, but it is better then crashing or looping for
> ever.

Without being able to detect this situation, we can't recover from it. 
Because coallescing and linscan are two different passes, we can't really 
undo both of them.  Once coallsecing is done, it's done.

>> this isn't super easy to fi
> OK. Do you see any further problems that I have not mentioned above?
> Can you elaborate a bit?

Fixing this properly requires changing the way we represent coallesced 
registers and how the RA acts on it.  In particular, right now, when we 
coallesce a  physreg with a virtreg, we completely lose information about 
what the code looked like before the coallescing occurred.  Instead of 
treating coallescing like this, it would be better to treat coallescing 
with a physreg as a hint that we would prefer the virtreg to be allocated 
to the physreg, not as a command.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/