search for: pbqpbuilder

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

...0 I have been busy with my thesis write-up recently and haven't had time to keep up with progress in the CodeGen framework. Last time I checked it didn't model this kind of constraint. If that's still the case (i.e. it still isn't modeled) then you'll have to derive your own PBQPBuilder in your target and set PBQP to be the default allocator for your system. If the CodeGen framework can represent this kind of pairing constraint now you could add your new PBQPBuilder to CodeGen so that other target writers can benefit from it. See lib/CodeGen/RegAllocPBQP.cpp for examples of how...

...ling on the following issue. Instruction 'MPQD' takes 3 register operands inputs, with the constraint that operands 0 and 2 must be consecutive registers. Operand 1 has no particular constraint. It has no output register. So we have something like MPQD R_n, R_x, R_n+1. I have derived from PBQPBuilder to add the MPQD constraint. It happens sometimes that the code for register allocation looks like this : ... MPQD %vreg80, %vreg79, %vreg80; GR16:%vreg80,%vreg79 ... Operands 0 & 2 have been coalesced and I can no longer set the constraint. I tried to add a pass right before register a...

...9;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 > inserting the copy only when needed. This had no visible effect. > Although I am deriving from PBQPBuilder, the PBQP seems to be coalescing > some register copy, without taking into account that the source or dest > reg may have different constraints. In which part of pbqp would this be > happening ? > > If you're deriving PBQPBuilder (and not PBQPBuilderWithCoalescing) then PBQP won&...

...ed 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 inserting the copy only when needed. This had no visible effect. Although I am deriving from PBQPBuilder, the PBQP seems to be coalescing some register copy, without taking into account that the source or dest reg may have different constraints. In which part of pbqp would this be happening ? Cheers, -- Arnaud de Grandmaison On 04/05/2012 05:23 PM, Arnaud de Grandmaison wrote: > Hi Lang, > &gt...

...for spill, as well as > > > the > > > edge costs, and they look ok. > > > > > > I also attached my target's pbqp related file in case you want to > > > double check what I did. This is llvm-3.0 based. It comprises 2 > > > passes : the FemtoPBQPBuilder, plus a FemtoPairablepass, which undo > > > some of the coalescer's work. The insertRegCopy may specifically > > > need a double check, as I am not 100% sure to have updated > > > correctly the LiveInterval information. > > > > > > In terms of regis...

...llowing issue. > > Instruction ‘MPQD’ takes 3 register operands inputs, with the constraint that operands 0 and 2 must be consecutive registers. Operand 1 has no particular constraint. It has no output register. So we have something like MPQD R_n, R_x, R_n+1. > > I have derived from PBQPBuilder to add the MPQD constraint. > > It happens sometimes that the code for register allocation looks like this : > ... > MPQD %vreg80, %vreg79, %vreg80; GR16:%vreg80,%vreg79 > ... > Operands 0 & 2 have been coalesced and I can no longer set the constraint. > > I t...

...side, I already checked the node cost for this register, which is correctly set to inf for spill, as well as the edge costs, and they look ok. I also attached my target's pbqp related file in case you want to double check what I did. This is llvm-3.0 based. It comprises 2 passes : the FemtoPBQPBuilder, plus a FemtoPairablepass, which undo some of the coalescer's work. The insertRegCopy may specifically need a double check, as I am not 100% sure to have updated correctly the LiveInterval information. In terms of registers, the Femto target is simplistic : a single register class GR16, for...

...he node cost for this register, which > is correctly set to inf for spill, as well as the edge costs, and they look > ok. > > I also attached my target's pbqp related file in case you want to double check > what I did. This is llvm-3.0 based. It comprises 2 passes : the > FemtoPBQPBuilder, plus a FemtoPairablepass, which undo some of the coalescer's > work. The insertRegCopy may specifically need a double check, as I am not 100% > sure to have updated correctly the LiveInterval information. > > In terms of registers, the Femto target is simplistic : a single register...

...register, which is correctly set to inf for spill, as well as the > > edge costs, and they look ok. > > > > I also attached my target's pbqp related file in case you want to double > > check what I did. This is llvm-3.0 based. It comprises 2 passes : the > > FemtoPBQPBuilder, plus a FemtoPairablepass, which undo some of the > > coalescer's work. The insertRegCopy may specifically need a double > > check, as I am not 100% sure to have updated correctly the LiveInterval > > information. > > > > In terms of registers, the Femto target is...

...set to inf for spill, as well as the > > > edge costs, and they look ok. > > > > > > I also attached my target's pbqp related file in case you want to > double > > > check what I did. This is llvm-3.0 based. It comprises 2 passes : the > > > FemtoPBQPBuilder, plus a FemtoPairablepass, which undo some of the > > > coalescer's work. The insertRegCopy may specifically need a double > > > check, as I am not 100% sure to have updated correctly the LiveInterval > > > information. > > > > > > In terms of regist...

...detail on all of this in [1] and [2], so I'll leave you to read them for more information if you're interested (or feel free to shoot me questions via email). For now I'll get on to the the how-to bit for LLVM. The new header include/llvm/CodeGen/RegAllocPBQP.h includes a class called PBQPBuilder. This class represents the mapping between machine functions and PBQP problems. By extending it and implementing the build method you can add your own register allocation constraints to the PBQP problem. Just call back to the PBQPBuilder base to have the spill costs and interference constraints ad...

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

...Instruction 'MPQD' takes 3 register operands inputs, with the > constraint that operands 0 and 2 must be consecutive registers. > Operand 1 has no particular constraint. It has no output register. > So we have something like MPQD R_n, R_x, R_n+1. > > I have derived from PBQPBuilder to add the MPQD constraint. > > It happens sometimes that the code for register allocation looks > like this : > ... > MPQD %vreg80, %vreg79, %vreg80; GR16:%vreg80,%vreg79 > ... > Operands 0 & 2 have been coalesced and I can no longer set the > constraint. &gt...

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