[LLVMdev] Possible bug in the linear scan register allocator

[Roman Levenstein]

--- Chris Lattner <sabre at nondot.org> wrote:
> On Thu, 21 Dec 2006, Roman Levenstein wrote:
> > following:
> > 1) some of the fixed registers intervals are merged with some
> virtual
> > registers intervals
> > 2) later there is a need to spill one of the allocated registers,
> but
> > since all joined intervals are FIXED intervals now due to (1), they
> > cannot be spilled. Therefore, the register allocator loops for
> ever.
> >
> > I would be grateful, if someone would confirm that this is a bug.
> And
> > of course, it would be very nice if one of the RegAlloc Gurus could
> fix
> > it ;)
> 
> 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.

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.

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

-Roman


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com