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 > >
Hi Lang, I'm surprised about the fact that you omit R1/R2 reductions in some cases. Can you give a more detailed description of the bug (e.g. a PBQP dump)? Best regards, Sebastian 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. > > 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 > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100128/9a1b4f7f/attachment.html>
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
Hi Sebastian,
It boils down to this: The previous heuristic solver could return
infinite cost solutions in some rare cases (despite finite-cost
solutions existing). The new solver is still heuristic, but it should
always return a finite cost solution if one exists. It does this by
avoiding early reduction of infinite spill cost nodes via R1 or R2.
To illustrate why the early reductions can be a problem here is some
output from the original test case which started this thread:
graph {
node0 [ label="0: [ 1.875000e-02, 0.000000e+00 ]" ]
node1 [ label="1: [ inf, 0.000000e+00 ]" ]
node2 [ label="2: [ inf, 0.000000e+00 ]" ]
node3 [ label="3: [ inf, 0.000000e+00 ]" ]
node4 [ label="4: [ 5.357143e-02, 0.000000e+00 ]" ]
node5 [ label="5: [ inf, 0.000000e+00 ]" ]
node6 [ label="6: [ 6.250000e-02, 0.000000e+00 ]" ]
node7 [ label="7: [ 7.500000e-02, 0.000000e+00 ]" ]
node8 [ label="8: [ inf, 0.000000e+00 ]" ]
node9 [ label="9: [ inf, 0.000000e+00 ]" ]
node10 [ label="10: [ inf, 0.000000e+00 ]" ]
node11 [ label="11: [ inf, 0.000000e+00 ]" ]
node12 [ label="12: [ 3.750000e-01, 0.000000e+00 ]" ]
edge [ len=13 ]
node0 -- node1 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node2 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node3 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node4 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node5 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node6 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node7 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node0 -- node8 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node4 -- node5 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node4 -- node6 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node4 -- node7 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node6 -- node7 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node6 -- node8 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
node7 -- node8 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
}
Applying R1 to 1
Applying R1 to 2
Applying R1 to 3
Applying R2 to 5
Applying RN (unsafe) to 0 safe = { }, unsafe = { 0 6 4 7 8 }
Applying R2 to 8
Applying R2 to 4
Applying R1 to 6
Selected 1 for node 9 (cost = 0.000000e+00)
Selected 1 for node 10 (cost = 0.000000e+00)
Selected 1 for node 11 (cost = 0.000000e+00)
Selected 1 for node 12 (cost = 0.000000e+00)
Selected 0 for node 7 (cost = 1.375000e-01)
Reduction stack is: [ 1 2 3 5 0 8 4 6 ]
Selected 0 for node 6 (cost = 6.250000e-02)
Selected 1 for node 4 (cost = 0.000000e+00)
Selected 1 for node 8 (cost = 0.000000e+00)
Selected 0 for node 0 (cost = 1.875000e-02)
Selected 0 for node 5 (cost = inf)
Selected 1 for node 3 (cost = 0.000000e+00)
Selected 1 for node 2 (cost = 0.000000e+00)
Selected 1 for node 1 (cost = 0.000000e+00)
llc:
/home/lhames/Projects/llvm/llvm-broken-pbqp/llvm/lib/CodeGen/RegAllocPBQP.cpp:701:
bool<unnamed>::PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution&):
Assertion `solution.getCost()
!std::numeric_limits<PBQP::PBQPNum>::infinity() && "Invalid
(infinite
cost) solution for PBQP problem."' failed.
The problem is that node 5 is being allocated an infinite cost option
(which implies that all its options have infinite cost). The following
steps lead to this situation:
-> Applying R2 to 5
Node 5 is pushed to the reduction stack and costs are pushed onto edge
(0, 4), ensuring that neither Node 0 nor Node 4 can be stored in a
register.
-> Applying RN (unsafe) to 0 safe = { }, unsafe = { 0 6 4 7 8 }
Node 0 is pushed to the reduction stack and all of its edges are
removed, including (0,4), throwing away the restriction that 4 must
not be stored in a register.
Node 4 is later reduced via R2, then assigned the cheaper register
option during backpropagation. This eliminates all finite cost options
for Node 5. This is our problem.
In the PIC16 case where there are only two options, spill or register,
I believe it should be possible to have RN preserve the constraints
when it reduces a node. This is not possible when 3 or more options
are present however, and we wanted a general solution. By forcing
nodes with infinite spill cost to be reduced via RN (even when R1 or
R2 could be applied) the problem is easily solved. The infinite spill
costs of such nodes mean that they will only be reduced at the end of
the reduction process (and thus will be colored first), unless they
are proven colorable, in which case it is safe to reduce them earlier.
I have not had a good look at the extent to which this policy impacts
allocation quality, but from the experimental results I've seen so far
it seems to work well.
Hope that answers your question?
Cheers,
Lang.