llvm dev - Dec 2009 - [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
>>
>>
>

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

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