[LLVMdev] Crash in PBQP register allocator

[Sanjiv Gupta]

On Tue, 2010-01-26 at 15:58 +1100, 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.
> 
Hi Lang, 
I haven't got it to test on trunk yet, as I am on 2.6.
Will let you know soon.

- Sanjiv

> 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