similar to: [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

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

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

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

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

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

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.

Hi Duncan, >> New PBQP solver. > > nice! Any chance of a quick summary of the state of the pbqp allocator and > who might want to use it? Sure. Here's an update, broken into three handy sections: Summary for LLVM users: --- PBQP is a heavyweight register allocator. A quick, not-at-all scientific look at SPEC2006 shows that compiling with -regalloc=pbqp increased runtime

Hi, Probably I did not mention my question correctly. I need to emit declarations of the libcalls (that are made in the current module) at the beginning of the assembly file. The class "Module" does not maintain any list of the libcalls made during the program. Although, it maintains lists of all the global variables and functions in the current module. Traversing each

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

Hi Sachin, The declaration of functions called via the "call" instruction is a GlobalValue in your Module. You can go through all of the GlobalValues, look for those that are Function declarations (use the "Function::isDeclaration()" method), and then placing them in the appropriate place in your assembly file. Would that work? -bw On Jan 28, 2009, at 12:23 AM,

> Hi Sachin, > > The declaration of functions called via the "call" instruction is a > GlobalValue in your Module. You can go through all of the > GlobalValues, look for those that are Function declarations (use the > "Function::isDeclaration()" method), and then placing them in the > appropriate place in your assembly file. > > Would that work? Hi

Hi Lang, I have reduced the testcase as much as possible. The log of the run and the dumped graphes are attached. Cheers, -- Arnaud de Grandmaison On Tuesday, March 27, 2012 01:20:35 Lang Hames wrote: > Hi Arnaud, > > Thanks for attaching those files. I'll take a look at them. > > Commit r153483 adds an option to the PBQP allocator, > "-pbqp-dump-graphs", to

Hi Lang, Thanks a lot for taking time to look into this. I will test the fix soon and let you know the results. Cheers, -- Arnaud de Grandmaison On Tuesday, April 03, 2012 17:30:33 Lang Hames wrote: > Hi Arnaud, > > Apologies for the delayed reply. > > Thank you for the excellent test case - it exposed a subtle bug in the > colorability heuristic. This has been fixed in

Hi Lang, The assert is not triggered any longer on my testcases :) I however still get my wrong allocation in some non trivial cases : the pairing constraint is not fulfilled. I have tried to modify the 'ensure pairable' pass (the pass undoing some of the coalescer's work) to always insert register copies for instructions with the pairable constraint, instead of being smart and

Hi Arnaud, Apologies for the delayed reply. Thank you for the excellent test case - it exposed a subtle bug in the colorability heuristic. This has been fixed in r153958. In case you are curious, the bug was as follows: the PBQP solver applies applies a simplification step to each matrix. When all elements of a matrix row or column are equal, the value for those elements is "pushed

Hi Arnaud, I'm glad to hear that your test case is working. I however still get my wrong allocation in some non trivial cases : the > pairing constraint is not fulfilled. > > I have tried to modify the 'ensure pairable' pass (the pass undoing some > of the coalescer's work) to always insert register copies for > instructions with the pairable constraint, instead of

> -----Original Message----- > From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On > Behalf Of Bill Wendling > Sent: Friday, September 19, 2008 4:38 AM > > On Thu, Sep 18, 2008 at 7:12 AM, <Sachin.Punyani at microchip.com> wrote: > > What changes would be required in LLVM to support illegal pointer type? > > > Hi Sachin, >

Lang Hames wrote: > Hi Sebastian, > > > We did. The success of normalization in this case depends on whether > you attempt to normalize rows first, then columns, or the other way > around. > > Currently rows are normalized first, then columns. In your example the > infinite costs are thus propagated onto element 1 of node 0, rather > than node 4, which leaves us

Hi Sebastian, > I think the crucial point is that node4 isn't aware of its own > restriction (after the first R2 reduction). > If you normalize the new matrix (shifting costs in the adjacent vector > until each row/column has minima 0) after a R2 reduction of a node with > infinite spill cost the problem should disappear. <snip> > Did you consider this option? We