similar to: [LLVMdev] PBQP & CalcSpillWeights

Hi Arnaud, LiveInterval::markNotSpillable() sets the live interval's spill weight to infinity. For well-formed PBQP graphs (i.e. ones that have some finite-cost solution), PBQP should never chose to spill such an interval. The two possibilities for this crash are that the input graph has no finite-cost solution, or that you've exposed a bug in the PBQP solver. >From memory your target

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 dump the PBQP graph for each round of each function in a compilation unit. The generated files are named "<module id>.<function>.<round>.pbqpgraph", and contain a simple text representation of the PBQP graph.

Hi Lang, > From memory your target is not public, so I won't be able to reproduce > the crash myself. Is that correct? Correct. > If that's the case, I could add functionality to dump the PBQP graphs > during allocation. I think they should give me enough information to > debug the issue. Would you be able to share the PBQP graphs? I can share the pbqp graph if you send

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

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

Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. I also intend to take

On Nov 8, 2013, at 7:40 AM, Arnaud Allard de Grandmaison <arnaud.adegm at gmail.com> wrote: > Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation

Committed at r194269 Thanks Jakob ! Cheers, -- Arnaud On Fri, Nov 8, 2013 at 6:34 PM, Jakob Stoklund Olesen <stoklund at 2pi.dk>wrote: > > On Nov 8, 2013, at 7:40 AM, Arnaud Allard de Grandmaison < > arnaud.adegm at gmail.com> wrote: > > > Based on discussions with Lang Hames and Jakob Stoklund Olesen at the > hacker's lab, and in the light of upcoming

On Sep 20, 2010, at 4:11 PM, Lang Hames wrote: > > The PBQP allocator uses the aggressive coalescer and optionally adds coalescing costs for any remaining copies to the PBQP problem (if you use -pbqp-coalescing). Unfortunately relying on PBQP's coalescing alone is not an option - the graphs coming out of PHI elimination are very large and without aggressive coalescing to bring the size

Hi Arnaud, The patch looks good. I've committed it in r133249. > > > I noticed an unexpected --- to me at least --- behaviour of the allocator. > > I have some instructions using 2 pairs of registers, say “mpra R_x, R_x+1, > R_y, R_y+1”, and setting the pairing constraints R_x -> R_x+1 and R_y -> > R_y+1 could silently produce wrong code like “mpra %R0, %R2, %R1,

Hi Jakob, > Out of curiosity, how are you dealing with live range splitting and > coalescing in PBQP? I know you added the LoopSplitter pass. > > For linear scan in LLVM we are going in the direction of aggressive > coalescing before allocation, and on-demand splitting during allocation. > > I know that other allocators use no early coalescing, and coalesce during >

Attached is a small patch to allow users of the PBQP allocator to optionally insert a custom pass. I believe it can be usefull to other users of the pbqp. I used it to undo some of the coalescer work, and make sure that I have different virtual registers, inserting a copy if necessary, to build a pair. I noticed an unexpected --- to me at least --- behaviour of the allocator. I have some

Hi Lang, > Hmm. Let me make sure I'm reading this right. The constraints are that: > a) All four operands have distinct registers. > b) The first two are in a consecutive pair (second > first) > c) The second two are in a consecutive pair (fourth > third) Constraints b & c are OK, but a is too strict : "mpra %R0, %R1, %R0, %R1" is OK. But I though, may be

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

On Sep 20, 2010, at 7:53 AM, Lang Hames wrote: > I've just committed some changes to the PBQP allocator which are designed to make it easier to implement custom register allocation constraints. This is a quick summary of those changes, and of the status of the PBQP allocator in general. Thanks, Lang! Out of curiosity, how are you dealing with live range splitting and coalescing in PBQP?