Sachin.Punyani at microchip.com
2009-Nov-12 08:46 UTC
[LLVMdev] Crash in PBQP register allocator
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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091112/dfe0cdc6/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: new.obc.ll.pass Type: application/octet-stream Size: 551 bytes Desc: new.obc.ll.pass URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091112/dfe0cdc6/attachment.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: new.obc.ll.crash Type: application/octet-stream Size: 679 bytes Desc: new.obc.ll.crash URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091112/dfe0cdc6/attachment-0001.obj>
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 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 >> >> >