[LLVMdev] Crash in PBQP register allocator

Sachin.Punyani at microchip.com Sachin.Punyani at microchip.com
Mon Nov 16 22:29:35 PST 2009


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
> >>
> >>
> >




More information about the llvm-dev mailing list