[LLVMdev] Crash in PBQP register allocator

[Sebastian Buchwald]

Hi Lang,

I'm surprised about the fact that you omit R1/R2 reductions in some cases.
Can you give a more detailed description of the bug (e.g. a PBQP dump)?

Best regards,
Sebastian

Lang Hames wrote:
> Hi Sachin, llvm-dev,
>
> I've just committed a new PBQP solver which, among other things,
> should take care of this bug.
>
> Please let me know how it works out for you.
>
> Cheers,
> Lang.
>
>
> On Tue, Dec 15, 2009 at 5:54 PM, Lang Hames <lhames at gmail.com> wrote:
>   
>> Hi Sachin,
>>
>> Yes. Bernhard Scholz and I have just discussed a fix for this. I hope to
>> commit it in the next few days. I will let you know as soon as it goes in to
>> the mainline.
>>
>> Regards,
>> Lang.
>>
>> On Tue, Dec 15, 2009 at 5:34 PM, <Sachin.Punyani at microchip.com> wrote:
>>     
>>> Hi Lang,
>>>
>>> Thanks for your inputs on the problem. I was just curious to know if you
>>> got any opportunity to work on the solution for this.
>>>
>>> Regards
>>> Sachin
>>>
>>>       
>>>> -----Original Message-----
>>>> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]
>>>> On
>>>> Behalf Of Sachin.Punyani at microchip.com
>>>> Sent: Tuesday, November 17, 2009 12:00 PM
>>>> Subject: Re: [LLVMdev] Crash in PBQP register allocator
>>>>
>>>> Thanks Lang!
>>>>
>>>> I think we can use linear scan as work around for short term.
>>>>
>>>> Thanks for your help.
>>>>
>>>> Regards
>>>> Sachin
>>>>
>>>>         
>>>>> -----Original Message-----
>>>>> From: Lang Hames [mailto:lhames at gmail.com]
>>>>> Sent: Sunday, November 15, 2009 10:08 AM
>>>>> To: Sachin Punyani - I00202
>>>>> Cc: llvmdev at cs.uiuc.edu
>>>>> Subject: Re: [LLVMdev] Crash in PBQP register allocator
>>>>>
>>>>> 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
>>>>>>>
>>>>>>>
>>>>>>>               
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>         
>>     
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>   

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100128/9a1b4f7f/attachment.html>