Sachin.Punyani at microchip.com
2009-Dec-15 06:34 UTC
[LLVMdev] Crash in PBQP register allocator
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
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 >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091215/842c68f4/attachment.html>
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 > >