similar to: [LLVMdev] PBQP & register pairing

On Jun 6, 2011, at 7:07 AM, Arnaud Allard de Grandmaison wrote: > Hi All, > > My target has some instructions requiring register pairs. I decided to give a try to the PBQP allocator : it is working fine in 99% of the cases, but I am stumbling on the following issue. > > Instruction ‘MPQD’ takes 3 register operands inputs, with the constraint that operands 0 and 2 must be

Arnaud, another way to look at it, if the description of your register sets includes "pairs", is that your assembly language syntax for MPQD is redundant, operand-2 is the second half of the register-pair in operand-0, so an alternative is to let llvm think this is a two operand instruction (one of them being a pair) rather than a three operand instruction. even

I also considered this approach, but did not want to dive in the constraint handling for now. The PBQP path seemed easier at first sight --- and was easy to setup. And I always wanted to give a try to the pbqp :) I will add the hook to the pbqp and propose a patch if this looks clean enough. Thanks, -- Arnaud de Grandmaison -----Original Message----- From: Jakob Stoklund Olesen

Hi Arnaud, That sounds great. I look forward to seeing a patch. You may also look forward to big performance improvements in the PBQP allocator: I'm working on updates which will improve compile speeds and massively reduce memory use. Regards, Lang. On Tue, Jun 7, 2011 at 7:02 PM, Arnaud Allard de Grandmaison < Arnaud.AllardDeGrandMaison at dibcom.com> wrote: > > I also

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

On Jun 6, 2011, at 12:14 PM, Peter Lawrence wrote: > Arnaud, > another way to look at it, if the description of your register sets includes "pairs", > is that your assembly language syntax for MPQD is redundant, operand-2 is the second > half of the register-pair in operand-0, so an alternative is to let llvm think this is a two > operand instruction (one

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. Im currently investigating LLVM's implementation of PBQP as a part of a bachelors thesis im doing on register allocation for regular architectures. In particullar, im looking at the possibility for improving the spill rate of PBQP for a particular DSP architecture, by using register pairing. >From reading the source code of lib/CodeGen/RegAllocPBQP.cpp i conclude that support for

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, > 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 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 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, 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, > 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 All, I finally had a chance to get back to my pbqp trials, now using the 3.0 release. I still hit the same assert : "Attempting to spill already spilled value." This is triggered because in RegAllocPBQP::mapPBQPToRegAlloc, a vreg node is either : - a physical register (problem.isPRegOption(vreg, alloc)), - or a spill (problem.isSpillOption(vreg, alloc)) The problem is that pass

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

Heads up: I posted this question on Stackoverflow yesterday (http://stackoverflow.com/questions/26484103/using-a-custom-memory-allocation-function-in-r). So far I haven?t gotten a response and I thought this could be an even better place to ask such a question. I would like to be able to use my own memory allocation function for certain data structures (real valued vectors and arrays) in R. The

Hi Jakob, The PBQP allocator should have no problem representing this. Between each pair of address/modification registers that are used together in a post-modification instruction you'll need to add the following cost matrix: sp r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 sp 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 m0 0 0 0 0 0 i