[LLVMdev] Crash in PBQP register allocator

[Sachin.Punyani at microchip.com]

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