[LLVMdev] Crash in PBQP register allocator

[Lang Hames]

Hi Sachin,

Confirmed: This is being caused by a subtle issue in the heuristic
PBQP solver. Specifically: R1/R2 reductions as currently implemented
can, on rare occasions, lead to the heuristic solver failing to find a
finite cost solution, even though one exists. The infinite cost
solution will always be in violation of some rule of register
allocation (failing to handle an interference, or spilling an infinite
cost node for instance).

There are several ways to fix the issue with the solver, but most
would pesimmize allocation quality in the general case. I will look
for a better solution when I return to the University of Sydney in a
couple of weeks. In the mean time I have added an assert to the
allocator to ensure that infinite cost solutions do not produce
miscompilations. For programs which trigger the assert you'll just
have to fall back on linear scan I'm afraid.

(If you particularly want PBQP to work in the short term you could
apply the following fix: Simply pre-color all infinite cost intervals
and remove the register option from any live intervals with which they
interfere).

Cheers,
Lang.

On Thu, Nov 12, 2009 at 4:29 PM, Lang Hames <lhames at gmail.com> wrote:
> This looks like a bug in the PBQP solver. I'm currently investigating.
>
> Cheers,
> Lang.
>
> On Thu, Nov 12, 2009 at 12:46 AM,  <Sachin.Punyani at microchip.com> wrote:
>> Hi,
>>
>>
>>
>> Please see the two “.ll’ files attached.
>>
>>
>>
>> Command line used
>>
>> llc –march=pic16  –pre-RA-sched=list-burr –regalloc=pbqp new.obc
>>
>>
>>
>> The above test case crashes only when I use the combination of list-burr
>> scheduler and pbqp register allocator. If any of them (scheduler or register
>> allocator) is replaced with some alternate then I don’t see the crash.
>>
>>
>>
>> I could not figure out the reason. Please provide some pointers to reasons
>> of the crash.
>>
>>
>>
>> Regards
>>
>> Sachin
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>